פתרון - היסטוריית גרסאות

Harel530 ב־15:15, 28 במאי 2019

2019-05-28T15:15:23Z

→ הגרסה הקודמת		גרסה מ־15:15, 28 במאי 2019
שורה 1:		שורה 1:
	===תרגיל 1===		===תרגיל 1===
	יהיו <math>A</math> ו-<math>B</math> קבוצות סופיות בעלות עוצמה זהה. הוכיחו שכל פונקציה מ-<math>A</math> ל-<math>B</math> הינה על אם"ם היא חח"ע.		יהיו <math>A</math> ו-<math>B</math> קבוצות סופיות בעלות עוצמה זהה. הוכיחו שכל פונקציה מ-<math>A</math> ל-<math>B</math> הינה על אם"ם היא חח"ע.
	פתרון:\
			פתרון:

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

שורה 13:		שורה 15:
	===תרגיל 2===		===תרגיל 2===
	תהא <math>A</math> קבוצה. נגדיר פונקציה <math>f:P(A)\rightarrow P(P(A))</math> ע"י: <math>f(X)=\{ B\subseteq A\|X\subseteq B\}</math> האם היא חח"ע? על?		תהא <math>A</math> קבוצה. נגדיר פונקציה <math>f:P(A)\rightarrow P(P(A))</math> ע"י: <math>f(X)=\{ B\subseteq A\|X\subseteq B\}</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)\setminus f(Y)</math>. אחרת <math>Y\in f(Y)\setminus f(X)</math>. כלומר <math>f(X)\neq f(Y)</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)\setminus f(Y)</math>. אחרת <math>Y\in f(Y)\setminus f(X)</math>. כלומר <math>f(X)\neq f(Y)</math>.

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

	פתרון:		פתרון:

	למעשה אפשר לעשות אינדוקציה על המשפט מן ההרצאה. עבור שתי פונקציות זה בהרצאה. נניח נכונות ל<math>k-1</math> ונוכיח ל<math>k</math>.		למעשה אפשר לעשות אינדוקציה על המשפט מן ההרצאה. עבור שתי פונקציות זה בהרצאה. נניח נכונות ל<math>k-1</math> ונוכיח ל<math>k</math>.

Harel530 ב־15:14, 28 במאי 2019

2019-05-28T15:14:16Z

→ הגרסה הקודמת		גרסה מ־15:14, 28 במאי 2019
שורה 1:		שורה 1:
	===תרגיל 1===		===תרגיל 1===
	יהיו <math>A</math> ו-<math>B</math> קבוצות סופיות בעלות עוצמה זהה. הוכיחו שכל פונקציה מ-<math>A</math> ל-<math>B</math> הינה על אם"ם היא חח"ע.		יהיו <math>A</math> ו-<math>B</math> קבוצות סופיות בעלות עוצמה זהה. הוכיחו שכל פונקציה מ-<math>A</math> ל-<math>B</math> הינה על אם"ם היא חח"ע.
	פתרון:		פתרון:\
	נסמן <math>f:A\to B, A=\{a_1,\dots, a_n\},B=\{b_1,\dots, b_n\} </math> . כאשר כל האיברים ב-<math>A</math> שונים זה מזה וכנ"ל ב-<math>B</math>.		נסמן <math>f:A\to B, A=\{a_1,\dots, a_n\},B=\{b_1,\dots, b_n\} </math> . כאשר כל האיברים ב-<math>A</math> שונים זה מזה וכנ"ל ב-<math>B</math>.

Harel530: יצירת דף עם התוכן "===תרגיל 1=== יהיו $A$ ו- $B$ קבוצות סופיות בעלות עוצמה זהה. הוכיחו שכל פונקציה מ- $..."$

2019-05-28T15:13:22Z

יצירת דף עם התוכן "===תרגיל 1=== יהיו <math>A</math> ו-<math>B</math> קבוצות סופיות בעלות עוצמה זהה. הוכיחו שכל פונקציה מ-<math>..."

דף חדש

===תרגיל 1===
יהיו <math>A</math> ו-<math>B</math> קבוצות סופיות בעלות עוצמה זהה. הוכיחו שכל פונקציה מ-<math>A</math> ל-<math>B</math> הינה על אם"ם היא חח"ע.
פתרון:
נסמן <math>f:A\to B, A=\{a_1,\dots, a_n\},B=\{b_1,\dots, b_n\} </math> . כאשר כל האיברים ב-<math>A</math> שונים זה מזה וכנ"ל ב-<math>B</math>.

נניח <math>f</math> חח"ע אזי <math>|\{f(a_1),\dots, f(a_n)\}|=n</math>
כיוון ש-<math>\{f(a_1),\dots, f(a_n)\}\subseteq B </math> ובשניהם יש אותו מספר איברים, מתקיים שיוון ולכן <math>f </math> על.

נניח <math>f </math> על. נניח בשלילה ש-<math>f</math> אינה חח"ע אזי <math>|\{f(a_1),\dots, f(a_n)\}|<n</math> (כי יש שני איברים שנשלחים לאותו מקום) ואז <math>f</math> אינה על, שזו סתירה.

הערה: הדבר אינו נכון אם <math>A</math> ו-<math>B</math> קבוצות אינסופיות. נסו למצוא דוגמה.

===תרגיל 2===
תהא <math>A</math> קבוצה. נגדיר פונקציה <math>f:P(A)\rightarrow P(P(A))</math> ע"י: <math>f(X)=\{ B\subseteq A|X\subseteq B\}</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)\setminus f(Y)</math>. אחרת <math>Y\in f(Y)\setminus f(X)</math>. כלומר <math>f(X)\neq f(Y)</math>.

על: לא. נבחר <math>A=\{1,\dots,7\}</math>. למשל לקבוצה <math>\{ \{ 1,2\}, \{ 3,4\} \}\in P(P(A))</math> אין מקור. אין תת קבוצה שהאוסף הזה הוא בדיוק אוסף הקבוצות המכילות אותה.

===תרגיל 3===
יהיו <math>f_1,\dots f_k:A\to A</math> שכולן הפיכות\חח"ע\על. הוכיחו שההרכבה <math>f_k \circ \dots \circ f_1</math> הפיכה\חח"ע\על.
פתרון:
למעשה אפשר לעשות אינדוקציה על המשפט מן ההרצאה. עבור שתי פונקציות זה בהרצאה. נניח נכונות ל<math>k-1</math> ונוכיח ל<math>k</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>k-1</math> פונקציות נקבל שההרכבה חח"ע ולכן <math>x_1=x_2</math>.

על: יהא <math>y\in A</math> כיוון ש-<math>f_k</math> על, קיים <math>a\in A</math> כך ש-<math>f_k(a) = y</math>.
בנוסף, מהנחת האינדוקציה קיים <math>b\in A</math> כך ש <math>f_{k-1}\circ \dots \circ f_1(b)=a</math> ולכן נקבל
<math>f_k\circ \dots \circ f_1(b) = f_k\circ (f_{k-1}\circ \dots \circ f_1)(b)=f_k(a)=y</math>. מש"ל.

הפיכות: נובע מחח"ע יחד עם על.

פתרון - היסטוריית גרסאות

Harel530 ב־15:15, 28 במאי 2019

Harel530 ב־15:14, 28 במאי 2019

Harel530: יצירת דף עם התוכן "===תרגיל 1=== יהיו A ו-B קבוצות סופיות בעלות עוצמה זהה. הוכיחו שכל פונקציה מ-..."

Harel530: יצירת דף עם התוכן "===תרגיל 1=== יהיו $A$ ו- $B$ קבוצות סופיות בעלות עוצמה זהה. הוכיחו שכל פונקציה מ- $..."$