תרגול 12 תשעז: הבדלים בין גרסאות בדף
אין תקציר עריכה |
|||
| שורה 35: | שורה 35: | ||
===דוגמאות=== | ===דוגמאות=== | ||
באופן רשלני (וחסכוני), כאשר אנחנו מגדירים פונקציה לא תמיד נשתמש בכמת "לכל" לגבי איברי תחום ההגדרה. | |||
*<math>f:\mathbb{N}\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^2</math> אינה חח"ע ואינה על. | *<math>f:\mathbb{Z}\rightarrow\mathbb{Z}</math> כאשר <math>f(p)=p^2</math> אינה חח"ע ואינה על. | ||
| שורה 40: | שורה 41: | ||
*<math>f:\mathbb{R}\rightarrow\mathbb{R}</math> כאשר <math>f(x)=x-1</math> חח"ע ועל. | *<math>f:\mathbb{R}\rightarrow\mathbb{R}</math> כאשר <math>f(x)=x-1</math> חח"ע ועל. | ||
*<math>f:\mathbb{N}\rightarrow\mathbb{N} \cup \{ 0\}</math> כאשר <math>f(x)=x-1</math> חח"ע ועל. | *<math>f:\mathbb{N}\rightarrow\mathbb{N} \cup \{ 0\}</math> כאשר <math>f(x)=x-1</math> חח"ע ועל. | ||
*<math>f:\mathbb{N}\rightarrow\mathbb{R}</math> כאשר <math>f(x)=x-1</math> חח"ע ואינה על. | |||
* תהא פונקציה <math>f:A\to B</math> אזי <math>g:A\to \mathrm{im}(f) </math> המוגדרת לכל <math>a\in A</math> לפי <math>g(a)=f(a)</math> היא על (במילים: פשוט חושבים על הטווח של <math>g</math> להיות התמונה של <math>f</math>). | * תהא פונקציה <math>f:A\to B</math> אזי <math>g:A\to \mathrm{im}(f) </math> המוגדרת לכל <math>a\in A</math> לפי <math>g(a)=f(a)</math> היא על (במילים: פשוט חושבים על הטווח של <math>g</math> להיות התמונה של <math>f</math>). | ||
* תהא <math>A\subseteq B</math> אזי הפונקציה <math>i : A\to B </math> המוגדרת לכל <math>a\in A</math> לפי <math>i(a)=a</math> נקראת פונקציה ההכלה (אם <math>A=B</math> זו פונקצית הזהות). פונקצית ההכלה היא חח"ע. | * תהא <math>A\subseteq B</math> אזי הפונקציה <math>i : A\to B </math> המוגדרת לכל <math>a\in A</math> לפי <math>i(a)=a</math> נקראת פונקציה ההכלה (אם <math>A=B</math> זו פונקצית הזהות). פונקצית ההכלה היא חח"ע. | ||
גרסה מ־19:31, 29 בדצמבר 2017
חזרה לדף מערכי התרגול.
פונקציות
הגדרה: יהיו [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 b\in B \exists a\in A:(a,b)\in R }[/math] כלומר [math]\displaystyle{ \mathrm{im}(R)=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{ 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{ \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{ 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 }[/math] ו-[math]\displaystyle{ B }[/math] קבוצות סופיות בעלות עוצמה זהה. הוכיחו שכל פונקציה מ-[math]\displaystyle{ A }[/math] ל-[math]\displaystyle{ B }[/math] הינה על אם"ם היא חח"ע.
הוכחה: נסמן [math]\displaystyle{ f:A\to B, A=\{a_1,\dots, a_n\},B=\{b_1,\dots, b_n\} }[/math] . כאשר כל האיברים ב-[math]\displaystyle{ A }[/math] שונים זה מזה וכנ"ל ב-[math]\displaystyle{ B }[/math].
נניח [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] אינה על, שזו סתירה.
הערה: הדבר אינו נכון אם [math]\displaystyle{ A }[/math] ו-[math]\displaystyle{ B }[/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 }[/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 }[/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].