שינויים
/* הרכבת פונקציות */
'''[[מתמטיקה בדידה - מערך תרגול|חזרה למערכי התרגול]]'''
==פונקציות==
'''הגדרה:''' (אפשר לדלג ולהתמקד בתחום וטווח של פונקציות ולא של יחסיים כללים) יהיו 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{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 </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 פחות אחד בסתירה.
==== תרגיל====
קבעו האם הפונקציות הבאות חח"ע/על
* <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>A</math> קבוצה. מצאו פונקציה <math>F:A\to A^A</math> שהיא חח"ע.
הוכיחו שאם <math>f</math> על, אז <math>g</math> לא חח"ע.
==הרכבת פונקציות== '''הגדרה:''' פונקצית הזהות על יהיו <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>היא '''הפיכה'''.
הערה: זכרו שפונקציה היא יחס. הפונקציה ההופכית שלה היא היחס ההופכי מטבע הדברים. על מנת שהיחס ההופכי יהיה פונקציה הוא צריך להיות ח"ע ושהתחום שלו יהיה כל B. תנאים אלה מתממשים רק אם f הינה חח"ע ועל.
הוכח כי f הפיכה אם"ם היא חח"ע ועל. כמו כן, הוכח שאם קיימת הופכית אזי היא יחידה.
אם f הפיכה, אזי <math>f\circ f^{-1} = id_B</math> וגם <math>f^{-1}\circ f = id_A</math>. מכיוון שהזהות הינה חח"ע ועל, אז היחס ההופכי שלה חנובע ש-f חח"ע ומוגדר והוא מהווה פונקציה הופכית. (אמנם החסרנו את רוב ההוכחה, אך היא פשוטה למדיועל לפי התרגיל הקודם בדבר הרכבת פונקציות.)
יחידות: נניח g,h הופכיות של f אזי <math>h= h\circ I_B=h\circ f \circ g=I_A \circ g=g</math>.
=====הוכחה=====
* אם <math>f,g</math> הפיכות אז <math>g\circ f</math> הפיכה.
תקיים כי<math>f(C)=f(A) </math> ואם <math>C\neq A</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> גורר שהימנית <math>g</math> על