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{ 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{ 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. 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{ B\subseteq f(f^{-1}(B)) = f(A)= \{f(x)\} }[/math] כיוון ש B אינה ריקה נקבל ש [math]\displaystyle{ B=\{f(x)\} }[/math] לכן [math]\displaystyle{ \{x\}=A=g(B)=f^{-1}(B)=f^{-1}(\{f(x)\})\supseteq \{x,y\} }[/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.

הגדרה. תהי [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].

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