'''[[מתמטיקה בדידה - מערך תרגול|חזרה למערכי התרגול]]'''
==המשך פונקציות- פונקציות על תת-קבוצות==
'''הגדרה.''' תהי <math>f:X\rightarrow Y</math> פונקציה, ויהיו תת קבוצות <math>A\subseteq X,B\subseteq Y</math>. אזי <math>f(A)=\{f(a)|a\in A\}</math>, <math>f^{-1}(B)=\{a\in A|f(a)\in B\}</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>A_1\subseteq A_2</math> אזי <math>f(A_1)\subseteq f(A_2)</math># אם <math>B_1\subseteq B_2</math> אזי <math>f^{-1}(B_1)\subseteq f^{-1}(B_2)</math># הוכיחו/הפריכו טענות מקבילות עם משלים של קבוצות. ==== תרגיל ====הוכיחו/הפריכו: תהי f פונקציה <math>f:X \to Y</math> ותהיינה <math>Z, W\; subseteq X, A,B \subset subseteq Y</math>. אזי # <math>f^{-1}[A]\cap f^{-1}[B]=f^{-1}[A\cap B]</math> # <math>f^{-1}[A]\cup f^{-1}[B]=f^{-1}[A\cup B]</math> # <math>f^{-1}[A\setminus B]=f^{-1}[A]\setminus f^{-1}[B]</math> # <math>f^{-1}[A]\triangle f^{-1}[B]=f^{-1}[A\triangle B]</math># <math>f[Z]\triangle f[W]=f[Z\triangle W]</math> פתרון: תחשבו. עדיף את שני האחרונים, כי הראשונים לפעמים נעשים בהרצאה. ====תרגיל====הוכח/הפרך: תהיינה <math>A,B \subseteq X</math> ותהי f פונקציה <math>f:X \to Y</math>. אזי <math>f(A)\cap f(B)=f(A\cap B)</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>X,Y</math> שתי קבוצות, ותהי תהי <math>f:X\rightarrow Y</math> פונקציה כלשהי. נגדיר את הפונקציה ותהי <math>g:P(A\subseteq Y)\rightarrow P(X)</math> על ידי . הוכח <math>g f(B)=f^{-1}(BA)) \subseteq A</math>.בדוק את הקשר בין החח"עוקיים שיוויון אם <math>f</math> על של f לבין אלה של g. (כלומר, מה גורר את מה בהכרח).
'''פתרון.'''
תהי f חח"ע שאינה על (קל למצוא כאלה). אזי יהא <math>\exists y\in Y\forall f(x) \in X:f(xf^{-1}(A))\neq y</math>. לכן כאשר <math>g(Y)=x\in f^{-1}(YA)=</math> ולכן <math> f^{-1}(Y/x)\{y\}=g(Y/\{y\})in A </math> בסתירה לחח"ע של g.
נראה את ההכלה בכיוון השני אם <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 חח"ע אך g אינה כזו''':\{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>.בדוק את הקשר בין החח"ע/על של f לבין אלה של g. כפי שראינו לעיל(כלומר, ניתן ישר להסיק ש-f הינה עלמה גורר את מה בהכרח).
'''פתרון.'''
נוכיח שאם 1. נמצא ב XI הטענה ''' f על אזי אמ"מ g חח"ע; '''בכיוון אחד- נתון ש f על. נניח בשלילה שg אינה חח"ע, אזי קיימות שתי קבוצות <math>f^{-1}(B\neq C \in P(Y)</math> כך ש <math>=g(B)=g(CA)=f^{-1}(A)</math>. בלי הגבלת הכלליות, נניח שקיים איבר <math>c\in C</math> כך ש <math>c\notin B</math>. מכיוון ש-נפעיל את f על, קיים איבר a כך שני הצדדים ונקבל (בגלל ש <math>f(aעל)=c</math>, לכן <math>a\in gB=f(f^{-1}(B)</math>, ואז קיים <math>b\in B</math> כך ש<math>)=f(af^{-1}(A))=bA</math> ולכן b=c בסתירה.
בכיוון השני- נתון כי 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.
*אם כן, הוכחנו ש-'''f על אם"ם 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=\mathbb{Z}x, Y=y \{0\}in X</math>. אזי קיימת פונקציה f יחידה מX לY. פונקציה זו אינה חח"ע כמובן, אך g כן חח"ע שכן שונים כך ש <math>gf(\{\}x)\neq g=f(y)</math>. נביט בנקודון <math>A=\{0x\})</math> ואלה הקבוצות היחידות בקבוצת החזקה של Y.
כיוון ש g על קיימת <math>B\in P(Y)</math> כך ש <math>f^{-1}(B)=g(B)=A</math>
*לכן '''יתכן ו-g חח"ע אך <math> \{f אינה כזו'''.(x)\}= f(A)= f(f^{-1}(B))\subseteq B </math>
ולכן <math>\{y,x\}\subseteq f^{-1}(\{f(x)=f(y)\})= f^{-1}(\{f(x)\}) \subseteq f^{-1}(B)=g(B)=A=\{x\}</math>
נניח וg על ונניח בשלילה ש-f אינה חח"ע. לכן קיימים <math>a\{y,b x\in X</math> שונים כך ש <math>f(x)=f(y)</math>. נביט בנקודון <math>A=}\subseteq \{x\}</math> נניח וקיימת כלומר <math>B\in P(Y)</math> כך ש <math>g(B)x=A</math>, לכן <math>f(x)\in B</math>. אבל אז בעצם גם <math>f(y)\in B</math> ולכן <math>y\in g(B)=A</math> בסתירה. לכן f חח"עסתירה.
מכאן ניתן להסיק כי שאר הגרירות אינן מוכרחות:
נניח * '''ייתכן ו-f חח"ע, הוכחנו כבר שבהכרח <math>f^{-1}אך g אינה כזו''' (ניקח f(A))=A</math> לכל A תת קבוצה של X. נובע ש <math>חח"ע שאינה על אזי g(f(A אינה חח"ע לפי 1))=A</math> ולכן g הינה על.
* '''יתכן ו-g חח"ע אך f אינה כזו'''. (ניקח g חח"ע שאינה על אזי f אינה חח"ע לפי 2)
*סה"כ, הוכחנו ש'''ייתכן ו-f על אך g אינה כזו ''' (ניקח f על שאינה חח"ע אם"ם אזי g הינה אינה על'''.לפי 2)
* '''ייתכן ו-g על אך f אינה כזו ''' (ניקח g על שאינה חח"ע אזי f אינה על לפי 1)
ניקח f פונקציה חח"ע שאינה על, לכן g היא על. אתם מוזמנים לתת דוגמאות למסקנות לעיל
למשל:
יהיו <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:A\rightarrow B</math>, ויהי R יחס שקילויות על A. אומרים כי '''f מוגדרת היטב על <math>A/R</math>''' אם <math>\forall a,b\in A:(a,b)\in R\Rightarrow f(a)=f(b)</math>
באופן דומה ניקח כלומר אם a שקול ל b אזי <math>f על שאינה חח"ע, לכן g אינה על(a)=f(b)</math>.
למה זה טוב?
כדי שנוכל להגדיר פונקציה על קבוצת המנה <math>g:A/R \to B </math> ע"י <math>[a]_R \mapsto f(a) </math>
*לכן '''ייתכן ו-f הינה על אך באופן מפורש <math>g אינה על'''=\{([a],f(a))|a\in A\}</math>.
טענה: g אכן פונקציה
הוכחה:
'''הגדרה1.''' תהי <math>f:X\rightarrow Y</math> ותהי <math>A\subseteq X</math>g שלמה - "לפי העיניים". הפונקציה '''f מצומצמת לA''' מוגדרת על ידי: <math>f|_A:A\rightarrow Y</math> כלל ההתאמה מנוסח כך ש <math>f|_A(a)=f(a)</math>שהיחס הוא שלם.
'''דוגמא2.''' נביט בg חד ערכית- נניח <math>f:\mathbb{R}\rightarrow[a]=[b]</math>, צ"ל <math>g([a])=g([b])</math>. מהנתון ש <math>[a]=[b]</math> נובע ש <math>(a,b)\mathbb{in R}</math> המוגדרת , ולכן, לפי הגדרת f כמוגדרת היטב על ידי קבוצת המנה, מתקיים <math>f(xa)=x^2f(b)</math> ואינה חח"ע. נכון לומר שהפונקציה המצומצמת , ולפי הגדרת g מתקיים <math>g([a])=f|_{\mathbb{N}}(a)=f(b)=g([b])</math> כן חח"ע.
==== דוגמא ====
נגדיר על השלמים יחס שקילות ע"י x~y אמ"מ y=x or y=-x.
'''תרגיל.'''בדקו מי מהבאות היא פונקציה מקבוצת המנה לשלמים:תהי # <math>f\{([n]_{~},n):Xn\rightarrow Yin \mathbb{Z} \}</math> פונקציה, הוכח שקיימת קבוצה A כך ש# <math>f|_A\{([n]_{~},n^2): n\in \mathbb{Z} \}</math> חח"ע
'''פתרון.'''====דוגמא ====האם f על הרציונאליים המוגדרת על ידי <math>f\bigg(\frac{p}{q}\bigg)=p</math> מוגדרת היטב?
פייי זו שאלה קשה. תזכירו לנו אותה כאשר נגיע לאקסיומת הבחירה. (שכן נביט ב'''פתרון'''לא! כזכור הרציונאליים הם קבוצת מנה של <math>\mathbb{f^Z}\times \mathbb{N}</math>. לפי היחס שהגדרנו מתקיים <math>\frac{-1}({3}=\frac{y2}{6}</math> אבל לא מתקיים <math>f\bigg(\frac{1}{3}\bigg)|y=1\in Ynot=2=f\bigg(\frac{2}{6}\bigg)</math> ונרצה לבחור איבר יחיד מבין כל קבוצה כזו. אקסיומת הבחירה היא זו המאפשרת לנו לבצע בחירה זו בשלום.)
במילים: לא ברור לאן f שולחת את השבר שליש!
'''הגדרה.''' תהי <math>fהערה:A\rightarrow A</math>, ויהי R בכוונה ניסחנו את התרגיל באופן הרומז על יחס שקילויות על Aהשקילויות מבלי לומר אותו במפורש. אומרים כי זו הדרך בה נתקל במושג '''f מוגדרת מוגדר היטב על <math>A/R</math>''' אם <math>\forall a,b\in A:(a,b)\in R\rightarrow (f(a),f(b)\in R</math>במהלך התואר - יחס השקילויות יהיה מרומז בלבד.
'''תרגיל מוטיבציה להגדרה לעיל.'''===פונקציה מצומצמת===
המוטיבציה להגדרה הזו היא היכולת לגזור ממנה פונקציה על חבורת המנה'''הגדרה. נגדיר יחס ''' תהי <math>f:X\rightarrow Y</math> ותהי <math>A\subseteq X</math>. הפונקציה '''f מצומצמת לA''' מוגדרת על חבורת המנה ידי: <math>g=f|_A:A\{rightarrow Y</math> כך ש-<math>f|_A([a],[)=f(a)])|a\in A\}</math>. נוכיח ש-g הינה חד-ערכית ולכן פונקציה.
'''הוכחהדוגמא.'''נביט ב-<math>f:\mathbb{R}\rightarrow\mathbb{R}</math> המוגדרת על ידי <math>f(x)=x^2</math> ואינה חח"ע. נכון לומר שהפונקציה המצומצמת <math>f|_{\mathbb{N}}</math> כן חח"ע.
נניח וקיימים <math>a,b\in A</math> כך ש <math>[a]=[b]</math>. לכן <math>(a,b)\in R</math> ולכן <math>(f(a),f(b))\in R</math> ולכן <math>[f(a)]=[f(b)]</math>. לכן לא ייתכן מצב בו <math>(x,y),(x,z)\in g</math> אבל <math>y\neq z</math>.
'''דוגמאתרגיל.'''האם הפונקציה תהי <math>f על הרציונאליים המוגדרת על ידי :X\rightarrow Y</math> פונקציה, הוכח שקיימת קבוצה A כך ש-<math>f|_A</math> חח"ע עם אותה התמונה כמו הפונקציה המקורית (\frac{p}{q}כלומר <math>im(f|_A)=pim(f)</math> מוגדרת היטב?).
'''פתרון.'''
יש לשים לב שלא באמת הגדרנו את הפונקציה על הרציונאליים, אלא על אוסף הזוגות הסדורים של שלמים נגדיר לכל <math>y\in im(p,qf)</math> כך שהאיבר הימני שונה מאפס. נגדיר על קבוצה זו את יחס השקילויות R המוגדר על ידי הקבוצה של המקורות שלו <math>B_y:=f^{-1}((p,q),(a,b)\{y\})</math>כעת נבחר מכל <math>B_y</math> איבר יחיד <math>x_y\in RB_y</math> אם . נגדיר <math>pbA=qa\{x_y | y\in im (f)\}</math>. נראה כי כיוון שבחרנו מקור '''לכל''' תמונה, ובחרנו מקור '''אחד''' אזי <math>f אינה מוגדרת היטב בתנאים אלו:|_A</math> חח"ע עם אותו טווח של <math>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>חח"ע.
בכוונה ניסחנו הוכחה: אם נצמצם את התרגיל באופן הרומז על יחס השקילויות מבלי לומר אותו במפורש. זו הדרך בה נתקל במושג הטווח והתחום של הפונקציות, <math>f'מוגדר היטב:A\to Im(f), g|_{Im(f)}:Im(f)\to C</math>, נקבל כי <math>g\circ f=g|_{Im(f)}\circ f'</math> חח"ע ובנוסף <math>f'</math> חח"ע ועל. מכאן ש <math>g|_{Im(f)}=g\circ f\circ f' במהלך התואר ^{- יחס השקילויות יהיה מרומז בלבד1}</math> חח"ע כהרכבה של חח"ע.
