תרגול 7 מדמח קיץ תשעז

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

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

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

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

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

דוגמאות

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

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

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

תכונות

1. אם $A_1\subseteq A_2$ אזי $f(A_1)\subseteq f(A_2)$
2. אם $B_1\subseteq B_2$ אזי $f^{-1}(B_1)\subseteq f^{-1}(B_2)$

תרגיל. הוכח/הפרך: תהיינה $A,B \subseteq X$ ותהי f פונקציה $f:X \to Y$. אזי:

א. $f(A)\cap f(B)\subseteq f(A\cap B)$.

ב. $f(A)\cap f(B)\supseteq 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(A\cap B)\subseteq f(A)\cap f(B)$

הערה אם $f$ חח"ע אז יש שיוויון!

תרגיל

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

פתרון.

יהא $a\in A$ אזי $f(a)\in f(A)$ ולכן $a\in f^{-1}(f(A))$.

נראה את ההכלה בכיוון השני אם $f$ חח"ע:

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

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

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

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

פתרון.

1. f על אמ"מ g חח"ע בכיוון אחד- נתון ש f על. נניח $f^{-1}(B)=g(B)=g(A)=f^{-1}(A)$ נפעיל את f על שני הצדדים ונקבל (בגלל ש f על) $B=f(f^{-1}(B))=f(f^{-1}(A))=A$

בכיוון השני- נתון כי 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.

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

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

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

לכן $\{f(x)\}= f(A)= f(f^{-1}(B))\subseteq B$

ולכן $\{y,x\}\subseteq f^{-1}(\{f(x)=f(y)\})= f^{-1}(\{f(x)\}) \subseteq f^{-1}(B)=g(B)=A=\{x\}$

לכן $\{y,x\}\subseteq \{x\}$ כלומר $x=y$. סתירה.

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

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

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

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

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

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

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

תרגיל

תהי $f:X\rightarrow X$ פונרציה. נקודת שבת של $f$ היא $x\in X:f(x)=x$ נגדיר $A=\{x\in X|f(x)=x\}$. הוכיחו או הפריכו:

א. $f[A]=A$.

ב. $f^{-1}[A]=A$.

ג. לכל $B\subseteq X$ נקבל: $f[B]\subseteq B$ אמ"ם קיים $b\in B$ נקודת שבת.

פתרון

א. הוכחה: $a\in A\iff f(a)=a\iff a\in f[A]$.

ב. הפרכה: מספיק שיש עוד מישהו מחוץ ל-A שנלשח לA.

ג. הפרכה: $f:\{ 0,1\} \rightarrow \{ 0,1\}$ המוגדרת $f(a)=1-a$ מקיימת עבור הקבוצה עצמה שיוויון אך אין נק' שבת.

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

הגדרה. תהי $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$ חח"ע עם אותה התמונה כמו הפונקציה המקורית (כלומר $im(f|_A)=im(f)$).

פתרון.

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

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