88-195 בדידה לתיכוניסטים תשעא/מערך שיעור/שיעור 5

המשך פונקציות - פונקציות על תת-קבוצות

תמונות חלקיות

הגדרה. תהי [math]\displaystyle{ f:X\rightarrow Y }[/math] פונקציה, ויהיו תת קבוצות [math]\displaystyle{ A\subseteq X,B\subseteq Y }[/math]. אזי התמונה החלקית של A תחת f היא התת-קבוצה [math]\displaystyle{ f(A)=\{f(a)|a\in A\} }[/math], והתמונה החלקית ההפוכה של B תחת f היא התת-קבוצה [math]\displaystyle{ f^{-1}(B)=\{a\in X|f(a)\in B\} }[/math].

שימו לב להבדל בין התמונה ההפוכה [math]\displaystyle{ f^{-1}(B) }[/math] לבין הפונקציה ההופכית [math]\displaystyle{ f^{-1}(y) }[/math]. התמונה ההפוכה איננה מניחה כי הפונקציה f הפיכה. הדרך להבחין בין פונקציה הפיכה לתמונה ההפוכה היא לבדוק האם בין הסוגריים נמצא איבר של התמונה (בדוגמאות לעיל זהו [math]\displaystyle{ y \in Y }[/math]) או שנמצאת תת-קבוצה של התמונה (בדוגמאות לעיל זו [math]\displaystyle{ B\subseteq Y }[/math]).

דוגמאות

תהא [math]\displaystyle{ D:\mathbb{R}\to \mathbb{R} }[/math] פונקצית דריכלה. אזי [math]\displaystyle{ D(\mathbb{Q})=\{1\},D^{-1}(\{1\})=\mathbb{Q}=D^{-1}((0.5, 18)) }[/math]

תהא [math]\displaystyle{ f:X\to Y }[/math] פונקצית . אזי [math]\displaystyle{ f^{-1}(Y)=X }[/math]

תהא [math]\displaystyle{ f:\mathbb{R}\to \mathbb{Z} }[/math] פונקצית הערך השלם התחתון. אזי [math]\displaystyle{ f((-0.5,3/4))=\{-1,0\},f^{-1}(\{1\})=[1,2) }[/math]

תכונות

אם [math]\displaystyle{ A_1\subseteq A_2 }[/math] אזי [math]\displaystyle{ f(A_1)\subseteq f(A_2) }[/math]
אם [math]\displaystyle{ B_1\subseteq B_2 }[/math] אזי [math]\displaystyle{ f^{-1}(B_1)\subseteq f^{-1}(B_2) }[/math]
הוכיחו/הפריכו טענות מקבילות עם משלים של קבוצות.

תרגיל

הוכיחו/הפריכו: תהי f פונקציה [math]\displaystyle{ f:X \to Y }[/math] ותהיינה [math]\displaystyle{ Z,W\subseteq X, A,B \subseteq Y }[/math]. אזי

[math]\displaystyle{ f^{-1}[A]\cap f^{-1}[B]=f^{-1}[A\cap B] }[/math]
[math]\displaystyle{ f^{-1}[A]\cup f^{-1}[B]=f^{-1}[A\cup B] }[/math]
[math]\displaystyle{ f^{-1}[A\setminus B]=f^{-1}[A]\setminus f^{-1}[B] }[/math]
[math]\displaystyle{ f^{-1}[A]\triangle f^{-1}[B]=f^{-1}[A\triangle B] }[/math]
[math]\displaystyle{ f[Z]\triangle f[W]=f[Z\triangle W] }[/math]

פתרון: תחשבו. עדיף את שני האחרונים, כי הראשונים לפעמים נעשים בהרצאה.

תרגיל

הוכח/הפרך: תהיינה [math]\displaystyle{ A,B \subseteq X }[/math] ותהי f פונקציה [math]\displaystyle{ f:X \to Y }[/math]. אזי [math]\displaystyle{ f(A)\cap f(B)=f(A\cap B) }[/math]

פתרון.

נפריך על ידי דוגמא נגדית. נניח וf אינה חח"ע, כלומר קיימים [math]\displaystyle{ x\neq y }[/math] כך ש [math]\displaystyle{ f(x)=f(y) }[/math]. ניקח [math]\displaystyle{ A=\{x\},B=\{y\} }[/math] אזי:

[math]\displaystyle{ f(A)\cap f(B) = \{f(x)\} \neq \phi = f(\{\}) = f(A\cap B) }[/math]

הערה תמיד מתקיים [math]\displaystyle{ f(A\cap B)\subseteq f(A)\cap f(B) }[/math]

הערה הטענה נכונה אם [math]\displaystyle{ f }[/math] חח"ע. הוכיחו!

תרגיל (בהרצאה בד"כ)

תהי [math]\displaystyle{ f:X\rightarrow Y }[/math] ותהי [math]\displaystyle{ A\subseteq X }[/math]. הוכח [math]\displaystyle{ A \subseteq f^{-1}(f(A)) }[/math]. וקיים שיוויון אם [math]\displaystyle{ f }[/math] חח"ע

פתרון.

יהא [math]\displaystyle{ a\in A }[/math] אזי [math]\displaystyle{ f(a)\in f(A) }[/math] ולכן [math]\displaystyle{ a\in f^{-1}(f(A)) }[/math].

נראה את ההכלה בכיוון השני אם [math]\displaystyle{ f }[/math] חח"ע:

יהא [math]\displaystyle{ x\in f^{-1}(f(A)) }[/math] לכן [math]\displaystyle{ f(x) \in f(A) }[/math] לכן [math]\displaystyle{ \exists a\in A : f(x)=f(a) }[/math]. כיוון ש [math]\displaystyle{ f }[/math] חח"ע נובע כי [math]\displaystyle{ x=a\in A }[/math]

דוגמא שלא מתקיים שיוויון [math]\displaystyle{ f:\{1,2\}\to \{1\} }[/math] (יש דרך אחת להגדיר את הפונקציה). אזי נגדיר [math]\displaystyle{ A=\{2\} }[/math] ומתקיים [math]\displaystyle{ f^{-1}(f(A))=\{1,2\}\neq A }[/math]

תרגיל (בXI)

תהי [math]\displaystyle{ f:X\rightarrow Y }[/math] ותהי [math]\displaystyle{ A\subseteq Y }[/math]. הוכח [math]\displaystyle{ f(f^{-1}(A)) \subseteq A }[/math]. וקיים שיוויון אם [math]\displaystyle{ f }[/math] על

פתרון.

יהא [math]\displaystyle{ f(x) \in f(f^{-1}(A)) }[/math] כאשר [math]\displaystyle{ x\in f^{-1}(A) }[/math] ולכן [math]\displaystyle{ f(x)\in A }[/math].

נראה את ההכלה בכיוון השני אם [math]\displaystyle{ f }[/math] על:

יהא [math]\displaystyle{ a\in A }[/math] כיוון ש f על [math]\displaystyle{ \exists x\in X : f(x)=a }[/math] לכן [math]\displaystyle{ x \in f^{-1}(A) }[/math]. ואז [math]\displaystyle{ a=f(x)\in f(f^{-1}(A)) }[/math]

דוגמא שלא מתקיים שיוויון [math]\displaystyle{ f:\{1\}\to \{1,2\} }[/math] המוגדרת [math]\displaystyle{ 1\mapsto 1 }[/math]. אזי נגדיר [math]\displaystyle{ B=\{1,2\} }[/math] ומתקיים [math]\displaystyle{ f(f^{-1}(B)) =\{1\}\neq B }[/math].

תרגיל ממבחן (קצת משודרג)

יהיו [math]\displaystyle{ X,Y }[/math] שתי קבוצות, ותהי [math]\displaystyle{ f:X\rightarrow Y }[/math] פונקציה כלשהי. נגדיר את הפונקציה [math]\displaystyle{ g:P(Y)\rightarrow P(X) }[/math] על ידי [math]\displaystyle{ g(B)=f^{-1}(B) }[/math]. בדוק את הקשר בין החח"ע/על של f לבין אלה של g. (כלומר, מה גורר את מה בהכרח).

פתרון.

1. נמצא ב XI הטענה f על אמ"מ g חח"ע בכיוון אחד- נתון ש f על. נניח [math]\displaystyle{ f^{-1}(B)=g(B)=g(A)=f^{-1}(A) }[/math] נפעיל את f על שני הצדדים ונקבל (בגלל ש f על) [math]\displaystyle{ B=f(f^{-1}(B))=f(f^{-1}(A))=A }[/math]

בכיוון השני- נתון כי g חח"ע. נניח בשלילה כי f אינה על אזי [math]\displaystyle{ \exists y\in Y\forall x\in X:f(x)\neq y }[/math] לכן [math]\displaystyle{ g(Y)=f^{-1}(Y)=f^{-1}(Y/\{y\})=g(Y/\{y\}) }[/math] בסתירה לחח"ע של g.

2. f חח"ע אמ"מ g על בכיוון אחד- נתון f חח"ע. אזי [math]\displaystyle{ g(f(A))=f^{-1}(f(A))=A }[/math] ולכן g על ( עבור A המקור שלה יהיה [math]\displaystyle{ f(A) }[/math] )

בכיוון השני- נתון g על. נניח בשלילה ש f אינה חח"ע אזי קיימים [math]\displaystyle{ x,y \in X }[/math] שונים כך ש [math]\displaystyle{ f(x)=f(y) }[/math]. נביט בנקודון [math]\displaystyle{ A=\{x\} }[/math]

כיוון ש g על קיימת [math]\displaystyle{ B\in P(Y) }[/math] כך ש [math]\displaystyle{ f^{-1}(B)=g(B)=A }[/math]

לכן [math]\displaystyle{ \{f(x)\}= f(A)= f(f^{-1}(B))\subseteq B }[/math]

ולכן [math]\displaystyle{ \{y,x\}\subseteq f^{-1}(\{f(x)=f(y)\})= f^{-1}(\{f(x)\}) \subseteq f^{-1}(B)=g(B)=A=\{x\} }[/math]

לכן [math]\displaystyle{ \{y,x\}\subseteq \{x\} }[/math] כלומר [math]\displaystyle{ x=y }[/math]. סתירה.

מכאן ניתן להסיק כי שאר הגרירות אינן מוכרחות:

ייתכן ו-f חח"ע אך g אינה כזו (ניקח f חח"ע שאינה על אזי g אינה חח"ע לפי 1)

יתכן ו-g חח"ע אך f אינה כזו. (ניקח g חח"ע שאינה על אזי f אינה חח"ע לפי 2)

ייתכן ו-f על אך g אינה כזו (ניקח f על שאינה חח"ע אזי g אינה על לפי 2)

ייתכן ו-g על אך f אינה כזו (ניקח g על שאינה חח"ע אזי f אינה על לפי 1)

אתם מוזמנים לתת דוגמאות למסקנות לעיל

למשל: יהיו [math]\displaystyle{ X=\mathbb{Z}, Y=\{0\} }[/math]. אזי קיימת פונקציה f יחידה מX לY. פונקציה זו אינה חח"ע כמובן, אך g כן חח"ע שכן [math]\displaystyle{ g(\{\})\neq g(\{0\}) }[/math] ואלה הקבוצות היחידות בקבוצת החזקה של Y.

תרגיל (בהרצאה בד"כ)

תהיינה A,B קבוצות לא ריקות. הוכיחו כי:

אם קיימת [math]\displaystyle{ f:A\to B }[/math] חח"ע אזי קיימת [math]\displaystyle{ g:B\to A }[/math] על.
אם A,B סופיות: קיימת [math]\displaystyle{ f:A\to B }[/math] חח"ע אמ"מ [math]\displaystyle{ |A|\leq |B| }[/math]
אם A,B סופיות: קיימת [math]\displaystyle{ f:A\to B }[/math] על אמ"מ [math]\displaystyle{ |B|\leq |A| }[/math]

פונקציות המכבדות יחס שקילות

הגדרה. תהי [math]\displaystyle{ f:A\rightarrow B }[/math], ויהי R יחס שקילויות על A. אומרים כי f מוגדרת היטב על [math]\displaystyle{ A/R }[/math] אם [math]\displaystyle{ \forall a,b\in A:(a,b)\in R\Rightarrow f(a)=f(b) }[/math]

כלומר אם a שקול ל b אזי [math]\displaystyle{ f(a)=f(b) }[/math].

למה זה טוב? כדי שנוכל להגדיר פונקציה על קבוצת המנה [math]\displaystyle{ g:A/R \to B }[/math] ע"י [math]\displaystyle{ [a]_R \mapsto f(a) }[/math]

באופן מפורש [math]\displaystyle{ g=\{([a],f(a))|a\in A\} }[/math].

טענה: g אכן פונקציה

הוכחה:

1. g שלמה - "לפי העיניים". כלל ההתאמה מנוסח כך שהיחס הוא שלם.

2. g חד ערכית- נניח [math]\displaystyle{ [a]=[b] }[/math], צ"ל [math]\displaystyle{ g([a])=g([b]) }[/math]. מהנתון ש [math]\displaystyle{ [a]=[b] }[/math] נובע ש [math]\displaystyle{ (a,b)\in R }[/math], ולכן, לפי הגדרת f כמוגדרת היטב על קבוצת המנה, מתקיים [math]\displaystyle{ f(a)=f(b) }[/math], ולפי הגדרת g מתקיים [math]\displaystyle{ g([a])=f(a)=f(b)=g([b]) }[/math].

דוגמא

נגדיר על השלמים יחס שקילות ע"י x~y אמ"מ y=x or y=-x.

בדקו מי מהבאות היא פונקציה מקבוצת המנה לשלמים:

[math]\displaystyle{ \{([n]_{~},n): n\in \mathbb{Z} \} }[/math]
[math]\displaystyle{ \{([n]_{~},n^2): n\in \mathbb{Z} \} }[/math]

דוגמא

האם f על הרציונאליים המוגדרת על ידי [math]\displaystyle{ f\bigg(\frac{p}{q}\bigg)=p }[/math] מוגדרת היטב?

פתרון לא! כזכור הרציונאליים הם קבוצת מנה של [math]\displaystyle{ \mathbb{Z}\times \mathbb{N} }[/math]. לפי היחס שהגדרנו מתקיים [math]\displaystyle{ \frac{1}{3}=\frac{2}{6} }[/math] אבל לא מתקיים [math]\displaystyle{ f\bigg(\frac{1}{3}\bigg)=1\not=2=f\bigg(\frac{2}{6}\bigg) }[/math]

במילים: לא ברור לאן f שולחת את השבר שליש!

הערה: בכוונה ניסחנו את התרגיל באופן הרומז על יחס השקילויות מבלי לומר אותו במפורש. זו הדרך בה נתקל במושג 'מוגדר היטב' במהלך התואר - יחס השקילויות יהיה מרומז בלבד.

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

הגדרה. תהי [math]\displaystyle{ f:X\rightarrow Y }[/math] ותהי [math]\displaystyle{ A\subseteq X }[/math]. הפונקציה f מצומצמת לA מוגדרת על ידי: [math]\displaystyle{ f|_A:A\rightarrow Y }[/math] כך ש-[math]\displaystyle{ f|_A(a)=f(a) }[/math].

דוגמא. נביט ב-[math]\displaystyle{ f:\mathbb{R}\rightarrow\mathbb{R} }[/math] המוגדרת על ידי [math]\displaystyle{ f(x)=x^2 }[/math] ואינה חח"ע. נכון לומר שהפונקציה המצומצמת [math]\displaystyle{ f|_{\mathbb{N}} }[/math] כן חח"ע.

תרגיל. תהי [math]\displaystyle{ f:X\rightarrow Y }[/math] פונקציה, הוכח שקיימת קבוצה A כך ש-[math]\displaystyle{ f|_A }[/math] חח"ע עם אותה התמונה כמו הפונקציה המקורית (כלומר [math]\displaystyle{ im(f|_A)=im(f) }[/math]).

פתרון.

נגדיר לכל [math]\displaystyle{ y\in im(f) }[/math] את הקבוצה של המקורות שלו [math]\displaystyle{ B_y:=f^{-1}(\{y\}) }[/math] כעת נבחר מכל [math]\displaystyle{ B_y }[/math] איבר יחיד [math]\displaystyle{ x_y\in B_y }[/math]. נגדיר [math]\displaystyle{ A=\{x_y | y\in im (f)\} }[/math]. כיוון שבחרנו מקור לכל תמונה, ובחרנו מקור אחד אזי [math]\displaystyle{ f|_A }[/math] חח"ע עם אותו טווח של [math]\displaystyle{ f }[/math].

אזהרה! ההוכחה מתבססת על אקסיומת הבחירה (נפגש איתה בהמשך)

תרגיל

תהיינה [math]\displaystyle{ f:A\to B, g:B\to C }[/math] פונקציות כך ש [math]\displaystyle{ g\circ f }[/math] חח"ע. הוכיחו כי [math]\displaystyle{ g|_{Im(f)} }[/math] חח"ע.

הוכחה: אם נצמצם את הטווח והתחום של הפונקציות, [math]\displaystyle{ f':A\to Im(f), g|_{Im(f)}:Im(f)\to C }[/math], נקבל כי [math]\displaystyle{ g\circ f=g|_{Im(f)}\circ f' }[/math] חח"ע ובנוסף [math]\displaystyle{ f' }[/math] חח"ע ועל. מכאן ש [math]\displaystyle{ g|_{Im(f)}=g\circ f\circ f'^{-1} }[/math] חח"ע כהרכבה של חח"ע.