הבדלים בין גרסאות בדף "פתרון"

מתוך Math-Wiki
קפיצה אל: ניווט, חיפוש
 
שורה 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

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

פתרון:

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

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

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

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

תרגיל 2

תהא A קבוצה. נגדיר פונקציה f:P(A)\rightarrow P(P(A)) ע"י: f(X)=\{ B\subseteq A|X\subseteq B\} האם היא חח"ע? על?

פתרון:

חח"ע: כן. תהיינה X,Y\in P(A), X\neq Y אם X\subsetneq Y\lor (X\nsubseteq Y\land Y\nsubseteq X) אזי X\in f(X)\setminus f(Y). אחרת Y\in f(Y)\setminus f(X). כלומר f(X)\neq f(Y).

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

תרגיל 3

יהיו f_1,\dots f_k:A\to A שכולן הפיכות\חח"ע\על. הוכיחו שההרכבה f_k \circ \dots \circ f_1 הפיכה\חח"ע\על.

פתרון:

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

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

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

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

מקור: https://math-wiki.com/index.php?title=פתרון&oldid=81284