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

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

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

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

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

תרגיל. הוכח/הפרך: תהא $f:X \to Y, \; A,B \subset X$ אזי $f(A)\cap f(B)=f(A\cap B)$

פתרון.

נניח וf אינה חח"ע, כלומר קיימים $x\neq y$ כך ש $f(x)=f(y)$. ניקח $A=\{x\},B=\{y\}$ אזי:

$f(A)\cap f(B) = \{f(x)\} \neq \phi = f(\{\}) = f(A\cap B)$

תרגיל. תהי $f:X\rightarrow Y$ חח"ע, ותהי $A\subseteq X$. הוכח $f^{-1}(f(A))=A$.

פתרון.

ישירות מההגדרות נובע שאם $a\in A$ אזי $f(a)\in f(A)$ ולכן $a\in f^{-1}(f(A))$. סה"כ הראנו $A\subseteq f^{-1}(f(A))$. (עד כה זה נכון לכל העתקה, לאו דווקא חח"ע.)

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

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

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

פתרון.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

הגדרה. תהי $f:X\rightarrow Y$ ותהי $A\subseteq X$. הפונקציה f מצומצמת לA מוגדרת על ידי: $f|_A:A\rightarrow Y$ כך ש $f|_A(a)=f(a)$.

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

תרגיל. תהי $f:X\rightarrow Y$ פונקציה, הוכח שקיימת קבוצה A כך ש$f|_A$ חח"ע

פתרון.

פייי זו שאלה קשה. תזכירו לנו אותה כאשר נגיע לאקסיומת הבחירה. (שכן נביט ב$\{f^{-1}(\{y\})|y\in Y\})$ ונרצה לבחור איבר יחיד מבין כל קבוצה כזו. אקסיומת הבחירה היא זו המאפשרת לנו לבצע בחירה זו בשלום.)

הגדרה. תהי $f:A\rightarrow A$, ויהי R יחס שקילויות על A. אומרים כי f מוגדרת היטב על $A/R$ אם $\forall a,b\in A:(a,b)\in R\rightarrow (f(a),f(b)\in R$

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

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

הוכחה

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

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

פתרון.

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

$((2,6),(1,3))\in R$ אולם $f(2,6)=(2,1),f(1,3)=(1,1)$ ו$((2,1),(1,1))\notin R$.

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