תרגול 12 תשעז: הבדלים בין גרסאות בדף
(←תרגיל) |
|||
| (15 גרסאות ביניים של 3 משתמשים אינן מוצגות) | |||
| שורה 1: | שורה 1: | ||
חזרה ל[[83-116, בדידה 1 להנדסה, מערכי תרגול|דף מערכי התרגול]]. | חזרה ל[[83-116, בדידה 1 להנדסה, מערכי תרגול|דף מערכי התרגול]]. | ||
== | ==הגדרות בסיסיות לפונקציות== | ||
'''הגדרה:''' יהיו <math>A,B</math> קבוצות ו-<math>R</math> יחס בינהן. אזי: | '''הגדרה:''' יהיו <math>A,B</math> קבוצות ו-<math>R</math> יחס בינהן. אזי: | ||
*התחום של R הינו <math>\mathrm{dom}(R)=\{a\in A|\exists b\in B,(a,b)\in R\}=\{(*,\;),(*,\;)\dots \}</math> | *התחום של R הינו <math>\mathrm{dom}(R)=\{a\in A|\exists b\in B,(a,b)\in R\}=\{(*,\;),(*,\;)\dots \}</math> | ||
| שורה 12: | שורה 12: | ||
'''הגדרה:''' | '''הגדרה:''' | ||
*יחס <math>R</math> מ-<math>A</math> ל-<math>B</math> נקרא ''' | *יחס <math>R</math> מ-<math>A</math> ל-<math>B</math> נקרא '''שלם''' אם <math>\forall a\in A \exists b\in B:(a,b)\in R</math> כלומר <math>\mathrm{dom}(R)=A</math> | ||
*יחס <math>R</math> נקרא '''חד ערכי''' אם <math>[(x,b)\in R] \and [(x,d) \in R] \rightarrow (d=b)</math> כלומר אין איבר מ-<math>A</math> שמתאים לשני איברים שונים מ-<math>B</math>. | *יחס <math>R</math> נקרא '''חד ערכי''' אם <math>[(x,b)\in R] \and [(x,d) \in R] \rightarrow (d=b)</math> כלומר אין איבר מ-<math>A</math> שמתאים לשני איברים שונים מ-<math>B</math>. | ||
| שורה 19: | שורה 18: | ||
'''הגדרה:''' | '''הגדרה:''' | ||
יחס חד ערכי | יחס חד ערכי ושלם נקרא '''פונקציה'''; נסמן במקרה זה <math>(a,b)\in R\leftrightarrow b=R(a)</math>. | ||
ובאופן כללי <math>f:A\to B \;\; , a \mapsto f(a)</math>. | ובאופן כללי <math>f:A\to B \;\; , a \mapsto f(a)</math>. | ||
(<math>A</math> נקרא תחום (הגדרה) של הפונקציה ו-<math>B</math> נקרא הטווח של הפונקציה.) | (<math>A</math> נקרא תחום (הגדרה) של הפונקציה ו-<math>B</math> נקרא הטווח של הפונקציה.) | ||
| שורה 29: | שורה 28: | ||
<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>. | <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>. | ||
פונקציה נקראת '''על''' אם <math>Im(f)=B</math>. | |||
'''הגדרה:''' | '''הגדרה:''' | ||
| שורה 46: | שורה 46: | ||
===תרגיל=== | ===תרגיל=== | ||
תהיינה <math>f,g:\mathbb{N}\rightarrow \mathbb{N}</math> פונקציות כך ש-<math>f(n)=g(3n-1)</math>. | |||
הוכיחו שאם <math>f</math> על, אז <math>g</math> לא חח"ע. | |||
====פתרון==== | ====פתרון==== | ||
נסמן <math>g(1)=k</math> כיון ש-<math>f</math> על אזי קיים <math>n\in \mathbb{N}</math> כך ש<math>f(n)=k</math>. מהנתון נקבל ש-<math>g(3n-1)=k</math>. כעת, כיון ש- <math>n\in \mathbb{N}</math> אזי ברור ש-<math>1\neq 3n-1</math>, ולכן אילו שני איברים שונים שנשלחים לאותו איבר. לכן <math>g</math> לא חח"ע. | |||
על | |||
===תרגיל=== | ===תרגיל=== | ||
נסמן ב-<math>\mathbb{N}^{\mathbb{N}}</math> את אוסף הפונקציות מהטבעיים לעצמם. | |||
נתבונן בפונקציה <math>f:\mathbb{N}^{\mathbb{N}} \rightarrow \mathbb{N} \times \mathbb{N}</math> המוגדרת ע"י <math>f(g)=(g(1),g(2))</math> האם היא חח"ע? האם היא על? | |||
====פתרון==== | ====פתרון==== | ||
חח"ע | הפונקציה לא חח"ע כי יש הרבה פונקציות שנותנות ל-1,2 (יחד!) את אותם ערכים. | ||
על: | היא כן על: לכל זוג סדור <math>(n,m)</math> הפונקציה ששולחת את 1 ל-<math>n</math>, ואת 2 ל-<math>m</math>, היא המקור (את שאר הטבעיים נשלח לאן שנרצה). | ||
===תרגיל=== | ===תרגיל=== | ||
תהיינה <math>A</math> ו-<math>B</math> קבוצות סופיות לא ריקות. הוכיחו: <math>|A|\geq |B|</math> אם ורק אם קיימת <math>f:A\to B</math> על. | |||
====הוכחה==== | |||
נסמן <math>f:A\to B, A=\{a_1,\dots, a_n\},B=\{b_1,\dots, | נסמן <math>f:A\to B, A=\{a_1,\dots, a_n\},B=\{b_1,\dots, b_m\} </math> . כאשר כל האיברים ב-<math>A</math> שונים זה מזה וכנ"ל ב-<math>B</math>. | ||
===תרגיל=== | |||
תהא <math>A</math> קבוצה. נגדיר פונקציה <math>f:P(A)\rightarrow P(P(A))</math> ע"י: <math>f(X)=\{ B\subseteq A|X\subseteq B\}</math> האם היא חח"ע? על? | |||
====פתרון==== | |||
חח"ע: כן. תהיינה <math>X,Y\in P(A), X\neq Y</math> אם <math>X\subsetneq Y\lor (X\nsubseteq Y\land Y\nsubseteq X)</math> אזי <math>X\in f(X)\setminus f(Y)</math>. אחרת <math>Y\in f(Y)\setminus f(X)</math>. כלומר <math>f(X)\neq f(Y)</math>. | |||
= | על: לא. נבחר <math>A=\{1,\dots,7\}</math>. למשל לקבוצה <math>\{ \{ 1,2\}, \{ 3,4\} \}\in P(P(A))</math> אין מקור. אין תת קבוצה שהאוסף הזה הוא בדיוק אוסף הקבוצות המכילות אותה. | ||
==הרכבת פונקציות והפיכות== | |||
'''הגדרה:''' | '''הגדרה:''' | ||
| שורה 87: | שורה 88: | ||
*אם <math>g \circ f</math> על אזי <math>g</math> על. | *אם <math>g \circ f</math> על אזי <math>g</math> על. | ||
*מסקנה: אם <math>g \circ f</math> חח"ע ועל אזי <math>f</math> חח"ע ו-<math>g</math> על. | *מסקנה: אם <math>g \circ f</math> חח"ע ועל אזי <math>f</math> חח"ע ו-<math>g</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>f</math> מתקיים <math>f\circ \mathrm{id} =f</math> וגם <math>\mathrm{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 = \mathrm{id}_B</math> וגם <math>g\circ f = \mathrm{id}_A</math>. במקרה זה נסמן את <math>g</math> על ידי <math>f^{-1}</math>, ונאמר שהפונקציה <math>f</math> היא '''הפיכה'''. | ||
שימו לב שאם <math>f</math> פונקציה הפיכה, אז גם <math>f^{-1}</math> היא פונקציה הפיכה, ומתקיים <math>(f^{-1})^{-1}=f</math>. | |||
===תרגיל=== | |||
(לדלג, היה בהרצאה): הוכיחו כי פונקציה <math>f</math> הפיכה אם"ם היא חח"ע ועל. | |||
====פתרון==== | |||
אם <math>f</math> הפיכה, אזי <math>f\circ f^{-1} = \mathrm{id}_B</math> וגם <math>f^{-1}\circ f = \mathrm{id}_A</math>. מכיוון שפונקציית הזהות הינה חח"ע ועל, נובע ש-<math>f</math> חח"ע ועל לפי משפט קודם. | |||
אם <math>f</math> חח"ע ועל, אז נגדיר <math>g:B\to A</math> ע"י: עבור <math>a\in A </math> קיים (כי <math>f</math> על) <math>b\in B</math> יחיד (כי <math>f</math> חח"ע) כך ש-<math>f(a)=b</math> . נגדיר <math>g(b):=a</math>. תרגיל: בדקו כי <math>g</math> היא ההופכית של <math>f</math>. | |||
===דוגמאות=== | |||
# פונקציות <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> לכל <math>k\in\mathbb{Z}</math>. | |||
# תהא <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</math> תת קבוצה. <math>f(B)= B \triangle C</math> הפיכה וההופכית היא <math>f^{-1}(B) = B \triangle C </math>. | |||
# תהא <math>A</math> קבוצה. אזי אפשר (בעזרת חומר שראינו בתרגול על יחסי שקילות) | |||
להגדיר <math>f:\{R \; | \; R \text{ Equivalence relation }\}\to \{\text{Partitions of }A\}</math> ע"י <math>f(R)=A/R</math> והיא תהיה חח"ע ועל, וכבר ראינו את הפונקציה ההופכית לה. | |||
===תרגיל === | |||
יהיו <math>f_1,\dots f_k:A\to A</math> שכולן הפיכות\חח"ע\על. הוכיחו שההרכבה <math>f_k \circ \dots \circ f_1</math> הפיכה\חח"ע\על. | |||
====פתרון==== | |||
למעשה אפשר לעשות אינדוקציה על המשפט מן ההרצאה. עבור שתי פונקציות זה בהרצאה. נניח נכונות ל<math>k-1</math> ונוכיח ל<math>k</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>k-1</math> פונקציות נקבל שההרכבה חח"ע ולכן <math>x_1=x_2</math>. | |||
על: יהא <math>y\in A</math> כיוון ש-<math>f_k</math> על, קיים <math>a\in A</math> כך ש-<math>f_k(a) = y</math>. | |||
בנוסף, מהנחת האינדוקציה קיים <math>b\in A</math> כך ש <math>f_{k-1}\circ \dots \circ f_1(b)=a</math> ולכן נקבל | |||
<math>f_k\circ \dots \circ f_1(b) = f_k\circ (f_{k-1}\circ \dots \circ f_1)(b)=f_k(a)=y</math>. מש"ל. | |||
הפיכות: נובע מחח"ע יחד עם על. | |||
===תרגיל === | |||
הוכיחו כי אם <math>g\circ f \circ g =\mathrm{id}</math> אז <math>f</math> הפיכה. | |||
הוכחה: | |||
הרכבה של פונקציה חח"ע <math>(g\circ f) \circ g =\mathrm{id}</math> גורר שהפונקציה <math>g</math> הימנית חח"ע. | |||
הרכבה של פונקציה על <math>g\circ (f \circ g) =\mathrm{id}</math> גורר שהפונקציה <math>g</math> השמאלית על. | |||
קיבלנו ש-<math>g</math> חח"ע ועל, כלומר הפיכה. נכפול את הנתון ב-<math>g^{-1}</math> מימין ומשמאל ונקבל כי <math>f=g^{-1}\circ g^{-1}</math> ואז <math>f</math> הפיכה כהרכבה של פונקציות הפיכות. | |||
== פונקציות המכבדות יחס שקילות == | |||
'''הגדרה.''' תהי <math>f:A\rightarrow B</math> פונקציה, ויהי <math>R</math> יחס שקילות על <math>A</math>. אומרים כי '''<math>f</math> מוגדרת היטב על <math>A/R</math>''' אם <math>\forall a,b\in A:(a,b)\in R\Rightarrow f(a)=f(b)</math> | |||
כלומר אם <math>a</math> שקול ל <math>b</math> אזי <math>f(a)=f(b)</math>. | |||
למה זה טוב? | |||
כדי שנוכל להגדיר פונקציה על קבוצת המנה <math>g:A/R \to B </math> ע"י <math>[a]_R \mapsto f(a) </math> | |||
טענה: <math>g</math> אכן פונקציה | |||
הוכחה: | |||
1. <math>g</math> שלמה - "לפי העיניים". כלל ההתאמה מנוסח כך שהיחס הוא שלם. | |||
2. <math>g</math> חד ערכית- נניח <math>[a]=[b]</math>, צ"ל <math>g([a])=g([b])</math>. מהנתון ש <math>[a]=[b]</math> נובע ש <math>(a,b)\in R</math>, ולכן, לפי הגדרת <math>f</math> כמוגדרת היטב על קבוצת המנה, מתקיים <math>f(a)=f(b)</math>, ולפי הגדרת <math>g</math> מתקיים <math>g([a])=f(a)=f(b)=g([b])</math>. | |||
'''דוגמא לחידוד''' | |||
ראינו מעל <math>\mathbb{R}\times \mathbb{R}</math> יחס <math>\sim</math> לפי זה שלכל <math>(x_1,y_1),(x_2,y_2)</math>: | |||
<math>(x_1,y_1)\sim (x_2,y_2)\iff x_1^2+y_1^2=x_2^2+y_2^2</math>. | |||
ראינו (שקל לראות) שזהו יחס שקילות. ושמבחינה גיאומטרית, קבוצת המנה היא אוסף המעגלים עם רדיוס חיובי והראשית. | |||
נגדיר פונקציה <math>f:\mathbb{R}\times \mathbb{R}\rightarrow \mathbb{R}</math> ע"י: <math>f((a,b))=a\cdot b</math>. האם היא מוגדרת היטב על קבוצת המנה? לא! למשל <math>f((\frac{1}{\sqrt{2}},\frac{1}{\sqrt{2}}))=\frac{1}{2}\neq 0=f((1,0))</math>, אך הם שקולים לפי היחס. | |||
תנו דוגמא לפונקציה שכן מוגדרת היטב. למשל המרחק מהראשית (או כל פונקציה של זה). | |||
==תמונות חלקיות== | |||
'''הגדרה.''' תהי <math>f:X\rightarrow Y</math> פונקציה, ויהיו תת קבוצות <math>A\subseteq X,B\subseteq Y</math>. אזי '''התמונה החלקית של A תחת f''' היא התת-קבוצה <math>f[A]=\{f(a)|a\in A\}</math>, ו'''התמונה החלקית ההפוכה של B תחת f''' היא התת-קבוצה <math>f^{-1}[B]=\{a\in X|f(a)\in B\}</math>. | |||
שימו לב להבדל בין התמונה ההפוכה <math>f^{-1}[B]</math> לבין הפונקציה ההופכית <math>f^{-1}(y)</math>. התמונה ההפוכה איננה מניחה כי הפונקציה f הפיכה. הדרך להבחין בין פונקציה הפיכה לתמונה ההפוכה היא לבדוק האם בין הסוגריים נמצא ''איבר'' של התמונה (בדוגמאות לעיל זהו <math>y \in Y</math>) או שנמצאת ''תת-קבוצה'' של התמונה (בדוגמאות לעיל זו <math>B\subseteq Y</math>). | |||
==== דוגמאות ==== | |||
תהא <math>D:\mathbb{R}\to \mathbb{R}</math> פונקצית דריכלה. אזי <math>D[\mathbb{Q}]=\{1\},D^{-1}[\{1\}]=\mathbb{Q}=D^{-1}[(0.5, 18)]</math> | |||
תהא <math>f:X\to Y</math> פונקצית . אזי <math>f^{-1}[Y]=X</math> | |||
תהא <math>f:\mathbb{R}\to \mathbb{Z}</math> פונקצית הערך השלם התחתון. אזי <math>f[(-0.5,3/4)]=\{-1,0\},f^{-1}[\{1\}]=[1,2)</math> | |||
===תרגיל=== | |||
תהי <math>f:X\rightarrow Y</math> ותהי <math>A\subseteq X</math>. הוכח <math>A \subseteq f^{-1}[f[A]]</math>. וקיים שיוויון אם <math>f</math> חח"ע | |||
====פתרון==== | |||
יהא <math>a\in A</math> אזי <math>f(a)\in f[A]</math> ולכן <math>a\in f^{-1}[f[A]]</math>. | |||
נראה את ההכלה בכיוון השני אם <math>f</math> חח"ע: | |||
יהא <math>x\in f^{-1}[f[A]]</math> לכן <math>f(x) \in f[A]</math> לכן <math>\exists a\in A : f(x)=f(a)</math>. כיוון ש <math>f</math> חח"ע נובע כי <math>x=a\in A</math> | |||
דוגמא שלא מתקיים שיוויון <math>f:\{1,2\}\to \{1\}</math> (יש דרך אחת להגדיר את הפונקציה). אזי נגדיר <math>A=\{2\}</math> ומתקיים <math> f^{-1}(f(A))=\{1,2\}\neq A</math> | |||
===תרגיל=== | |||
תהי <math>f:X\rightarrow Y</math> פונקציה, ותהיינה <math>A,B\subseteq X</math>. הוכיחו: <math>f[A\triangle B]=f[A]\triangle f[B]</math> <math>\iff</math> <math>f</math> חח"ע | |||
גרסה אחרונה מ־15:51, 14 בינואר 2020
חזרה לדף מערכי התרגול.
הגדרות בסיסיות לפונקציות
הגדרה: יהיו [math]\displaystyle{ A,B }[/math] קבוצות ו-[math]\displaystyle{ R }[/math] יחס בינהן. אזי:
- התחום של R הינו [math]\displaystyle{ \mathrm{dom}(R)=\{a\in A|\exists b\in B,(a,b)\in R\}=\{(*,\;),(*,\;)\dots \} }[/math]
- התמונה של R הינה [math]\displaystyle{ \mathrm{im}(R)=\{b\in B|\exists a\in A,(a,b)\in R\}=\{(\;,*),(\; ,*)\dots \} }[/math]
הערה: ישירות מהגדרה מתקיים כי [math]\displaystyle{ \mathrm{dom}(R)\subseteq A, \mathrm{im}(R)\subseteq B }[/math].
דוגמה:
- [math]\displaystyle{ R=\{(1,a),(2,b),(3,a),(a,1)\} }[/math] אזי התחום הוא [math]\displaystyle{ \mathrm{dom}(R)=\{a,1,2,3\} }[/math] והתמונה הינה [math]\displaystyle{ \mathrm{im}(R)=\{1,a,b\} }[/math].
הגדרה:
- יחס [math]\displaystyle{ R }[/math] מ-[math]\displaystyle{ A }[/math] ל-[math]\displaystyle{ B }[/math] נקרא שלם אם [math]\displaystyle{ \forall a\in A \exists b\in B:(a,b)\in R }[/math] כלומר [math]\displaystyle{ \mathrm{dom}(R)=A }[/math]
- יחס [math]\displaystyle{ R }[/math] נקרא חד ערכי אם [math]\displaystyle{ [(x,b)\in R] \and [(x,d) \in R] \rightarrow (d=b) }[/math] כלומר אין איבר מ-[math]\displaystyle{ A }[/math] שמתאים לשני איברים שונים מ-[math]\displaystyle{ B }[/math].
הגדרה:
יחס חד ערכי ושלם נקרא פונקציה; נסמן במקרה זה [math]\displaystyle{ (a,b)\in R\leftrightarrow b=R(a) }[/math]. ובאופן כללי [math]\displaystyle{ f:A\to B \;\; , a \mapsto f(a) }[/math]. ([math]\displaystyle{ A }[/math] נקרא תחום (הגדרה) של הפונקציה ו-[math]\displaystyle{ B }[/math] נקרא הטווח של הפונקציה.)
פונקציה נקראת חד-חד ערכית אם בנוסף היחס ההפוך הוא חד ערכי.
כלומר:
[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{ Im(f)=B }[/math].
הגדרה:
תהא [math]\displaystyle{ A }[/math] קבוצה. פונקציית הזהות היא פונקציה [math]\displaystyle{ f:A \to A }[/math] המקיימת [math]\displaystyle{ \forall a\in A: f(a)=a }[/math]. נהוג לסמנה [math]\displaystyle{ \mathrm{id}_A }[/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^2 }[/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{R}\rightarrow\mathbb{R} }[/math] כאשר [math]\displaystyle{ f(x)=x-1 }[/math] חח"ע ועל.
- [math]\displaystyle{ f:\mathbb{N}\rightarrow\mathbb{N} \cup \{ 0\} }[/math] כאשר [math]\displaystyle{ f(x)=x-1 }[/math] חח"ע ועל.
- [math]\displaystyle{ f:\mathbb{N}\rightarrow\mathbb{R} }[/math] כאשר [math]\displaystyle{ f(x)=x-1 }[/math] חח"ע ואינה על.
- תהא פונקציה [math]\displaystyle{ f:A\to B }[/math] אזי [math]\displaystyle{ g:A\to \mathrm{im}(f) }[/math] המוגדרת לכל [math]\displaystyle{ a\in A }[/math] לפי [math]\displaystyle{ g(a)=f(a) }[/math] היא על (במילים: פשוט חושבים על הטווח של [math]\displaystyle{ g }[/math] להיות התמונה של [math]\displaystyle{ f }[/math]).
- תהא [math]\displaystyle{ A\subseteq B }[/math] אזי הפונקציה [math]\displaystyle{ i : A\to B }[/math] המוגדרת לכל [math]\displaystyle{ a\in A }[/math] לפי [math]\displaystyle{ i(a)=a }[/math] נקראת פונקציה ההכלה (אם [math]\displaystyle{ A=B }[/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] לא חח"ע.
תרגיל
נסמן ב-[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 ל-[math]\displaystyle{ n }[/math], ואת 2 ל-[math]\displaystyle{ m }[/math], היא המקור (את שאר הטבעיים נשלח לאן שנרצה).
תרגיל
תהיינה [math]\displaystyle{ A }[/math] ו-[math]\displaystyle{ B }[/math] קבוצות סופיות לא ריקות. הוכיחו: [math]\displaystyle{ |A|\geq |B| }[/math] אם ורק אם קיימת [math]\displaystyle{ f:A\to B }[/math] על.
הוכחה
נסמן [math]\displaystyle{ f:A\to B, A=\{a_1,\dots, a_n\},B=\{b_1,\dots, b_m\} }[/math] . כאשר כל האיברים ב-[math]\displaystyle{ A }[/math] שונים זה מזה וכנ"ל ב-[math]\displaystyle{ B }[/math].
תרגיל
תהא [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)\setminus f(Y) }[/math]. אחרת [math]\displaystyle{ Y\in f(Y)\setminus f(X) }[/math]. כלומר [math]\displaystyle{ f(X)\neq f(Y) }[/math].
על: לא. נבחר [math]\displaystyle{ A=\{1,\dots,7\} }[/math]. למשל לקבוצה [math]\displaystyle{ \{ \{ 1,2\}, \{ 3,4\} \}\in P(P(A)) }[/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].
הערה: אם מתייחסים לפונקציות כאל יחסים - מקבלים את ההגדרה של הרכבת יחסים.
משפט:
- אם [math]\displaystyle{ g \circ f }[/math] חח"ע אזי [math]\displaystyle{ f }[/math] חח"ע.
- אם [math]\displaystyle{ g \circ f }[/math] על אזי [math]\displaystyle{ g }[/math] על.
- מסקנה: אם [math]\displaystyle{ g \circ f }[/math] חח"ע ועל אזי [math]\displaystyle{ f }[/math] חח"ע ו-[math]\displaystyle{ g }[/math] על.
תכונות של הרכבת פונקציות:
- הרכבה היא קיבוצית. כלומר [math]\displaystyle{ f_3 \circ (f_2 \circ f_1) = (f_3 \circ f_2) \circ f_1 }[/math].
- הרכבה אינה (בהכרח) חילופית כלומר לא מתקיים בהכרח כי [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 }[/math] מתקיים [math]\displaystyle{ f\circ \mathrm{id} =f }[/math] וגם [math]\displaystyle{ \mathrm{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 = \mathrm{id}_B }[/math] וגם [math]\displaystyle{ g\circ f = \mathrm{id}_A }[/math]. במקרה זה נסמן את [math]\displaystyle{ g }[/math] על ידי [math]\displaystyle{ f^{-1} }[/math], ונאמר שהפונקציה [math]\displaystyle{ f }[/math] היא הפיכה.
שימו לב שאם [math]\displaystyle{ f }[/math] פונקציה הפיכה, אז גם [math]\displaystyle{ f^{-1} }[/math] היא פונקציה הפיכה, ומתקיים [math]\displaystyle{ (f^{-1})^{-1}=f }[/math].
תרגיל
(לדלג, היה בהרצאה): הוכיחו כי פונקציה [math]\displaystyle{ f }[/math] הפיכה אם"ם היא חח"ע ועל.
פתרון
אם [math]\displaystyle{ f }[/math] הפיכה, אזי [math]\displaystyle{ f\circ f^{-1} = \mathrm{id}_B }[/math] וגם [math]\displaystyle{ f^{-1}\circ f = \mathrm{id}_A }[/math]. מכיוון שפונקציית הזהות הינה חח"ע ועל, נובע ש-[math]\displaystyle{ f }[/math] חח"ע ועל לפי משפט קודם.
אם [math]\displaystyle{ f }[/math] חח"ע ועל, אז נגדיר [math]\displaystyle{ g:B\to A }[/math] ע"י: עבור [math]\displaystyle{ a\in A }[/math] קיים (כי [math]\displaystyle{ f }[/math] על) [math]\displaystyle{ b\in B }[/math] יחיד (כי [math]\displaystyle{ f }[/math] חח"ע) כך ש-[math]\displaystyle{ f(a)=b }[/math] . נגדיר [math]\displaystyle{ g(b):=a }[/math]. תרגיל: בדקו כי [math]\displaystyle{ g }[/math] היא ההופכית של [math]\displaystyle{ f }[/math].
דוגמאות
- פונקציות [math]\displaystyle{ f:\mathbb{R} \to \mathbb{R} }[/math] המוגדרות לפי:
- [math]\displaystyle{ f(x)=x+1 }[/math] הפיכה וההופכית היא [math]\displaystyle{ f^{-1}(x) = x-1 }[/math].
- [math]\displaystyle{ f(x)=x^3 }[/math] הפיכה וההופכית היא [math]\displaystyle{ f^{-1}(x) = x^{1/3} }[/math].
- [math]\displaystyle{ f(x)=\sin (x) }[/math] אינה הפיכה כי איננה חח"ע למשל [math]\displaystyle{ \sin(0) =\sin(2\pi k) }[/math] לכל [math]\displaystyle{ k\in\mathbb{Z} }[/math].
- תהא [math]\displaystyle{ A }[/math] קבוצה. פונקציות [math]\displaystyle{ f:P(A)\to P(A) }[/math] המוגדרות לפי:
- [math]\displaystyle{ f(B)= B^c }[/math] הפיכה וההופכית היא [math]\displaystyle{ f^{-1}(B) = B^c }[/math].
- תהא [math]\displaystyle{ C\subseteq A }[/math] תת קבוצה. [math]\displaystyle{ f(B)= B \triangle C }[/math] הפיכה וההופכית היא [math]\displaystyle{ f^{-1}(B) = B \triangle C }[/math].
- תהא [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{ k-1 }[/math] ונוכיח ל[math]\displaystyle{ k }[/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{ k-1 }[/math] פונקציות נקבל שההרכבה חח"ע ולכן [math]\displaystyle{ x_1=x_2 }[/math].
על: יהא [math]\displaystyle{ y\in A }[/math] כיוון ש-[math]\displaystyle{ f_k }[/math] על, קיים [math]\displaystyle{ a\in A }[/math] כך ש-[math]\displaystyle{ f_k(a) = y }[/math]. בנוסף, מהנחת האינדוקציה קיים [math]\displaystyle{ b\in A }[/math] כך ש [math]\displaystyle{ f_{k-1}\circ \dots \circ f_1(b)=a }[/math] ולכן נקבל [math]\displaystyle{ f_k\circ \dots \circ f_1(b) = f_k\circ (f_{k-1}\circ \dots \circ f_1)(b)=f_k(a)=y }[/math]. מש"ל.
הפיכות: נובע מחח"ע יחד עם על.
תרגיל
הוכיחו כי אם [math]\displaystyle{ g\circ f \circ g =\mathrm{id} }[/math] אז [math]\displaystyle{ f }[/math] הפיכה.
הוכחה:
הרכבה של פונקציה חח"ע [math]\displaystyle{ (g\circ f) \circ g =\mathrm{id} }[/math] גורר שהפונקציה [math]\displaystyle{ g }[/math] הימנית חח"ע.
הרכבה של פונקציה על [math]\displaystyle{ g\circ (f \circ g) =\mathrm{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:A\rightarrow B }[/math] פונקציה, ויהי [math]\displaystyle{ R }[/math] יחס שקילות על [math]\displaystyle{ A }[/math]. אומרים כי [math]\displaystyle{ f }[/math] מוגדרת היטב על [math]\displaystyle{ A/R }[/math] אם [math]\displaystyle{ \forall a,b\in A:(a,b)\in R\Rightarrow f(a)=f(b) }[/math]
כלומר אם [math]\displaystyle{ a }[/math] שקול ל [math]\displaystyle{ b }[/math] אזי [math]\displaystyle{ f(a)=f(b) }[/math].
למה זה טוב? כדי שנוכל להגדיר פונקציה על קבוצת המנה [math]\displaystyle{ g:A/R \to B }[/math] ע"י [math]\displaystyle{ [a]_R \mapsto f(a) }[/math]
טענה: [math]\displaystyle{ g }[/math] אכן פונקציה
הוכחה:
1. [math]\displaystyle{ g }[/math] שלמה - "לפי העיניים". כלל ההתאמה מנוסח כך שהיחס הוא שלם.
2. [math]\displaystyle{ g }[/math] חד ערכית- נניח [math]\displaystyle{ [a]=[b] }[/math], צ"ל [math]\displaystyle{ g([a])=g([b]) }[/math]. מהנתון ש [math]\displaystyle{ [a]=[b] }[/math] נובע ש [math]\displaystyle{ (a,b)\in R }[/math], ולכן, לפי הגדרת [math]\displaystyle{ f }[/math] כמוגדרת היטב על קבוצת המנה, מתקיים [math]\displaystyle{ f(a)=f(b) }[/math], ולפי הגדרת [math]\displaystyle{ g }[/math] מתקיים [math]\displaystyle{ g([a])=f(a)=f(b)=g([b]) }[/math].
דוגמא לחידוד
ראינו מעל [math]\displaystyle{ \mathbb{R}\times \mathbb{R} }[/math] יחס [math]\displaystyle{ \sim }[/math] לפי זה שלכל [math]\displaystyle{ (x_1,y_1),(x_2,y_2) }[/math]:
[math]\displaystyle{ (x_1,y_1)\sim (x_2,y_2)\iff x_1^2+y_1^2=x_2^2+y_2^2 }[/math].
ראינו (שקל לראות) שזהו יחס שקילות. ושמבחינה גיאומטרית, קבוצת המנה היא אוסף המעגלים עם רדיוס חיובי והראשית.
נגדיר פונקציה [math]\displaystyle{ f:\mathbb{R}\times \mathbb{R}\rightarrow \mathbb{R} }[/math] ע"י: [math]\displaystyle{ f((a,b))=a\cdot b }[/math]. האם היא מוגדרת היטב על קבוצת המנה? לא! למשל [math]\displaystyle{ f((\frac{1}{\sqrt{2}},\frac{1}{\sqrt{2}}))=\frac{1}{2}\neq 0=f((1,0)) }[/math], אך הם שקולים לפי היחס.
תנו דוגמא לפונקציה שכן מוגדרת היטב. למשל המרחק מהראשית (או כל פונקציה של זה).
תמונות חלקיות
הגדרה. תהי [math]\displaystyle{ f:X\rightarrow Y }[/math] פונקציה, ויהיו תת קבוצות [math]\displaystyle{ A\subseteq X,B\subseteq Y }[/math]. אזי התמונה החלקית של A תחת f היא התת-קבוצה [math]\displaystyle{ f[A]=\{f(a)|a\in A\} }[/math], והתמונה החלקית ההפוכה של B תחת f היא התת-קבוצה [math]\displaystyle{ f^{-1}[B]=\{a\in X|f(a)\in B\} }[/math].
שימו לב להבדל בין התמונה ההפוכה [math]\displaystyle{ f^{-1}[B] }[/math] לבין הפונקציה ההופכית [math]\displaystyle{ f^{-1}(y) }[/math]. התמונה ההפוכה איננה מניחה כי הפונקציה f הפיכה. הדרך להבחין בין פונקציה הפיכה לתמונה ההפוכה היא לבדוק האם בין הסוגריים נמצא איבר של התמונה (בדוגמאות לעיל זהו [math]\displaystyle{ y \in Y }[/math]) או שנמצאת תת-קבוצה של התמונה (בדוגמאות לעיל זו [math]\displaystyle{ B\subseteq Y }[/math]).
דוגמאות
תהא [math]\displaystyle{ D:\mathbb{R}\to \mathbb{R} }[/math] פונקצית דריכלה. אזי [math]\displaystyle{ D[\mathbb{Q}]=\{1\},D^{-1}[\{1\}]=\mathbb{Q}=D^{-1}[(0.5, 18)] }[/math]
תהא [math]\displaystyle{ f:X\to Y }[/math] פונקצית . אזי [math]\displaystyle{ f^{-1}[Y]=X }[/math]
תהא [math]\displaystyle{ f:\mathbb{R}\to \mathbb{Z} }[/math] פונקצית הערך השלם התחתון. אזי [math]\displaystyle{ f[(-0.5,3/4)]=\{-1,0\},f^{-1}[\{1\}]=[1,2) }[/math]
תרגיל
תהי [math]\displaystyle{ f:X\rightarrow Y }[/math] ותהי [math]\displaystyle{ A\subseteq X }[/math]. הוכח [math]\displaystyle{ A \subseteq f^{-1}[f[A]] }[/math]. וקיים שיוויון אם [math]\displaystyle{ f }[/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{ f }[/math] חח"ע:
יהא [math]\displaystyle{ x\in f^{-1}[f[A]] }[/math] לכן [math]\displaystyle{ f(x) \in f[A] }[/math] לכן [math]\displaystyle{ \exists a\in A : f(x)=f(a) }[/math]. כיוון ש [math]\displaystyle{ f }[/math] חח"ע נובע כי [math]\displaystyle{ x=a\in A }[/math]
דוגמא שלא מתקיים שיוויון [math]\displaystyle{ f:\{1,2\}\to \{1\} }[/math] (יש דרך אחת להגדיר את הפונקציה). אזי נגדיר [math]\displaystyle{ A=\{2\} }[/math] ומתקיים [math]\displaystyle{ f^{-1}(f(A))=\{1,2\}\neq A }[/math]
תרגיל
תהי [math]\displaystyle{ f:X\rightarrow Y }[/math] פונקציה, ותהיינה [math]\displaystyle{ A,B\subseteq X }[/math]. הוכיחו: [math]\displaystyle{ f[A\triangle B]=f[A]\triangle f[B] }[/math] [math]\displaystyle{ \iff }[/math] [math]\displaystyle{ f }[/math] חח"ע