תרגול 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{N}\rightarrow\mathbb{N} }[/math] כאשר [math]\displaystyle{ f(x)=x-1 }[/math] (לא מוגדרת כי [math]\displaystyle{ f(1)=? }[/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] על.

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

הערה: לכל פונקציה [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 }[/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].