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

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

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

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

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

תרגיל. הוכח/הפרך: תהא [math]\displaystyle{ f:X \to Y, \; A,B \subset X }[/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:X\rightarrow Y }[/math] חח"ע, ותהי [math]\displaystyle{ A\subseteq X }[/math]. הוכח [math]\displaystyle{ f^{-1}(f(A))=A }[/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{ A\subseteq f^{-1}(f(A)) }[/math]. (עד כה זה נכון לכל העתקה, לאו דווקא חח"ע.)

נניח כעת בשלילה ש [math]\displaystyle{ f^{-1}(f(A))\neq A }[/math] לכן קיים [math]\displaystyle{ x\in f^{-1}(f(A)) }[/math] כך ש [math]\displaystyle{ x\notin A }[/math]. לכן לפי ההגדרה, [math]\displaystyle{ f(x)\in f(A) }[/math]. לכן קיים a בA כך ש [math]\displaystyle{ f(a)=f(x) }[/math]. מתוך החח"ע נובע ש-x=a בסתירה.

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

יהיו [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. (כלומר, מה גורר את מה בהכרח).

פתרון.

תהי 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.

• לכן ייתכן ו-f חח"ע אך g אינה כזו.

תהי f כך ש-g חח"ע. כפי שראינו לעיל, ניתן ישר להסיק ש-f הינה על.

נוכיח שאם f על אזי g חח"ע; נניח בשלילה שg אינה חח"ע, אזי קיימות שתי קבוצות [math]\displaystyle{ B\neq C \in P(Y) }[/math] כך ש [math]\displaystyle{ g(B)=g(C) }[/math]. בלי הגבלת הכלליות, נניח שקיים איבר [math]\displaystyle{ c\in C }[/math] כך ש [math]\displaystyle{ c\notin B }[/math]. מכיוון ש-f על, קיים איבר a כך ש [math]\displaystyle{ f(a)=c }[/math], לכן [math]\displaystyle{ a\in g(B) }[/math], ואז קיים [math]\displaystyle{ b\in B }[/math] כך ש[math]\displaystyle{ f(a)=b }[/math] ולכן b=c בסתירה.

• אם כן, הוכחנו ש-f על אם"ם g חח"ע.

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

• לכן יתכן ו-g חח"ע אך f אינה כזו.

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

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

• סה"כ, הוכחנו שf חח"ע אם"ם g הינה על.

ניקח f פונקציה חח"ע שאינה על, לכן g היא על.

• לכן ייתכן ו-g הינה על אך f אינה על

באופן דומה ניקח f על שאינה חח"ע, לכן g אינה על.

• לכן ייתכן ו-f הינה על אך g אינה על

הגדרה. תהי [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{ \{f^{-1}(\{y\})|y\in Y\}) }[/math] ונרצה לבחור איבר יחיד מבין כל קבוצה כזו. אקסיומת הבחירה היא זו המאפשרת לנו לבצע בחירה זו בשלום.)

הגדרה. תהי [math]\displaystyle{ f:A\rightarrow A }[/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)\in R }[/math]

תרגיל מוטיבציה להגדרה לעיל.

המוטיבציה להגדרה הזו היא היכולת לגזור ממנה פונקציה על חבורת המנה. נגדיר יחס על חבורת המנה [math]\displaystyle{ g=\{([a],[f(a)])|a\in A\} }[/math]. נוכיח ש-g הינה חד-ערכית ולכן פונקציה.

הוכחה

נניח וקיימים [math]\displaystyle{ a,b\in A }[/math] כך ש [math]\displaystyle{ [a]=[b] }[/math]. לכן [math]\displaystyle{ (a,b)\in R }[/math] ולכן [math]\displaystyle{ (f(a),f(b))\in R }[/math] ולכן [math]\displaystyle{ [f(a)]=[f(b)] }[/math]. לכן לא ייתכן מצב בו [math]\displaystyle{ (x,y),(x,z)\in g }[/math] אבל [math]\displaystyle{ y\neq z }[/math].

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

פתרון.

יש לשים לב שלא באמת הגדרנו את הפונקציה על הרציונאליים, אלא על אוסף הזוגות הסדורים של שלמים [math]\displaystyle{ (p,q) }[/math] כך שהאיבר הימני שונה מאפס. נגדיר על קבוצה זו את יחס השקילויות R המוגדר על ידי [math]\displaystyle{ ((p,q),(a,b))\in R }[/math] אם [math]\displaystyle{ pb=qa }[/math]. נראה כי f אינה מוגדרת היטב בתנאים אלו:

[math]\displaystyle{ ((2,6),(1,3))\in R }[/math] אולם [math]\displaystyle{ f(2,6)=(2,1),f(1,3)=(1,1) }[/math] ו[math]\displaystyle{ ((2,1),(1,1))\notin R }[/math].

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