הבדלים בין גרסאות בדף "תרגול 12 תשעז"

מתוך Math-Wiki
קפיצה אל: ניווט, חיפוש
(←‏דוגמאות)
(←‏פתרון)
שורה 51: שורה 51:
  
 
====פתרון====
 
====פתרון====
−
לא חח"ע כי יש הרבה פונקציות שנותנות ל-1,2 (יחד!) את אותם ערכים.
+
הפונקציה לא חח"ע כי יש הרבה פונקציות שנותנות ל-1,2 (יחד!) את אותם ערכים.
−
על: לכל זוג סדור <math>(n,m)</math> הפונקציה ששולחת את 1 ל-<math>n</math>, ואת 2 ל-<math>m</math>, היא המקור (את שאר הטבעיים נשלח לאן שנרצה).
+
 
 +
היא כן על: לכל זוג סדור <math>(n,m)</math> הפונקציה ששולחת את 1 ל-<math>n</math>, ואת 2 ל-<math>m</math>, היא המקור (את שאר הטבעיים נשלח לאן שנרצה).
  
 
===תרגיל===
 
===תרגיל===

גרסה מ־19:32, 29 בדצמבר 2017

חזרה לדף מערכי התרגול.

פונקציות

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

  • התחום של R הינו \mathrm{dom}(R)=\{a\in A|\exists b\in B,(a,b)\in R\}=\{(*,\;),(*,\;)\dots \}
  • התמונה של R הינה \mathrm{im}(R)=\{b\in B|\exists a\in A,(a,b)\in R\}=\{(\;,*),(\; ,*)\dots \}

הערה: ישירות מהגדרה מתקיים כי \mathrm{dom}(R)\subseteq A, \mathrm{im}(R)\subseteq B.

דוגמה:

  • R=\{(1,a),(2,b),(3,a),(a,1)\} אזי התחום הוא \mathrm{dom}(R)=\{a,1,2,3\} והתמונה הינה \mathrm{im}(R)=\{1,a,b\}.

הגדרה:

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


הגדרה:

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

פונקציה נקראת חד-חד ערכית אם בנוסף היחס ההפוך הוא חד ערכי.

כלומר:

f חח"ע אמ"מ f(x_1)=f(x_2)\Rightarrow x_1=x_2 אמ"מ x_1\neq x_2 \Rightarrow f(x_1)\neq f(x_2).


הגדרה:

תהא A קבוצה. פונקציית הזהות היא פונקציה f:A \to A המקיימת \forall a\in A: f(a)=a. נהוג לסמנה \mathrm{id}_A. פונקציית הזהות היא חח"ע ועל.

דוגמאות

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

  • f:\mathbb{N}\rightarrow\mathbb{Z} כאשר f(p)=p^2 חח"ע ואינה על.
  • f:\mathbb{Z}\rightarrow\mathbb{Z} כאשר f(p)=p^2 אינה חח"ע ואינה על.
  • f:\mathbb{N}\rightarrow\mathbb{N} כאשר f(x)=x-1 לא מוגדרת כי f(1)=?.
  • f:\mathbb{R}\rightarrow\mathbb{R} כאשר f(x)=x-1 חח"ע ועל.
  • f:\mathbb{N}\rightarrow\mathbb{N} \cup \{ 0\} כאשר f(x)=x-1 חח"ע ועל.
  • f:\mathbb{N}\rightarrow\mathbb{R} כאשר f(x)=x-1 חח"ע ואינה על.
  • תהא פונקציה f:A\to B אזי g:A\to \mathrm{im}(f) המוגדרת לכל a\in A לפי g(a)=f(a) היא על (במילים: פשוט חושבים על הטווח של g להיות התמונה של f).
  • תהא A\subseteq B אזי הפונקציה i : A\to B המוגדרת לכל a\in A לפי i(a)=a נקראת פונקציה ההכלה (אם A=B זו פונקצית הזהות). פונקצית ההכלה היא חח"ע.

תרגיל

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

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

פתרון

הפונקציה לא חח"ע כי יש הרבה פונקציות שנותנות ל-1,2 (יחד!) את אותם ערכים.

היא כן על: לכל זוג סדור (n,m) הפונקציה ששולחת את 1 ל-n, ואת 2 ל-m, היא המקור (את שאר הטבעיים נשלח לאן שנרצה).

תרגיל

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

פתרון

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

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

תרגיל

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

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

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

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

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

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

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

הערה: אם מתייחסים לפונקציות כאל יחסים - מקבלים את ההגדרה של הרכבת יחסים.

משפט:

  • אם g \circ f חח"ע אזי f חח"ע.
  • אם g \circ f על אזי g על.
  • מסקנה: אם g \circ f חח"ע ועל אזי f חח"ע ו-g על.

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

הערה: לכל פונקציה f מתקיים f\circ \mathrm{id} =f וגם \mathrm{id} \circ f =f.

הגדרה: תהי f פונקציה f:A\rightarrow B. פונקציה g:B\rightarrow A תיקרא הפונקציה ההופכית ל-f אם f\circ g = \mathrm{id}_B וגם g\circ f = \mathrm{id}_A. במקרה זה נסמן את g על ידי f^{-1}, ונאמר שהפונקציה f היא הפיכה.

תרגיל (בהרצאה):

הוכיחו כי פונקציה f הפיכה אם"ם היא חח"ע ועל.

הוכחה:

אם f הפיכה, אזי f\circ f^{-1} = \mathrm{id}_B וגם f^{-1}\circ f = \mathrm{id}_A. מכיוון שפונקציית הזהות הינה חח"ע ועל, נובע ש-f חח"ע ועל לפי משפט קודם.

אם f חח"ע ועל, אז נגדיר g:B\to A ע"י: עבור a\in A קיים (כי f על) b\in B יחיד (כי f חח"ע) כך ש-f(a)=b . נגדיר g(b):=a. תרגיל: בדקו כי g היא ההופכית של f.

מקור: https://math-wiki.com/index.php?title=תרגול_12_תשעז&oldid=74191