תרגול 6 מדמח קיץ תשעז - היסטוריית גרסאות

אריאל: /* פונקציות */

2017-08-23T09:47:26Z

פונקציות

→ הגרסה הקודמת		גרסה מ־09:47, 23 באוגוסט 2017
שורה 179:		שורה 179:

	ביחד נקבל ש <math>g</math> חח"ע ועל כלומר הפיכה. נכפול ב <math>g^{-1}</math> מימין ומשמאל ונקבל כי <math>f=g^{-1}\circ g^{-1}</math> ואז <math>f</math> הפיכה כהרכבה של הפיכות.		ביחד נקבל ש <math>g</math> חח"ע ועל כלומר הפיכה. נכפול ב <math>g^{-1}</math> מימין ומשמאל ונקבל כי <math>f=g^{-1}\circ g^{-1}</math> ואז <math>f</math> הפיכה כהרכבה של הפיכות.

			===תרגיל===
			תהיינה <math>f,g:\mathbb{N}\rightarrow \mathbb{N}</math> פונקציות כך ש- <math>f(n)=g(3n-1)</math> הוכיחו:

			אם <math>f</math> על אזי <math>g</math> לא חח"ע.

			====פתרון====
			נסמן <math>g(1)=k</math> כיון ש-<math>f</math> על אזי קיים <math>n\in \mathbb{N}</math> כך ש<math>f(n)=k</math>. מהנתון נקבל ש-<math>g(3n-1)=k</math>. כעת, כיון ש- <math>n\in \mathbb{N}</math> אזי ברור ש-<math>1\neq 3n-1</math>, ולכן אילו שני איברים שונים שנשלחים לאותו איבר. לכן <math>g</math> לא חח"ע.

אריאל: /* פתרון */

2017-08-23T08:54:27Z

פתרון

→ הגרסה הקודמת		גרסה מ־08:54, 23 באוגוסט 2017
שורה 64:		שורה 64:
	חח"ע: כן. תהיינה <math>X,Y\in P(A), X\neq Y</math> אם <math>X\subsetneq Y\lor (X\nsubseteq Y\land Y\nsubseteq X)</math> אזי <math>X\in f(X)\smallsetminus f(Y)</math>. אחרת <math>Y\in f(Y)\smallsetminus f(X)</math>.		חח"ע: כן. תהיינה <math>X,Y\in P(A), X\neq Y</math> אם <math>X\subsetneq Y\lor (X\nsubseteq Y\land Y\nsubseteq X)</math> אזי <math>X\in f(X)\smallsetminus f(Y)</math>. אחרת <math>Y\in f(Y)\smallsetminus f(X)</math>.

	על: לא. למשל לקבוצה <math>\{ \{ 1,2\} \{ 3,4\} \}</math> אין מקור. אין תת קבוצה שהאוסף הזה הוא בדיוק אוסף הקבוצות המכילות אותה.		על: לא. למשל לקבוצה <math>\{ \{ 1,2\}, \{ 3,4\} \}</math> אין מקור. אין תת קבוצה שהאוסף הזה הוא בדיוק אוסף הקבוצות המכילות אותה.

	===תרגיל===		===תרגיל===

אריאל: /* פונקציות */

2017-08-23T08:52:57Z

פונקציות

@@ שורה 48: / שורה 48: @@
 * תהא <math>f:A\to B</math> אזי <math>g:A\to Im(f) </math> המוגדרת <math>g(a)=f(a)</math> היא על (במילים: פשוט חושבים על הטווח של f להיות התמונה של f)
 * תהא <math>A\subseteq B</math>  אזי הפונקציה <math>i : A\to B </math> המוגדרת <math>i(a)=a</math> נקראת פונקציה ההכלה (במקרה ש <math>A=B</math> זה פונקצית הזהות). פונקצית ההכלה היא חח"ע.
 ===תרגיל===

אריאל: /* דוגמאות: */

2017-08-23T08:09:14Z

דוגמאות:

→ הגרסה הקודמת		גרסה מ־08:09, 23 באוגוסט 2017
שורה 37:		שורה 37:
	*<math>f:\mathbb{R}\rightarrow\mathbb{R}</math> כאשר <math>f(x)=x-1</math> ( חח"ע ו על)		*<math>f:\mathbb{R}\rightarrow\mathbb{R}</math> כאשר <math>f(x)=x-1</math> ( חח"ע ו על)
	*<math>f:\mathbb{N}\rightarrow\mathbb{N}</math> כאשר <math>f(x)=x-1</math> ( לא מוגדר כי <math>f(1)=?</math>)		*<math>f:\mathbb{N}\rightarrow\mathbb{N}</math> כאשר <math>f(x)=x-1</math> ( לא מוגדר כי <math>f(1)=?</math>)
	*<math>f:\mathbb{R}\rightarrow\mathbb{Z}</math> כאשר <math>f(x)=[x]</math> ~~מוגדר להיות הערך השלם הקרוב ביותר ל-x~~ (~~במקרה של חצי לוקחים את הגבוה). זו פונקציה על שאינה~~ חח"ע		*<math>f:\mathbb{N}\rightarrow\mathbb{N} \cup \{ 0\}</math> כאשר <math>f(x)=x-1</math> (חח"ע ועל)
	*<math>f:\mathbb{Z}_2\rightarrow\mathbb{Z}_3</math> כאשר לוקחים את ~~0 ל0 ואת 1 ל1~~. זו פונקציה חח"ע ~~שאינה על~~. ~~(כל פונקציה היא על לתמונה של עצמה.)~~		*<math>f:\mathbb{R}\rightarrow\mathbb{Z}</math> כאשר <math>f(x)=[x]</math> מוגדר להיות הערך השלם הקרוב ביותר ל-x (במקרה של חצי לוקחים את הגבוה). זו פונקציה על שאינה חח"ע.
	*<math>D:\mathbb{R}\rightarrow\mathbb{R}</math> פונקצית דיריכלה: על כל מספר רציונאלי מקבלת 1 ועל כל מספר אי רציונאלי מקבלת אפס.		*<math>D:\mathbb{R}\rightarrow\mathbb{R}</math> פונקצית דיריכלה: על כל מספר רציונאלי מקבלת 1 ועל כל מספר אי רציונאלי מקבלת אפס.
	* תהא <math>A</math> קבוצה ו <math>B\subseteq A</math> תת קבוצה. הפונקציה		* תהא <math>A</math> קבוצה ו <math>B\subseteq A</math> תת קבוצה. הפונקציה

אריאל: /* פונקציות הפיכות */

2017-08-22T19:46:09Z

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

→ הגרסה הקודמת		גרסה מ־19:46, 22 באוגוסט 2017
שורה 114:		שורה 114:
	הערה: זכרו שפונקציה היא יחס. הפונקציה ההופכית שלה היא היחס ההופכי מטבע הדברים. על מנת שהיחס ההופכי יהיה פונקציה הוא צריך להיות ח"ע ושהתחום שלו יהיה כל B. תנאים אלה מתממשים רק אם f הינה חח"ע ועל.		הערה: זכרו שפונקציה היא יחס. הפונקציה ההופכית שלה היא היחס ההופכי מטבע הדברים. על מנת שהיחס ההופכי יהיה פונקציה הוא צריך להיות ח"ע ושהתחום שלו יהיה כל B. תנאים אלה מתממשים רק אם f הינה חח"ע ועל.

	~~'''תרגיל.'''~~

	~~תהא <math>f:A\rightarrow B</math> פונקציה. הוכיחו:~~

	~~1. <math>f</math> חח"ע אמ"ם <math>\exists g:B\rightarrow A:g\circ f=I_A</math> (קיימת לה הופכית ימנית)~~

	~~2. <math>f</math> על אמ"ם <math>\exists g:B\rightarrow A:f\circ g=I_B</math> (קיימת לה הופכית שמאלית)~~

	~~'''הוכחה:'''~~

	1. מימין לשמאל: אם <math>A</math> ריקה אז הפונקציה הריקה היא הזהות. אחרת יש <math>a_1\in A</math>. מחח"ע של <math>f</math> נקבל שלכל <math>b\in Im(f)</math> יש מקור יחיד, נסמנו ב-<math>f^{-1}(b)</math>. לכן נוכל להגדיר (כלומר הפונקציה תהיה חד-ערכית) פונקציה <math>g:B\rightarrow A</math> ע"י: <math>g(b)=\begin{cases}
	~~f^{-1}(b) & b\in Im(f)\\~~
	~~a_{1} & b\notin Im(f)~~
	~~\end{cases}</math>~~

	~~כעת, יהי <math>a\in A</math>, נקבל לפי ההגדרה ש- <math>g\circ f(a)=g(f(a))=a</math>, כי <math>f(a)\in Im(f)</math>.~~

	~~משמאל לימין: הזהות חח"ע ולפי תרגיל מקודם נקבל <math>f</math> חח"ע.~~

	2. מימין לשמאל: אם <math>A</math> ריקה זה מתקיים באופן ריק. אחרת, לכל <math>b\in B</math>, מעל של <math>f</math> יש <math>a\in A</math> עבורו <math>f(a)=b</math>, נגדיר <math>g(b)=a</math>. כעת <math>f\circ g(b)=f(g(b))</math> ו-<math>g(b)</math> הוא איבר שנשלח ל-<math>b</math> תחת <math>f</math> כמו שרצינו.

	~~משמאל לימין: הזהות תמיד על, ולכן לפי תרגיל ממקודם, <math>f</math> על.~~

	==== דוגמאות ====		==== דוגמאות ====

אריאל: /* פונקציות הפיכות */

2017-08-22T10:11:26Z

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

→ הגרסה הקודמת		גרסה מ־10:11, 22 באוגוסט 2017
שורה 116:		שורה 116:
	'''תרגיל.'''		'''תרגיל.'''

	~~הוכח כי~~ f ~~הפיכה אם"ם היא~~ חח"ע ~~ועל~~. ~~כמו כן, הוכח שאם~~ קיימת הופכית ~~אזי היא יחידה.~~		תהא <math>f:A\rightarrow B</math> פונקציה. הוכיחו:

			1. <math>f</math> חח"ע אמ"ם <math>\exists g:B\rightarrow A:g\circ f=I_A</math> (קיימת לה הופכית ימנית)

			2. <math>f</math> על אמ"ם <math>\exists g:B\rightarrow A:f\circ g=I_B</math> (קיימת לה הופכית שמאלית)

	'''הוכחה:'''		'''הוכחה:'''

	אם f ~~הפיכה~~, ~~אזי~~ <math>~~f\circ~~ f^{-1} ~~= id_B~~</math> ~~וגם~~ <math>f^{-1}\circ f = ~~id_A~~</math>~~. מכיוון שהזהות הינה חח"ע ועל~~, ~~נובע ש-~~f ~~חח"ע ועל לפי התרגיל הקודם בדבר הרכבת פונקציות~~.		1. מימין לשמאל: אם <math>A</math> ריקה אז הפונקציה הריקה היא הזהות. אחרת יש <math>a_1\in A</math>. מחח"ע של <math>f</math> נקבל שלכל <math>b\in Im(f)</math> יש מקור יחיד, נסמנו ב-<math>f^{-1}(b)</math>. לכן נוכל להגדיר (כלומר הפונקציה תהיה חד-ערכית) פונקציה <math>g:B\rightarrow A</math> ע"י: <math>g(b)=\begin{cases}
			f^{-1}(b) & b\in Im(f)\\
			a_{1} & b\notin Im(f)
			\end{cases}</math>

			כעת, יהי <math>a\in A</math>, נקבל לפי ההגדרה ש- <math>g\circ f(a)=g(f(a))=a</math>, כי <math>f(a)\in Im(f)</math>.

	~~אם f~~ חח"ע ~~ועל, אז נגדיר~~ <math>~~g:B\to A</math> ע"י: עבור <math>a\in A~~ </math> ~~קיים (כי f על) יחיד (כי f~~ חח"ע)		משמאל לימין: הזהות חח"ע ולפי תרגיל מקודם נקבל <math>f</math> חח"ע.
	~~<math>b\in B</math> כך ש <math>f(a)=b</math> . נגדיר <math>g(b):=a</math>. תרגיל: בדקו ש g ההופכית של f~~.

	~~יחידות~~: ~~נניח g~~,~~h הופכיות~~ של f ~~אזי~~ <math>h= ~~h\circ I_B~~=~~h\circ~~ f \circ g=~~I_A \circ~~ g=g</math>.		2. מימין לשמאל: אם <math>A</math> ריקה זה מתקיים באופן ריק. אחרת, לכל <math>b\in B</math>, מעל של <math>f</math> יש <math>a\in A</math> עבורו <math>f(a)=b</math>, נגדיר <math>g(b)=a</math>. כעת <math>f\circ g(b)=f(g(b))</math> ו-<math>g(b)</math> הוא איבר שנשלח ל-<math>b</math> תחת <math>f</math> כמו שרצינו.

	~~דרך אחרת להוכחת יחידות~~: ~~נניח בשלילה ש g וh הופכיות שונות של f. מכיוון שהן שונות~~, ~~הן חייבות להיות שונות על איבר אחד לפחות. כלומר~~, ~~<math>\exists a\in A:g(a)\neq h(a)</math>. אבל~~ <math>f~~(g(a))=f(h(a))~~</math> ~~וזו סתירה לחח"ע של f~~.		משמאל לימין: הזהות תמיד על, ולכן לפי תרגיל ממקודם, <math>f</math> על.

	==== דוגמאות ====		==== דוגמאות ====

אריאל: /* הרכבת פונקציות */

2017-08-22T09:51:58Z

הרכבת פונקציות

→ הגרסה הקודמת		גרסה מ־09:51, 22 באוגוסט 2017
שורה 80:		שורה 80:

	'''הגדרה:'''		'''הגדרה:'''
	~~יהיו~~ <math>f:A\to B, g:B\to C </math> שתי פונקציות אזי '''ההרכבה של <math>g</math> על <math>f</math>''' היא פונקציה <math>g \circ f:A\to C </math> המוגדרת על ידי הכלל <math>g \circ f(a)=g(f(a)) </math>		תהיינה <math>f:A\to B, g:B\to C </math> שתי פונקציות אזי '''ההרכבה של <math>g</math> על <math>f</math>''' היא פונקציה <math>g \circ f:A\to C </math> המוגדרת על ידי הכלל <math>g \circ f(a)=g(f(a)) </math>


שורה 88:		שורה 88:

	====תרגיל====		====תרגיל====
	*~~נניח~~ <math>g \circ f</math> חח"ע. הוכח/הפרך: g חח"ע, f חח"ע		*תהיינה <math>f:A\to B, g:B\to C </math> פונקציות כך ש- <math>g \circ f</math> חח"ע. הוכח/הפרך: g חח"ע, f חח"ע
	*~~נניח~~ <math>g \circ f</math> על. הוכח/הפרך: g על, f על		*תהיינה <math>f:A\to B, g:B\to C </math> פונקציות כך ש- <math>g \circ f</math> על. הוכח/הפרך: g על, f על

	'''פתרון:'''		'''פתרון:'''
שורה 98:		שורה 98:


	נניח <math>g \circ f</math> על. נסמן <math>g \circ f : A\rightarrow B</math> אזי לכל איבר <math>b\in B</math> קיים איבר <math>a\in A</math> כך ש <math>g(f(a))=b</math>. לכן עבור g ~~לכל b~~ קיים <math>f(a)</math> שנותן את b תחת g ולכן g על.		נניח <math>g \circ f</math> על. נסמן <math>g \circ f : A\rightarrow C</math> אזי לכל איבר <math>c\in C</math> קיים איבר <math>a\in A</math> כך ש <math>g(f(a))=c</math>. לכן עבור g נקבל שלכל <math>c\in C</math> קיים <math>f(a)\in B</math> שנותן את <math>c</math> תחת g, ולכן g על.

	דוגמא נגדית ל f: נתבונן בשתי הפונקציות מהטבעיים לעצמם		דוגמא נגדית ל f: נתבונן בשתי הפונקציות מהטבעיים לעצמם
	<math>f(n)=n+1</math>;		<math>f(n)=n+1</math>;
	<math>\forall n\~~not=~~0 g(n)=n-1 , g(0)=0</math>		<math>\forall n\neq 0 g(n)=n-1 , g(0)=0</math>
	ההרכבה היא הזהות		ההרכבה היא הזהות ו-<math>f</math> לא על, אין מקור ל-1.

	(עוד דוגמא נביט בפונקציות מהטבעיים לטבעיים. <math>f(n)=2n</math>, והפונקציה g מוגדרת כ <math>g(2n)=n</math> ו <math>g(2n+1)=n</math>. ההרכבה הינה פונקצית הזהות שהיא בפרט על, אבל f אינה על כיוון שהאי זוגיים כלל לא נמצאים בתמונה שלה.)		(עוד דוגמא נביט בפונקציות מהטבעיים לטבעיים. <math>f(n)=2n</math>, והפונקציה g מוגדרת כ <math>g(2n)=n</math> ו <math>g(2n+1)=n</math>. ההרכבה הינה פונקצית הזהות שהיא בפרט על, אבל f אינה על כיוון שהאי זוגיים כלל לא נמצאים בתמונה שלה.)

אריאל: /* פתרון */

2017-08-22T09:39:04Z

פתרון

→ הגרסה הקודמת		גרסה מ־09:39, 22 באוגוסט 2017
שורה 74:		שורה 74:
	הערה: הדבר אינו נכון אם A וB קבוצות אינסופיות.		הערה: הדבר אינו נכון אם A וB קבוצות אינסופיות.

	למשל ~~פונקצית הערך השלם~~ <math>f:\mathbb{R} \to \mathbb{Z} </math> המוגדרת <math>f(x) =~~\lfloor{x}\rfloor~~</math> היא ~~על ואינה~~ חח"ע		למשל הפונקציה <math>f:\mathbb{N} \to \mathbb{N} </math> המוגדרת <math>f(n) = n+1</math> היא חח"ע ואינה על.

	===הרכבת פונקציות===		===הרכבת פונקציות===

אריאל: /* תרגיל */

2017-08-22T09:35:55Z

תרגיל

→ הגרסה הקודמת		גרסה מ־09:35, 22 באוגוסט 2017
שורה 53:		שורה 53:

	====פתרון====		====פתרון====
	מימין לשמאל: נניח שקיימת פונקציה כנ"ל על, אם <math>B</math> ~~ריקה אז כמובן~~ <math>\|A\|\geq \|B\|</math>.		מימין לשמאל: נניח שקיימת פונקציה כנ"ל על, נסמן <math>\|B\|=k</math> ונסמן עוד <math>B=\{ b_1,...,b_k\} </math>. לכל <math>1\leq i\leq k</math> לאיבר <math>b_i\in B</math> יש מקור השונה משאר מקורות חבריו <math>f(a_i)=b_i</math>. לכן הקבוצה המתקבלת <math>\{ a_1,...,a_k\} \subseteq A</math> בעלת <math>k</math> איברים ולכן <math>\|A\|\geq \|B\|</math>

	~~אחרת,~~ נסמן <math>\|B\|=k</math> ונסמן עוד <math>B=\{ b_1,...,~~b_k~~\} ~~</math>. לכל <math>1\leq i\leq k</math> לאיבר <math>b_i\in B</math> יש מקור השונה משאר מקורות חבריו <math>f(a_i)~~=~~b_i</math>. לכן הקבוצה המתקבלת <math>~~\{ a_1,...,~~a_k~~\} ~~\subseteq A~~</math> ~~בעלת~~ <math>~~k</math> איברים ולכן <math>\|A\|~~\~~geq \|B\|</math>~~		משמאל לימין: נסמן <math>\|A\|=n,\|B\|=m,n\geq m</math>, ונסמן עוד <math>B=\{ b_1,...,b_m\} ,A=\{ a_1,...,a_m,...,a_n\}</math>, ונגדיר פונקציה ע"י <math>f(a_{i})=\begin{cases}
			b_{i} & 1\leq i\leq m\\
	~~משמאל לימין: שוב, אם <math>B~~</math> ~~ריקה~~		b_{1} & m+1\leq i\leq n
			\end{cases}</math>. זו פונקציה על.

	===תרגיל===		===תרגיל===

אריאל: /* תרגיל */

2017-08-22T09:26:29Z

תרגיל

→ הגרסה הקודמת		גרסה מ־09:26, 22 באוגוסט 2017
שורה 50:		שורה 50:

	===תרגיל===		===תרגיל===
	תהיינה <math>A,B</math> קבוצות סופיות. הוכיחו שקיימת פונקציה <math>f:A\rightarrow B</math> על אמ"ם <math>\|A\|\geq \|B\|</math>.		תהיינה <math>A,B</math> קבוצות סופיות לא ריקות. הוכיחו שקיימת פונקציה <math>f:A\rightarrow B</math> על אמ"ם <math>\|A\|\geq \|B\|</math>.

	====פתרון====		====פתרון====
שורה 57:		שורה 57:
	אחרת, נסמן <math>\|B\|=k</math> ונסמן עוד <math>B=\{ b_1,...,b_k\} </math>. לכל <math>1\leq i\leq k</math> לאיבר <math>b_i\in B</math> יש מקור השונה משאר מקורות חבריו <math>f(a_i)=b_i</math>. לכן הקבוצה המתקבלת <math>\{ a_1,...,a_k\} \subseteq A</math> בעלת <math>k</math> איברים ולכן <math>\|A\|\geq \|B\|</math>		אחרת, נסמן <math>\|B\|=k</math> ונסמן עוד <math>B=\{ b_1,...,b_k\} </math>. לכל <math>1\leq i\leq k</math> לאיבר <math>b_i\in B</math> יש מקור השונה משאר מקורות חבריו <math>f(a_i)=b_i</math>. לכן הקבוצה המתקבלת <math>\{ a_1,...,a_k\} \subseteq A</math> בעלת <math>k</math> איברים ולכן <math>\|A\|\geq \|B\|</math>

	משמאל לימין: שוב, אם <math>B</math> ריקה		משמאל לימין: שוב, אם <math>B</math> ריקה

	===תרגיל===		===תרגיל===