שינויים
/* תרגיל */
'''הגדרה:'''
*יחס <math>R</math> מ-<math>A</math> ל-<math>B</math> נקרא '''על''' אם <math>\forall b\in B \exists a\in A:(a,b)\in R</math> כלומר <math>\mathrm{im}(R)=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>(a,b)\in R\leftrightarrow b=R(a)</math>.
ובאופן כללי <math>f:A\to B \;\; , a \mapsto f(a)</math>.
(<math>A</math> נקרא תחום (הגדרה) של הפונקציה ו-<math>B</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>.
'''הגדרה:'''
* תהא פונקציה <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>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>(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, b_m\} </math> . כאשר כל האיברים ב-<math>A</math> שונים זה מזה וכנ"ל ב-<math>B</math>.
===תרגיל===
על: לא. נבחר <math>A=\{1,\dots,7\}</math>. למשל לקבוצה <math>\{ \{ 1,2\}, \{ 3,4\} \}\in P(P(A))</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_ka\in A</math> כך ש-<math>f_k(a_ka)= y</math> .באותו אופן בנוסף, מהנחת האינדוקציה קיים <math>a_{k-1}b\in A</math> כך ש <math>f_{k-1}\circ \dots \circ f_1(a_{k-1}b)=a_ka</math> נמשיך באופן דומה (או באינקודציה) ולכן נקבלונקבל <math>(f_k \circ \dots \circ f_1)(a_1b)=(f_k \circ \dots \circ f_2)(a_2)=\\ \dots =f_k\circ f_{k-1} \circ \dots \circ f_1)(a_{k-1}b) = f_k(a_ka)=y</math>. מש"ל.
הפיכות: נובע מחח"ע יחד עם על.
קיבלנו ש-<math>g</math> חח"ע ועל, כלומר הפיכה. נכפול את הנתון ב-<math>g^{-1}</math> מימין ומשמאל ונקבל כי <math>f=g^{-1}\circ g^{-1}</math> ואז <math>f</math> הפיכה כהרכבה של פונקציות הפיכות.
===תרגיל=פונקציות המכבדות יחס שקילות ==תהיינה '''הגדרה.''' תהי <math>f,g:\mathbb{N}A\rightarrow \mathbb{N}B</math> פונקציות כך ש-פונקציה, ויהי <math>R</math> יחס שקילות על <math>A</math>. אומרים כי '''<math>f</math> מוגדרת היטב על <math>A/R</math>''' אם <math>\forall a,b\in A:(na,b)\in R\Rightarrow f(a)=gf(3n-1b)</math>.
====פתרון====