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

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

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

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

הגדרה. תהי $f:X\rightarrow Y$ פונקציה, ויהיו תת קבוצות $A\subseteq X,B\subseteq Y$. אזי התמונה החלקית של A תחת f היא התת-קבוצה $f(A)=\{f(a)|a\in A\}$, והתמונה החלקית ההפוכה של B תחת f היא התת-קבוצה $f^{-1}(B)=\{a\in X|f(a)\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)$
3. הוכיחו/הפריכו טענות מקבילות עם משלים של קבוצות.

תרגיל

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

1. $f^{-1}(A)\cap f^{-1}(B)=f^{-1}(A\cap B)$
2. $f^{-1}(A)\cup f^{-1}(B)=f^{-1}(A\cup B)$

פתרון: תחשבו

תרגיל

הוכח/הפרך: תהיינה $A,B \subseteq X$ ותהי f פונקציה $f:X \to Y$. אזי $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(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$

תרגיל

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

פתרון.

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

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

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

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

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

יהיו $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:A\to B$ פונקציה בין קבוצות לא ריקות. הוכיחו כי

1. אם f חח"ע אזי קיימת $g:B\to A$ על.
2. במידה ו A,B סופיות: f חח"ע אמ"מ $|A|\leq |B|$
3. במידה ו A,B סופיות: f על אמ"מ $|B|\leq |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$.

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