הבדלים בין גרסאות בדף "פתרון"
(יצירת דף עם התוכן "===תרגיל 1=== יהיו <math>A</math> ו-<math>B</math> קבוצות סופיות בעלות עוצמה זהה. הוכיחו שכל פונקציה מ-<math>...") |
|||
(גרסת ביניים אחת של אותו משתמש אינה מוצגת) | |||
שורה 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>. | ||
גרסה אחרונה מ־15:15, 28 במאי 2019
תרגיל 1
יהיו ו-
קבוצות סופיות בעלות עוצמה זהה. הוכיחו שכל פונקציה מ-
ל-
הינה על אם"ם היא חח"ע.
פתרון:
נסמן . כאשר כל האיברים ב-
שונים זה מזה וכנ"ל ב-
.
נניח חח"ע אזי
כיוון ש-
ובשניהם יש אותו מספר איברים, מתקיים שיוון ולכן
על.
נניח על. נניח בשלילה ש-
אינה חח"ע אזי
(כי יש שני איברים שנשלחים לאותו מקום) ואז
אינה על, שזו סתירה.
הערה: הדבר אינו נכון אם ו-
קבוצות אינסופיות. נסו למצוא דוגמה.
תרגיל 2
תהא קבוצה. נגדיר פונקציה
ע"י:
האם היא חח"ע? על?
פתרון:
חח"ע: כן. תהיינה אם
אזי
. אחרת
. כלומר
.
על: לא. נבחר . למשל לקבוצה
אין מקור. אין תת קבוצה שהאוסף הזה הוא בדיוק אוסף הקבוצות המכילות אותה.
תרגיל 3
יהיו שכולן הפיכות\חח"ע\על. הוכיחו שההרכבה
הפיכה\חח"ע\על.
פתרון:
למעשה אפשר לעשות אינדוקציה על המשפט מן ההרצאה. עבור שתי פונקציות זה בהרצאה. נניח נכונות ל ונוכיח ל
.
חח"ע: נניח אזי מחח"ע של
נקבל כי
מהנחת האינדוקציה עבור
פונקציות נקבל שההרכבה חח"ע ולכן
.
על: יהא כיוון ש-
על, קיים
כך ש-
.
בנוסף, מהנחת האינדוקציה קיים
כך ש
ולכן נקבל
. מש"ל.
הפיכות: נובע מחח"ע יחד עם על.