תרגול 12 תשעז

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

פונקציות

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

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

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

דוגמא:

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

הגדרה:

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

הגדרה:

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

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

כלומר:

[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]

הגדרה:

תהא A קבוצה. פונקציית הזהות היא פונקציה [math]\displaystyle{ f:A \to A }[/math] המקיימת [math]\displaystyle{ \forall a\in A: f(a)=a }[/math]. נהוג לסמנה: [math]\displaystyle{ 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])

תרגיל

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

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

נניח [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] אינה על -סתירה.

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

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

הגדרה: יהיו [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] חח"ע אזי f חח"ע.
• אם [math]\displaystyle{ g \circ f }[/math] על אזי g על.

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

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