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

רועי91: /* הרכבת פונקציות */

2023-08-21T20:19:28Z

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

→ הגרסה הקודמת		גרסה מ־20:19, 21 באוגוסט 2023
שורה 98:		שורה 98:

	'''הגדרה:'''		'''הגדרה:'''
	יהיו <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>

אחיה בר-און: /* פונקציות */

2021-06-21T09:33:03Z

פונקציות

→ הגרסה הקודמת		גרסה מ־09:33, 21 ביוני 2021
שורה 2:		שורה 2:

	==פונקציות==		==פונקציות==
	'''הגדרה:''' יהיו A,B קבוצות וR יחס בינהן. אזי:		'''הגדרה:''' (אפשר לדלג ולהתמקד בתחום וטווח של פונקציות ולא של יחסיים כללים) יהיו A,B קבוצות וR יחס בינהן. אזי:
	התחום של R הינו <math>dom(R)=\{a\in A\|\exists b\in B:(a,b)\in R\}=\{(,\;),(*,\;)\dots \}</math>		התחום של R הינו <math>dom(R)=\{a\in A\|\exists b\in B:(a,b)\in R\}=\{(,\;),(*,\;)\dots \}</math>
	התמונה של R הינה <math>im(R)=\{b\in B\|\exists a\in A:(a,b)\in R\}=\{(\;,),(\; ,*)\dots \}</math>		התמונה של R הינה <math>im(R)=\{b\in B\|\exists a\in A:(a,b)\in R\}=\{(\;,),(\; ,*)\dots \}</math>

אחיה בר-און: /* דוגמאות: */

2020-07-24T14:10:11Z

דוגמאות:

→ הגרסה הקודמת		גרסה מ־14:10, 24 ביולי 2020
שורה 38:		שורה 38:
	*<math>f:\mathbb{Z}\rightarrow\mathbb{Z}</math> כאשר <math>f(p)=p</math>. זו פונקציית הזהות.		*<math>f:\mathbb{Z}\rightarrow\mathbb{Z}</math> כאשר <math>f(p)=p</math>. זו פונקציית הזהות.
	*<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{R}\to\mathbb{R}</math> המוגדרת ע"י הכלל <math>f(x)=\sin(x)</math>.
			*<math>f:\mathbb{R}\to\mathbb{R}</math> המוגדרת ע"י הכלל <math>f(x)=x^{3}</math>
			* <math>f:\mathbb{C}\to\mathbb{C}</math> המוגדרת ע"י הכלל <math>f(x)=x^{2}</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{R}\rightarrow\mathbb{Z}</math> כאשר <math>f(x)=[x]</math> מוגדר להיות הערך השלם הקרוב ביותר ל-x (במקרה של חצי לוקחים את הגבוה). זו פונקציה על שאינה חח"ע

Relweiz ב־07:47, 31 ביולי 2019

2019-07-31T07:47:58Z

→ הגרסה הקודמת		גרסה מ־07:47, 31 ביולי 2019
שורה 91:		שורה 91:
	הוכיחו שאם <math>f</math> על, אז <math>g</math> לא חח"ע.		הוכיחו שאם <math>f</math> על, אז <math>g</math> לא חח"ע.

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


שורה 114:		שורה 114:
	*נניח <math>g \circ f</math> על. הוכח/הפרך: g על, f על		*נניח <math>g \circ f</math> על. הוכח/הפרך: g על, f על

	~~'''~~פתרון~~:'''~~		=====פתרון=====

	נניח <math>g \circ f</math> חח"ע. נניח בשלילה ש-f אינה חח"ע. לכן קיימים <math>x,y</math> כך ש <math>f(x)=f(y)</math> אבל <math>x\neq y</math>. אבל, <math>g\circ f (x) = g(f(x))=g(f(y))=g\circ f(y)</math> בסתירה לחח"ע של ההרכבה, ולכן f חח"ע.		נניח <math>g \circ f</math> חח"ע. נניח בשלילה ש-f אינה חח"ע. לכן קיימים <math>x,y</math> כך ש <math>f(x)=f(y)</math> אבל <math>x\neq y</math>. אבל, <math>g\circ f (x) = g(f(x))=g(f(y))=g\circ f(y)</math> בסתירה לחח"ע של ההרכבה, ולכן f חח"ע.
שורה 130:		שורה 130:
	(עוד דוגמא נביט בפונקציות מהטבעיים לטבעיים. <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 אינה על כיוון שהאי זוגיים כלל לא נמצאים בתמונה שלה.)

	===פונקציות הפיכות===		==פונקציות הפיכות==
	'''הערה:''' לכל פונקציה <math>f</math> מתקיים <math>f\circ id =f</math> וגם <math>id \circ f =f</math>		'''הערה:''' לכל פונקציה <math>f</math> מתקיים <math>f\circ id =f</math> וגם <math>id \circ f =f</math>

שורה 152:		שורה 152:
	דרך אחרת להוכחת יחידות: נניח בשלילה ש g וh הופכיות שונות של f. מכיוון שהן שונות, הן חייבות להיות שונות על איבר אחד לפחות. כלומר, <math>\exists a\in A:g(a)\neq h(a)</math>. אבל <math>f(g(a))=f(h(a))</math> וזו סתירה לחח"ע של f.		דרך אחרת להוכחת יחידות: נניח בשלילה ש 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_1,\dots f_k:A\to A</math> הפיכות/חח"ע/על. הוכח שההרכבה <math>f_k \circ \dots \circ f_1</math> הפיכה/חח"ע/על

			=====הוכחה=====

			חח"ע: נניח <math>(f_k \circ \dots \circ f_1)(x_1) =(f_k \circ \dots \circ f_1)(x_2)</math> אזי מח"ע של <math>f_k</math>
			נקבל כי <math>(f_{k-1} \circ \dots \circ f_1)(x_1) =(f_{k-1} \circ \dots \circ f_1)(x_2)</math> באופן דומה נמשיך (או באינדוקציה) ונקבל <math>x_1=x_2</math>

			על: יהא <math>y\in A</math> כיוון ש <math>f_k</math> על קיים <math>a_k\in A</math> כך ש <math>f_k(a_k)= y</math>
			באותו אופן קיים <math>a_{k-1}</math> כך ש <math>f_{k-1}(a_{k-1}=a_k</math> נמשיך באופן דומה (או באינקודציה)
			ונקבל <math>(f_k \circ \dots \circ f_1)(a_1)=(f_k \circ \dots \circ f_2)(a_2)=\dots f_k\circ f_{k-1} (a_{k-1}) = f_k(a_k)=y</math>

			הפיכות: נובע מחח"ע+על

			====מסקנות====

	* אם <math>f,g</math> הפיכות אז <math>g\circ f</math> הפיכה.		* אם <math>f,g</math> הפיכות אז <math>g\circ f</math> הפיכה.
שורה 181:		שורה 195:
	5 <math>\{4,5,6\}^{\{1,2,3\}}\to \{4,5,6\}\times \{4,5,6\}\times\{4,5,6\}</math>, המוגדרת <math>f\mapsto (f(1),f(2),f(3))</math> חח"ע ועל.		5 <math>\{4,5,6\}^{\{1,2,3\}}\to \{4,5,6\}\times \{4,5,6\}\times\{4,5,6\}</math>, המוגדרת <math>f\mapsto (f(1),f(2),f(3))</math> חח"ע ועל.

	===תרגיל ===		====תרגיל====
	~~יהיו <math>f_1,\dots f_k:A\to A</math> הפיכות/חח"ע/על. הוכח שההרכבה <math>f_k \circ \dots \circ f_1</math> הפיכה/חח"ע/על~~

	~~הוכחה:~~

	~~חח"ע: נניח <math>(f_k \circ \dots \circ f_1)(x_1) =(f_k \circ \dots \circ f_1)(x_2)</math> אזי מח"ע של <math>f_k</math>~~
	~~נקבל כי <math>(f_{k-1} \circ \dots \circ f_1)(x_1) =(f_{k-1} \circ \dots \circ f_1)(x_2)</math> באופן דומה נמשיך (או באינדוקציה) ונקבל <math>x_1=x_2</math>~~

	~~על: יהא <math>y\in A</math> כיוון ש <math>f_k</math> על קיים <math>a_k\in A</math> כך ש <math>f_k(a_k)= y</math>~~
	~~באותו אופן קיים <math>a_{k-1}</math> כך ש <math>f_{k-1}(a_{k-1}=a_k</math> נמשיך באופן דומה (או באינקודציה)~~
	~~ונקבל <math>(f_k \circ \dots \circ f_1)(a_1)=(f_k \circ \dots \circ f_2)(a_2)=\dots f_k\circ f_{k-1} (a_{k-1}) = f_k(a_k)=y</math>~~

	~~הפיכות: נובע מחח"ע+על~~

	~~===תרגיל~~ ===
	הוכח כי אם <math>g\circ f \circ g =id</math> אז <math>f </math> הפיכה		הוכח כי אם <math>g\circ f \circ g =id</math> אז <math>f </math> הפיכה

Relweiz: /* פונקציות הפיכות */

2019-07-31T07:44:47Z

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

→ הגרסה הקודמת		גרסה מ־07:44, 31 ביולי 2019
שורה 137:		שורה 137:
	הערה: זכרו שפונקציה היא יחס. הפונקציה ההופכית שלה היא היחס ההופכי מטבע הדברים. על מנת שהיחס ההופכי יהיה פונקציה הוא צריך להיות ח"ע ושהתחום שלו יהיה כל B. תנאים אלה מתממשים רק אם f הינה חח"ע ועל.		הערה: זכרו שפונקציה היא יחס. הפונקציה ההופכית שלה היא היחס ההופכי מטבע הדברים. על מנת שהיחס ההופכי יהיה פונקציה הוא צריך להיות ח"ע ושהתחום שלו יהיה כל B. תנאים אלה מתממשים רק אם f הינה חח"ע ועל.

	~~'''תרגיל.'''~~		====משפט====

	הוכח כי f הפיכה אם"ם היא חח"ע ועל. כמו כן, הוכח שאם קיימת הופכית אזי היא יחידה.		הוכח כי f הפיכה אם"ם היא חח"ע ועל. כמו כן, הוכח שאם קיימת הופכית אזי היא יחידה.

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

	אם f הפיכה, אזי <math>f\circ f^{-1} = id_B</math> וגם <math>f^{-1}\circ f = id_A</math>. מכיוון שהזהות הינה חח"ע ועל, נובע ש-f חח"ע ועל לפי התרגיל הקודם בדבר הרכבת פונקציות.		אם f הפיכה, אזי <math>f\circ f^{-1} = id_B</math> וגם <math>f^{-1}\circ f = id_A</math>. מכיוון שהזהות הינה חח"ע ועל, נובע ש-f חח"ע ועל לפי התרגיל הקודם בדבר הרכבת פונקציות.
שורה 151:		שורה 151:

	דרך אחרת להוכחת יחידות: נניח בשלילה ש g וh הופכיות שונות של f. מכיוון שהן שונות, הן חייבות להיות שונות על איבר אחד לפחות. כלומר, <math>\exists a\in A:g(a)\neq h(a)</math>. אבל <math>f(g(a))=f(h(a))</math> וזו סתירה לחח"ע של f.		דרך אחרת להוכחת יחידות: נניח בשלילה ש 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,g</math> הפיכות אז <math>g\circ f</math> הפיכה.

			* אם <math>g\circ f</math> הפיכה אז <math>f</math> חח"ע, <math>g</math> על (והן לאו דוקא הפיכות).

	==== דוגמאות ====		==== דוגמאות ====
שורה 174:		שורה 180:

	5 <math>\{4,5,6\}^{\{1,2,3\}}\to \{4,5,6\}\times \{4,5,6\}\times\{4,5,6\}</math>, המוגדרת <math>f\mapsto (f(1),f(2),f(3))</math> חח"ע ועל.		5 <math>\{4,5,6\}^{\{1,2,3\}}\to \{4,5,6\}\times \{4,5,6\}\times\{4,5,6\}</math>, המוגדרת <math>f\mapsto (f(1),f(2),f(3))</math> חח"ע ועל.


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

אחיה בר-און: /* דוגמאות */

2019-07-30T12:10:16Z

דוגמאות

→ הגרסה הקודמת		גרסה מ־12:10, 30 ביולי 2019
שורה 163:		שורה 163:

	3 תהא <math>A</math> קבוצה ו <math>C\subseteq A</math> תת קבוצה. נגדיר <math>f:P(A)\to \{0,1\}</math> ע"י :		3 תהא <math>A</math> קבוצה ו <math>C\subseteq A</math> תת קבוצה. נגדיר <math>f:P(A)\to \{0,1\}</math> ע"י :
			<math>

	f(B)=		f(B)=
	\begin{cases} 1 & \text{ if } C\subseteq B \\ 0 & \text{ otherwise } \end{cases}		\begin{cases} 1 & \text{ if } C\subseteq B \\ 0 & \text{ otherwise } \end{cases}
שורה 175:		שורה 174:

	5 <math>\{4,5,6\}^{\{1,2,3\}}\to \{4,5,6\}\times \{4,5,6\}\times\{4,5,6\}</math>, המוגדרת <math>f\mapsto (f(1),f(2),f(3))</math> חח"ע ועל.		5 <math>\{4,5,6\}^{\{1,2,3\}}\to \{4,5,6\}\times \{4,5,6\}\times\{4,5,6\}</math>, המוגדרת <math>f\mapsto (f(1),f(2),f(3))</math> חח"ע ועל.
	~~<math>,~~

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

אחיה בר-און: /* דוגמאות */

2019-07-30T12:08:26Z

דוגמאות

→ הגרסה הקודמת		גרסה מ־12:08, 30 ביולי 2019
שורה 164:		שורה 164:
	3 תהא <math>A</math> קבוצה ו <math>C\subseteq A</math> תת קבוצה. נגדיר <math>f:P(A)\to \{0,1\}</math> ע"י :		3 תהא <math>A</math> קבוצה ו <math>C\subseteq A</math> תת קבוצה. נגדיר <math>f:P(A)\to \{0,1\}</math> ע"י :

	~~4 <math>\{4,5,6\}^{\{1,2,3\}}\to \{4,5,6\}\times \{4,5,6\}\times\{4,5,6\}</math>, המוגדרת <math>f\mapsto (f(1),f(2),f(3))</math> חח"ע ועל.~~
	~~<math>,~~
	f(B)=		f(B)=
	\begin{cases} 1 & \text{ if } C\subseteq B \\ 0 & \text{ otherwise } \end{cases}		\begin{cases} 1 & \text{ if } C\subseteq B \\ 0 & \text{ otherwise } \end{cases}
שורה 174:		שורה 173:
	4. תהא <math>A</math> קבוצה. אזי אפשר (בעזרת חומר שראינו בתירגול על יחסי שקילות)		4. תהא <math>A</math> קבוצה. אזי אפשר (בעזרת חומר שראינו בתירגול על יחסי שקילות)
	להגדיר <math>f:\{R \; \| \; R \text{ Equivalence relation }\}\to \{\text{Partitions of }A\}</math> ע"י <math>f(R)=A/R</math> והיא תהיה חח"ע ועל כי ראינו את הפונקציה ההופכית לה		להגדיר <math>f:\{R \; \| \; R \text{ Equivalence relation }\}\to \{\text{Partitions of }A\}</math> ע"י <math>f(R)=A/R</math> והיא תהיה חח"ע ועל כי ראינו את הפונקציה ההופכית לה

			5 <math>\{4,5,6\}^{\{1,2,3\}}\to \{4,5,6\}\times \{4,5,6\}\times\{4,5,6\}</math>, המוגדרת <math>f\mapsto (f(1),f(2),f(3))</math> חח"ע ועל.
			<math>,

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

אחיה בר-און: /* תרגיל */

2019-07-30T11:39:35Z

תרגיל

→ הגרסה הקודמת		גרסה מ־11:39, 30 ביולי 2019
שורה 80:		שורה 80:

	==== תרגיל ====		==== תרגיל ====
	א. תהא A קבוצה לא ריקה. מצאו פונקציה על <math>F:A^A\to A</math>.		א. תהא A קבוצה לא ריקה. מצאו פונקציה <math>F:A^A\to A</math> שהיא על.

	ב. תהא <math>A</math> קבוצה. מצאו פונקציה <math>F:A\to A^A</math>.		ב. תהא <math>A</math> קבוצה. מצאו פונקציה <math>F:A\to A^A</math> שהיא חח"ע.

	ג. למה בסעיף א צריך לא ריקה ובסעיף ב אפשר גם ריקה?		ג. למה בסעיף א צריך לא ריקה ובסעיף ב אפשר גם ריקה?

Relweiz: /* תרגיל */

2019-07-29T09:38:58Z

תרגיל

→ הגרסה הקודמת		גרסה מ־09:38, 29 ביולי 2019
שורה 51:		שורה 51:
	* תהא <math>A\subseteq B</math> אזי הפונקציה <math>i : A\to B </math> המוגדרת <math>i(a)=a</math> נקראת פונקציה ההכלה (במקרה ש <math>A=B</math> זה פונקצית הזהות). פונקצית ההכלה היא חח"ע.		* תהא <math>A\subseteq B</math> אזי הפונקציה <math>i : A\to B </math> המוגדרת <math>i(a)=a</math> נקראת פונקציה ההכלה (במקרה ש <math>A=B</math> זה פונקצית הזהות). פונקצית ההכלה היא חח"ע.

	===תרגיל===		====תרגיל (בשיעוריי הבית)====
	יהיו A ו-B קבוצות סופיות בעלות עוצמה זהה. הוכח שכל פונקציה מ-A ל-B הינה על אם"ם היא חח"ע		יהיו A ו-B קבוצות סופיות בעלות עוצמה זהה. הוכח שכל פונקציה מ-A ל-B הינה על אם"ם היא חח"ע

	~~'''~~הוכחה~~:'''~~		=====הוכחה=====
	נסמן <math>f:A\to B, A=\{a_1,\dots a_n\},B=\{b_1,\dots b_n\} </math> . כאשר כל האיברים ב A שונים זה מזה וכנ"ל ל B		נסמן <math>f:A\to B, A=\{a_1,\dots a_n\},B=\{b_1,\dots b_n\} </math> . כאשר כל האיברים ב A שונים זה מזה וכנ"ל ל B

Relweiz: /* פתרון */

2019-07-29T09:34:45Z

פתרון

→ הגרסה הקודמת		גרסה מ־09:34, 29 ביולי 2019
שורה 108:		שורה 108:
	<math>\Leftarrow</math>: נתון: F חח"ע. נניח <math>g(n)=g(m)</math>, לכן עבור הפונקציות הקבועות <math>f\equiv n,f'\equiv m</math> נקבל <math>\forall k:g\circ f(k)=g((n)=g(m)=g\circ f'(k)</math> ולכן <math>F(f)=g\circ f=g\circ f'=F(f')</math>, ומחח"ע של F נקבל <math>f=f'</math> ולכן <math>n=m</math>.		<math>\Leftarrow</math>: נתון: F חח"ע. נניח <math>g(n)=g(m)</math>, לכן עבור הפונקציות הקבועות <math>f\equiv n,f'\equiv m</math> נקבל <math>\forall k:g\circ f(k)=g((n)=g(m)=g\circ f'(k)</math> ולכן <math>F(f)=g\circ f=g\circ f'=F(f')</math>, ומחח"ע של F נקבל <math>f=f'</math> ולכן <math>n=m</math>.

	<math>Rightarrow</math>: נתון <math>g</math> חח"ע. תהיינה <math>f\neq f'\in \mathbb{N}^{\mathbb{N}}</math>, לכן יש <math>n\in \mathbb {N}</math> כך ש- <math>f(n)\neq f'(n)</math>, ולכן זה מתקיים גם אחרי ההרכבה, ולכן <math>F(f)\neq F(f')</math>.		<math>\Rightarrow</math>: נתון <math>g</math> חח"ע. תהיינה <math>f\neq f'\in \mathbb{N}^{\mathbb{N}}</math>, לכן יש <math>n\in \mathbb {N}</math> כך ש- <math>f(n)\neq f'(n)</math>, ולכן זה מתקיים גם אחרי ההרכבה, ולכן <math>F(f)\neq F(f')</math>.

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