שינויים

קפיצה אל: ניווט, חיפוש

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

נוספו 2,289 בתים, 20:19, 21 באוגוסט 2023
/* הרכבת פונקציות */
'''[[מתמטיקה בדידה - מערך תרגול|חזרה למערכי התרגול]]'''
 
==פונקציות==
'''הגדרה:''' (אפשר לדלג ולהתמקד בתחום וטווח של פונקציות ולא של יחסיים כללים) יהיו A,B קבוצות וR יחס בינהן. אזי:*התחום של 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\}=\{(\;,*),(\; ,*)\dots \}</math> '''הערה''': ישירות מהגדרה מתקיים כי <math>dom(R)\subseteq A, Im(R)\subseteq B</math>
'''דוגמא.:'''*אם R יחס מלא על A אזי האיחוד של התמונה והתחום שווה A(כי כל שני איברים ניתן להשוות)*<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 מ-A ל-B נקרא '''חד ערכיעל''' אם <math>[\forall b\in B \exists a\in A:(xa,b)\in R] </math> כלומר <math>im(R)=B</math>*יחס R מ-A ל-B נקרא '''שלם''' אם <math>\and [forall a\in A \exists b\in B:(xa,db) \in R] \rightarrow </math> כלומר <math>dom(d=bR)=A</math>*יחס R נקרא '''חד-חד ערכי''' אם <math>[(x,b)\in R] \and [(yx,bd) \in R] \rightarrow (xd=yb)</math> (כלומר, היחס ההופכי הינו חד ערכי)אין איבר שנשלח ל-2 מקומות שונים*יחס R נקרא '''עלחד-חד ערכי''' אם <math>\forall [(x,b)\in B:R] \exists a\in A:and [(ay,b)\in R] \rightarrow (x=y)</math> כלומר <math>imאיברים שונים נשלחים למקומות שונים (Rכלומר, היחס ההופכי הינו חד ערכי)=B</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 ועל כל מספר אי רציונאלי מקבלת אפס.
'''תרגיל.'''יהיו A וB קבוצות סופיות בעלות עוצמה זהה. הוכח שכל פונקציה מA לB הינה על אם"ם היא <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 מספר הזוגות הוא בדיוק מספר האיברים בA (מתוך חד ערכיות והעובדה שזה תחום). לכל איבר בA קיים זוג יחיד בפונקציה. אם היה זוג שהיה מקבל את אותו איבר בB זו הייתה סתירה לח"ע ולכן מספר האיברים מB שמופיעים בזוגות הוא כמספר האיברים בA. מכיוון שעוצמת הקבוצות זהה, כל האיברים מB מופיעים בזוג ולכן הפונקציה על.
נניח שהפונקציה על. אם היא לא הייתה חח"ע היה איבר בB שחוזר על עצמו בזוגות לעיל ולכן מספר האיברים המופיע בB היה לכל היותר מספר האיברים בA פחות אחד בסתירה.'''הגדרה:'''
תהא A קבוצה. '''תרגיל.פונקציית הזהות'''יהיו היא פונקציה <math>f:A וB קבוצות אינסופיות\to A</math> המקיימת <math>\forall a\in A: f(a)=a</math>. האם כל פונקציה בינהן היא על אם"ם נהוג לסמנה: <math>id_A</math> פונקציית הזהות היא חח"ע?ועל.
'''פתרון===דוגמאות:===*<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> חח"עיהיו A ו-B קבוצות סופיות בעלות עוצמה זהה. הוכח/הפרך: f חחשכל פונקציה מ-A ל-B הינה על אם"ע, g ם היא חח"ע *נניח <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,yf </math> כך ש אינה חח"ע אזי <math>g|\{f(xa_1)=g,\dots f(ya_n)\}|</math> אבל <math>x\neq yn</math>. אבל, (כי יש שני איברים שנשלחים לאותו מקום)ואז <math>f\circ g (x) = f(g(x))=f(g(y))=f\circ g(y)</math> בסתירה לחח"ע של ההרכבה, ולכן g חח"עאינה על -סתירה.
לגבי 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 :\mathbb{R}\to \circ gmathbb{R}</math> על. נסמן המוגדרת <math>f (x)=\circ g : Alfloor x \rightarrow Brfloor</math> אזי לכל איבר * <math>bf:\in Bmathbb{N}\times \mathbb{N}\to \mathbb{Z}</math> קיים איבר המוגדרת <math>a\in Af(n,m)=n-m</math> כך ש *תהא A קבוצה, הפונקציה <math>f:A\to P(gP(aA))=b</math>. לכן עבור f לכל b קיים המוגדרת <math>gf(ax)=\{B\subseteq A \mid x\in B\}</math> שנותן את b תחת f ולכן f על.
דוגמא נגדית ל g: נביט בפונקציות מהטבעיים לטבעיים. <math>g(n)=2n</math>, והפונקציה f מוגדרת כ <math>f(2n)=n</math> ו == תרגיל====מצאו פונקציה <math>f(2n+1)=n:\mathbb{N}\to \mathbb{N}</math>. ההרכבה הינה פונקצית הזהות שהיא בפרט על, אבל g אינה על כיוון שהאי זוגיים כלל לא נמצאים בתמונה שלהשאינה חח"ע.
==== תרגיל ====
תהא 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>fF:A\rightarrow B</math> נקראת הפיכה אם קיימת לה הופכית - פונקציה <math>f^{-1}:BA\rightarrow to A</math> כך שמתקיים <math>f\circ f^{-1} = id_B</math> וגם <math>f^{-1}\circ f = id_A</math>שהיא על.
הערה: זכרו שפונקציה היא יחסב. הפונקציה ההופכית שלה היא היחס ההופכי מטבע הדבריםתהא <math>A</math> קבוצה. על מנת שהיחס ההופכי יהיה מצאו פונקציה הוא צריך להיות ח"ע ושהתחום שלו יהיה כל B. תנאים אלה מתממשים רק אם f הינה <math>F:A\to A^A</math> שהיא חח"ע ועל.
'''תרגילג.'''למה בסעיף א צריך לא ריקה ובסעיף ב אפשר גם ריקה?
הוכח כי ==== תרגיל ====תהיינה <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 הופכיות שונות של '''הגדרה:'''יהיו <math>f. מכיוון שהן שונות:A\to B, הן חייבות להיות שונות g:B\to C </math> שתי פונקציות אז '''ההרכבה של <math>g</math> על איבר אחד לפחות. כלומר, <math>f</math>''' היא פונקציה <math>g \exists a\in Acirc f:g(a)A\neq h(a)to C </math>. אבל המוגדרת על ידי הכלל <math>g \circ f(g(a))=fg(hf(a))</math> וזו סתירה לחח"ע של f.
'''הגדרהתכונות:# הרכבה היא קיבוצית.''' תהי כלומר <math>f:Xf_3 \rightarrow Ycirc (f_2 \circ f_1) = (f_3 \circ f_2) \circ f_1 </math> פונקציה, ויהיו תת קבוצות # הרכבה '''אינה''' (בהכרח) חילופית כלומר לא מתקיים בהכרח כי <math>Af_2 \subseteq X,Bcirc f_1 = f_2 \subseteq Ycirc f_1 </math>. אזי למשל <math>f(Ax)=\{fx^2 , g(ax)|a\in A\}= x+1</math>, אזי <math>f^{-1}(Bg(2))=\{a\in A|f(a3)=9, g(f(2))=g(4)=5</math> ולכן <math>f\in Bcirc g \}neq g \circ f</math>.
שימו לב שהסימון ==== תרגיל ====תהא <math>fg:\mathbb{N}\to \mathbb{N}</math> פונקציה. נגדיר <math>F:\mathbb{N}^{-1\mathbb{N}}\to \mathbb{N}^{\mathbb{N}}</math> ע"י <math>F(Bf)=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(An)\cap neq f'(Bn)=f</math>, ולכן זה מתקיים גם אחרי ההרכבה, ולכן <math>F(Af)\cap Bneq F(f')</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)g \cap circ f</math> חח"ע. נניח בשלילה ש-f אינה חח"ע. לכן קיימים <math>x,y</math> כך ש <math>f(Bx) = \{f(xy)\} </math> אבל <math>x\neq y</math>. אבל, <math>g\phi circ f (x) = g(f(\{\}x)) = g(f(Ay))=g\cap Bcirc f(y)</math>בסתירה לחח"ע של ההרכבה, ולכן f חח"ע.
'''תרגיל.'''תהי לגבי g ניתן דוגמא נגדית: <math>f:X\rightarrow Y</math> חח"ע(x)=e^x , ותהי <math>A\subseteq Xg(y)=y^2</math>. הוכח ההרכבה היא <math>fh(x)=e^{-12x}(f(A))=A</math>.
'''פתרון.'''
ישירות מההגדרות נובע שאם נניח <math>ag \in circ f</math> על. נסמן <math>g \circ f : A\rightarrow B</math> אזי לכל איבר <math>f(a)b\in f(A)B</math> ולכן קיים איבר <math>a\in f^{-1}A</math> כך ש <math>g(f(Aa))=b</math>. סה"כ הראנו לכן עבור g לכל b קיים <math>A\subseteq f^{-1}(f(A)a)</math>שנותן את b תחת g ולכן g על. (עד כה זה נכון לכל העתקה, לאו דווקא חח"ע.)
נניח כעת בשלילה ש דוגמא נגדית ל f: נתבונן בשתי הפונקציות מהטבעיים לעצמם<math>f^{-1}(f(An))\neq A</math> לכן קיים <math>x\in f^{-=n+1}(f(A))</math> כך ש ; <math>x\notin A</math>. לכן לפי ההגדרה, <math>f(x)forall n\in fnot=0 g(An)</math>. לכן קיים a בA כך ש <math>f=n-1 , g(a0)=f(x)0</math>. מתוך החח"ע נובע ש-x=a בסתירה.ההרכבה היא הזהות
(עוד דוגמא נביט בפונקציות מהטבעיים לטבעיים. <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>.בדוק את הקשר בין החחהינה חח/על של 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 חח"ע אך 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 על שאינה הפיכה, אזי <math>f\circ f^{-1} = id_B</math> וגם <math>f^{-1}\circ f = id_A</math>. מכיוון שהזהות הינה חח"עועל, לכן g אינה עלנובע ש-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.
*לכן '''ייתכן ו-יחידות: נניח 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:(f_k \mathbb{R}circ \rightarrowdots \mathbb{R}circ f_1)(x_1) =(f_k \circ \dots \circ f_1)(x_2)</math> המוגדרת על ידי אזי מח"ע של <math>f(x)=x^2f_k</math> ואינה חח"ע. נכון לומר שהפונקציה המצומצמת נקבל כי <math>f|_(f_{k-1} \mathbbcirc \dots \circ f_1)(x_1) =(f_{N}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}(,g</math> הפיכות אז <math>g\{y\})|y\in Y\})circ f</math> ונרצה לבחור איבר יחיד מבין כל קבוצה כזו. אקסיומת הבחירה היא זו המאפשרת לנו לבצע בחירה זו בשלוםהפיכה.)
* אם <math>g\circ f</math> הפיכה אז <math>f</math> חח"ע, <math>g</math> על (והן לאו דוקא הפיכות).
'''הגדרה==== דוגמאות ==== 1.''' תהי <math>f:A\rightarrow Amathbb{R} \to \mathbb{R}</math>, ויהי R יחס שקילויות על A. אומרים כי '''f מוגדרת היטב על המוגדרת:# <math>A/Rf(x)=x+1</math>''' אם הפיכה וההופכית היא <math>\forall a,b\in A:f^{-1}(a,bx)\in R\rightarrow = x-1 </math># <math>f(x)=x^3</math> הפיכה וההופכית היא <math>f^{-1}(ax),= x^{1/3} </math># <math>f(bx)=\in Rsin (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>
המוטיבציה להגדרה הזו היא היכולת לגזור ממנה פונקציה על חבורת המנה3 תהא <math>A</math> קבוצה ו <math>C\subseteq A</math> תת קבוצה. נגדיר יחס על חבורת המנה <math>g=f:P(A)\to \{([a]0,[1\}</math> ע"י :<math>f(aB)])|a= \in Abegin{cases} 1 & \text{ if }C\subseteq B \\ 0 & \text{ otherwise } \end{cases}</math>. נוכיח ש-g הינה חד-ערכית ולכן פונקציה.
'''הוכחה'''תקיים כי<math>f(C)=f(A) </math> ואם <math>C\neq A</math> אזי הפונקציה אינה חח"ע ובפרט אינה הפיכה
נניח וקיימים 4. תהא <math>a,b\in A</math> כך ש <math>[a]=[b]</math>קבוצה. לכן <math>אזי אפשר (a,bבעזרת חומר שראינו בתירגול על יחסי שקילות)\in Rלהגדיר </math> ולכן <math>(f(a),f(b)):\in {R\; | \; R \text{ Equivalence relation }\}\to \{\text{Partitions of }A\}</math> ולכן ע"י <math>[f(aR)]=[f(b)]<A/math>. לכן לא ייתכן מצב בו <math>(x,y),(x,z)\in gR</math> אבל <math>y\neq z</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>g\circ f(\frac{p}{q})circ g =pid</math> אז <math>f </math> מוגדרת היטב?הפיכה
'''פתרון.'''הוכחה:
יש לשים לב שלא באמת הגדרנו את הפונקציה על הרציונאליים, אלא על אוסף הזוגות הסדורים הרכבה של שלמים פונקציה חח"ע <math>(p,q)</math> כך שהאיבר הימני שונה מאפס. נגדיר על קבוצה זו את יחס השקילויות R המוגדר על ידי <math>((p,q),(a,b)g\circ f)\in Rcirc g =id</math> אם גורר שהשמאלית <math>pb=qag</math>. נראה כי f אינה מוגדרת היטב בתנאים אלו:חח"ע
הרכבה של פונקציה על <math>((2,6),(1,3))g\in R</math> אולם <math>fcirc (2,6)=(2,1),f(1,3\circ g)=(1,1)id</math> וגורר שהימנית <math>((2,1),(1,1))\notin Rg</math>.על
בכוונה ניסחנו את התרגיל באופן הרומז על יחס השקילויות מבלי לומר אותו במפורשביחד נקבל ש <math>g</math> חח"ע ועל כלומר הפיכה. זו הדרך בה נתקל במושג 'מוגדר היטב' במהלך התואר נכפול ב <math>g^{- יחס השקילויות יהיה מרומז בלבד1}</math> מימין ומשמאל ונקבל כי <math>f=g^{-1}\circ g^{-1}</math> ואז <math>f</math> הפיכה כהרכבה של הפיכות.
2
עריכות