תרגול 6 מדמח קיץ תשעז

פונקציות

הגדרה: יהיו A,B קבוצות וR יחס בינהן. אזי:

• התחום של R הינו [math]\displaystyle{ Dom(R)=\{a\in A|\exists b\in B:(a,b)\in R\}=\{(*,\;),(*,\;)\dots \} }[/math]
• התמונה של R הינה [math]\displaystyle{ Im(R)=\{b\in B|\exists a\in A:(a,b)\in R\}=\{(\;,*),(\; ,*)\dots \} }[/math]

הערה: ישירות מהגדרה מתקיים כי [math]\displaystyle{ Dom(R)\subseteq A, Im(R)\subseteq B }[/math]

דוגמא:

• אם R יחס מלא על A אזי האיחוד של התמונה והתחום שווה A (כי כל שני איברים ניתן להשוות)
• [math]\displaystyle{ R=\{(1,a),(2,b),(3,a),(a,1)\} }[/math] אזי התחום הוא [math]\displaystyle{ Dom(R)=\{a,1,2,3\} }[/math] והתמונה הינה [math]\displaystyle{ Im(R)=\{1,a,b\} }[/math]

הגדרה:

• יחס R מ-A ל-B נקרא שלם אם [math]\displaystyle{ \forall a\in A \exists b\in B:(a,b)\in R }[/math] כלומר [math]\displaystyle{ dom(R)=A }[/math]
• יחס R נקרא חד ערכי אם [math]\displaystyle{ [(x,b)\in R] \and [(x,d) \in R] \rightarrow (d=b) }[/math] כלומר אין איבר שנשלח ל-2 מקומות שונים

הגדרה:

יחס חד ערכי ושלם נקרא פונקציה; נסמן במקרה זה [math]\displaystyle{ (a,b)\in R\leftrightarrow b=R(a) }[/math]. ובאופן כללי [math]\displaystyle{ f:A\to B \;\; , a \mapsto f(a) }[/math]. (A נקרא תחום (הגדרה) של הפונקציה. ו B נקרא הטווח של הפונקציה)

הגדרת חח"ע עבור פונקציה:

[math]\displaystyle{ f }[/math] חח"ע אמ"מ [math]\displaystyle{ f(x_1)=f(x_2)\Rightarrow x_1=x_2 }[/math] אמ"מ [math]\displaystyle{ x_1\neq x_2 \Rightarrow f(x_1)\neq f(x_2) }[/math]

בנוסף, פונקציה [math]\displaystyle{ f:A\rightarrow B }[/math] נקראת "על" אם [math]\displaystyle{ Im(f)=B }[/math].

הגדרה:

תהא A קבוצה. פונקציית הזהות היא פונקציה [math]\displaystyle{ f:A \to A }[/math] המקיימת [math]\displaystyle{ \forall a\in A: f(a)=a }[/math]. נהוג לסמנה: [math]\displaystyle{ id_A }[/math] פונקציית הזהות היא חח"ע ועל.

דוגמאות:

• [math]\displaystyle{ f:\mathbb{Z}\rightarrow\mathbb{Z} }[/math] כאשר [math]\displaystyle{ f(p)=p^2 }[/math] (אינה חח"ע ואינה על)
• [math]\displaystyle{ f:\mathbb{N}\rightarrow\mathbb{Z} }[/math] כאשר [math]\displaystyle{ f(p)=p^2 }[/math] ( חח"ע ואינה על)
• [math]\displaystyle{ f:\mathbb{Z}\rightarrow\mathbb{Z} }[/math] כאשר [math]\displaystyle{ f(p)=p }[/math]. זו פונקציית הזהות.
• [math]\displaystyle{ f:\mathbb{R}\rightarrow\mathbb{R} }[/math] כאשר [math]\displaystyle{ f(x)=x-1 }[/math] ( חח"ע ו על)
• [math]\displaystyle{ f:\mathbb{N}\rightarrow\mathbb{N} }[/math] כאשר [math]\displaystyle{ f(x)=x-1 }[/math] ( לא מוגדר כי [math]\displaystyle{ f(1)=? }[/math])
• [math]\displaystyle{ f:\mathbb{N}\rightarrow\mathbb{N} \cup \{ 0\} }[/math] כאשר [math]\displaystyle{ f(x)=x-1 }[/math] (חח"ע ועל)
• [math]\displaystyle{ f:\mathbb{R}\rightarrow\mathbb{Z} }[/math] כאשר [math]\displaystyle{ f(x)=[x] }[/math] מוגדר להיות הערך השלם הקרוב ביותר ל-x (במקרה של חצי לוקחים את הגבוה). זו פונקציה על שאינה חח"ע.
• [math]\displaystyle{ D:\mathbb{R}\rightarrow\mathbb{R} }[/math] פונקצית דיריכלה: על כל מספר רציונאלי מקבלת 1 ועל כל מספר אי רציונאלי מקבלת אפס.
• תהא [math]\displaystyle{ A }[/math] קבוצה ו [math]\displaystyle{ B\subseteq A }[/math] תת קבוצה. הפונקציה

[math]\displaystyle{ \chi_B= \begin{cases} 1 & \text{ if } x\in B \\ 0 & \text{ otherwise } \end{cases} }[/math] פונקצית האינדקטור. במקרה של דריכלה [math]\displaystyle{ D=\chi_{\mathbb{Q}} }[/math]

• תהא [math]\displaystyle{ f:A\to B }[/math] אזי [math]\displaystyle{ g:A\to Im(f) }[/math] המוגדרת [math]\displaystyle{ g(a)=f(a) }[/math] היא על (במילים: פשוט חושבים על הטווח של f להיות התמונה של f)
• תהא [math]\displaystyle{ A\subseteq B }[/math] אזי הפונקציה [math]\displaystyle{ i : A\to B }[/math] המוגדרת [math]\displaystyle{ i(a)=a }[/math] נקראת פונקציה ההכלה (במקרה ש [math]\displaystyle{ A=B }[/math] זה פונקצית הזהות). פונקצית ההכלה היא חח"ע.

תרגיל

נסמן ב- [math]\displaystyle{ \mathbb{N}^{\mathbb{N}} }[/math] את אוסף הפונקציות מהטבעיים לעצמם.

נתבונן בפונקציה [math]\displaystyle{ f:\mathbb{N}^{\mathbb{N}} \rightarrow \mathbb{N} \times \mathbb{N} }[/math] המוגדרת ע"י [math]\displaystyle{ f(g)=(g(1),g(2)) }[/math] האם היא חח"ע? האם היא על?

פתרון

לא חח"ע כי יש הרבה פונקציות שנותנות ל-1,2 את אותם ערכים. על: לכל זוג סדור [math]\displaystyle{ (n,m) }[/math] הפונקציה ששולחת את 1 ל-n, ואת 2 ל-m, היא המקור (את השאר תשלחו לאן שאתם רוצים).

תרגיל

תהא [math]\displaystyle{ A }[/math] קבוצה. נגדיר פונקציה [math]\displaystyle{ f:P(A)\rightarrow P(P(A)) }[/math] ע"י: [math]\displaystyle{ f(X)=\{ B\subseteq A|X\subseteq B\} }[/math] האם היא חח"ע? על?

פתרון

חח"ע: כן. תהיינה [math]\displaystyle{ X,Y\in P(A), X\neq Y }[/math] אם [math]\displaystyle{ X\subsetneq Y\lor (X\nsubseteq Y\land Y\nsubseteq X) }[/math] אזי [math]\displaystyle{ X\in f(X)\smallsetminus f(Y) }[/math]. אחרת [math]\displaystyle{ Y\in f(Y)\smallsetminus f(X) }[/math].

על: לא. למשל לקבוצה [math]\displaystyle{ \{ \{ 1,2\}, \{ 3,4\} \} }[/math] אין מקור. אין תת קבוצה שהאוסף הזה הוא בדיוק אוסף הקבוצות המכילות אותה.

תרגיל

תהיינה [math]\displaystyle{ A,B }[/math] קבוצות סופיות לא ריקות. הוכיחו שקיימת פונקציה [math]\displaystyle{ f:A\rightarrow B }[/math] על אמ"ם [math]\displaystyle{ |A|\geq |B| }[/math].

פתרון

מימין לשמאל: נניח שקיימת פונקציה כנ"ל על, נסמן [math]\displaystyle{ |B|=k }[/math] ונסמן עוד [math]\displaystyle{ B=\{ b_1,...,b_k\} }[/math]. לכל [math]\displaystyle{ 1\leq i\leq k }[/math] לאיבר [math]\displaystyle{ b_i\in B }[/math] יש מקור השונה משאר מקורות חבריו [math]\displaystyle{ f(a_i)=b_i }[/math]. לכן הקבוצה המתקבלת [math]\displaystyle{ \{ a_1,...,a_k\} \subseteq A }[/math] בעלת [math]\displaystyle{ k }[/math] איברים ולכן [math]\displaystyle{ |A|\geq |B| }[/math]

משמאל לימין: נסמן [math]\displaystyle{ |A|=n,|B|=m,n\geq m }[/math], ונסמן עוד [math]\displaystyle{ B=\{ b_1,...,b_m\} ,A=\{ a_1,...,a_m,...,a_n\} }[/math], ונגדיר פונקציה ע"י [math]\displaystyle{ f(a_{i})=\begin{cases} b_{i} & 1\leq i\leq m\\ b_{1} & m+1\leq i\leq n \end{cases} }[/math]. זו פונקציה על.

תרגיל

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

פתרון

נסמן [math]\displaystyle{ f:A\to B, A=\{a_1,\dots a_n\},B=\{b_1,\dots b_n\} }[/math] . כאשר כל האיברים ב A שונים זה מזה וכנ"ל ל B

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

נניח [math]\displaystyle{ f }[/math] על. נניח בשלילה ש [math]\displaystyle{ f }[/math] אינה חח"ע אזי [math]\displaystyle{ |\{f(a_1),\dots f(a_n)\}|\lt n }[/math] (כי יש שני איברים שנשלחים לאותו מקום) ואז [math]\displaystyle{ f }[/math] אינה על -סתירה.

הערה: הדבר אינו נכון אם A וB קבוצות אינסופיות.

למשל הפונקציה [math]\displaystyle{ f:\mathbb{N} \to \mathbb{N} }[/math] המוגדרת [math]\displaystyle{ f(n) = n+1 }[/math] היא חח"ע ואינה על.

הרכבת פונקציות

הגדרה: תהיינה [math]\displaystyle{ f:A\to B, g:B\to C }[/math] שתי פונקציות אזי ההרכבה של [math]\displaystyle{ g }[/math] על [math]\displaystyle{ f }[/math] היא פונקציה [math]\displaystyle{ g \circ f:A\to C }[/math] המוגדרת על ידי הכלל [math]\displaystyle{ g \circ f(a)=g(f(a)) }[/math]

תכונות:

1. הרכבה היא קיבוצית. כלומר [math]\displaystyle{ f_3 \circ (f_2 \circ f_1) = (f_3 \circ f_2) \circ f_1 }[/math]
2. הרכבה אינה (בהכרח) חילופית כלומר לא מתקיים בהכרח כי [math]\displaystyle{ f_2 \circ f_1 = f_2 \circ f_1 }[/math]. למשל [math]\displaystyle{ f(x) =x^2 , g(x) = x+1 }[/math] אזי [math]\displaystyle{ f(g(2))=f(3)=9, g(f(2))=g(4)=5 }[/math] ולכן [math]\displaystyle{ f\circ g \neq g \circ f }[/math]

תרגיל

• תהיינה [math]\displaystyle{ f:A\to B, g:B\to C }[/math] פונקציות כך ש- [math]\displaystyle{ g \circ f }[/math] חח"ע. הוכח/הפרך: g חח"ע, f חח"ע
• תהיינה [math]\displaystyle{ f:A\to B, g:B\to C }[/math] פונקציות כך ש- [math]\displaystyle{ g \circ f }[/math] על. הוכח/הפרך: g על, f על

פתרון:

נניח [math]\displaystyle{ g \circ f }[/math] חח"ע. נניח בשלילה ש-f אינה חח"ע. לכן קיימים [math]\displaystyle{ x,y }[/math] כך ש [math]\displaystyle{ f(x)=f(y) }[/math] אבל [math]\displaystyle{ x\neq y }[/math]. אבל, [math]\displaystyle{ g\circ f (x) = g(f(x))=g(f(y))=g\circ f(y) }[/math] בסתירה לחח"ע של ההרכבה, ולכן f חח"ע.

לגבי g ניתן דוגמא נגדית: [math]\displaystyle{ f(x)=e^x ,g(y)=y^2 }[/math] ההרכבה היא [math]\displaystyle{ h(x)=e^{2x} }[/math]

נניח [math]\displaystyle{ g \circ f }[/math] על. נסמן [math]\displaystyle{ g \circ f : A\rightarrow C }[/math] אזי לכל איבר [math]\displaystyle{ c\in C }[/math] קיים איבר [math]\displaystyle{ a\in A }[/math] כך ש [math]\displaystyle{ g(f(a))=c }[/math]. לכן עבור g נקבל שלכל [math]\displaystyle{ c\in C }[/math] קיים [math]\displaystyle{ f(a)\in B }[/math] שנותן את [math]\displaystyle{ c }[/math] תחת g, ולכן g על.

דוגמא נגדית ל f: נתבונן בשתי הפונקציות מהטבעיים לעצמם [math]\displaystyle{ f(n)=n+1 }[/math]; [math]\displaystyle{ \forall n\neq 0 g(n)=n-1 , g(0)=0 }[/math] ההרכבה היא הזהות ו-[math]\displaystyle{ f }[/math] לא על, אין מקור ל-1.

(עוד דוגמא נביט בפונקציות מהטבעיים לטבעיים. [math]\displaystyle{ f(n)=2n }[/math], והפונקציה g מוגדרת כ [math]\displaystyle{ g(2n)=n }[/math] ו [math]\displaystyle{ g(2n+1)=n }[/math]. ההרכבה הינה פונקצית הזהות שהיא בפרט על, אבל f אינה על כיוון שהאי זוגיים כלל לא נמצאים בתמונה שלה.)

פונקציות הפיכות

הערה: לכל פונקציה [math]\displaystyle{ f }[/math] מתקיים [math]\displaystyle{ f\circ id =f }[/math] וגם [math]\displaystyle{ id \circ f =f }[/math]

הגדרה: תהי [math]\displaystyle{ f }[/math] פונקציה [math]\displaystyle{ f:A\rightarrow B }[/math]. פונקציה [math]\displaystyle{ g:B\rightarrow A }[/math] תיקרא הפונקציה ההופכית ל-[math]\displaystyle{ f }[/math] אם [math]\displaystyle{ f\circ g = id_B }[/math] וגם [math]\displaystyle{ g\circ f = id_A }[/math]. במקרה זה נסמן את [math]\displaystyle{ g }[/math] על ידי [math]\displaystyle{ f^{-1} }[/math], ונאמר שהפונקציה [math]\displaystyle{ f }[/math] היא הפיכה.

הערה: זכרו שפונקציה היא יחס. הפונקציה ההופכית שלה היא היחס ההופכי מטבע הדברים. על מנת שהיחס ההופכי יהיה פונקציה הוא צריך להיות ח"ע ושהתחום שלו יהיה כל B. תנאים אלה מתממשים רק אם f הינה חח"ע ועל.

דוגמאות

1. [math]\displaystyle{ f:\mathbb{R} \to \mathbb{R} }[/math] המוגדרת:

1. [math]\displaystyle{ f(x)=x+1 }[/math] הפיכה וההופכית היא [math]\displaystyle{ f^{-1}(x) = x-1 }[/math]
2. [math]\displaystyle{ f(x)=x^3 }[/math] הפיכה וההופכית היא [math]\displaystyle{ f^{-1}(x) = x^{1/3} }[/math]
3. [math]\displaystyle{ f(x)=\sin (x) }[/math] אינה הפיכה כי איננה חח"ע למשל [math]\displaystyle{ \sin(0) =\sin(2\pi k) }[/math]

2 תהא [math]\displaystyle{ A }[/math] קבוצה [math]\displaystyle{ f:P(A)\to P(A) }[/math] המוגדרת:

1. [math]\displaystyle{ f(B)= B^c }[/math] הפיכה וההופכית היא [math]\displaystyle{ f^{-1}(B) = B^c }[/math]
2. תהא [math]\displaystyle{ C\subseteq A }[/math] תת קבוצה [math]\displaystyle{ f(B)= B \triangle C }[/math] הפיכה וההופכית היא [math]\displaystyle{ f^{-1}(B) = B \triangle C }[/math]

3 תהא [math]\displaystyle{ A }[/math] קבוצה ו [math]\displaystyle{ C\subseteq A }[/math] תת קבוצה. נגדיר [math]\displaystyle{ f:P(A)\to \{0,1\} }[/math] ע"י :

[math]\displaystyle{ f(B)= \begin{cases} 1 & \text{ if } C\subseteq B \\ 0 & \text{ otherwise } \end{cases} }[/math]

תקיים כי[math]\displaystyle{ f(C)=f(A) }[/math] ואם [math]\displaystyle{ C\neq A }[/math] אזי הפונקציה אינה חח"ע ובפרט אינה הפיכה

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

תרגיל

יהיו [math]\displaystyle{ f_1,\dots f_k:A\to A }[/math] הפיכות/חח"ע/על. הוכח שההרכבה [math]\displaystyle{ f_k \circ \dots \circ f_1 }[/math] הפיכה/חח"ע/על

הוכחה:

חח"ע: נניח [math]\displaystyle{ (f_k \circ \dots \circ f_1)(x_1) =(f_k \circ \dots \circ f_1)(x_2) }[/math] אזי מח"ע של [math]\displaystyle{ f_k }[/math] נקבל כי [math]\displaystyle{ (f_{k-1} \circ \dots \circ f_1)(x_1) =(f_{k-1} \circ \dots \circ f_1)(x_2) }[/math] באופן דומה נמשיך (או באינדוקציה) ונקבל [math]\displaystyle{ x_1=x_2 }[/math]

על: יהא [math]\displaystyle{ y\in A }[/math] כיוון ש [math]\displaystyle{ f_k }[/math] על קיים [math]\displaystyle{ a_k\in A }[/math] כך ש [math]\displaystyle{ f_k(a_k)= y }[/math] באותו אופן קיים [math]\displaystyle{ a_{k-1} }[/math] כך ש [math]\displaystyle{ f_{k-1}(a_{k-1}=a_k }[/math] נמשיך באופן דומה (או באינקודציה) ונקבל [math]\displaystyle{ (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]\displaystyle{ g\circ f \circ g =id }[/math] אז [math]\displaystyle{ f }[/math] הפיכה

הוכחה:

הרכבה של פונקציה חח"ע [math]\displaystyle{ (g\circ f) \circ g =id }[/math] גורר שהשמאלית [math]\displaystyle{ g }[/math] חח"ע

הרכבה של פונקציה על [math]\displaystyle{ g\circ (f \circ g) =id }[/math] גורר שהימנית [math]\displaystyle{ g }[/math] על

ביחד נקבל ש [math]\displaystyle{ g }[/math] חח"ע ועל כלומר הפיכה. נכפול ב [math]\displaystyle{ g^{-1} }[/math] מימין ומשמאל ונקבל כי [math]\displaystyle{ f=g^{-1}\circ g^{-1} }[/math] ואז [math]\displaystyle{ f }[/math] הפיכה כהרכבה של הפיכות.

תרגיל

תהיינה [math]\displaystyle{ f,g:\mathbb{N}\rightarrow \mathbb{N} }[/math] פונקציות כך ש- [math]\displaystyle{ f(n)=g(3n-1) }[/math] הוכיחו:

אם [math]\displaystyle{ f }[/math] על אזי [math]\displaystyle{ g }[/math] לא חח"ע.

פתרון

נסמן [math]\displaystyle{ g(1)=k }[/math] כיון ש-[math]\displaystyle{ f }[/math] על אזי קיים [math]\displaystyle{ n\in \mathbb{N} }[/math] כך ש[math]\displaystyle{ f(n)=k }[/math]. מהנתון נקבל ש-[math]\displaystyle{ g(3n-1)=k }[/math]. כעת, כיון ש- [math]\displaystyle{ n\in \mathbb{N} }[/math] אזי ברור ש-[math]\displaystyle{ 1\neq 3n-1 }[/math], ולכן אילו שני איברים שונים שנשלחים לאותו איבר. לכן [math]\displaystyle{ g }[/math] לא חח"ע.