4. פונקציה הופכית והרכבת פונקציות
פונקציה הופכית (Inverse Function)
פונקציה הופכית שמאלית
לפונקציה מלאה ו-חח"ע \(f: A \to B\) יש פונקציה הופכית (שמאלית), \(f^{-1}: B \to A\), שהינה חח"ע ועל, אולי לא מלאה. נקראת
left inverse function.
פונקציה הופכית מלאה
לפונקציית שקילות (מלאה, חח"ע ועל) \(f: A \leftrightarrow B\) יש פונקציה הופכית \(f^{-1}: B \leftrightarrow A\) שהיא גם מלאה, חח"ע ועל.
הרכבת פונקציות (Composition)
הגדרה
עבור פונקציות \(f: A \to B\) ו-\(g: B \to C\), ההרכבה מוגדרת להיות:
\(g \circ f(x) := g(f(x))\)
תכונה חשובה
הרכבה של פונקציות שקילות הינה גם כן פונקציית שקילות.
5. הפרדוקס של גלילאו גלילי (1638)
נתבונן על קבוצת המספרים הטבעיים:
\(0, \; 1, \; 2, \; 3, \; 4, \; 5, \; 6, \; 7, \; 8, \; 9, \; \ldots\)
נוסיף סימון "ריבוע" ליד כל מספר:
\(0^2, \; 1^2, \; 2^2, \; 3^2, \; 4^2, \; 5^2, \; 6^2, \; 7^2, \; 8^2, \; 9^2, \; \ldots\)
נפרש את הסימן כהעלאה בריבוע:
\(0, \; 1, \; 4, \; 9, \; 16, \; 25, \; 36, \; 49, \; 64, \; 81, \; \ldots\)
הפרדוקס
הקבוצה של ריבועי המספרים הטבעיים \(\{0^2, 1^2, 2^2, 3^2, \ldots\}\)
מוכלת ממש בקבוצת כל הטבעיים \(\mathbb{N}\) — אך ישנה
התאמה מלאה (bijection) ביניהן!
הפונקציה \(f(n) = n^2\) היא חח"ע ועל מ-\(\mathbb{N}\) אל קבוצת הריבועים.
6. דוגמאות נוספות להשוואת קבוצות
\(|\mathbb{N}| \stackrel{?}{=} |\mathbb{Z}|\)
כן! ניתן לבנות bijection מ-\(\mathbb{N}\) ל-\(\mathbb{Z}\) למשל:
\(0 \mapsto 0, \quad 1 \mapsto 1, \quad 2 \mapsto -1, \quad 3 \mapsto 2, \quad 4 \mapsto -2, \quad \ldots\)
\(|(0,1)| \stackrel{?}{=} |(1,\infty)|\)
כן! הפונקציה \(f(x) = \frac{1}{x}\) היא bijection מ-\((0,1)\) ל-\((1,\infty)\).
\(|(0,1)| \stackrel{?}{=} |[0,1)|\)
כן! למרות ש-\((0,1) \subset [0,1)\), ניתן לבנות bijection ביניהן.
8. סדר עוצמות - \(|A| \leq |B|\)
הגדרה: קטנה או שווה עוצמה
קבוצה \(A\) קטנה או שוות-עוצמה לקבוצה \(B\), בסימון \(|A| \leq |B|\), אם יש
פונקציה מלאה ו-חח"ע מ-\(A\) ל-\(B\).
הגדרה חלופית
\(|A| \leq |B|\) אם יש פונקציה (חלקית או מלאה) מ-\(B\)
על \(A\).
דוגמאות
- \(|\{a,b\}| \leq |\{2,5,8\}|\)
- \(|\{a,b\}| \leq |\mathbb{N}|\)
- \(|\mathbb{N}| \leq |\mathbb{R}|\)
- \(|(0,\infty)| \leq |(0,1)|\)
משפט: שקילות בין הגדרות
משפט
לכל שתי קבוצות לא ריקות \(A\) ו-\(B\), מתקיים ש- \(|A| \leq |B|\)
אם ורק אם יש פונקציה מ-\(B\) על \(A\).
מתחבאים כאן שני משפטים:
- משפט 1: \(|A| \leq |B|\) אמ"מ יש פונקציה מ-\(B\) על \(A\).
- משפט 2: יש פונקציה מ-\(B\) על \(A\) אמ"מ יש פונקציה מלאה מ-\(B\) על \(A\).
רעיון ההוכחה (סכמטית)
כיוון א': אם \(|A| \leq |B|\) אז יש פונקציה מלאה ו-חח"ע \(f: A \to B\). ניתן "להפוך" אותה כדי לקבל פונקציה מ-\(B\) על \(A\).
כיוון ב': אם יש פונקציה מ-\(B\) על \(A\), ניתן לבחור לכל איבר ב-\(A\) מקור אחד ב-\(B\), ולקבל פונקציה חח"ע מ-\(A\) ל-\(B\).
9. עוצמה ממש קטנה - \(|A| < |B|\)
הגדרה: קטנה ממש (Strictly Smaller)
עבור קבוצות \(A\) ו-\(B\), נגדיר ש-\(A\)
קטנה ממש מ-\(B\), ונסמן \(|A| < |B|\), אם:
\(|A| \leq |B| \quad \text{ו-} \quad |A| \neq |B|\)
כלומר, קיימת פונקציה מלאה וחח"ע מ-\(A\) ל-\(B\),
ולא קיימת פונקציה מלאה ו-חח"ע מ-\(B\) ל-\(A\).
דוגמאות
- \(|\{4,1,2\}| < |\{2,8\}|\) (3 < 2? לא!) — תיקון: \(|\{2,8\}| < |\{4,1,2\}|\)
- \(|\{7,8,9\}| < |\mathbb{N}|\)
- \(|\mathbb{Z}| \not< |\mathbb{N}|\) (כי \(|\mathbb{N}| = |\mathbb{Z}|\))
- \(|\mathbb{N}| \stackrel{?}{<} |\mathbb{R}|\) (נראה בהמשך הקורס...)
10. קבוצות סופיות ואינסופיות
הגדרה: קבוצה אינסופית
קבוצה הינה
אינסופית אם היא שקולה לתת-קבוצה ממש שלה.
הגדרה: קבוצה סופית
קבוצה הינה
סופית אם היא לא אינסופית.
דוגמאות
- \(\emptyset\) סופית.
- \(\{1,5\}\) סופית.
- לכל \(n \in \mathbb{N}\), הקבוצה \(\{0, 1, \ldots, n-1\}\) סופית.
- \(\mathbb{N}\) אינסופית.
- \(\mathbb{R}\) אינסופית.
משפטים על קבוצות אינסופיות
משפט 1
אם \(A\) אינסופית ו-\(A \subseteq B\) אז \(B\) אינסופית.
רעיון: מהיות \(A\) אינסופית, קיימות \(S \subset A\) ו-\(f: A \to S\) הפיכה. ניתן להרחיב את \(f\) ל-\(B\) כולה.
משפט 2
אם \(A\) אינסופית ו-\(A \sim B\) אז \(B\) אינסופית.
(תוכיחו זאת בתירגול.)
מסקנה
אם \(A\) סופית ו-\(A \sim B\) אז \(B\) סופית.