שינויים
/* תרגיל */
'''[[מתמטיקה בדידה - מערך תרגול|חזרה למערכי התרגול]]'''
==המשך פונקציות- פונקציות על תת-קבוצות==
שימו לב להבדל בין התמונה ההפוכה <math>f^{-1}(B)</math> לבין הפונקציה ההופכית <math>f^{-1}(y)</math>. התמונה ההפוכה איננה מניחה כי הפונקציה f הפיכה. הדרך להבחין בין פונקציה הפיכה לתמונה ההפוכה היא לבדוק האם בין הסוגריים נמצא ''איבר'' של התמונה (בדוגמאות לעיל זהו <math>y \in Y</math>) או שנמצאת ''תת-קבוצה'' של התמונה (בדוגמאות לעיל זו <math>B\subseteq Y</math>).
'''פתרון.'''
נפריך על ידי דוגמא נגדית. נניח וf אינה חח"ע, כלומר קיימים <math>x\neq y </math> כך ש <math>f(x)=f(y)</math>. ניקח <math>A=\{x\},B=\{y\}</math> אזי:
<math>f(A)\cap f(B) = \{f(x)\} \neq \phi = f(\{\}) = f(A\cap B)</math>
'''הערה''' תמיד מתקיים <math>f(A\cap B)\subseteq f(A)\cap f(B)</math>
'''תרגיל.הערה'''הטענה נכונה אם <math>f</math> חח"ע. הוכיחו! ===תרגיל (בהרצאה בד"כ)===
תהי <math>f:X\rightarrow Y</math> ותהי <math>A\subseteq X</math>. הוכח <math>A \subseteq f^{-1}(f(A))</math>. וקיים שיוויון אם <math>f</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>
===תרגיל (בXI)===
תהי <math>f:X\rightarrow Y</math> ותהי <math>A\subseteq Y</math>. הוכח <math> f(f^{-1}(A)) \subseteq A</math>. וקיים שיוויון אם <math>f</math> על
'''פתרון.'''
יהא <math>f(x) \in f(f^{-1}(A))</math> כאשר <math>x\in f^{-1}(A)</math> ולכן <math> f(x)\in A </math>.
נראה את ההכלה בכיוון השני אם <math>f</math> על:
יהא <math> a\in A </math> כיוון ש f על <math>\exists x\in X : f(x)=a </math> לכן <math> x \in f^{-1}(A) </math>. ואז <math>a=f(x)\in f(f^{-1}(A)) </math>
דוגמא שלא מתקיים שיוויון <math>f:\{1\}\to \{1,2\}</math> המוגדרת <math>1\mapsto 1</math>. אזי נגדיר <math>B=\{1,2\}</math> ומתקיים <math> f(f^{-1}(B)) =\{1\}\neq B</math>.
יהיו <math>X,Y</math> שתי קבוצות, ותהי <math>f:X\rightarrow Y</math> פונקציה כלשהי. נגדיר את הפונקציה <math>g:P(Y)\rightarrow P(X)</math> על ידי <math>g(B)=f^{-1}(B)</math>.
'''פתרון.'''
1. נמצא ב XI הטענה ''' f על אמ"מ g חח"ע '''בכיוון אחד- נתון ש f על. נניח <math>f^{-1}(B)=g(B)=g(A)=f^{-1}(A)</math> נפעיל את f על שני הצדדים ונקבל (בגלל ש f על) <math>B=f(f^{-1}(B))=f(f^{-1}(A))=A(</math>
בכיוון השני- נתון כי g חח"ע. נניח בשלילה כי f אינה על אזי <math>\exists y\in Y\forall x\in X:f(x)\neq y</math> לכן <math>g(Y)=f^{-1}(Y)=f^{-1}(Y/\{y\})=g(Y/\{y\})</math> בסתירה לחח"ע של g.
2. ''' f חח"ע אמ"מ g על '''
בכיוון אחד- נתון f חח"ע. אזי <math>g(f(A))=f^{-1}(f(A))=A</math> ולכן g על ( עבור A המקור שלה יהיה <math>f(A)</math> )
בכיוון השני- נתון g על. נניח בשלילה ש f אינה חח"ע אזי קיימים <math>x,y \in X</math> שונים כך ש <math>f(x)=f(y)</math>. נביט בנקודון <math>A=\{x\}</math> כיוון ש g כלקיימת על קיימת <math>B\in P(Y)</math> כך ש <math>f^{-1}(B)=g(B)=A</math> לכן <math>B\subseteq {f(f^{-1x)\}(B)) = f(A)= \{f(x)\} </math> כיוון ש B אינה ריקה נקבל ש <math>B=\f^{f-1}(xB))\} subseteq B </math> לכן ולכן <math> \{y,x\}=A=g(B)=\subseteq f^{-1}(B\{f(x)=f(y)\})=f^{-1}(\{f(x)\})\supseteq subseteq f^{-1}(B)=g(B)=A=\{x,\}</math> לכן <math>\{y,x\}\subseteq \{x\}</math>. ולכן כלומר <math>x=y</math>. סתירה.
מכאן ניתן להסיק כי שאר הגרירות אינן מוכרחות:
למשל:
יהיו <math>X=\mathbb{Z}, Y=\{0\}</math>. אזי קיימת פונקציה f יחידה מX לY. פונקציה זו אינה חח"ע כמובן, אך g כן חח"ע שכן <math>g(\{\})\neq g(\{0\})</math> ואלה הקבוצות היחידות בקבוצת החזקה של Y.
==== תרגיל (בהרצאה בד"כ) ====
תהיינה A,B קבוצות לא ריקות. הוכיחו כי:
# אם קיימת <math>f:A\to B</math> חח"ע אזי קיימת <math>g:B\to A</math> על.
# אם A,B סופיות: קיימת <math>f:A\to B</math> חח"ע אמ"מ <math>|A|\leq |B|</math>
# אם A,B סופיות: קיימת <math>f:A\to B</math> על אמ"מ <math>|B|\leq |A|</math>
=== פונקציות המכבדות יחס שקילות ==='''הגדרה.''' תהי <math>f:XA\rightarrow YB</math> ותהי <math>, ויהי R יחס שקילויות על A\subseteq X</math>. הפונקציה אומרים כי '''f מצומצמת לA''' מוגדרת היטב על ידי: <math>f|_A:A\rightarrow Y/R</math> כך ש ''' אם <math>\forall a,b\in A:(a,b)\in R\Rightarrow f|_A(a)=f(ab)</math>.
למה זה טוב?
כדי שנוכל להגדיר פונקציה על קבוצת המנה <math>g:A/R \to B </math> ע"י <math>[a]_R \mapsto f(a) </math>
1. g שלמה - "לפי העיניים". כלל ההתאמה מנוסח כך שהיחס הוא שלם.
במילים: לא ברור לאן f שולחת את השבר שליש!
הערה: בכוונה ניסחנו את התרגיל באופן הרומז על יחס השקילויות מבלי לומר אותו במפורש. זו הדרך בה נתקל במושג 'מוגדר היטב'במהלך התואר - יחס השקילויות יהיה מרומז בלבד. ===פונקציה מצומצמת=== 'דוגמא''הגדרה.'''האם תהי <math>f:X\rightarrow Y</math> ותהי <math>A\subseteq X</math>. הפונקציה '''f מצומצמת לA''' מוגדרת על הרציונאליים ידי: <math>f|_A:A\rightarrow Y</math> כך ש-<math>f|_A(a)=f(a)</math>. '''דוגמא.''' נביט ב-<math>f:\mathbb{R}\rightarrow\mathbb{R}</math> המוגדרת על ידי <math>f(x)=x^2</math> ואינה חח"ע. נכון לומר שהפונקציה המצומצמת <math>f|_{\fracmathbb{pN}{q}</math> כן חח"ע. '''תרגיל.'''תהי <math>f:X\rightarrow Y</math> פונקציה, הוכח שקיימת קבוצה A כך ש-<math>f|_A</math> חח"ע עם אותה התמונה כמו הפונקציה המקורית (כלומר <math>im(f|_A)=pim(f)</math> מוגדרת היטב?).
'''פתרון.'''
'''אזהרה!''' ההוכחה מתבססת על אקסיומת הבחירה (נפגש איתה בהמשך)==== תרגיל ====תהיינה <math>((2f:A\to B,6),(1,3))g:B\in Rto C</math> אולם פונקציות כך ש <math>g\circ f(2,6)=(2,1),f(1,3)=(1,1)</math> וחח"ע. הוכיחו כי <math>g|_{Im((2,1f),(1,1))\notin R}</math>חח"ע.