תרגול 12 תשעז: הבדלים בין גרסאות בדף

מתוך Math-Wiki
אין תקציר עריכה
 
(4 גרסאות ביניים של 2 משתמשים אינן מוצגות)
שורה 12: שורה 12:


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


שורה 19: שורה 18:
'''הגדרה:'''
'''הגדרה:'''


יחס חד ערכי ומלא נקרא '''פונקציה'''; נסמן במקרה זה <math>(a,b)\in R\leftrightarrow b=R(a)</math>.  
יחס חד ערכי ושלם נקרא '''פונקציה'''; נסמן במקרה זה <math>(a,b)\in R\leftrightarrow b=R(a)</math>.  
ובאופן כללי <math>f:A\to B \;\; , a \mapsto f(a)</math>.  
ובאופן כללי <math>f:A\to B \;\; , a \mapsto f(a)</math>.  
(<math>A</math> נקרא תחום (הגדרה) של הפונקציה ו-<math>B</math> נקרא הטווח של הפונקציה.)
(<math>A</math> נקרא תחום (הגדרה) של הפונקציה ו-<math>B</math> נקרא הטווח של הפונקציה.)
שורה 29: שורה 28:
<math>f</math> חח"ע אמ"מ <math>f(x_1)=f(x_2)\Rightarrow x_1=x_2</math> אמ"מ <math>x_1\neq x_2 \Rightarrow f(x_1)\neq f(x_2)</math>.
<math>f</math> חח"ע אמ"מ <math>f(x_1)=f(x_2)\Rightarrow x_1=x_2</math> אמ"מ <math>x_1\neq x_2 \Rightarrow f(x_1)\neq f(x_2)</math>.


פונקציה נקראת '''על''' אם <math>Im(f)=B</math>.


'''הגדרה:'''
'''הגדרה:'''
שורה 64: שורה 64:


===תרגיל===
===תרגיל===
יהיו <math>A</math> ו-<math>B</math> קבוצות סופיות בעלות עוצמה זהה. הוכיחו שכל פונקציה מ-<math>A</math> ל-<math>B</math> הינה על אם"ם היא חח"ע.
תהיינה <math>A</math> ו-<math>B</math> קבוצות סופיות לא ריקות. הוכיחו: <math>|A|\geq |B|</math> אם ורק אם קיימת <math>f:A\to B</math> על.


'''הוכחה:'''
====הוכחה====
נסמן <math>f:A\to B, A=\{a_1,\dots, a_n\},B=\{b_1,\dots, b_n\} </math> . כאשר כל האיברים ב-<math>A</math> שונים זה מזה וכנ"ל ב-<math>B</math>.
נסמן <math>f:A\to B, A=\{a_1,\dots, a_n\},B=\{b_1,\dots, b_m\} </math> . כאשר כל האיברים ב-<math>A</math> שונים זה מזה וכנ"ל ב-<math>B</math>.
 
נניח <math>f</math> חח"ע אזי <math>|\{f(a_1),\dots, f(a_n)\}|=n</math>
כיוון ש-<math>\{f(a_1),\dots, f(a_n)\}\subseteq B </math>  ובשניהם יש אותו מספר איברים, מתקיים שיוון ולכן <math>f </math> על.
 
נניח  <math>f </math> על. נניח בשלילה ש-<math>f</math> אינה חח"ע אזי <math>|\{f(a_1),\dots, f(a_n)\}|<n</math> (כי יש שני איברים שנשלחים לאותו מקום) ואז <math>f</math> אינה על, שזו סתירה.
 
הערה: הדבר אינו נכון אם <math>A</math> ו-<math>B</math> קבוצות אינסופיות. נסו למצוא דוגמה.


===תרגיל===
===תרגיל===
שורה 130: שורה 123:
====פתרון====
====פתרון====


למעשה אפשר לעשות אינדוקציה על המשפט מן ההרצאה.
למעשה אפשר לעשות אינדוקציה על המשפט מן ההרצאה. עבור שתי פונקציות זה בהרצאה. נניח נכונות ל<math>k-1</math> ונוכיח ל<math>k</math>.


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


על: יהא <math>y\in A</math> כיוון ש-<math>f_k</math> על, קיים <math>a_k\in A</math> כך ש-<math>f_k(a_k)= y</math>  
על: יהא <math>y\in A</math> כיוון ש-<math>f_k</math> על, קיים <math>a\in A</math> כך ש-<math>f_k(a) = y</math>.
באותו אופן קיים <math>a_{k-1}</math> כך ש <math>f_{k-1}(a_{k-1})=a_k</math> נמשיך באופן דומה (או באינקודציה)
בנוסף, מהנחת האינדוקציה קיים <math>b\in A</math> כך ש <math>f_{k-1}\circ \dots \circ f_1(b)=a</math> ולכן נקבל
ונקבל <math>(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>f_k\circ \dots \circ f_1(b) = f_k\circ (f_{k-1}\circ \dots \circ f_1)(b)=f_k(a)=y</math>. מש"ל.


הפיכות: נובע מחח"ע יחד עם על.
הפיכות: נובע מחח"ע יחד עם על.
שורה 177: שורה 170:
ראינו (שקל לראות) שזהו יחס שקילות. ושמבחינה גיאומטרית, קבוצת המנה היא אוסף המעגלים עם רדיוס חיובי והראשית.
ראינו (שקל לראות) שזהו יחס שקילות. ושמבחינה גיאומטרית, קבוצת המנה היא אוסף המעגלים עם רדיוס חיובי והראשית.


נגדיר פונקציה <math>f:\mathbb{R}\times \mathbb{R}:\mathbb{R}</math> ע"י: <math>f((a,b))=a\cdot b</math>. האם היא מוגדרת היטב על קבוצת המנה? לא! למשל <math>f((\frac{1}{\sqrt{2}},\frac{1}{\sqrt{2}}))=\frac{1}{2}\neq 0=f((1,0))</math>, אך הם שקולים לפי היחס.
נגדיר פונקציה <math>f:\mathbb{R}\times \mathbb{R}\rightarrow \mathbb{R}</math> ע"י: <math>f((a,b))=a\cdot b</math>. האם היא מוגדרת היטב על קבוצת המנה? לא! למשל <math>f((\frac{1}{\sqrt{2}},\frac{1}{\sqrt{2}}))=\frac{1}{2}\neq 0=f((1,0))</math>, אך הם שקולים לפי היחס.


תנו דוגמא לפונקציה שכן מוגדרת היטב. למשל המרחק מהראשית (או כל פונקציה של זה).
תנו דוגמא לפונקציה שכן מוגדרת היטב. למשל המרחק מהראשית (או כל פונקציה של זה).

גרסה אחרונה מ־15:51, 14 בינואר 2020

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

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

הגדרה: יהיו [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 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{ Im(f)=B }[/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{ 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] לא חח"ע.

תרגיל

נסמן ב-[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{ B }[/math] קבוצות סופיות לא ריקות. הוכיחו: [math]\displaystyle{ |A|\geq |B| }[/math] אם ורק אם קיימת [math]\displaystyle{ f:A\to B }[/math] על.

הוכחה

נסמן [math]\displaystyle{ f:A\to B, A=\{a_1,\dots, a_n\},B=\{b_1,\dots, b_m\} }[/math] . כאשר כל האיברים ב-[math]\displaystyle{ A }[/math] שונים זה מזה וכנ"ל ב-[math]\displaystyle{ B }[/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{ 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{ k-1 }[/math] ונוכיח ל[math]\displaystyle{ k }[/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{ k-1 }[/math] פונקציות נקבל שההרכבה חח"ע ולכן [math]\displaystyle{ x_1=x_2 }[/math].

על: יהא [math]\displaystyle{ y\in A }[/math] כיוון ש-[math]\displaystyle{ f_k }[/math] על, קיים [math]\displaystyle{ a\in A }[/math] כך ש-[math]\displaystyle{ f_k(a) = y }[/math]. בנוסף, מהנחת האינדוקציה קיים [math]\displaystyle{ b\in A }[/math] כך ש [math]\displaystyle{ f_{k-1}\circ \dots \circ f_1(b)=a }[/math] ולכן נקבל [math]\displaystyle{ f_k\circ \dots \circ f_1(b) = f_k\circ (f_{k-1}\circ \dots \circ f_1)(b)=f_k(a)=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:A\rightarrow B }[/math] פונקציה, ויהי [math]\displaystyle{ R }[/math] יחס שקילות על [math]\displaystyle{ A }[/math]. אומרים כי [math]\displaystyle{ f }[/math] מוגדרת היטב על [math]\displaystyle{ A/R }[/math] אם [math]\displaystyle{ \forall a,b\in A:(a,b)\in R\Rightarrow f(a)=f(b) }[/math]

כלומר אם [math]\displaystyle{ a }[/math] שקול ל [math]\displaystyle{ b }[/math] אזי [math]\displaystyle{ f(a)=f(b) }[/math].

למה זה טוב? כדי שנוכל להגדיר פונקציה על קבוצת המנה [math]\displaystyle{ g:A/R \to B }[/math] ע"י [math]\displaystyle{ [a]_R \mapsto f(a) }[/math]

טענה: [math]\displaystyle{ g }[/math] אכן פונקציה

הוכחה:

1. [math]\displaystyle{ g }[/math] שלמה - "לפי העיניים". כלל ההתאמה מנוסח כך שהיחס הוא שלם.

2. [math]\displaystyle{ g }[/math] חד ערכית- נניח [math]\displaystyle{ [a]=[b] }[/math], צ"ל [math]\displaystyle{ g([a])=g([b]) }[/math]. מהנתון ש [math]\displaystyle{ [a]=[b] }[/math] נובע ש [math]\displaystyle{ (a,b)\in R }[/math], ולכן, לפי הגדרת [math]\displaystyle{ f }[/math] כמוגדרת היטב על קבוצת המנה, מתקיים [math]\displaystyle{ f(a)=f(b) }[/math], ולפי הגדרת [math]\displaystyle{ g }[/math] מתקיים [math]\displaystyle{ g([a])=f(a)=f(b)=g([b]) }[/math].


דוגמא לחידוד

ראינו מעל [math]\displaystyle{ \mathbb{R}\times \mathbb{R} }[/math] יחס [math]\displaystyle{ \sim }[/math] לפי זה שלכל [math]\displaystyle{ (x_1,y_1),(x_2,y_2) }[/math]:

[math]\displaystyle{ (x_1,y_1)\sim (x_2,y_2)\iff x_1^2+y_1^2=x_2^2+y_2^2 }[/math].

ראינו (שקל לראות) שזהו יחס שקילות. ושמבחינה גיאומטרית, קבוצת המנה היא אוסף המעגלים עם רדיוס חיובי והראשית.

נגדיר פונקציה [math]\displaystyle{ f:\mathbb{R}\times \mathbb{R}\rightarrow \mathbb{R} }[/math] ע"י: [math]\displaystyle{ f((a,b))=a\cdot b }[/math]. האם היא מוגדרת היטב על קבוצת המנה? לא! למשל [math]\displaystyle{ f((\frac{1}{\sqrt{2}},\frac{1}{\sqrt{2}}))=\frac{1}{2}\neq 0=f((1,0)) }[/math], אך הם שקולים לפי היחס.

תנו דוגמא לפונקציה שכן מוגדרת היטב. למשל המרחק מהראשית (או כל פונקציה של זה).

תמונות חלקיות

הגדרה. תהי [math]\displaystyle{ f:X\rightarrow Y }[/math] פונקציה, ויהיו תת קבוצות [math]\displaystyle{ A\subseteq X,B\subseteq Y }[/math]. אזי התמונה החלקית של A תחת f היא התת-קבוצה [math]\displaystyle{ f[A]=\{f(a)|a\in A\} }[/math], והתמונה החלקית ההפוכה של B תחת f היא התת-קבוצה [math]\displaystyle{ f^{-1}[B]=\{a\in X|f(a)\in B\} }[/math].

שימו לב להבדל בין התמונה ההפוכה [math]\displaystyle{ f^{-1}[B] }[/math] לבין הפונקציה ההופכית [math]\displaystyle{ f^{-1}(y) }[/math]. התמונה ההפוכה איננה מניחה כי הפונקציה f הפיכה. הדרך להבחין בין פונקציה הפיכה לתמונה ההפוכה היא לבדוק האם בין הסוגריים נמצא איבר של התמונה (בדוגמאות לעיל זהו [math]\displaystyle{ y \in Y }[/math]) או שנמצאת תת-קבוצה של התמונה (בדוגמאות לעיל זו [math]\displaystyle{ B\subseteq Y }[/math]).

דוגמאות

תהא [math]\displaystyle{ D:\mathbb{R}\to \mathbb{R} }[/math] פונקצית דריכלה. אזי [math]\displaystyle{ D[\mathbb{Q}]=\{1\},D^{-1}[\{1\}]=\mathbb{Q}=D^{-1}[(0.5, 18)] }[/math]

תהא [math]\displaystyle{ f:X\to Y }[/math] פונקצית . אזי [math]\displaystyle{ f^{-1}[Y]=X }[/math]

תהא [math]\displaystyle{ f:\mathbb{R}\to \mathbb{Z} }[/math] פונקצית הערך השלם התחתון. אזי [math]\displaystyle{ f[(-0.5,3/4)]=\{-1,0\},f^{-1}[\{1\}]=[1,2) }[/math]


תרגיל

תהי [math]\displaystyle{ f:X\rightarrow Y }[/math] ותהי [math]\displaystyle{ A\subseteq X }[/math]. הוכח [math]\displaystyle{ A \subseteq f^{-1}[f[A]] }[/math]. וקיים שיוויון אם [math]\displaystyle{ f }[/math] חח"ע

פתרון

יהא [math]\displaystyle{ a\in A }[/math] אזי [math]\displaystyle{ f(a)\in f[A] }[/math] ולכן [math]\displaystyle{ a\in f^{-1}[f[A]] }[/math].

נראה את ההכלה בכיוון השני אם [math]\displaystyle{ f }[/math] חח"ע:

יהא [math]\displaystyle{ x\in f^{-1}[f[A]] }[/math] לכן [math]\displaystyle{ f(x) \in f[A] }[/math] לכן [math]\displaystyle{ \exists a\in A : f(x)=f(a) }[/math]. כיוון ש [math]\displaystyle{ f }[/math] חח"ע נובע כי [math]\displaystyle{ x=a\in A }[/math]

דוגמא שלא מתקיים שיוויון [math]\displaystyle{ f:\{1,2\}\to \{1\} }[/math] (יש דרך אחת להגדיר את הפונקציה). אזי נגדיר [math]\displaystyle{ A=\{2\} }[/math] ומתקיים [math]\displaystyle{ f^{-1}(f(A))=\{1,2\}\neq A }[/math]

תרגיל

תהי [math]\displaystyle{ f:X\rightarrow Y }[/math] פונקציה, ותהיינה [math]\displaystyle{ A,B\subseteq X }[/math]. הוכיחו: [math]\displaystyle{ f[A\triangle B]=f[A]\triangle f[B] }[/math] [math]\displaystyle{ \iff }[/math] [math]\displaystyle{ f }[/math] חח"ע