תרגול 12 תשעז

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

הגדרות בסיסיות לפונקציות

הגדרה: יהיו [math]\displaystyle{ A,B }[/math] קבוצות ו-[math]\displaystyle{ R }[/math] יחס בינהן. אזי:

• התחום של R הינו [math]\displaystyle{ \mathrm{dom}(R)=\{a\in A|\exists b\in B,(a,b)\in R\}=\{(*,\;),(*,\;)\dots \} }[/math]
• התמונה של R הינה [math]\displaystyle{ \mathrm{im}(R)=\{b\in B|\exists a\in A,(a,b)\in R\}=\{(\;,*),(\; ,*)\dots \} }[/math]

הערה: ישירות מהגדרה מתקיים כי [math]\displaystyle{ \mathrm{dom}(R)\subseteq A, \mathrm{im}(R)\subseteq B }[/math].

דוגמה:

• [math]\displaystyle{ R=\{(1,a),(2,b),(3,a),(a,1)\} }[/math] אזי התחום הוא [math]\displaystyle{ \mathrm{dom}(R)=\{a,1,2,3\} }[/math] והתמונה הינה [math]\displaystyle{ \mathrm{im}(R)=\{1,a,b\} }[/math].

הגדרה:

• יחס [math]\displaystyle{ R }[/math] מ-[math]\displaystyle{ A }[/math] ל-[math]\displaystyle{ B }[/math] נקרא על אם [math]\displaystyle{ \forall b\in B \exists a\in A:(a,b)\in R }[/math] כלומר [math]\displaystyle{ \mathrm{im}(R)=B }[/math].
• יחס [math]\displaystyle{ R }[/math] מ-[math]\displaystyle{ A }[/math] ל-[math]\displaystyle{ B }[/math] נקרא מלא אם [math]\displaystyle{ \forall a\in A \exists b\in B:(a,b)\in R }[/math] כלומר [math]\displaystyle{ \mathrm{dom}(R)=A }[/math]
• יחס [math]\displaystyle{ R }[/math] נקרא חד ערכי אם [math]\displaystyle{ [(x,b)\in R] \and [(x,d) \in R] \rightarrow (d=b) }[/math] כלומר אין איבר מ-[math]\displaystyle{ A }[/math] שמתאים לשני איברים שונים מ-[math]\displaystyle{ B }[/math].

הגדרה:

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

פונקציה נקראת חד-חד ערכית אם בנוסף היחס ההפוך הוא חד ערכי.

כלומר:

[math]\displaystyle{ f }[/math] חח"ע אמ"מ [math]\displaystyle{ f(x_1)=f(x_2)\Rightarrow x_1=x_2 }[/math] אמ"מ [math]\displaystyle{ x_1\neq x_2 \Rightarrow f(x_1)\neq f(x_2) }[/math].

הגדרה:

תהא [math]\displaystyle{ A }[/math] קבוצה. פונקציית הזהות היא פונקציה [math]\displaystyle{ f:A \to A }[/math] המקיימת [math]\displaystyle{ \forall a\in A: f(a)=a }[/math]. נהוג לסמנה [math]\displaystyle{ \mathrm{id}_A }[/math]. פונקציית הזהות היא חח"ע ועל.

דוגמאות

באופן רשלני (וחסכוני), כאשר אנחנו מגדירים פונקציה לא תמיד נשתמש בכמת "לכל" לגבי איברי תחום ההגדרה.

• [math]\displaystyle{ f:\mathbb{N}\rightarrow\mathbb{Z} }[/math] כאשר [math]\displaystyle{ f(p)=p^2 }[/math] חח"ע ואינה על.
• [math]\displaystyle{ f:\mathbb{Z}\rightarrow\mathbb{Z} }[/math] כאשר [math]\displaystyle{ f(p)=p^2 }[/math] אינה חח"ע ואינה על.
• [math]\displaystyle{ f:\mathbb{N}\rightarrow\mathbb{N} }[/math] כאשר [math]\displaystyle{ f(x)=x-1 }[/math] לא מוגדרת כי [math]\displaystyle{ f(1)=? }[/math].
• [math]\displaystyle{ f:\mathbb{R}\rightarrow\mathbb{R} }[/math] כאשר [math]\displaystyle{ f(x)=x-1 }[/math] חח"ע ועל.
• [math]\displaystyle{ f:\mathbb{N}\rightarrow\mathbb{N} \cup \{ 0\} }[/math] כאשר [math]\displaystyle{ f(x)=x-1 }[/math] חח"ע ועל.
• [math]\displaystyle{ f:\mathbb{N}\rightarrow\mathbb{R} }[/math] כאשר [math]\displaystyle{ f(x)=x-1 }[/math] חח"ע ואינה על.
• תהא פונקציה [math]\displaystyle{ f:A\to B }[/math] אזי [math]\displaystyle{ g:A\to \mathrm{im}(f) }[/math] המוגדרת לכל [math]\displaystyle{ a\in A }[/math] לפי [math]\displaystyle{ g(a)=f(a) }[/math] היא על (במילים: פשוט חושבים על הטווח של [math]\displaystyle{ g }[/math] להיות התמונה של [math]\displaystyle{ f }[/math]).
• תהא [math]\displaystyle{ A\subseteq B }[/math] אזי הפונקציה [math]\displaystyle{ i : A\to B }[/math] המוגדרת לכל [math]\displaystyle{ a\in A }[/math] לפי [math]\displaystyle{ i(a)=a }[/math] נקראת פונקציה ההכלה (אם [math]\displaystyle{ A=B }[/math] זו פונקצית הזהות). פונקצית ההכלה היא חח"ע.

תרגיל

נסמן ב-[math]\displaystyle{ \mathbb{N}^{\mathbb{N}} }[/math] את אוסף הפונקציות מהטבעיים לעצמם.

נתבונן בפונקציה [math]\displaystyle{ f:\mathbb{N}^{\mathbb{N}} \rightarrow \mathbb{N} \times \mathbb{N} }[/math] המוגדרת ע"י [math]\displaystyle{ f(g)=(g(1),g(2)) }[/math] האם היא חח"ע? האם היא על?

פתרון

הפונקציה לא חח"ע כי יש הרבה פונקציות שנותנות ל-1,2 (יחד!) את אותם ערכים.

היא כן על: לכל זוג סדור [math]\displaystyle{ (n,m) }[/math] הפונקציה ששולחת את 1 ל-[math]\displaystyle{ n }[/math], ואת 2 ל-[math]\displaystyle{ m }[/math], היא המקור (את שאר הטבעיים נשלח לאן שנרצה).

תרגיל

תהא [math]\displaystyle{ A }[/math] קבוצה. נגדיר פונקציה [math]\displaystyle{ f:P(A)\rightarrow P(P(A)) }[/math] ע"י: [math]\displaystyle{ f(X)=\{ B\subseteq A|X\subseteq B\} }[/math] האם היא חח"ע? על?

פתרון

חח"ע: כן. תהיינה [math]\displaystyle{ X,Y\in P(A), X\neq Y }[/math] אם [math]\displaystyle{ X\subsetneq Y\lor (X\nsubseteq Y\land Y\nsubseteq X) }[/math] אזי [math]\displaystyle{ X\in f(X)\setminus f(Y) }[/math]. אחרת [math]\displaystyle{ Y\in f(Y)\setminus f(X) }[/math]. כלומר [math]\displaystyle{ f(X)\neq f(Y) }[/math].

על: לא. נבחר [math]\displaystyle{ A=\{1,\dots,7\} }[/math]. למשל לקבוצה [math]\displaystyle{ \{ \{ 1,2\}, \{ 3,4\} \}\in P(P(A)) }[/math] אין מקור. אין תת קבוצה שהאוסף הזה הוא בדיוק אוסף הקבוצות המכילות אותה.

תרגיל

יהיו [math]\displaystyle{ A }[/math] ו-[math]\displaystyle{ B }[/math] קבוצות סופיות בעלות עוצמה זהה. הוכיחו שכל פונקציה מ-[math]\displaystyle{ A }[/math] ל-[math]\displaystyle{ B }[/math] הינה על אם"ם היא חח"ע.

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

נניח [math]\displaystyle{ f }[/math] חח"ע אזי [math]\displaystyle{ |\{f(a_1),\dots, f(a_n)\}|=n }[/math] כיוון ש-[math]\displaystyle{ \{f(a_1),\dots, f(a_n)\}\subseteq B }[/math] ובשניהם יש אותו מספר איברים, מתקיים שיוון ולכן [math]\displaystyle{ f }[/math] על.

נניח [math]\displaystyle{ f }[/math] על. נניח בשלילה ש-[math]\displaystyle{ f }[/math] אינה חח"ע אזי [math]\displaystyle{ |\{f(a_1),\dots, f(a_n)\}|\lt n }[/math] (כי יש שני איברים שנשלחים לאותו מקום) ואז [math]\displaystyle{ f }[/math] אינה על, שזו סתירה.

הערה: הדבר אינו נכון אם [math]\displaystyle{ A }[/math] ו-[math]\displaystyle{ B }[/math] קבוצות אינסופיות. נסו למצוא דוגמה.

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

הגדרה: יהיו [math]\displaystyle{ f:A\to B, g:B\to C }[/math] שתי פונקציות אזי ההרכבה של [math]\displaystyle{ g }[/math] על [math]\displaystyle{ f }[/math] היא פונקציה [math]\displaystyle{ g \circ f:A\to C }[/math] המוגדרת על ידי הכלל [math]\displaystyle{ g \circ f(a)=g(f(a)) }[/math].

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

משפט:

• אם [math]\displaystyle{ g \circ f }[/math] חח"ע אזי [math]\displaystyle{ f }[/math] חח"ע.
• אם [math]\displaystyle{ g \circ f }[/math] על אזי [math]\displaystyle{ g }[/math] על.
• מסקנה: אם [math]\displaystyle{ g \circ f }[/math] חח"ע ועל אזי [math]\displaystyle{ f }[/math] חח"ע ו-[math]\displaystyle{ g }[/math] על.

תכונות של הרכבת פונקציות:

1. הרכבה היא קיבוצית. כלומר [math]\displaystyle{ f_3 \circ (f_2 \circ f_1) = (f_3 \circ f_2) \circ f_1 }[/math].
2. הרכבה אינה (בהכרח) חילופית כלומר לא מתקיים בהכרח כי [math]\displaystyle{ f_2 \circ f_1 = f_2 \circ f_1 }[/math]. למשל לפונקציות מעל הטבעיים [math]\displaystyle{ f(x) =x^2 , g(x) = x+1 }[/math] אזי [math]\displaystyle{ f(g(2))=f(3)=9, g(f(2))=g(4)=5 }[/math] ולכן [math]\displaystyle{ f\circ g \neq g \circ f }[/math].
3. לכל פונקציה [math]\displaystyle{ f }[/math] מתקיים [math]\displaystyle{ f\circ \mathrm{id} =f }[/math] וגם [math]\displaystyle{ \mathrm{id} \circ f =f }[/math]. שימו לב לתחומי ההגדרה והטווחים של הפונקציות שנדרשים כדי שהטענות האלו יהיו נכונות.

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

הגדרה: תהי [math]\displaystyle{ f }[/math] פונקציה [math]\displaystyle{ f:A\rightarrow B }[/math]. פונקציה [math]\displaystyle{ g:B\rightarrow A }[/math] תקרא הפונקציה ההופכית ל-[math]\displaystyle{ f }[/math] אם [math]\displaystyle{ f\circ g = \mathrm{id}_B }[/math] וגם [math]\displaystyle{ g\circ f = \mathrm{id}_A }[/math]. במקרה זה נסמן את [math]\displaystyle{ g }[/math] על ידי [math]\displaystyle{ f^{-1} }[/math], ונאמר שהפונקציה [math]\displaystyle{ f }[/math] היא הפיכה.

שימו לב שאם [math]\displaystyle{ f }[/math] פונקציה הפיכה, אז גם [math]\displaystyle{ f^{-1} }[/math] היא פונקציה הפיכה, ומתקיים [math]\displaystyle{ (f^{-1})^{-1}=f }[/math].

תרגיל

(לדלג, היה בהרצאה): הוכיחו כי פונקציה [math]\displaystyle{ f }[/math] הפיכה אם"ם היא חח"ע ועל.

פתרון

אם [math]\displaystyle{ f }[/math] הפיכה, אזי [math]\displaystyle{ f\circ f^{-1} = \mathrm{id}_B }[/math] וגם [math]\displaystyle{ f^{-1}\circ f = \mathrm{id}_A }[/math]. מכיוון שפונקציית הזהות הינה חח"ע ועל, נובע ש-[math]\displaystyle{ f }[/math] חח"ע ועל לפי משפט קודם.

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

דוגמאות

1. פונקציות [math]\displaystyle{ f:\mathbb{R} \to \mathbb{R} }[/math] המוגדרות לפי:
   1. [math]\displaystyle{ f(x)=x+1 }[/math] הפיכה וההופכית היא [math]\displaystyle{ f^{-1}(x) = x-1 }[/math].
   2. [math]\displaystyle{ f(x)=x^3 }[/math] הפיכה וההופכית היא [math]\displaystyle{ f^{-1}(x) = x^{1/3} }[/math].
   3. [math]\displaystyle{ f(x)=\sin (x) }[/math] אינה הפיכה כי איננה חח"ע למשל [math]\displaystyle{ \sin(0) =\sin(2\pi k) }[/math] לכל [math]\displaystyle{ k\in\mathbb{Z} }[/math].
2. תהא [math]\displaystyle{ A }[/math] קבוצה. פונקציות [math]\displaystyle{ f:P(A)\to P(A) }[/math] המוגדרות לפי:
   1. [math]\displaystyle{ f(B)= B^c }[/math] הפיכה וההופכית היא [math]\displaystyle{ f^{-1}(B) = B^c }[/math].
   2. תהא [math]\displaystyle{ C\subseteq A }[/math] תת קבוצה. [math]\displaystyle{ f(B)= B \triangle C }[/math] הפיכה וההופכית היא [math]\displaystyle{ f^{-1}(B) = B \triangle C }[/math].
3. תהא [math]\displaystyle{ A }[/math] קבוצה. אזי אפשר (בעזרת חומר שראינו בתרגול על יחסי שקילות)

להגדיר [math]\displaystyle{ f:\{R \; | \; R \text{ Equivalence relation }\}\to \{\text{Partitions of }A\} }[/math] ע"י [math]\displaystyle{ f(R)=A/R }[/math] והיא תהיה חח"ע ועל, וכבר ראינו את הפונקציה ההופכית לה.

תרגיל

יהיו [math]\displaystyle{ f_1,\dots f_k:A\to A }[/math] שכולן הפיכות\חח"ע\על. הוכיחו שההרכבה [math]\displaystyle{ f_k \circ \dots \circ f_1 }[/math] הפיכה\חח"ע\על.

פתרון

למעשה אפשר לעשות אינדוקציה על המשפט מן ההרצאה.

חח"ע: נניח [math]\displaystyle{ (f_k \circ \dots \circ f_1)(x_1) =(f_k \circ \dots \circ f_1)(x_2) }[/math] אזי מחח"ע של [math]\displaystyle{ f_k }[/math] נקבל כי [math]\displaystyle{ (f_{k-1} \circ \dots \circ f_1)(x_1) =(f_{k-1} \circ \dots \circ f_1)(x_2) }[/math] באופן דומה נמשיך (או באינדוקציה) ונקבל [math]\displaystyle{ x_1=x_2 }[/math].

על: יהא [math]\displaystyle{ y\in A }[/math] כיוון ש-[math]\displaystyle{ f_k }[/math] על, קיים [math]\displaystyle{ a_k\in A }[/math] כך ש-[math]\displaystyle{ f_k(a_k)= y }[/math] באותו אופן קיים [math]\displaystyle{ a_{k-1} }[/math] כך ש [math]\displaystyle{ f_{k-1}(a_{k-1})=a_k }[/math] נמשיך באופן דומה (או באינקודציה) ונקבל [math]\displaystyle{ (f_k \circ \dots \circ f_1)(a_1)=(f_k \circ \dots \circ f_2)(a_2)=\\ \dots =f_k\circ f_{k-1} (a_{k-1}) = f_k(a_k)=y }[/math]

הפיכות: נובע מחח"ע יחד עם על.

תרגיל

הוכיחו כי אם [math]\displaystyle{ g\circ f \circ g =\mathrm{id} }[/math] אז [math]\displaystyle{ f }[/math] הפיכה.

הוכחה:

הרכבה של פונקציה חח"ע [math]\displaystyle{ (g\circ f) \circ g =\mathrm{id} }[/math] גורר שהפונקציה [math]\displaystyle{ g }[/math] הימנית חח"ע.

הרכבה של פונקציה על [math]\displaystyle{ g\circ (f \circ g) =\mathrm{id} }[/math] גורר שהפונקציה [math]\displaystyle{ g }[/math] השמאלית על.

קיבלנו ש-[math]\displaystyle{ g }[/math] חח"ע ועל, כלומר הפיכה. נכפול את הנתון ב-[math]\displaystyle{ g^{-1} }[/math] מימין ומשמאל ונקבל כי [math]\displaystyle{ f=g^{-1}\circ g^{-1} }[/math] ואז [math]\displaystyle{ f }[/math] הפיכה כהרכבה של פונקציות הפיכות.

תרגיל

תהיינה [math]\displaystyle{ f,g:\mathbb{N}\rightarrow \mathbb{N} }[/math] פונקציות כך ש-[math]\displaystyle{ f(n)=g(3n-1) }[/math].

הוכיחו שאם [math]\displaystyle{ f }[/math] על, אז [math]\displaystyle{ g }[/math] לא חח"ע.

פתרון

נסמן [math]\displaystyle{ g(1)=k }[/math] כיון ש-[math]\displaystyle{ f }[/math] על אזי קיים [math]\displaystyle{ n\in \mathbb{N} }[/math] כך ש[math]\displaystyle{ f(n)=k }[/math]. מהנתון נקבל ש-[math]\displaystyle{ g(3n-1)=k }[/math]. כעת, כיון ש- [math]\displaystyle{ n\in \mathbb{N} }[/math] אזי ברור ש-[math]\displaystyle{ 1\neq 3n-1 }[/math], ולכן אילו שני איברים שונים שנשלחים לאותו איבר. לכן [math]\displaystyle{ g }[/math] לא חח"ע.