שינויים

'''הגדרה:''' (אפשר לדלג ולהתמקד בתחום וטווח של פונקציות ולא של יחסיים כללים) יהיו 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 קבוצה. '''תרגיל.פונקציית הזהות'''יהיו היא פונקציה <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 </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 \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 הינה פונקציה מ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>.

אם f הפיכה, אזי <math>f\circ f^{-1} = id_B</math> וגם <math>f^{-1}\circ f = id_A</math>. מכיוון שהזהות הינה חח"ע ועל, נובע ש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>\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</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 כך שהפיכה, אזי <math>f\circ f^{-g 1} = id_B</math> וגם <math>f^{-1}\circ f = id_A</math>. מכיוון שהזהות הינה חח"ע. כפי שראינו לעילועל, ניתן ישר להסיק נובע ש-f הינה עלחח"ע ועל לפי התרגיל הקודם בדבר הרכבת פונקציות.

נוכיח שאם f על אזי יחידות: נניח g חח"ע; נניח בשלילה שg אינה חח"ע, h הופכיות של f אזי קיימות שתי קבוצות <math>Bh= h\neq C \in P(Y)</math> כך ש <math>g(B)circ I_B=g(C)</math>. בלי הגבלת הכלליות, נניח שקיים איבר <math>ch\in C</math> כך ש <math>ccirc f \notin B</math>. מכיוון ש-f על, קיים איבר a כך ש <math>f(a)circ g=c</math>, לכן <math>aI_A \in circ g(B)</math>, ואז קיים <math>b\in B</math> כך ש<math>f(a)=bg</math> ולכן b=c בסתירה.

*אם כן====משפט====יהיו <math>f_1, הוכחנו ש-'''f על אם"ם g \dots f_k:A\to A</math> הפיכות/חח"ע/על.'''הוכח שההרכבה <math>f_k \circ \dots \circ f_1</math> הפיכה/חח"ע/על

יהיו חח"ע: נניח <math>X=(f_k \mathbb{Z}, Ycirc \dots \circ f_1)(x_1) =(f_k \{0circ \}dots \circ f_1)(x_2)</math>. אזי קיימת פונקציה f יחידה מX לY. פונקציה זו אינה חחמח"ע כמובן, אך g כן חח"ע שכן של <math>f_k</math> נקבל כי <math>g(\f_{\k-1})\neq g(circ \{0dots \circ f_1)(x_1) =(f_{k-1}\circ \dots \circ f_1)(x_2)</math> ואלה הקבוצות היחידות בקבוצת החזקה של Y. באופן דומה נמשיך (או באינדוקציה) ונקבל <math>x_1=x_2</math>

*לכן '''יתכן ו-g חחהפיכות: נובע מחח"ע אך f אינה כזו'''.+על

נניח וg על ונניח בשלילה ש-f אינה חח"ע. לכן קיימים * אם <math>af,b \in Xg</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>circ f(y)\in B</math> ולכן <math>y\in g(B)=A</math> בסתירה. לכן f חח"עהפיכה.

נניח ==== דוגמאות ==== 1. <math>f חח"ע, הוכחנו כבר שבהכרח :\mathbb{R} \to \mathbb{R}</math> המוגדרת:# <math>f(x)=x+1</math> הפיכה וההופכית היא <math>f^{-1}(x) = x-1 </math># <math>f(A)x)=Ax^3</math> לכל A תת קבוצה של X. נובע ש הפיכה וההופכית היא <math>gf^{-1}(x) = x^{1/3} </math># <math>f(Ax)=\sin (x)</math> אינה הפיכה כי איננה חח"ע למשל <math>\sin(0)=A\sin(2\pi k)</math> ולכן g הינה על.

*סה"כ3 תהא <math>A</math> קבוצה ו <math>C\subseteq A</math> תת קבוצה. נגדיר <math>f:P(A)\to \{0, הוכחנו ש'''f חח"1\}</math> ע אם"ם g הינה על'''.י :<math>f(B)= \begin{cases} 1 & \text{ if } C\subseteq B \\ 0 & \text{ otherwise } \end{cases}</math>

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

*לכן '''ייתכן ו-====תרגיל====הוכח כי אם <math>g הינה על אך \circ f אינה על'''\circ g =id</math> אז <math>f </math> הפיכה

באופן דומה ניקח f על שאינה הרכבה של פונקציה חח"ע, לכן <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> הפיכה כהרכבה של הפיכות.