שינויים

'''הגדרה:''' (אפשר לדלג ולהתמקד בתחום וטווח של פונקציות ולא של יחסיים כללים) יהיו 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</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 \to A</math> המקיימת <math>\forall a\in A: f(a)=a</math>. נהוג לסמנה: <math>id_A</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>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> זה פונקצית הזהות). פונקצית ההכלה היא חח"ע.

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

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

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

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

'''פתרוןהערה: הדבר אינו נכון אם A וB קבוצות אינסופיות.'''לא. דוגמא: פונקצית הערך השלם על ואינה חח"ע

'''תרגיל.'''*נניח למשל פונקצית הערך השלם <math>f :\mathbb{R} \circ gto \mathbb{Z} </math> חח"ע. הוכח/הפרך: f חח"ע, g חח"ע *נניח המוגדרת <math>f (x) =\circ glfloor{x}\rfloor</math> היא על. הוכח/הפרך: f על, g עלואינה חח"ע

'''פתרון==== תרגיל====מצאו פונקציה <math>f:\mathbb{N}\to \mathbb{N}</math> על שאינה חח"ע.'''

נניח ==== תרגיל ====תהא A קבוצה ו <math>f :A\circ gto \mathbb{N}</math> חח"פונקציה. נגדיר יחס R על A ע. נניח בשלילה ש-g אינה חח"ע. לכן קיימים י <math>x,y</math> כך ש <math>gaRa'\iff f(xa)=g\leq f(ya')</math> אבל <math>x\neq y</math>. אבל, הוכיחו כי R יחס סדר על A אמ"מ <math>f\circ g (x) = f(g(x))=f(g(y))=f\circ g(y)</math> בסתירה לחח"ע של ההרכבה, ולכן g חח"ע.

לגבי f ניתן דוגמא נגדית: ==== תרגיל ====א. תהא A קבוצה לא ריקה. מצאו פונקציה <math>(e^x)F:A^2A\to A</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 עלג. למה בסעיף א צריך לא ריקה ובסעיף ב אפשר גם ריקה?

דוגמא נגדית ל g: נביט בפונקציות מהטבעיים לטבעיים. ==== תרגיל ====תהיינה <math>f,g(n)=2n:\mathbb{N}\rightarrow \mathbb{N}</math>, והפונקציה f מוגדרת כ פונקציות כך ש-<math>f(2nn)=n</math> ו <math>fg(2n+3n-1)=n</math>. ההרכבה הינה פונקצית הזהות שהיא בפרט על, אבל g אינה על כיוון שהאי זוגיים כלל לא נמצאים בתמונה שלה.

==הרכבת פונקציות==  '''הגדרה:''' פונקצית הזהות על יהיו <math>f:A הינה \to B, g:B\to C </math> שתי פונקציות אז '''ההרכבה של <math>g</math> על <math>f</math>''' היא פונקציה מA לעצמו השולחת כל איבר לעצמו <math>g \circ f:A\to C </math> המוגדרת על ידי הכלל <math>g \circ f(a)=g(f(a)) </math>  תכונות:# הרכבה היא קיבוצית. נהוג לסמנה בכלומר <math>id_Af_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>g:A\rightarrow Bmathbb{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}^{-1\mathbb{N}}</math>, לכן יש <math>n\in \mathbb {N}</math> כך ש- <math>f(n)\neq f'(n)</math>, ולכן זה מתקיים גם אחרי ההרכבה, ולכן <math>F(f)\neq F(f')</math>. ====תרגיל====*נניח <math>g \circ f</math> חח"ע. הוכח/הפרך:Bg חח"ע, f חח"ע *נניח <math>g \rightarrow Acirc f</math> על. הוכח/הפרך: g על, f על =====פתרון===== נניח <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>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 על.  דוגמא נגדית ל 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}\circ </math>, ונאמר שהפונקציה <math>f = id_A</math>היא '''הפיכה'''.

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

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

נניח בשלילה ש g וh הופכיות שונות של אם f. מכיוון שהן שונות, הן חייבות להיות שונות על איבר אחד לפחות. כלומרחח"ע ועל, אז נגדיר <math>g:B\exists to A</math> ע"י: עבור <math>a\in A:g</math> קיים (aכי f על)יחיד (כי f חח"ע) <math>b\neq hin B</math> כך ש <math>f(a)=b</math>. אבל נגדיר <math>f(g(a)b):=f(h(a))</math> וזו סתירה לחח"ע . תרגיל: בדקו ש g ההופכית של f.

'''הגדרהדרך אחרת להוכחת יחידות: נניח בשלילה ש g וh הופכיות שונות של f.''' תהי <math>f:X\rightarrow Y</math> פונקציהמכיוון שהן שונות, הן חייבות להיות שונות על איבר אחד לפחות. כלומר, ויהיו תת קבוצות <math>A\subseteq X,Bexists a\subseteq Y</math>. אזי <math>fin A:g(Aa)=\{fneq h(a)|a\in A\}</math>, . אבל <math>f^{-1}(Bg(a))=\{a\in A|f(h(a)\in B\})</math>וזו סתירה לחח"ע של f.

שימו לב שהסימון ====משפט====יהיו <math>f^{-1}(B)f_1,\dots f_k:A\to A</math> אינו רומז בשום צורה שהפונקציה צריכה להיות הפיכה, הגדרה זו תקפה לכל פונקציההפיכות/חח"ע/על.הוכח שההרכבה <math>f_k \circ \dots \circ f_1</math> הפיכה/חח"ע/על

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

נניח ו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> הפיכה אז <math>f</math> חח"ע, <math>g</math> על (קצת משודרגוהן לאו דוקא הפיכות).'''

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

תהי f חח"ע שאינה על (קל למצוא כאלה). אזי 3 תהא <math>A</math> קבוצה ו <math>C\exists y\in Y\forall x\in X:f(x)\neq ysubseteq A</math>תת קבוצה. לכן נגדיר <math>gf:P(YA)=f^\to \{-0,1\}</math> ע"י :<math>f(YB)=f^\begin{-cases} 1& \text{ if }(Y/C\subseteq B \\ 0 & \text{y\otherwise }=g(Y/\end{y\cases})</math> בסתירה לחח"ע של g. לכן '''ייתכן ו-f חח"ע אך g אינה כזו'''.

תהי 4. תהא <math>A</math> קבוצה. אזי אפשר (בעזרת חומר שראינו בתירגול על יחסי שקילות) להגדיר <math>f:\{R \; | \; R \text{ Equivalence relation }\}\to \{\text{Partitions of }A\}</math> ע"י <math>f כך ש-g (R)=A/R</math> והיא תהיה חח"ע. כפי שראינו לעיל, ניתן ישר להסיק ש-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>. מכיוון ש-circ f על, קיים איבר a כך ש <math>f(a)=c</math>, לכן <math>a\in circ g(B)=id</math>, ואז קיים <math>b\in B</math> כך שאז <math>f(a)=b</math> ולכן b=c בסתירה.הפיכה

אם כן, הוכחנו ש-'''f על אםהרכבה של פונקציה חח"ם ע <math>(g\circ f) \circ g =id</math> גורר שהשמאלית <math>g </math> חח"ע.'''

יהיו ביחד נקבל ש <math>X=\mathbb{Z}, Y=\{0\}g</math>. אזי קיימת פונקציה f יחידה מX לY. פונקציה זו אינה חח"ע כמובן, אך ועל כלומר הפיכה. נכפול ב <math>g כן חח"ע שכן ^{-1}</math>מימין ומשמאל ונקבל כי <math>f=g(\^{\-1})\neq circ g(\^{0\-1})</math> ואלה הקבוצות היחידות בקבוצת החזקה ואז <math>f</math> הפיכה כהרכבה של Y. לכן '''יתכן ו-g חח"ע אך f אינה כזו'''הפיכות.