88-195 בדידה לתיכוניסטים תשעא/מערך שיעור/שיעור 4

חזרה למערכי התרגול

פונקציות

הגדרה: יהיו A,B קבוצות וR יחס בינהן. אזי:

• התחום של R הינו $dom(R)=\{a\in A|\exists b\in B:(a,b)\in R\}=\{(*,\;),(*,\;)\dots \}$
• התמונה של R הינה $im(R)=\{b\in B|\exists a\in A:(a,b)\in R\}=\{(\;,*),(\; ,*)\dots \}$

דוגמא:

• אם R יחס מלא על A אזי האיחוד של התמונה והתחום שווה A (כי כל שני איברים ניתן להשוות)
• $R=\{(1,a),(2,b),(3,a),(a,1)\}$ אזי התחום הוא $dom(R)=\{a,1,2,3\}$ והתמונה הינה $im(R)=\{1,a,b\}$

הגדרה:

• יחס R מ-A ל-B נקרא על אם $\forall b\in B \exists a\in A:(a,b)\in R$ כלומר $im(R)=B$
• יחס R מ-A ל-B נקרא שלם אם $\forall a\in A \exists b\in B:(a,b)\in R$ כלומר $dom(R)=A$
• יחס R נקרא חד ערכי אם $[(x,b)\in R] \and [(x,d) \in R] \rightarrow (d=b)$ כלומר אין איבר שנשלח ל-2 מקומות שונים
• יחס R נקרא חד-חד ערכי אם $[(x,b)\in R] \and [(y,b) \in R] \rightarrow (x=y)$ כלומר איברים שונים נשלחים למקומות שונים (כלומר, היחס ההופכי הינו חד ערכי)

הגדרה:

יחס חד ערכי ושלם נקרא פונקציה; נסמן במקרה זה $(a,b)\in R\leftrightarrow b=R(a)$. ובאופן כללי $f:A\to B \;\; , a \mapsto f(a)$. (A נקרא תחום הגדרה של הפונקציה.)

הגדרה:

תהא A קבוצה. פונקציית הזהות היא פונקציה $f:A \to A$ המקיימת $\forall a\in A: f(a)=a$. נהוג לסמנה: $id_A$ פונקציית הזהות היא חח"ע ועל.

דוגמאות:

• $f:\mathbb{Z}\rightarrow\mathbb{Z}$ כאשר $f(p)=p^2$ (אינה חח"ע ואינה על)
• $f:\mathbb{Z}\rightarrow\mathbb{Z}$ כאשר $f(p)=p$. זו פונקציית הזהות.
• $f:\mathbb{R}\rightarrow\mathbb{Z}$ כאשר $f(x)=[x]$ מוגדר להיות הערך השלם הקרוב ביותר ל-x (במקרה של חצי לוקחים את הגבוה). זו פונקציה על שאינה חח"ע
• $f:\mathbb{Z}_2\rightarrow\mathbb{Z}_3$ כאשר לוקחים את 0 ל0 ואת 1 ל1. זו פונקציה חח"ע שאינה על. (כל פונקציה היא על לתמונה של עצמה.)
• $D:\mathbb{R}\rightarrow\mathbb{R}$ פונקצית דיריכלה: על כל מספר רציונאלי מקבלת 1 ועל כל מספר אי רציונאלי מקבלת אפס.

תרגיל: יהיו A ו-B קבוצות סופיות בעלות עוצמה זהה. הוכח שכל פונקציה מ-A ל-B הינה על אם"ם היא חח"ע

הוכחה: נסמן $f:A\to B, A=\{a_1,\dots a_n\},B=\{b_1,\dots b_n\}$ . כאשר כל האיברים ב A שונים זה מזה וכנ"ל ל B

נניח $f$ חח"ע אזי $|\{f(a_1),\dots f(a_n)\}|=n$ כיוון ש $\{f(a_1),\dots f(a_n)\}\subseteq B$ מתקיים שיוון ולכן $f$ על.

נניח $f$ על. נניח בשלילה ש $f$ אינה חח"ע אזי $|\{f(a_1),\dots f(a_n)\}|<n$ ואז $f$ אינה על -סתירה.

הערה: הדבר אינו נכון אם A וB קבוצות אינסופיות.

למשל פונקצית הערך השלם על ואינה חח"ע

הרכבת פונקציות

הגדרה: יהיו $f:A\to B, g:B\to C$ שתי פונקציות אזי ההרכבה של $g$ על $f$ היא פונקציה $g \circ f:A\to C$ המוגדרת על ידי הכלל $g \circ f(a)=g(f(a))$

תרגיל:

• נניח $g \circ f$ חח"ע. הוכח/הפרך: g חח"ע, f חח"ע
• נניח $g \circ f$ על. הוכח/הפרך: g על, f על

פתרון:

נניח $g \circ f$ חח"ע. נניח בשלילה ש-f אינה חח"ע. לכן קיימים $x,y$ כך ש $f(x)=f(y)$ אבל $x\neq y$. אבל, $g\circ f (x) = g(f(x))=g(f(y))=g\circ f(y)$ בסתירה לחח"ע של ההרכבה, ולכן f חח"ע.

לגבי g ניתן דוגמא נגדית: $f(x)=e^x ,g(y)=y^2$ ההרכבה היא $h(x)=e^{2x}$

נניח $g \circ f$ על. נסמן $g \circ f : A\rightarrow B$ אזי לכל איבר $b\in B$ קיים איבר $a\in A$ כך ש $g(f(a))=b$. לכן עבור g לכל b קיים $f(a)$ שנותן את b תחת g ולכן g על.

דוגמא נגדית ל f: נתבונן בשתי הפונקציות מהטבעיים לעצמם $f(n)=n+1$; $\forall n\not=0 g(n)=n-1 , g(0)=0$ ההרכבה היא הזהות

(עוד דוגמא נביט בפונקציות מהטבעיים לטבעיים. $f(n)=2n$, והפונקציה g מוגדרת כ $g(2n)=n$ ו $g(2n+1)=n$. ההרכבה הינה פונקצית הזהות שהיא בפרט על, אבל f אינה על כיוון שהאי זוגיים כלל לא נמצאים בתמונה שלה.)

פונקציות הפיכות

הגדרה: תהי $f$ פונקציה $f:A\rightarrow B$. פונקציה $g:B\rightarrow A$ תיקרא הפונקציה ההופכית ל-$f$ אם $f\circ g = id_B$ וגם $g\circ f = id_A$. במקרה זה נסמן את $g$ על ידי $f^{-1}$, ונאמר שהפונקציה $f$ היא הפיכה.

הערה: זכרו שפונקציה היא יחס. הפונקציה ההופכית שלה היא היחס ההופכי מטבע הדברים. על מנת שהיחס ההופכי יהיה פונקציה הוא צריך להיות ח"ע ושהתחום שלו יהיה כל B. תנאים אלה מתממשים רק אם f הינה חח"ע ועל.

תרגיל.

הוכח כי f הפיכה אם"ם היא חח"ע ועל. כמו כן, הוכח שאם קיימת הופכית אזי היא יחידה.

הוכחה:

אם f הפיכה, אזי $f\circ f^{-1} = id_B$ וגם $f^{-1}\circ f = id_A$. מכיוון שהזהות הינה חח"ע ועל, נובע ש-f חח"ע ועל לפי התרגיל הקודם בדבר הרכבת פונקציות.

אם f חח"ע ועל, אז נגדיר $g:B\to A$ ע"י: עבור $a\in A$ קיים (כי f על) יחיד (כי f חח"ע) $b\in B$ כך ש $f(a)=b$ . נגדיר $g(b):=a$. תרגיל: בדקו ש g ההופכית של f.

יחידות: נניח g,h הופכיות של f אזי $h= h\circ I_B=h\circ f \circ g=I_A \circ g=g$.

דרך אחרת להוכחת יחידות: נניח בשלילה ש g וh הופכיות שונות של f. מכיוון שהן שונות, הן חייבות להיות שונות על איבר אחד לפחות. כלומר, $\exists a\in A:g(a)\neq h(a)$. אבל $f(g(a))=f(h(a))$ וזו סתירה לחח"ע של f.