הבדלים בין גרסאות בדף "פתרון"
שורה 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
יהיו שכולן הפיכות\חח"ע\על. הוכיחו שההרכבה הפיכה\חח"ע\על.
פתרון:
למעשה אפשר לעשות אינדוקציה על המשפט מן ההרצאה. עבור שתי פונקציות זה בהרצאה. נניח נכונות ל ונוכיח ל.
חח"ע: נניח אזי מחח"ע של נקבל כי מהנחת האינדוקציה עבור פונקציות נקבל שההרכבה חח"ע ולכן .
על: יהא כיוון ש- על, קיים כך ש-. בנוסף, מהנחת האינדוקציה קיים כך ש ולכן נקבל . מש"ל.
הפיכות: נובע מחח"ע יחד עם על.