שינויים

'''הגדרה:''' (אפשר לדלג ולהתמקד בתחום וטווח של פונקציות ולא של יחסיים כללים) יהיו 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 קבוצות סופיות בעלות עוצמה זהה. הוכח שכל פונקציה מ-A ל-B הינה על אם"ם היא חח"ע =====הוכחה=====נסמן <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 </math> על. נניח בשלילה ש <math>f </math> אינה חח"ע אזי <math>|\{f(a_1),\dots f(a_n)\}|<n</math> (כי יש שני איברים שנשלחים לאותו מקום)ואז <math>f </math> אינה על -סתירה.  הערה: הדבר אינו נכון אם A וB קבוצות אינסופיות. למשל פונקצית הערך השלם <math>f:\mathbb{R} \to \mathbb{Z} </math> המוגדרת <math>f(x) =\lfloor{x}\rfloor</math> היא על ואינה חח"ע ==== תרגיל====קבעו האם הפונקציות הבאות חח"ע/על* <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> ==== תרגיל====מצאו פונקציה <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 קבוצה לא ריקה. מצאו פונקציה <math>F:A^A\to A</math> שהיא על. ב. תהא <math>A</math> קבוצה. מצאו פונקציה <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> לא חח"ע. ==הרכבת פונקציות==  '''הגדרה:'''יהיו <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_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:\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>g \circ f</math> חח"ע. הוכח/הפרך: g חח"ע, f חח"ע *נניח <math>g \circ 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}</math>, ונאמר שהפונקציה <math>f</math> היא '''הפיכה'''. הערה: זכרו שפונקציה היא יחס. הפונקציה ההופכית שלה היא היחס ההופכי מטבע הדברים. על מנת שהיחס ההופכי יהיה פונקציה הוא צריך להיות ח"ע ושהתחום שלו יהיה כל B. תנאים אלה מתממשים רק אם f הינה חח"ע ועל. ====משפט==== הוכח כי f הפיכה אם"ם היא חח"ע ועל. כמו כן, הוכח שאם קיימת הופכית אזי היא יחידה. =====הוכחה===== אם 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. יחידות: נניח 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_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>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,g</math> הפיכות אז <math>g\circ f</math> הפיכה. * אם <math>g\circ f</math> הפיכה אז <math>f</math> חח"ע, <math>g</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 וB קבוצות סופיות בעלות עוצמה זהה. הוכח שכל פונקציה מA לB הינה על אם"ם </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>f:P(A)\to \{0,1\}</math> ע"י :נניח שהפונקציה חח"ע. נזכר שפונקציה הינה יחס, ונספור את הזוגות הסדורים שהיא מכילה; מכיוון שהתחום של הפונקציה הוא A מספר הזוגות הוא בדיוק מספר האיברים בA <math>f(מתוך חד ערכיות והעובדה שזה תחוםB). לכל איבר בA קיים זוג יחיד בפונקציה. אם היה זוג שהיה מקבל את אותו איבר בB זו הייתה סתירה לח"ע ולכן מספר האיברים מB שמופיעים בזוגות הוא כמספר האיברים בA. מכיוון שעוצמת הקבוצות זהה, כל האיברים מ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> אזי הפונקציה אינה חח"ע היה איבר בB שחוזר על עצמו בזוגות לעיל ולכן מספר האיברים המופיע בB היה לכל היותר מספר האיברים בA פחות אחד בסתירה.ובפרט אינה הפיכה

'''תרגיל4.'''יהיו תהא <math>A וB קבוצות אינסופיות</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> חח"עועל.

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

נניח הרכבה של פונקציה על <math>f g\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)id</math> בסתירה לחח"ע של ההרכבה, ולכן g חח"ע. לגבי f ניתן דוגמא נגדית: גורר שהימנית <math>(e^x)^2g</math>על

נניח ביחד נקבל ש <math>f \circ g</math> עלחח"ע ועל כלומר הפיכה. נסמן נכפול ב <math>f \circ g : A\rightarrow B^{-1}</math> אזי לכל איבר מימין ומשמאל ונקבל כי <math>bf=g^{-1}\in Bcirc g^{-1}</math> קיים איבר <math>a\in A</math> כך ש ואז <math>f(g(a))=b</math>הפיכה כהרכבה של הפיכות. לכן עבור f לכל b קיים <math>g(a)</math> שנותן את b תחת f ולכן f על. דוגמא נגדית ל g: נביט בפונקציה