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

מתוך Math-Wiki
קפיצה אל: ניווט, חיפוש
(←‏המשך פונקציות)
(←‏תרגיל)
 
(28 גרסאות ביניים של 7 משתמשים אינן מוצגות)
שורה 1: שורה 1:
 
'''[[מתמטיקה בדידה - מערך תרגול|חזרה למערכי התרגול]]'''
 
'''[[מתמטיקה בדידה - מערך תרגול|חזרה למערכי התרגול]]'''
  
−
==המשך פונקציות==
+
==המשך פונקציות - פונקציות על תת-קבוצות==
  
−
'''הגדרה.''' תהי <math>f:X\rightarrow Y</math> פונקציה, ויהיו תת קבוצות <math>A\subseteq X,B\subseteq Y</math>. אזי <math>f(A)=\{f(a)|a\in A\}</math>, <math>f^{-1}(B)=\{a\in A|f(a)\in B\}</math>.
+
===תמונות חלקיות===
  
−
שימו לב שהסימון <math>f^{-1}(B)</math> אינו רומז בשום צורה שהפונקציה צריכה להיות הפיכה, הגדרה זו תקפה לכל פונקציה.
+
'''הגדרה.''' תהי <math>f:X\rightarrow Y</math> פונקציה, ויהיו תת קבוצות <math>A\subseteq X,B\subseteq Y</math>. אזי '''התמונה החלקית של A תחת f''' היא התת-קבוצה <math>f(A)=\{f(a)|a\in A\}</math>, ו'''התמונה החלקית ההפוכה של B תחת f''' היא התת-קבוצה <math>f^{-1}(B)=\{a\in X|f(a)\in B\}</math>.
  
 +
שימו לב להבדל בין התמונה ההפוכה <math>f^{-1}(B)</math> לבין הפונקציה ההופכית <math>f^{-1}(y)</math>. התמונה ההפוכה איננה מניחה כי הפונקציה f הפיכה. הדרך להבחין בין פונקציה הפיכה לתמונה ההפוכה היא לבדוק האם בין הסוגריים נמצא ''איבר'' של התמונה (בדוגמאות לעיל זהו <math>y \in Y</math>) או שנמצאת ''תת-קבוצה'' של התמונה (בדוגמאות לעיל זו <math>B\subseteq Y</math>).
  
−
'''תרגיל.'''
+
==== דוגמאות ====
−
הוכח/הפרך: תהא <math>f:X \to Y, \; A,B \subset X</math> אזי <math>f(A)\cap f(B)=f(A\cap B)</math>  
+
תהא <math>D:\mathbb{R}\to \mathbb{R}</math> פונקצית דריכלה. אזי <math>D(\mathbb{Q})=\{1\},D^{-1}(\{1\})=\mathbb{Q}=D^{-1}((0.5, 18))</math>
 +
 
 +
תהא <math>f:X\to Y</math> פונקצית . אזי <math>f^{-1}(Y)=X</math>
 +
 
 +
תהא <math>f:\mathbb{R}\to \mathbb{Z}</math> פונקצית הערך השלם התחתון. אזי <math>f((-0.5,3/4))=\{-1,0\},f^{-1}(\{1\})=[1,2)</math>
 +
 
 +
 
 +
==== תכונות ====
 +
# אם <math>A_1\subseteq A_2</math> אזי <math>f(A_1)\subseteq f(A_2)</math>
 +
# אם <math>B_1\subseteq B_2</math> אזי <math>f^{-1}(B_1)\subseteq f^{-1}(B_2)</math>
 +
# הוכיחו/הפריכו טענות מקבילות עם משלים של קבוצות.
 +
 
 +
 
 +
==== תרגיל ====
 +
הוכיחו/הפריכו: תהי f פונקציה <math>f:X \to Y</math> ותהיינה <math>Z,W\subseteq X, A,B \subseteq Y</math>. אזי
 +
# <math>f^{-1}[A]\cap f^{-1}[B]=f^{-1}[A\cap B]</math>
 +
# <math>f^{-1}[A]\cup f^{-1}[B]=f^{-1}[A\cup B]</math>
 +
# <math>f^{-1}[A\setminus B]=f^{-1}[A]\setminus f^{-1}[B]</math>
 +
# <math>f^{-1}[A]\triangle f^{-1}[B]=f^{-1}[A\triangle B]</math>
 +
# <math>f[Z]\triangle f[W]=f[Z\triangle W]</math>
 +
 
 +
פתרון: תחשבו. עדיף את שני האחרונים, כי הראשונים לפעמים נעשים בהרצאה.
 +
 
 +
====תרגיל====
 +
הוכח/הפרך: תהיינה <math>A,B \subseteq X</math> ותהי f פונקציה <math>f:X \to Y</math>. אזי <math>f(A)\cap f(B)=f(A\cap B)</math>  
  
 
'''פתרון.'''
 
'''פתרון.'''
  
−
נניח וf אינה חח"ע, כלומר קיימים <math>x\neq y </math> כך ש <math>f(x)=f(y)</math>. ניקח <math>A=\{x\},B=\{y\}</math> אזי:
+
נפריך על ידי דוגמא נגדית. נניח וf אינה חח"ע, כלומר קיימים <math>x\neq y </math> כך ש <math>f(x)=f(y)</math>. ניקח <math>A=\{x\},B=\{y\}</math> אזי:
  
 
<math>f(A)\cap f(B) = \{f(x)\} \neq \phi = f(\{\}) = f(A\cap B)</math>
 
<math>f(A)\cap f(B) = \{f(x)\} \neq \phi = f(\{\}) = f(A\cap B)</math>
  
 +
'''הערה''' תמיד מתקיים  <math>f(A\cap B)\subseteq f(A)\cap f(B)</math>
  
−
'''תרגיל.'''
+
'''הערה''' הטענה נכונה אם <math>f</math> חח"ע. הוכיחו!
 +
 
 +
===תרגיל (בהרצאה בד"כ)===
 
תהי <math>f:X\rightarrow Y</math>  ותהי <math>A\subseteq X</math>. הוכח <math>A \subseteq f^{-1}(f(A))</math>. וקיים שיוויון אם <math>f</math> חח"ע
 
תהי <math>f:X\rightarrow Y</math>  ותהי <math>A\subseteq X</math>. הוכח <math>A \subseteq f^{-1}(f(A))</math>. וקיים שיוויון אם <math>f</math> חח"ע
  
שורה 29: שורה 57:
 
יהא <math>x\in f^{-1}(f(A))</math> לכן  <math>f(x) \in f(A)</math> לכן <math>\exists a\in A : f(x)=f(a)</math>. כיוון ש <math>f</math> חח"ע נובע כי <math>x=a\in A</math>
 
יהא <math>x\in f^{-1}(f(A))</math> לכן  <math>f(x) \in f(A)</math> לכן <math>\exists a\in A : f(x)=f(a)</math>. כיוון ש <math>f</math> חח"ע נובע כי <math>x=a\in A</math>
  
 +
דוגמא שלא מתקיים שיוויון <math>f:\{1,2\}\to \{1\}</math> (יש דרך אחת להגדיר את הפונקציה). אזי נגדיר <math>A=\{2\}</math> ומתקיים <math> f^{-1}(f(A))=\{1,2\}\neq A</math>
  
−
'''תרגיל.'''
+
===תרגיל (בXI)===
 
תהי <math>f:X\rightarrow Y</math>  ותהי <math>A\subseteq Y</math>. הוכח <math>  f(f^{-1}(A)) \subseteq A</math>. וקיים שיוויון אם <math>f</math> על
 
תהי <math>f:X\rightarrow Y</math>  ותהי <math>A\subseteq Y</math>. הוכח <math>  f(f^{-1}(A)) \subseteq A</math>. וקיים שיוויון אם <math>f</math> על
  
שורה 41: שורה 70:
 
יהא <math> a\in A </math> כיוון ש f על  <math>\exists x\in X : f(x)=a  </math> לכן <math> x  \in f^{-1}(A) </math>. ואז <math>a=f(x)\in f(f^{-1}(A)) </math>  
 
יהא <math> a\in A </math> כיוון ש f על  <math>\exists x\in X : f(x)=a  </math> לכן <math> x  \in f^{-1}(A) </math>. ואז <math>a=f(x)\in f(f^{-1}(A)) </math>  
  
 +
דוגמא שלא מתקיים שיוויון <math>f:\{1\}\to \{1,2\}</math> המוגדרת <math>1\mapsto 1</math>. אזי נגדיר <math>B=\{1,2\}</math> ומתקיים <math>  f(f^{-1}(B)) =\{1\}\neq B</math>.
  
−
 
+
===תרגיל ממבחן (קצת משודרג)===
−
'''תרגיל ממבחן (קצת משודרג).'''
+
  
 
יהיו <math>X,Y</math> שתי קבוצות, ותהי <math>f:X\rightarrow Y</math> פונקציה כלשהי. נגדיר את הפונקציה <math>g:P(Y)\rightarrow P(X)</math> על ידי <math>g(B)=f^{-1}(B)</math>.
 
יהיו <math>X,Y</math> שתי קבוצות, ותהי <math>f:X\rightarrow Y</math> פונקציה כלשהי. נגדיר את הפונקציה <math>g:P(Y)\rightarrow P(X)</math> על ידי <math>g(B)=f^{-1}(B)</math>.
שורה 50: שורה 79:
 
'''פתרון.'''
 
'''פתרון.'''
  
−
1. ''' f על אמ"מ g חח"ע '''
+
1. נמצא ב XI הטענה  ''' f על אמ"מ g חח"ע '''
−
בכיוון אחד- נתון ש f על. נניח <math>f^{-1}(B)=g(B)=g(A)=f^{-1}(A)</math> נפעיל את f  על שני הצדדים ונקבל (בגלל ש f על) <math>B=f(f^{-1}(B))=f(f^{-1}(A))=A(</math>
+
בכיוון אחד- נתון ש f על. נניח <math>f^{-1}(B)=g(B)=g(A)=f^{-1}(A)</math> נפעיל את f  על שני הצדדים ונקבל (בגלל ש f על) <math>B=f(f^{-1}(B))=f(f^{-1}(A))=A</math>
  
−
בכיוון השני- נתון כי g חח"ע. נניח בשלילה כי f אינה על אזי <math>\exists y\in Y\forall x\in X:f(x)\neq y</math> לכן <math>g(Y)=f^{-1}(Y)=f^{-1}(Y/\{y\}=g(Y/\{y\})</math> בסתירה לחח"ע של g.  
+
בכיוון השני- נתון כי g חח"ע. נניח בשלילה כי f אינה על אזי <math>\exists y\in Y\forall x\in X:f(x)\neq y</math> לכן <math>g(Y)=f^{-1}(Y)=f^{-1}(Y/\{y\})=g(Y/\{y\})</math> בסתירה לחח"ע של g.  
  
  
שורה 82: שורה 111:
  
 
למשל:
 
למשל:
−
יהיו <math>X=\mathbb{Z}, Y=\{0\}</math>. אזי קיימת פונקציה f יחידה מX לY. פונקציה זו אינה חח"ע כמובן, אך g כן חח"ע שכן <math>g(\{\})\neq g(\{0\})</math> ואלה הקבוצות היחידות בקבוצת החזקה של Y.  
+
יהיו <math>X=\mathbb{Z}, Y=\{0\}</math>. אזי קיימת פונקציה f יחידה מX לY. פונקציה זו אינה חח"ע כמובן, אך g כן חח"ע שכן <math>g(\{\})\neq g(\{0\})</math> ואלה הקבוצות היחידות בקבוצת החזקה של Y.
  
 +
==== תרגיל (בהרצאה בד"כ) ====
 +
תהיינה A,B קבוצות לא ריקות. הוכיחו כי:
 +
# אם קיימת <math>f:A\to B</math> חח"ע אזי קיימת <math>g:B\to A</math> על.
 +
# אם A,B סופיות: קיימת <math>f:A\to B</math> חח"ע אמ"מ <math>|A|\leq |B|</math>
 +
# אם A,B סופיות: קיימת <math>f:A\to B</math> על אמ"מ <math>|B|\leq |A|</math>
  
−
'''הגדרה.'''
+
=== פונקציות המכבדות יחס שקילות ===
−
תהי <math>f:X\rightarrow Y</math> ותהי <math>A\subseteq X</math>. הפונקציה '''f מצומצמת לA''' מוגדרת על ידי: <math>f|_A:A\rightarrow Y</math> כך ש <math>f|_A(a)=f(a)</math>.
+
−
 
+
−
'''דוגמא.'''
+
−
נביט ב<math>f:\mathbb{R}\rightarrow\mathbb{R}</math> המוגדרת על ידי <math>f(x)=x^2</math> ואינה חח"ע. נכון לומר שהפונקציה המצומצמת <math>f|_{\mathbb{N}}</math> כן חח"ע.
+
−
 
+
−
 
+
−
'''תרגיל.'''
+
−
תהי <math>f:X\rightarrow Y</math> פונקציה, הוכח שקיימת קבוצה A כך ש<math>f|_A</math> חח"ע עם אותו טווח כמו הפונקציה המקורית (כלומר <math>im(f|_A)=im(f)</math>
+
−
 
+
−
'''פתרון.'''
+
−
 
+
−
נגדיר לכל <math>y\in im(f)</math> את הקבוצה של המקורות שלו <math>B_y:=f^{-1}(\{y\})</math>
+
−
כעת נבחר מכל <math>A_y</math> איבר יחיד <math>x_y\in B_y</math>/
+
−
 
+
−
נגדיר <math>A=\bigcup_{y\in im f}x_y</math>. כיוון שבחרנו מקור לכל תמונה ובחרנו מקור אחד אזי <math>f|_A</math> חח"ע עם אותו טווח של <math>f</math>
+
−
 
+
−
אזהרה! ההוכחה מתבססת על אקסיומת הבחירה (נפגש איתה בהמשך)
+
−
 
+
 
'''הגדרה.''' תהי <math>f:A\rightarrow B</math>, ויהי R יחס שקילויות על A. אומרים כי '''f מוגדרת היטב על <math>A/R</math>''' אם <math>\forall a,b\in A:(a,b)\in R\Rightarrow f(a)=f(b)</math>
 
'''הגדרה.''' תהי <math>f:A\rightarrow B</math>, ויהי R יחס שקילויות על A. אומרים כי '''f מוגדרת היטב על <math>A/R</math>''' אם <math>\forall a,b\in A:(a,b)\in R\Rightarrow f(a)=f(b)</math>
  
−
כלומר אם a שקול ל b אזי <math>f(a)=f(b)</math>/
+
כלומר אם a שקול ל b אזי <math>f(a)=f(b)</math>.
  
 
למה זה טוב?
 
למה זה טוב?
שורה 117: שורה 133:
 
הוכחה:
 
הוכחה:
  
−
1. g שלמה - לפי העיניים
+
1. g שלמה - "לפי העיניים". כלל ההתאמה מנוסח כך שהיחס הוא שלם.
  
−
2. g חד ערכית- נניח <math>[a]=[b]</math> צ"ל <math>f(a)=f(b)</math> וזה אכן מתקיים כי f מוגדרת היטב על קבוצת המנה.
+
2. g חד ערכית- נניח <math>[a]=[b]</math>, צ"ל <math>g([a])=g([b])</math>. מהנתון ש <math>[a]=[b]</math> נובע ש <math>(a,b)\in R</math>, ולכן, לפי הגדרת f כמוגדרת היטב על קבוצת המנה, מתקיים <math>f(a)=f(b)</math>, ולפי הגדרת g מתקיים <math>g([a])=f(a)=f(b)=g([b])</math>.
  
 +
==== דוגמא ====
 +
נגדיר על השלמים יחס שקילות ע"י x~y אמ"מ y=x or y=-x.
  
−
'''דוגמא לחידוד'''
+
בדקו מי מהבאות היא פונקציה מקבוצת המנה לשלמים:
−
האם  f על הרציונאליים המוגדרת על ידי <math>f(\frac{p}{q})=p</math> מוגדרת היטב?
+
# <math>\{([n]_{~},n): n\in \mathbb{Z} \}</math>
 +
# <math>\{([n]_{~},n^2): n\in \mathbb{Z} \}</math>
 +
 
 +
====דוגמא ====
 +
האם  f על הרציונאליים המוגדרת על ידי <math>f\bigg(\frac{p}{q}\bigg)=p</math> מוגדרת היטב?
  
 
'''פתרון'''
 
'''פתרון'''
−
לא! כזכור הרציונאליים הם קבוצת מנה של <math>\mathbb{Z}\times \mathbb{N}</math>. לפי היחס שהגדרנו מתקיים <math>\frac{1}{3}=\frac{2}{6}</math> אבל לא מתקיים <math>f(\frac{1}{3})=1\not=2=f(\frac{2}{6})</math>
+
לא! כזכור הרציונאליים הם קבוצת מנה של <math>\mathbb{Z}\times \mathbb{N}</math>. לפי היחס שהגדרנו מתקיים <math>\frac{1}{3}=\frac{2}{6}</math> אבל לא מתקיים <math>f\bigg(\frac{1}{3}\bigg)=1\not=2=f\bigg(\frac{2}{6}\bigg)</math>
  
 
במילים: לא ברור לאן f שולחת את השבר שליש!
 
במילים: לא ברור לאן f שולחת את השבר שליש!
  
 
הערה: בכוונה ניסחנו את התרגיל באופן הרומז על יחס השקילויות מבלי לומר אותו במפורש. זו הדרך בה נתקל במושג 'מוגדר היטב' במהלך התואר - יחס השקילויות יהיה מרומז בלבד.
 
הערה: בכוונה ניסחנו את התרגיל באופן הרומז על יחס השקילויות מבלי לומר אותו במפורש. זו הדרך בה נתקל במושג 'מוגדר היטב' במהלך התואר - יחס השקילויות יהיה מרומז בלבד.
 +
 +
===פונקציה מצומצמת===
 +
 +
'''הגדרה.'''
 +
תהי <math>f:X\rightarrow Y</math> ותהי <math>A\subseteq X</math>. הפונקציה '''f מצומצמת לA''' מוגדרת על ידי: <math>f|_A:A\rightarrow Y</math> כך ש-<math>f|_A(a)=f(a)</math>.
 +
 +
'''דוגמא.'''
 +
נביט ב-<math>f:\mathbb{R}\rightarrow\mathbb{R}</math> המוגדרת על ידי <math>f(x)=x^2</math> ואינה חח"ע. נכון לומר שהפונקציה המצומצמת <math>f|_{\mathbb{N}}</math> כן חח"ע.
 +
 +
 +
'''תרגיל.'''
 +
תהי <math>f:X\rightarrow Y</math> פונקציה, הוכח שקיימת קבוצה A כך ש-<math>f|_A</math> חח"ע עם אותה התמונה כמו הפונקציה המקורית (כלומר <math>im(f|_A)=im(f)</math>).
 +
 +
'''פתרון.'''
 +
 +
נגדיר לכל <math>y\in im(f)</math> את הקבוצה של המקורות שלו <math>B_y:=f^{-1}(\{y\})</math>
 +
כעת נבחר מכל <math>B_y</math> איבר יחיד <math>x_y\in B_y</math>. נגדיר <math>A=\{x_y | y\in im (f)\}</math>. כיוון שבחרנו מקור '''לכל''' תמונה, ובחרנו מקור '''אחד''' אזי <math>f|_A</math> חח"ע עם אותו טווח של <math>f</math>.
 +
 +
'''אזהרה!''' ההוכחה מתבססת על אקסיומת הבחירה (נפגש איתה בהמשך)
 +
==== תרגיל ====
 +
תהיינה <math>f:A\to B, g:B\to C</math> פונקציות כך ש <math>g\circ f</math> חח"ע. הוכיחו כי <math>g|_{Im(f)}</math> חח"ע.
 +
 +
הוכחה: אם נצמצם את הטווח והתחום של הפונקציות, <math>f':A\to Im(f), g|_{Im(f)}:Im(f)\to C</math>, נקבל כי <math>g\circ f=g|_{Im(f)}\circ f'</math> חח"ע ובנוסף <math>f'</math> חח"ע ועל. מכאן ש  <math>g|_{Im(f)}=g\circ f\circ f'^{-1}</math> חח"ע כהרכבה של חח"ע.

גרסה אחרונה מ־14:49, 27 ביולי 2021

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

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

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

הגדרה. תהי 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 ותהיינה Z,W\subseteq X, 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]
  3. f^{-1}[A\setminus B]=f^{-1}[A]\setminus f^{-1}[B]
  4. f^{-1}[A]\triangle f^{-1}[B]=f^{-1}[A\triangle B]
  5. f[Z]\triangle f[W]=f[Z\triangle W]

פתרון: תחשבו. עדיף את שני האחרונים, כי הראשונים לפעמים נעשים בהרצאה.

תרגיל

הוכח/הפרך: תהיינה 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

תרגיל (בXI)

תהי 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. נמצא ב XI הטענה 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.

תרגיל (בהרצאה בד"כ)

תהיינה A,B קבוצות לא ריקות. הוכיחו כי:

  1. אם קיימת f:A\to B חח"ע אזי קיימת g:B\to A על.
  2. אם A,B סופיות: קיימת f:A\to B חח"ע אמ"מ |A|\leq |B|
  3. אם A,B סופיות: קיימת f:A\to B על אמ"מ |B|\leq |A|

פונקציות המכבדות יחס שקילות

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

כלומר אם a שקול ל b אזי f(a)=f(b).

למה זה טוב? כדי שנוכל להגדיר פונקציה על קבוצת המנה g:A/R \to B ע"י [a]_R \mapsto f(a)

באופן מפורש g=\{([a],f(a))|a\in A\}.

טענה: g אכן פונקציה

הוכחה:

1. g שלמה - "לפי העיניים". כלל ההתאמה מנוסח כך שהיחס הוא שלם.

2. g חד ערכית- נניח [a]=[b], צ"ל g([a])=g([b]). מהנתון ש [a]=[b] נובע ש (a,b)\in R, ולכן, לפי הגדרת f כמוגדרת היטב על קבוצת המנה, מתקיים f(a)=f(b), ולפי הגדרת g מתקיים g([a])=f(a)=f(b)=g([b]).

דוגמא

נגדיר על השלמים יחס שקילות ע"י x~y אמ"מ y=x or y=-x.

בדקו מי מהבאות היא פונקציה מקבוצת המנה לשלמים:

  1. \{([n]_{~},n): n\in \mathbb{Z} \}
  2. \{([n]_{~},n^2): n\in \mathbb{Z} \}

דוגמא

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

פתרון לא! כזכור הרציונאליים הם קבוצת מנה של \mathbb{Z}\times \mathbb{N}. לפי היחס שהגדרנו מתקיים \frac{1}{3}=\frac{2}{6} אבל לא מתקיים f\bigg(\frac{1}{3}\bigg)=1\not=2=f\bigg(\frac{2}{6}\bigg)

במילים: לא ברור לאן f שולחת את השבר שליש!

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

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

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

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

תרגיל

תהיינה f:A\to B, g:B\to C פונקציות כך ש g\circ f חח"ע. הוכיחו כי g|_{Im(f)} חח"ע.

הוכחה: אם נצמצם את הטווח והתחום של הפונקציות, f':A\to Im(f), g|_{Im(f)}:Im(f)\to C, נקבל כי g\circ f=g|_{Im(f)}\circ f' חח"ע ובנוסף f' חח"ע ועל. מכאן ש g|_{Im(f)}=g\circ f\circ f'^{-1} חח"ע כהרכבה של חח"ע.

מקור: https://math-wiki.com/index.php?title=88-195_בדידה_לתיכוניסטים_תשעא/מערך_שיעור/שיעור_5&oldid=87995