פתרון

תרגיל 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$. מש"ל.

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