תרגול 12 תשעז

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

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

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

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

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

דוגמה:

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

הגדרה:

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

הגדרה:

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

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

כלומר:

$f$ חח"ע אמ"מ $f(x_1)=f(x_2)\Rightarrow x_1=x_2$ אמ"מ $x_1\neq x_2 \Rightarrow f(x_1)\neq f(x_2)$.

הגדרה:

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

דוגמאות

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

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

תרגיל

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

הוכיחו שאם $f$ על, אז $g$ לא חח"ע.

פתרון

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

תרגיל

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

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

פתרון

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

היא כן על: לכל זוג סדור $(n,m)$ הפונקציה ששולחת את 1 ל-$n$, ואת 2 ל-$m$, היא המקור (את שאר הטבעיים נשלח לאן שנרצה).

תרגיל

יהיו $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$ קבוצות אינסופיות. נסו למצוא דוגמה.

תרגיל

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

פתרון

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

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

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

הגדרה: יהיו $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$ חח"ע אזי $f$ חח"ע.
• אם $g \circ f$ על אזי $g$ על.
• מסקנה: אם $g \circ f$ חח"ע ועל אזי $f$ חח"ע ו-$g$ על.

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

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

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

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

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

תרגיל

(לדלג, היה בהרצאה): הוכיחו כי פונקציה $f$ הפיכה אם"ם היא חח"ע ועל.

פתרון

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

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

דוגמאות

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

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

תרגיל

יהיו $f_1,\dots f_k:A\to A$ שכולן הפיכות\חח"ע\על. הוכיחו שההרכבה $f_k \circ \dots \circ f_1$ הפיכה\חח"ע\על.

פתרון

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

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

על: יהא $y\in A$ כיוון ש-$f_k$ על, קיים $a_k\in A$ כך ש-$f_k(a_k)= y$ באותו אופן קיים $a_{k-1}$ כך ש $f_{k-1}(a_{k-1})=a_k$ נמשיך באופן דומה (או באינקודציה) ונקבל עיבוד הנוסחה נכשל (שגיאת תחביר): (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

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

תרגיל

הוכיחו כי אם $g\circ f \circ g =\mathrm{id}$ אז $f$ הפיכה.

הוכחה:

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

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

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