88-195 בדידה לתיכוניסטים תשעא/מערך שיעור/שיעור 4

פונקציות

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

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

דוגמא.

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

הגדרה:

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

הגדרה:

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

דוגמאות:

• [math]\displaystyle{ f:\mathbb{Z}\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{Z} }[/math] כאשר [math]\displaystyle{ f(x)=[x] }[/math] מוגדר להיות הערך השלם הקרוב ביותר ל-x (במקרה של חצי לוקחים את הגבוה). זו פונקציה על שאינה חח"ע
• [math]\displaystyle{ f:\mathbb{Z}_2\rightarrow\mathbb{Z}_3 }[/math] כאשר לוקחים את 0 ל0 ואת 1 ל1. זו פונקציה חח"ע שאינה על. (כל פונקציה היא על לתמונה של עצמה.)
• [math]\displaystyle{ D:\mathbb{R}\rightarrow\mathbb{R} }[/math] פונקצית דיריכליי: על כל מספר רציונאלי מקבלת 1 ועל כל מספר אי רציונאלי מקבלת אפס.

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

הוכחה. נניח שהפונקציה חח"ע. נזכר שפונקציה הינה יחס, ונספור את הזוגות הסדורים שהיא מכילה; מכיוון שהתחום של הפונקציה הוא A מספר הזוגות הוא בדיוק מספר האיברים בA (מתוך חד ערכיות והעובדה שזה תחום). לכל איבר בA קיים זוג יחיד בפונקציה. אם היה זוג שהיה מקבל את אותו איבר בB זו הייתה סתירה לח"ע ולכן מספר האיברים מB שמופיעים בזוגות הוא כמספר האיברים בA. מכיוון שעוצמת הקבוצות זהה, כל האיברים מB מופיעים בזוג ולכן הפונקציה על.

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

תרגיל. יהיו A וB קבוצות אינסופיות. האם כל פונקציה בינהן היא על אם"ם היא חח"ע?

פתרון. לא. דוגמא: פונקצית הערך השלם על ואינה חח"ע

תרגיל.

• נניח [math]\displaystyle{ f \circ g }[/math] חח"ע. הוכח/הפרך: f חח"ע, g חח"ע
• נניח [math]\displaystyle{ f \circ g }[/math] על. הוכח/הפרך: f על, g על

פתרון.

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

לגבי f ניתן דוגמא נגדית: [math]\displaystyle{ (e^x)^2 }[/math]

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

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

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

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

תרגיל.

הוכח כי f הפיכה אם"ם היא חח"ע ועל. כמו כן, הוכח שאם קיימת הופכית אזי היא יחידה.

הוכחה:

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

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

נניח בשלילה ש g וh הופכיות שונות של f. מכיוון שהן שונות, הן חייבות להיות שונות על איבר אחד לפחות. כלומר, [math]\displaystyle{ \exists a\in A:g(a)\neq h(a) }[/math]. אבל [math]\displaystyle{ f(g(a))=f(h(a)) }[/math] וזו סתירה לחח"ע של f.

הגדרה. תהי [math]\displaystyle{ f:X\rightarrow Y }[/math] פונקציה, ויהיו תת קבוצות [math]\displaystyle{ A\subseteq X,B\subseteq Y }[/math]. אזי [math]\displaystyle{ f(A)=\{f(a)|a\in A\} }[/math], [math]\displaystyle{ f^{-1}(B)=\{a\in A|f(a)\in B\} }[/math].

שימו לב שהסימון [math]\displaystyle{ f^{-1}(B) }[/math] אינו רומז בשום צורה שהפונקציה צריכה להיות הפיכה, הגדרה זו תקפה לכל פונקציה.

תרגיל. הוכח/הפרך: [math]\displaystyle{ f(A)\cap f(B)=f(A\cap B) }[/math]

פתרון.

נניח וf אינה חח"ע, כלומר קיימים [math]\displaystyle{ x\neq y }[/math] כך ש [math]\displaystyle{ f(x)=f(y) }[/math]. ניקח [math]\displaystyle{ A=\{x\},B=\{y\} }[/math] אזי:

[math]\displaystyle{ f(A)\cap f(B) = \{f(x)\} \neq \phi = f(\{\}) = f(A\cap B) }[/math]

תרגיל. תהי [math]\displaystyle{ f:X\rightarrow Y }[/math] חח"ע, ותהי [math]\displaystyle{ A\subseteq X }[/math]. הוכח [math]\displaystyle{ f^{-1}(f(A))=A }[/math].

פתרון.

ישירות מההגדרות נובע שאם [math]\displaystyle{ a\in A }[/math] אזי [math]\displaystyle{ f(a)\in f(A) }[/math] ולכן [math]\displaystyle{ a\in f^{-1}(f(A)) }[/math]. סה"כ הראנו [math]\displaystyle{ A\subseteq f^{-1}(f(A)) }[/math]. (עד כה זה נכון לכל העתקה, לאו דווקא חח"ע.)

נניח כעת בשלילה ש [math]\displaystyle{ f^{-1}(f(A))\neq A }[/math] לכן קיים [math]\displaystyle{ x\in f^{-1}(f(A)) }[/math] כך ש [math]\displaystyle{ x\notin A }[/math]. לכן לפי ההגדרה, [math]\displaystyle{ f(x)\in f(A) }[/math]. לכן קיים a בA כך ש [math]\displaystyle{ f(a)=f(x) }[/math]. מתוך החח"ע נובע ש-x=a בסתירה.

תרגיל ממבחן (קצת משודרג).

יהיו [math]\displaystyle{ X,Y }[/math] שתי קבוצות, ותהי [math]\displaystyle{ f:X\rightarrow Y }[/math] פונקציה כלשהי. נגדיר את הפונקציה [math]\displaystyle{ g:P(Y)\rightarrow P(X) }[/math] על ידי [math]\displaystyle{ g(B)=f^{-1}(B) }[/math]. בדוק את הקשר בין החח"ע/על של f לבין אלה של g. (כלומר, מה גורר את מה בהכרח).

פתרון.

תהי f חח"ע שאינה על (קל למצוא כאלה). אזי [math]\displaystyle{ \exists y\in Y\forall x\in X:f(x)\neq y }[/math]. לכן [math]\displaystyle{ g(Y)=f^{-1}(Y)=f^{-1}(Y/\{y\}=g(Y/\{y\}) }[/math] בסתירה לחח"ע של g.

• לכן ייתכן ו-f חח"ע אך g אינה כזו.

תהי f כך ש-g חח"ע. כפי שראינו לעיל, ניתן ישר להסיק ש-f הינה על.

נוכיח שאם f על אזי g חח"ע; נניח בשלילה שg אינה חח"ע, אזי קיימות שתי קבוצות [math]\displaystyle{ B\neq C \in P(Y) }[/math] כך ש [math]\displaystyle{ g(B)=g(C) }[/math]. בלי הגבלת הכלליות, נניח שקיים איבר [math]\displaystyle{ c\in C }[/math] כך ש [math]\displaystyle{ c\notin B }[/math]. מכיוון ש-f על, קיים איבר a כך ש [math]\displaystyle{ f(a)=c }[/math], לכן [math]\displaystyle{ a\in g(B) }[/math], ואז קיים [math]\displaystyle{ b\in B }[/math] כך ש[math]\displaystyle{ f(a)=b }[/math] ולכן b=c בסתירה.

• אם כן, הוכחנו ש-f על אם"ם g חח"ע.

יהיו [math]\displaystyle{ X=\mathbb{Z}, Y=\{0\} }[/math]. אזי קיימת פונקציה f יחידה מX לY. פונקציה זו אינה חח"ע כמובן, אך g כן חח"ע שכן [math]\displaystyle{ g(\{\})\neq g(\{0\}) }[/math] ואלה הקבוצות היחידות בקבוצת החזקה של Y.

• לכן יתכן ו-g חח"ע אך f אינה כזו.

נניח וg על ונניח בשלילה ש-f אינה חח"ע. לכן קיימים [math]\displaystyle{ a,b \in X }[/math] שונים כך ש [math]\displaystyle{ f(x)=f(y) }[/math]. נביט בנקודון [math]\displaystyle{ A=\{x\} }[/math] נניח וקיימת [math]\displaystyle{ B\in P(Y) }[/math] כך ש [math]\displaystyle{ g(B)=A }[/math], לכן [math]\displaystyle{ f(x)\in B }[/math]. אבל אז בעצם גם [math]\displaystyle{ f(y)\in B }[/math] ולכן [math]\displaystyle{ y\in g(B)=A }[/math] בסתירה. לכן f חח"ע.

נניח f חח"ע, הוכחנו כבר שבהכרח [math]\displaystyle{ f^{-1}(f(A))=A }[/math] לכל A תת קבוצה של X. נובע ש [math]\displaystyle{ g(f(A))=A }[/math] ולכן g הינה על.

• סה"כ, הוכחנו שf חח"ע אם"ם g הינה על.

ניקח f פונקציה חח"ע שאינה על, לכן g היא על.

• לכן ייתכן ו-g הינה על אך f אינה על

באופן דומה ניקח f על שאינה חח"ע, לכן g אינה על.

• לכן ייתכן ו-f הינה על אך g אינה על

הגדרה. תהי [math]\displaystyle{ f:X\rightarrow Y }[/math] ותהי [math]\displaystyle{ A\subseteq X }[/math]. הפונקציה f מצומצמת לA מוגדרת על ידי: [math]\displaystyle{ f|_A:A\rightarrow Y }[/math] כך ש [math]\displaystyle{ f|_A(a)=f(a) }[/math].

דוגמא. נביט ב[math]\displaystyle{ f:\mathbb{R}\rightarrow\mathbb{R} }[/math] המוגדרת על ידי [math]\displaystyle{ f(x)=x^2 }[/math] ואינה חח"ע. נכון לומר שהפונקציה המצומצמת [math]\displaystyle{ f|_{\mathbb{N}} }[/math] כן חח"ע.

תרגיל. תהי [math]\displaystyle{ f:X\rightarrow Y }[/math] פונקציה, הוכח שקיימת קבוצה A כך ש[math]\displaystyle{ f|_A }[/math] חח"ע

פתרון.

פייי זו שאלה קשה. תזכירו לנו אותה כאשר נגיע לאקסיומת הבחירה. (שכן נביט ב[math]\displaystyle{ \{f^{-1}(\{y\})|y\in Y\}) }[/math] ונרצה לבחור איבר יחיד מבין כל קבוצה כזו. אקסיומת הבחירה היא זו המאפשרת לנו לבצע בחירה זו בשלום.)

הגדרה. תהי [math]\displaystyle{ f:A\rightarrow A }[/math], ויהי R יחס שקילויות על A. אומרים כי f מוגדרת היטב על [math]\displaystyle{ A/R }[/math] אם [math]\displaystyle{ \forall a,b\in A:(a,b)\in R\rightarrow (f(a),f(b)\in R }[/math]

תרגיל מוטיבציה להגדרה לעיל.

המוטיבציה להגדרה הזו היא היכולת לגזור ממנה פונקציה על חבורת המנה. נגדיר יחס על חבורת המנה [math]\displaystyle{ g=\{([a],[f(a)])|a\in A\} }[/math]. נוכיח ש-g הינה חד-ערכית ולכן פונקציה.

הוכחה

נניח וקיימים [math]\displaystyle{ a,b\in A }[/math] כך ש [math]\displaystyle{ [a]=[b] }[/math]. לכן [math]\displaystyle{ (a,b)\in R }[/math] ולכן [math]\displaystyle{ (f(a),f(b))\in R }[/math] ולכן [math]\displaystyle{ [f(a)]=[f(b)] }[/math]. לכן לא ייתכן מצב בו [math]\displaystyle{ (x,y),(x,z)\in g }[/math] אבל [math]\displaystyle{ y\neq z }[/math].

דוגמא. האם הפונקציה f על הרציונאליים המוגדרת על ידי [math]\displaystyle{ f(\frac{p}{q})=p }[/math] מוגדרת היטב?

פתרון.

יש לשים לב שלא באמת הגדרנו את הפונקציה על הרציונאליים, אלא על אוסף הזוגות הסדורים של שלמים [math]\displaystyle{ (p,q) }[/math] כך שהאיבר הימני שונה מאפס. נגדיר על קבוצה זו את יחס השקילויות R המוגדר על ידי [math]\displaystyle{ ((p,q),(a,b))\in R }[/math] אם [math]\displaystyle{ pb=qa }[/math]. נראה כי f אינה מוגדרת היטב בתנאים אלו:

[math]\displaystyle{ ((2,6),(1,3))\in R }[/math] אולם [math]\displaystyle{ f(2,6)=(2,1),f(1,3)=(1,1) }[/math] ו[math]\displaystyle{ ((2,1),(1,1))\notin R }[/math].

בכוונה ניסחנו את התרגיל באופן הרומז על יחס השקילויות מבלי לומר אותו במפורש. זו הדרך בה נתקל במושג 'מוגדר היטב' במהלך התואר - יחס השקילויות יהיה מרומז בלבד.