הבדלים בין גרסאות בדף "88-195 בדידה לתיכוניסטים תשעא/מערך שיעור/שיעור 4"

מתוך Math-Wiki
קפיצה אל: ניווט, חיפוש
(←‏פונקציות)
(←‏הרכבת פונקציות)
 
(58 גרסאות ביניים של 8 משתמשים אינן מוצגות)
שורה 1: שורה 1:
 +
'''[[מתמטיקה בדידה - מערך תרגול|חזרה למערכי התרגול]]'''
 +
 
==פונקציות==
 
==פונקציות==
−
'''הגדרה:''' יהיו A,B קבוצות וR יחס בינהן. אזי:
+
'''הגדרה:''' (אפשר לדלג ולהתמקד בתחום וטווח של פונקציות ולא של יחסיים כללים) יהיו A,B קבוצות וR יחס בינהן. אזי:
−
*התחום של R הינו <math>dom(R)=\{a\in A|\exists b\in B:(a,b)\in R\}</math>
+
*התחום של R הינו <math>dom(R)=\{a\in A|\exists b\in B:(a,b)\in R\}=\{(*,\;),(*,\;)\dots \}</math>
−
*התמונה של R הינה <math>im(R)=\{b\in B|\exists a\in A:(a,b)\in R\}</math>
+
*התמונה של R הינה <math>im(R)=\{b\in B|\exists a\in A:(a,b)\in R\}=\{(\;,*),(\; ,*)\dots \}</math>
 +
 
 +
'''הערה''': ישירות מהגדרה  מתקיים כי <math>dom(R)\subseteq A, Im(R)\subseteq B</math>
  
−
'''דוגמא.'''
+
'''דוגמא:'''
−
*אם R יחס מלא על A אזי האיחוד של התמונה והתחום שווה A
+
*אם R יחס מלא על A אזי האיחוד של התמונה והתחום שווה A (כי כל שני איברים ניתן להשוות)
−
*<math>R=\{(1,a),(2,b),(3,a)\}</math> אזי התחום הוא <math>dom(R)=\{1,2,3\}</math> והתמונה הינה <math>im(R)=\{a,b\}</math>
+
*<math>R=\{(1,a),(2,b),(3,a),(a,1)\}</math> אזי התחום הוא <math>dom(R)=\{a,1,2,3\}</math> והתמונה הינה <math>im(R)=\{1,a,b\}</math>
  
 
'''הגדרה:'''  
 
'''הגדרה:'''  
−
*יחס R נקרא '''חד ערכי''' אם <math>[(x,b)\in R] \and [(x,d) \in R] \rightarrow (d=b)</math>
+
*יחס R מ-A ל-B נקרא '''על''' אם <math>\forall b\in B \exists a\in A:(a,b)\in R</math> כלומר <math>im(R)=B</math>
−
*יחס R נקרא '''חד-חד ערכי''' אם <math>[(x,b)\in R] \and [(y,b) \in R] \rightarrow (x=y)</math> (כלומר, היחס ההופכי הינו חד ערכי)
+
*יחס R מ-A ל-B נקרא '''שלם''' אם <math>\forall a\in A \exists b\in B:(a,b)\in R</math> כלומר <math>dom(R)=A</math>
−
*יחס R נקרא '''על''' אם <math>\forall b\in B:\exists a\in A:(a,b)\in R</math> כלומר <math>im(R)=B</math>
+
*יחס R נקרא '''חד ערכי''' אם <math>[(x,b)\in R] \and [(x,d) \in R] \rightarrow (d=b)</math> כלומר אין איבר שנשלח ל-2 מקומות שונים
 +
*יחס R נקרא '''חד-חד ערכי''' אם <math>[(x,b)\in R] \and [(y,b) \in R] \rightarrow (x=y)</math> כלומר איברים שונים נשלחים למקומות שונים (כלומר, היחס ההופכי הינו חד ערכי)
  
 
'''הגדרה:'''
 
'''הגדרה:'''
  
−
יחס חד ערכי נקרא '''פונקציה'''; נסמן במקרה זה <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>.
 +
(A נקרא תחום (הגדרה) של הפונקציה. ו B נקרא הטווח של הפונקציה)
  
−
'''דוגמאות:'''
+
נחזור על הגדרת חח"ע עבור פונקציה:
−
*<math>f:\mathbb{Z}\rightarrow\mathbb{Z}</math> כאשר <math>f(p)=p^2</math> (אינה חח"ע ואינה על)
+
−
*<math>f:\mathbb{Z}\rightarrow\mathbb{Z}</math> כאשר <math>f(p)=p</math>. זו נקראת פונקצית הזהות והיא חח"ע וגם על
+
−
*<math>f:\mathbb{R}\rightarrow\mathbb{Z}</math> כאשר <math>f(x)=[x]</math> מוגדר להיות הערך השלם הקרוב ביותר ל-x (במקרה של חצי לוקחים את הגבוה). זו פונקציה על שאינה חח"ע
+
−
*<math>f:\mathbb{Z}_2\rightarrow\mathbb{Z}_3</math> כאשר לוקחים את 0 ל0 ואת 1 ל1. זו פונקציה חח"ע שאינה על. (כל פונקציה היא על לתמונה של עצמה.)
+
−
*<math>D:\mathbb{R}\rightarrow\mathbb{R}</math> פונקצית דיריכליי: על כל מספר רציונאלי מקבלת 1 ועל כל מספר אי רציונאלי מקבלת אפס.
+
  
−
'''תרגיל.'''
+
<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>
−
יהיו A וB קבוצות סופיות בעלות עוצמה זהה. הוכח שכל פונקציה מA לB הינה על אם"ם היא חח"ע
+
  
−
'''הוכחה.'''
 
−
נניח שהפונקציה חח"ע. נזכר שפונקציה הינה יחס, ונספור את הזוגות הסדורים שהיא מכילה; מכיוון שהתחום של הפונקציה הוא A מספר הזוגות הוא בדיוק מספר האיברים בA (מתוך חד ערכיות והעובדה שזה תחום). לכל איבר בA קיים זוג יחיד בפונקציה. אם היה זוג שהיה מקבל את אותו איבר בB זו הייתה סתירה לח"ע ולכן מספר האיברים מB שמופיעים בזוגות הוא כמספר האיברים בA. מכיוון שעוצמת הקבוצות זהה, כל האיברים מB מופיעים בזוג ולכן הפונקציה על.
 
  
−
נניח שהפונקציה על. אם היא לא הייתה חח"ע היה איבר בB שחוזר על עצמו בזוגות לעיל ולכן מספר האיברים המופיע בB היה לכל היותר מספר האיברים בA פחות אחד בסתירה.
+
'''הגדרה:'''
  
−
'''תרגיל.'''
+
תהא A קבוצה. '''פונקציית הזהות''' היא פונקציה <math>f:A \to A</math> המקיימת <math>\forall a\in A: f(a)=a</math>. נהוג לסמנה: <math>id_A</math> פונקציית הזהות היא חח"ע ועל.
−
יהיו A וB קבוצות אינסופיות. האם כל פונקציה בינהן היא על אם"ם היא חח"ע?
+
  
−
'''פתרון.'''
+
===דוגמאות:===
−
לא. דוגמא: פונקצית הערך השלם על ואינה חח"ע
+
*<math>f:\mathbb{Z}\rightarrow\mathbb{Z}</math> כאשר <math>f(p)=p^2</math> (אינה חח"ע ואינה על)
 +
*<math>f:\mathbb{N}\rightarrow\mathbb{Z}</math> כאשר <math>f(p)=p^2</math> ( חח"ע ואינה על)
 +
*<math>f:\mathbb{Z}\rightarrow\mathbb{Z}</math> כאשר <math>f(p)=p</math>. זו פונקציית הזהות.
 +
*<math>f:\mathbb{R}\rightarrow\mathbb{R}</math> כאשר <math>f(x)=x-1</math> ( חח"ע ו על)
 +
* <math>f:\mathbb{R}\to\mathbb{R}</math> המוגדרת ע"י הכלל <math>f(x)=\sin(x)</math>.  
 +
*<math>f:\mathbb{R}\to\mathbb{R}</math> המוגדרת ע"י הכלל <math>f(x)=x^{3}</math>
 +
* <math>f:\mathbb{C}\to\mathbb{C}</math> המוגדרת ע"י הכלל <math>f(x)=x^{2}</math>
 +
*<math>f:\mathbb{N}\rightarrow\mathbb{N}</math> כאשר <math>f(x)=x-1</math> ( לא מוגדר כי <math>f(1)=?</math>)
 +
*<math>f:\mathbb{R}\rightarrow\mathbb{Z}</math> כאשר <math>f(x)=[x]</math> מוגדר להיות הערך השלם הקרוב ביותר ל-x (במקרה של חצי לוקחים את הגבוה). זו פונקציה על שאינה חח"ע
 +
*<math>f:\mathbb{Z}_2\rightarrow\mathbb{Z}_3</math> כאשר לוקחים את 0 ל0 ואת 1 ל1. זו פונקציה חח"ע שאינה על. (כל פונקציה היא על לתמונה של עצמה.)
 +
*<math>D:\mathbb{R}\rightarrow\mathbb{R}</math> פונקצית דיריכלה: על כל מספר רציונאלי מקבלת 1 ועל כל מספר אי רציונאלי מקבלת אפס.
 +
* תהא <math>A</math> קבוצה ו <math>B\subseteq A</math> תת קבוצה. הפונקציה
 +
<math>
 +
\chi_B=
 +
\begin{cases} 1 & \text{ if } x\in B \\ 0 & \text{ otherwise } \end{cases}
 +
</math>
 +
פונקצית האינדקטור. במקרה של דריכלה <math>D=\chi_{\mathbb{Q}}</math>
 +
* תהא <math>f:A\to B</math> אזי <math>g:A\to Im(f) </math> המוגדרת <math>g(a)=f(a)</math> היא על (במילים: פשוט חושבים על הטווח של f להיות התמונה של g)
 +
* תהא <math>A\subseteq B</math>  אזי הפונקציה <math>i : A\to B </math> המוגדרת <math>i(a)=a</math> נקראת פונקציה ההכלה (במקרה ש <math>A=B</math> זה פונקצית הזהות). פונקצית ההכלה היא חח"ע.
  
−
'''תרגיל.'''
+
====תרגיל (בשיעוריי הבית)====
−
*נניח <math>f \circ g</math> חח"ע. הוכח/הפרך: f חח"ע, g חח"ע  
+
יהיו A ו-B קבוצות סופיות בעלות עוצמה זהה. הוכח שכל פונקציה מ-A ל-B הינה על אם"ם היא חח"ע
−
*נניח <math>f \circ g</math> על. הוכח/הפרך: f על, g על
+
  
 +
=====הוכחה=====
 +
נסמן <math>f:A\to B, A=\{a_1,\dots a_n\},B=\{b_1,\dots b_n\} </math> . כאשר כל האיברים ב A שונים זה מזה וכנ"ל ל B
  
−
'''פתרון.'''
+
נניח  <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 \circ g</math> חח"ע. נניח בשלילה ש-g אינה חח"ע. לכן קיימים <math>x,y</math> כך ש <math>g(x)=g(y)</math> אבל <math>x\neq y</math>. אבל, <math>f\circ g (x) = f(g(x))=f(g(y))=f\circ g(y)</math> בסתירה לחח"ע של ההרכבה, ולכן g חח"ע.  
+
נניח <math>f </math> על. נניח בשלילה ש <math>f </math> אינה חח"ע אזי <math>|\{f(a_1),\dots f(a_n)\}|<n</math> (כי יש שני איברים שנשלחים לאותו מקום)
 +
ואז <math>f </math> אינה על -סתירה.  
  
−
לגבי f ניתן דוגמא נגדית: <math>(e^x)^2</math>
+
הערה: הדבר אינו נכון אם  A וB קבוצות אינסופיות.
  
 +
למשל פונקצית הערך השלם  <math>f:\mathbb{R} \to \mathbb{Z} </math>  המוגדרת <math>f(x) =\lfloor{x}\rfloor</math> היא על ואינה חח"ע
  
−
נניח <math>f \circ g</math> על. נסמן <math>f \circ g : A\rightarrow B</math> אזי לכל איבר <math>b\in B</math> קיים איבר <math>a\in A</math> כך ש <math>f(g(a))=b</math>. לכן עבור f לכל b קיים <math>g(a)</math> שנותן את b תחת f ולכן f על.
+
==== תרגיל====
 +
קבעו האם הפונקציות הבאות חח"ע/על
 +
* <math>f:\mathbb{R}\to \mathbb{R}</math> המוגדרת <math>f(x)=\lfloor x \rfloor</math>
 +
* <math>f:\mathbb{N}\times \mathbb{N}\to \mathbb{Z}</math> המוגדרת <math>f(n,m)=n-m</math>
 +
*תהא A קבוצה, הפונקציה <math>f:A\to P(P(A))</math> המוגדרת <math>f(x)=\{B\subseteq A \mid x\in B\}</math>
  
−
דוגמא נגדית ל g: נביט בפונקציות מהטבעיים לטבעיים. <math>g(n)=2n</math>, והפונקציה f מוגדרת כ <math>f(2n)=n</math> ו <math>f(2n+1)=n</math>. ההרכבה הינה פונקצית הזהות שהיא בפרט על, אבל g אינה על כיוון שהאי זוגיים כלל לא נמצאים בתמונה שלה.
+
==== תרגיל====
 +
מצאו פונקציה <math>f:\mathbb{N}\to \mathbb{N}</math> על שאינה חח"ע.
  
 +
==== תרגיל ====
 +
תהא A קבוצה ו <math>f:A\to \mathbb{N}</math> פונקציה. נגדיר יחס R על A ע"י <math>aRa'\iff f(a)\leq f(a')</math>. הוכיחו כי R יחס סדר על A אמ"מ <math>f</math> חח"ע.
  
−
'''הגדרה:''' פונקצית הזהות על A הינה פונקציה מA לעצמו השולחת כל איבר לעצמו. נהוג לסמנה ב<math>id_A</math>. פונקציה <math>f:A\rightarrow B</math> נקראת הפיכה אם קיימת לה הופכית - פונקציה <math>f^{-1}:B\rightarrow A</math> כך שמתקיים <math>f\circ f^{-1} = id_B</math> וגם <math>f^{-1}\circ f = id_A</math>.  
+
==== תרגיל ====
 +
א. תהא A קבוצה לא ריקה. מצאו פונקציה <math>F:A^A\to A</math> שהיא על.
  
−
הערה: זכרו שפונקציה היא יחס. הפונקציה ההופכית שלה היא היחס ההופכי מטבע הדברים. על מנת שהיחס ההופכי יהיה פונקציה הוא צריך להיות ח"ע ושהתחום שלו יהיה כל B. תנאים אלה מתממשים רק אם f הינה חח"ע ועל.
+
ב. תהא <math>A</math> קבוצה. מצאו פונקציה <math>F:A\to A^A</math> שהיא חח"ע.
  
−
'''תרגיל.'''
+
ג. למה בסעיף א צריך לא ריקה ובסעיף ב אפשר גם ריקה?
  
−
הוכח כי f הפיכה אם"ם היא חח"ע ועל. כמו כן, הוכח שאם קיימת הופכית אזי היא יחידה.
+
==== תרגיל ====
 +
תהיינה <math>f,g:\mathbb{N}\rightarrow \mathbb{N}</math> פונקציות כך ש-<math>f(n)=g(3n-1)</math>.
  
−
'''הוכחה:'''
+
הוכיחו שאם <math>f</math> על, אז <math>g</math> לא חח"ע.
  
−
אם f הפיכה, אזי <math>f\circ f^{-1} = id_B</math> וגם <math>f^{-1}\circ f = id_A</math>. מכיוון שהזהות הינה חח"ע ועל, נובע שf חח"ע ועל לפי התרגיל הקודם.
+
==הרכבת פונקציות==
  
−
אם f חח"ע ועל, אז היחס ההופכי שלה ח"ע ומוגדר והוא מהווה פונקציה הופכית. (אמנם החסרנו את רוב ההוכחה, אך היא פשוטה למדי.)
 
  
−
נניח בשלילה ש g וh הופכיות שונות של f. מכיוון שהן שונות, הן חייבות להיות שונות על איבר אחד לפחות. כלומר, <math>\exists a\in A:g(a)\neq h(a)</math>. אבל <math>f(g(a))=f(h(a))</math> וזו סתירה לחח"ע של f.
+
'''הגדרה:'''
 +
יהיו  <math>f:A\to B, g:B\to C </math> שתי פונקציות אז '''ההרכבה של <math>g</math> על <math>f</math>''' היא פונקציה  <math>g \circ f:A\to C </math> המוגדרת על ידי הכלל <math>g \circ f(a)=g(f(a)) </math>
  
  
−
'''הגדרה.''' תהי <math>f:X\rightarrow Y</math> פונקציה, ויהיו תת קבוצות <math>A\subseteq X,B\subseteq Y</math>. אזי <math>f(A)=\{f(a)|a\in A\}</math>, <math>f^{-1}(B)=\{a\in A|f(a)\in B\}</math>.
+
תכונות:
 +
# הרכבה היא קיבוצית. כלומר <math>f_3 \circ (f_2 \circ f_1) = (f_3 \circ f_2) \circ f_1 </math>
 +
# הרכבה '''אינה''' (בהכרח) חילופית כלומר לא מתקיים בהכרח כי <math>f_2 \circ f_1 = f_2 \circ  f_1 </math>. למשל <math>f(x) =x^2 , g(x) = x+1</math> אזי <math>f(g(2))=f(3)=9, g(f(2))=g(4)=5</math> ולכן <math>f\circ g \neq g \circ f</math>
  
−
שימו לב שהסימון <math>f^{-1}(B)</math> אינו רומז בשום צורה שהפונקציה צריכה להיות הפיכה, הגדרה זו תקפה לכל פונקציה.
+
==== תרגיל ====
 +
תהא <math>g:\mathbb{N}\to \mathbb{N}</math> פונקציה. נגדיר <math>F:\mathbb{N}^{\mathbb{N}}\to \mathbb{N}^{\mathbb{N}}</math> ע"י <math>F(f)=g\circ f</math>. הוכיחו כי F חח"ע אמ"מ g חח"ע.
  
 +
=====פתרון=====
 +
<math>\Leftarrow</math>: נתון: F חח"ע. נניח <math>g(n)=g(m)</math>, לכן עבור הפונקציות הקבועות <math>f\equiv n,f'\equiv m</math> נקבל <math>\forall k:g\circ f(k)=g((n)=g(m)=g\circ f'(k)</math> ולכן <math>F(f)=g\circ f=g\circ f'=F(f')</math>, ומחח"ע של F נקבל <math>f=f'</math> ולכן <math>n=m</math>.
  
−
'''תרגיל.'''
+
<math>\Rightarrow</math>: נתון <math>g</math> חח"ע. תהיינה <math>f\neq f'\in \mathbb{N}^{\mathbb{N}}</math>, לכן יש <math>n\in \mathbb {N}</math> כך ש- <math>f(n)\neq f'(n)</math>, ולכן זה מתקיים גם אחרי ההרכבה, ולכן <math>F(f)\neq F(f')</math>.
−
הוכח/הפרך: <math>f(A)\cap f(B)=f(A\cap B)</math>
+
  
−
'''פתרון.'''
+
====תרגיל====
 +
*נניח <math>g \circ f</math> חח"ע. הוכח/הפרך: g חח"ע, f חח"ע
 +
*נניח <math>g \circ f</math> על. הוכח/הפרך: g על, f על
  
−
נניח וf אינה חח"ע, כלומר קיימים <math>x\neq y </math> כך ש <math>f(x)=f(y)</math>. ניקח <math>A=\{x\},B=\{y\}</math> אזי:
+
=====פתרון=====
  
−
<math>f(A)\cap f(B) = \{f(x)\} \neq \phi = f(\{\}) = f(A\cap B)</math>
+
נניח <math>g \circ f</math> חח"ע. נניח בשלילה ש-f אינה חח"ע. לכן קיימים <math>x,y</math> כך ש <math>f(x)=f(y)</math> אבל <math>x\neq y</math>. אבל, <math>g\circ f (x) = g(f(x))=g(f(y))=g\circ f(y)</math> בסתירה לחח"ע של ההרכבה, ולכן f חח"ע.
  
−
'''תרגיל.'''
+
לגבי g ניתן דוגמא נגדית: <math>f(x)=e^x ,g(y)=y^2</math> ההרכבה היא <math>h(x)=e^{2x}</math>
−
תהי <math>f:X\rightarrow Y</math> חח"ע, ותהי <math>A\subseteq X</math>. הוכח <math>f^{-1}(f(A))=A</math>.
+
  
−
'''פתרון.'''
 
  
−
ישירות מההגדרות נובע שאם <math>a\in A</math> אזי <math>f(a)\in f(A)</math> ולכן <math>a\in f^{-1}(f(A))</math>. סה"כ הראנו <math>A\subseteq f^{-1}(f(A))</math>. (עד כה זה נכון לכל העתקה, לאו דווקא חח"ע.)
+
נניח <math>g \circ f</math> על. נסמן <math>g \circ f : A\rightarrow B</math> אזי לכל איבר <math>b\in B</math> קיים איבר <math>a\in A</math> כך ש <math>g(f(a))=b</math>. לכן עבור g לכל b קיים <math>f(a)</math> שנותן את b תחת g ולכן g על.  
  
−
נניח כעת בשלילה ש <math>f^{-1}(f(A))\neq A</math> לכן קיים <math>x\in f^{-1}(f(A))</math> כך ש <math>x\notin A</math>. לכן לפי ההגדרה, <math>f(x)\in f(A)</math>. לכן קיים a בA כך ש <math>f(a)=f(x)</math>. מתוך החח"ע נובע ש-x=a בסתירה.
+
דוגמא נגדית ל f: נתבונן בשתי הפונקציות מהטבעיים לעצמם
 +
<math>f(n)=n+1</math>;
 +
<math>\forall n\not=0 g(n)=n-1 , g(0)=0</math>
 +
ההרכבה היא הזהות
  
 +
(עוד דוגמא נביט בפונקציות מהטבעיים לטבעיים. <math>f(n)=2n</math>, והפונקציה g מוגדרת כ <math>g(2n)=n</math> ו <math>g(2n+1)=n</math>. ההרכבה הינה פונקצית הזהות שהיא בפרט על, אבל f אינה על כיוון שהאי זוגיים כלל לא נמצאים בתמונה שלה.)
  
 +
==פונקציות הפיכות==
 +
'''הערה:''' לכל פונקציה <math>f</math> מתקיים <math>f\circ id =f</math> וגם <math>id \circ f =f</math>
  
−
'''תרגיל ממבחן (קצת משודרג).'''
+
'''הגדרה:''' תהי <math>f</math> פונקציה <math>f:A\rightarrow B</math>. פונקציה <math>g:B\rightarrow A</math> תיקרא '''הפונקציה ההופכית ל-<math>f</math>''' אם <math>f\circ g = id_B</math> וגם <math>g\circ f = id_A</math>. במקרה זה נסמן את <math>g</math> על ידי <math>f^{-1}</math>, ונאמר שהפונקציה <math>f</math> היא '''הפיכה'''.
  
−
יהיו <math>X,Y</math> שתי קבוצות, ותהי <math>f:X\rightarrow Y</math> פונקציה כלשהי. נגדיר את הפונקציה <math>g:P(Y)\rightarrow P(X)</math> על ידי <math>g(B)=f^{-1}(B)</math>.
+
הערה: זכרו שפונקציה היא יחס. הפונקציה ההופכית שלה היא היחס ההופכי מטבע הדברים. על מנת שהיחס ההופכי יהיה פונקציה הוא צריך להיות ח"ע ושהתחום שלו יהיה כל B. תנאים אלה מתממשים רק אם f הינה חח"ע ועל.
−
בדוק את הקשר בין החח"ע/על של f לבין אלה של g. (כלומר, מה גורר את מה בהכרח).
+
  
−
'''פתרון.'''
+
====משפט====
  
−
תהי f חח"ע שאינה על (קל למצוא כאלה). אזי <math>\exists y\in Y\forall x\in X:f(x)\neq y</math>. לכן <math>g(Y)=f^{-1}(Y)=f^{-1}(Y/\{y\}=g(Y/\{y\})</math> בסתירה לחח"ע של g.
+
הוכח כי f הפיכה אם"ם היא חח"ע ועל. כמו כן, הוכח שאם קיימת הופכית אזי היא יחידה.
−
 
+
−
 
+
−
*לכן '''ייתכן ו-f חח"ע אך g אינה כזו'''.
+
−
 
+
−
 
+
−
תהי f כך ש-g חח"ע. כפי שראינו לעיל, ניתן ישר להסיק ש-f הינה על.
+
−
 
+
−
 
+
−
נוכיח שאם f על אזי g חח"ע; נניח בשלילה שg אינה חח"ע, אזי קיימות שתי קבוצות <math>B\neq C \in P(Y)</math> כך ש <math>g(B)=g(C)</math>. בלי הגבלת הכלליות, נניח שקיים איבר <math>c\in C</math> כך ש <math>c\notin B</math>. מכיוון ש-f על, קיים איבר a כך ש <math>f(a)=c</math>, לכן <math>a\in g(B)</math>, ואז קיים <math>b\in B</math> כך ש<math>f(a)=b</math> ולכן b=c בסתירה.
+
−
 
+
−
 
+
−
*אם כן, הוכחנו ש-'''f על אם"ם g חח"ע.'''
+
−
 
+
−
 
+
−
יהיו <math>X=\mathbb{Z}, Y=\{0\}</math>. אזי קיימת פונקציה f יחידה מX לY. פונקציה זו אינה חח"ע כמובן, אך g כן חח"ע שכן <math>g(\{\})\neq g(\{0\})</math> ואלה הקבוצות היחידות בקבוצת החזקה של Y.
+
−
 
+
−
 
+
−
*לכן '''יתכן ו-g חח"ע אך f אינה כזו'''.
+
−
 
+
−
 
+
−
נניח וg על ונניח בשלילה ש-f אינה חח"ע. לכן קיימים <math>a,b \in X</math> שונים כך ש <math>f(x)=f(y)</math>. נביט בנקודון <math>A=\{x\}</math> נניח וקיימת <math>B\in P(Y)</math> כך ש <math>g(B)=A</math>, לכן <math>f(x)\in B</math>. אבל אז בעצם גם <math>f(y)\in B</math> ולכן <math>y\in g(B)=A</math> בסתירה. לכן f חח"ע.
+
−
 
+
−
 
+
−
נניח f חח"ע, הוכחנו כבר שבהכרח <math>f^{-1}(f(A))=A</math> לכל A תת קבוצה של X. נובע ש <math>g(f(A))=A</math> ולכן g הינה על.
+
−
 
+
−
 
+
−
*סה"כ, הוכחנו ש'''f חח"ע אם"ם g הינה על'''.
+
−
 
+
−
 
+
−
ניקח f פונקציה חח"ע שאינה על, לכן g היא על.
+
−
 
+
−
 
+
−
*לכן '''ייתכן ו-g הינה על אך f אינה על'''
+
  
 +
=====הוכחה=====
  
−
באופן דומה ניקח f על שאינה חח"ע, לכן g אינה על.
+
אם f הפיכה, אזי <math>f\circ f^{-1} = id_B</math> וגם <math>f^{-1}\circ f = id_A</math>. מכיוון שהזהות הינה חח"ע ועל, נובע ש-f חח"ע ועל לפי התרגיל הקודם בדבר הרכבת פונקציות.
  
 +
אם f חח"ע ועל, אז נגדיר <math>g:B\to A</math> ע"י: עבור <math>a\in A </math> קיים (כי f על) יחיד (כי f חח"ע)
 +
<math>b\in B</math> כך ש <math>f(a)=b</math> . נגדיר <math>g(b):=a</math>. תרגיל: בדקו ש g ההופכית של f.
  
−
*לכן '''ייתכן ו-f הינה על אך g אינה על'''
+
יחידות: נניח g,h הופכיות של f אזי <math>h= h\circ I_B=h\circ f \circ g=I_A \circ g=g</math>.
  
 +
דרך אחרת להוכחת יחידות: נניח בשלילה ש g וh הופכיות שונות של f. מכיוון שהן שונות, הן חייבות להיות שונות על איבר אחד לפחות. כלומר, <math>\exists a\in A:g(a)\neq h(a)</math>. אבל <math>f(g(a))=f(h(a))</math> וזו סתירה לחח"ע של f.
  
 +
====משפט====
 +
יהיו <math>f_1,\dots f_k:A\to A</math> הפיכות/חח"ע/על. הוכח שההרכבה <math>f_k \circ \dots \circ f_1</math> הפיכה/חח"ע/על
  
−
'''הגדרה.'''
+
=====הוכחה=====
−
תהי <math>f:X\rightarrow Y</math> ותהי <math>A\subseteq X</math>. הפונקציה '''f מצומצמת לA''' מוגדרת על ידי: <math>f|_A:A\rightarrow Y</math> כך ש <math>f|_A(a)=f(a)</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:\mathbb{R}\rightarrow\mathbb{R}</math> המוגדרת על ידי <math>f(x)=x^2</math> ואינה חח"ע. נכון לומר שהפונקציה המצומצמת <math>f|_{\mathbb{N}}</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>y\in A</math> כיוון ש <math>f_k</math> על קיים <math>a_k\in A</math> כך ש <math>f_k(a_k)= y</math>
 +
באותו אופן קיים <math>a_{k-1}</math> כך ש <math>f_{k-1}(a_{k-1}=a_k</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:X\rightarrow Y</math> פונקציה, הוכח שקיימת קבוצה A כך ש<math>f|_A</math> חח"ע
+
  
−
'''פתרון.'''
+
====מסקנות====
  
−
פייי זו שאלה קשה. תזכירו לנו אותה כאשר נגיע לאקסיומת הבחירה. (שכן נביט ב<math>\{f^{-1}(\{y\})|y\in Y\})</math> ונרצה לבחור איבר יחיד מבין כל קבוצה כזו. אקסיומת הבחירה היא זו המאפשרת לנו לבצע בחירה זו בשלום.)
+
* אם <math>f,g</math> הפיכות אז <math>g\circ f</math> הפיכה.
  
 +
* אם <math>g\circ f</math> הפיכה אז <math>f</math> חח"ע, <math>g</math> על (והן לאו דוקא הפיכות).
  
−
'''הגדרה.''' תהי <math>f:A\rightarrow A</math>, ויהי R יחס שקילויות על A. אומרים כי '''f מוגדרת היטב על <math>A/R</math>''' אם <math>\forall a,b\in A:(a,b)\in R\rightarrow (f(a),f(b)\in R</math>
+
==== דוגמאות ====
 +
1. <math>f:\mathbb{R} \to \mathbb{R}</math> המוגדרת:
 +
# <math>f(x)=x+1</math> הפיכה וההופכית היא <math>f^{-1}(x) = x-1 </math>
 +
# <math>f(x)=x^3</math> הפיכה וההופכית היא <math>f^{-1}(x) = x^{1/3} </math>
 +
# <math>f(x)=\sin (x)</math> אינה הפיכה כי איננה חח"ע למשל <math>\sin(0) =\sin(2\pi k)</math>
  
−
'''תרגיל מוטיבציה להגדרה לעיל.'''
+
2 תהא <math>A</math> קבוצה <math>f:P(A)\to P(A)</math> המוגדרת:
 +
# <math>f(B)= B^c</math> הפיכה וההופכית היא <math>f^{-1}(B) = B^c </math>
 +
# תהא <math>C\subseteq A</math> תת קבוצה <math>f(B)= B \triangle C</math> הפיכה וההופכית היא <math>f^{-1}(B) = B \triangle C </math>
  
−
המוטיבציה להגדרה הזו היא היכולת לגזור ממנה פונקציה על חבורת המנה. נגדיר יחס על חבורת המנה <math>g=\{([a],[f(a)])|a\in A\}</math>. נוכיח ש-g הינה חד-ערכית ולכן פונקציה.
+
3 תהא <math>A</math> קבוצה ו <math>C\subseteq A</math> תת קבוצה. נגדיר <math>f:P(A)\to \{0,1\}</math> ע"י :
 +
<math>
 +
f(B)=
 +
\begin{cases} 1 & \text{ if } C\subseteq B \\ 0 & \text{ otherwise } \end{cases}
 +
</math>  
  
−
'''הוכחה'''
+
תקיים כי<math>f(C)=f(A) </math> ואם <math>C\neq A</math> אזי הפונקציה אינה חח"ע ובפרט אינה הפיכה
  
−
נניח וקיימים <math>a,b\in A</math> כך ש <math>[a]=[b]</math>. לכן <math>(a,b)\in R</math> ולכן <math>(f(a),f(b))\in R</math> ולכן <math>[f(a)]=[f(b)]</math>. לכן לא ייתכן מצב בו <math>(x,y),(x,z)\in g</math> אבל <math>y\neq z</math>.
+
4. תהא <math>A</math> קבוצה. אזי אפשר (בעזרת חומר שראינו בתירגול על יחסי שקילות)  
 +
להגדיר <math>f:\{R \; | \; R \text{ Equivalence relation }\}\to \{\text{Partitions of }A\}</math> ע"י <math>f(R)=A/R</math> והיא תהיה חח"ע ועל כי ראינו את הפונקציה ההופכית לה
  
 +
5 <math>\{4,5,6\}^{\{1,2,3\}}\to \{4,5,6\}\times \{4,5,6\}\times\{4,5,6\}</math>, המוגדרת <math>f\mapsto (f(1),f(2),f(3))</math> חח"ע ועל.
  
−
'''דוגמא.'''
+
====תרגיל====
−
האם הפונקציה f על הרציונאליים המוגדרת על ידי <math>f(\frac{p}{q})=p</math> מוגדרת היטב?
+
הוכח כי אם <math>g\circ f \circ g =id</math> אז <math>f </math> הפיכה
  
−
'''פתרון.'''
+
הוכחה:
  
−
יש לשים לב שלא באמת הגדרנו את הפונקציה על הרציונאליים, אלא על אוסף הזוגות הסדורים של שלמים <math>(p,q)</math> כך שהאיבר הימני שונה מאפס. נגדיר על קבוצה זו את יחס השקילויות R המוגדר על ידי <math>((p,q),(a,b))\in R</math> אם <math>pb=qa</math>. נראה כי f אינה מוגדרת היטב בתנאים אלו:
+
הרכבה של פונקציה חח"ע <math>(g\circ f) \circ g =id</math> גורר שהשמאלית <math>g</math> חח"ע
  
−
<math>((2,6),(1,3))\in R</math> אולם <math>f(2,6)=(2,1),f(1,3)=(1,1)</math> ו<math>((2,1),(1,1))\notin R</math>.
+
הרכבה של פונקציה על <math>g\circ (f \circ g) =id</math> גורר שהימנית <math>g</math> על
  
−
בכוונה ניסחנו את התרגיל באופן הרומז על יחס השקילויות מבלי לומר אותו במפורש. זו הדרך בה נתקל במושג 'מוגדר היטב' במהלך התואר - יחס השקילויות יהיה מרומז בלבד.
+
ביחד נקבל ש <math>g</math> חח"ע ועל כלומר הפיכה. נכפול ב <math>g^{-1}</math> מימין ומשמאל ונקבל כי <math>f=g^{-1}\circ g^{-1}</math> ואז <math>f</math> הפיכה כהרכבה של הפיכות.

גרסה אחרונה מ־20:19, 21 באוגוסט 2023

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

פונקציות

הגדרה: (אפשר לדלג ולהתמקד בתחום וטווח של פונקציות ולא של יחסיים כללים) יהיו A,B קבוצות וR יחס בינהן. אזי:

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

הערה: ישירות מהגדרה מתקיים כי dom(R)\subseteq A, Im(R)\subseteq B

דוגמא:

  • אם R יחס מלא על A אזי האיחוד של התמונה והתחום שווה A (כי כל שני איברים ניתן להשוות)
  • R=\{(1,a),(2,b),(3,a),(a,1)\} אזי התחום הוא dom(R)=\{a,1,2,3\} והתמונה הינה im(R)=\{1,a,b\}

הגדרה:

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

הגדרה:

יחס חד ערכי ושלם נקרא פונקציה; נסמן במקרה זה (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. נהוג לסמנה: id_A פונקציית הזהות היא חח"ע ועל.

דוגמאות:

  • f:\mathbb{Z}\rightarrow\mathbb{Z} כאשר f(p)=p^2 (אינה חח"ע ואינה על)
  • f:\mathbb{N}\rightarrow\mathbb{Z} כאשר f(p)=p^2 ( חח"ע ואינה על)
  • f:\mathbb{Z}\rightarrow\mathbb{Z} כאשר f(p)=p. זו פונקציית הזהות.
  • f:\mathbb{R}\rightarrow\mathbb{R} כאשר f(x)=x-1 ( חח"ע ו על)
  • f:\mathbb{R}\to\mathbb{R} המוגדרת ע"י הכלל f(x)=\sin(x).
  • f:\mathbb{R}\to\mathbb{R} המוגדרת ע"י הכלל f(x)=x^{3}
  • f:\mathbb{C}\to\mathbb{C} המוגדרת ע"י הכלל f(x)=x^{2}
  • f:\mathbb{N}\rightarrow\mathbb{N} כאשר f(x)=x-1 ( לא מוגדר כי f(1)=?)
  • f:\mathbb{R}\rightarrow\mathbb{Z} כאשר f(x)=[x] מוגדר להיות הערך השלם הקרוב ביותר ל-x (במקרה של חצי לוקחים את הגבוה). זו פונקציה על שאינה חח"ע
  • f:\mathbb{Z}_2\rightarrow\mathbb{Z}_3 כאשר לוקחים את 0 ל0 ואת 1 ל1. זו פונקציה חח"ע שאינה על. (כל פונקציה היא על לתמונה של עצמה.)
  • D:\mathbb{R}\rightarrow\mathbb{R} פונקצית דיריכלה: על כל מספר רציונאלי מקבלת 1 ועל כל מספר אי רציונאלי מקבלת אפס.
  • תהא A קבוצה ו B\subseteq A תת קבוצה. הפונקציה

\chi_B= \begin{cases} 1 & \text{ if } x\in B \\ 0 & \text{ otherwise } \end{cases} פונקצית האינדקטור. במקרה של דריכלה D=\chi_{\mathbb{Q}}

  • תהא f:A\to B אזי g:A\to Im(f) המוגדרת g(a)=f(a) היא על (במילים: פשוט חושבים על הטווח של f להיות התמונה של g)
  • תהא A\subseteq B אזי הפונקציה i : A\to B המוגדרת i(a)=a נקראת פונקציה ההכלה (במקרה ש A=B זה פונקצית הזהות). פונקצית ההכלה היא חח"ע.

תרגיל (בשיעוריי הבית)

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

למשל פונקצית הערך השלם f:\mathbb{R} \to \mathbb{Z} המוגדרת f(x) =\lfloor{x}\rfloor היא על ואינה חח"ע

תרגיל

קבעו האם הפונקציות הבאות חח"ע/על

  • f:\mathbb{R}\to \mathbb{R} המוגדרת f(x)=\lfloor x \rfloor
  • f:\mathbb{N}\times \mathbb{N}\to \mathbb{Z} המוגדרת f(n,m)=n-m
  • תהא A קבוצה, הפונקציה f:A\to P(P(A)) המוגדרת f(x)=\{B\subseteq A \mid x\in B\}

תרגיל

מצאו פונקציה f:\mathbb{N}\to \mathbb{N} על שאינה חח"ע.

תרגיל

תהא A קבוצה ו f:A\to \mathbb{N} פונקציה. נגדיר יחס R על A ע"י aRa'\iff f(a)\leq f(a'). הוכיחו כי R יחס סדר על A אמ"מ f חח"ע.

תרגיל

א. תהא A קבוצה לא ריקה. מצאו פונקציה F:A^A\to A שהיא על.

ב. תהא A קבוצה. מצאו פונקציה F:A\to A^A שהיא חח"ע.

ג. למה בסעיף א צריך לא ריקה ובסעיף ב אפשר גם ריקה?

תרגיל

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

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

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

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


תכונות:

  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

תרגיל

תהא g:\mathbb{N}\to \mathbb{N} פונקציה. נגדיר F:\mathbb{N}^{\mathbb{N}}\to \mathbb{N}^{\mathbb{N}} ע"י F(f)=g\circ f. הוכיחו כי F חח"ע אמ"מ g חח"ע.

פתרון

\Leftarrow: נתון: F חח"ע. נניח g(n)=g(m), לכן עבור הפונקציות הקבועות f\equiv n,f'\equiv m נקבל \forall k:g\circ f(k)=g((n)=g(m)=g\circ f'(k) ולכן F(f)=g\circ f=g\circ f'=F(f'), ומחח"ע של F נקבל f=f' ולכן n=m.

\Rightarrow: נתון g חח"ע. תהיינה f\neq f'\in \mathbb{N}^{\mathbb{N}}, לכן יש n\in \mathbb {N} כך ש- f(n)\neq f'(n), ולכן זה מתקיים גם אחרי ההרכבה, ולכן F(f)\neq F(f').

תרגיל

  • נניח g \circ f חח"ע. הוכח/הפרך: g חח"ע, f חח"ע
  • נניח g \circ f על. הוכח/הפרך: g על, f על
פתרון

נניח g \circ f חח"ע. נניח בשלילה ש-f אינה חח"ע. לכן קיימים x,y כך ש f(x)=f(y) אבל x\neq y. אבל, g\circ f (x) = g(f(x))=g(f(y))=g\circ f(y) בסתירה לחח"ע של ההרכבה, ולכן f חח"ע.

לגבי g ניתן דוגמא נגדית: f(x)=e^x ,g(y)=y^2 ההרכבה היא h(x)=e^{2x}


נניח g \circ f על. נסמן g \circ f : A\rightarrow B אזי לכל איבר b\in B קיים איבר a\in A כך ש g(f(a))=b. לכן עבור g לכל b קיים f(a) שנותן את b תחת g ולכן g על.

דוגמא נגדית ל f: נתבונן בשתי הפונקציות מהטבעיים לעצמם f(n)=n+1; \forall n\not=0 g(n)=n-1 , g(0)=0 ההרכבה היא הזהות

(עוד דוגמא נביט בפונקציות מהטבעיים לטבעיים. f(n)=2n, והפונקציה g מוגדרת כ g(2n)=n ו g(2n+1)=n. ההרכבה הינה פונקצית הזהות שהיא בפרט על, אבל f אינה על כיוון שהאי זוגיים כלל לא נמצאים בתמונה שלה.)

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

הערה: לכל פונקציה f מתקיים f\circ id =f וגם id \circ f =f

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

הערה: זכרו שפונקציה היא יחס. הפונקציה ההופכית שלה היא היחס ההופכי מטבע הדברים. על מנת שהיחס ההופכי יהיה פונקציה הוא צריך להיות ח"ע ושהתחום שלו יהיה כל B. תנאים אלה מתממשים רק אם f הינה חח"ע ועל.

משפט

הוכח כי f הפיכה אם"ם היא חח"ע ועל. כמו כן, הוכח שאם קיימת הופכית אזי היא יחידה.

הוכחה

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

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

יחידות: נניח g,h הופכיות של f אזי h= h\circ I_B=h\circ f \circ g=I_A \circ g=g.

דרך אחרת להוכחת יחידות: נניח בשלילה ש g וh הופכיות שונות של f. מכיוון שהן שונות, הן חייבות להיות שונות על איבר אחד לפחות. כלומר, \exists a\in A:g(a)\neq h(a). אבל f(g(a))=f(h(a)) וזו סתירה לחח"ע של f.

משפט

יהיו 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

הפיכות: נובע מחח"ע+על

מסקנות

  • אם f,g הפיכות אז g\circ f הפיכה.
  • אם g\circ f הפיכה אז f חח"ע, g על (והן לאו דוקא הפיכות).

דוגמאות

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)

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 קבוצה ו C\subseteq A תת קבוצה. נגדיר f:P(A)\to \{0,1\} ע"י : f(B)= \begin{cases} 1 & \text{ if } C\subseteq B \\ 0 & \text{ otherwise } \end{cases}

תקיים כיf(C)=f(A) ואם C\neq A אזי הפונקציה אינה חח"ע ובפרט אינה הפיכה

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

5 \{4,5,6\}^{\{1,2,3\}}\to \{4,5,6\}\times \{4,5,6\}\times\{4,5,6\}, המוגדרת f\mapsto (f(1),f(2),f(3)) חח"ע ועל.

תרגיל

הוכח כי אם g\circ f \circ g =id אז f הפיכה

הוכחה:

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

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

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

מקור: https://math-wiki.com/index.php?title=88-195_בדידה_לתיכוניסטים_תשעא/מערך_שיעור/שיעור_4&oldid=89820