רקע: הגדרת פעולות וחוקים מרכזיים
פעולות על עוצמות
עבור \(|A|=\alpha,\;|B|=\beta\),
זרות:
- \(\alpha + \beta = |A \cup B|\)
- \(\alpha \cdot \beta = |A \times B|\)
- \(\alpha^\beta = |A^B|\) (קבוצת הפונקציות המלאות \(B \to A\))
חוקי חזקות
\((\alpha \cdot \beta)^\gamma = \alpha^\gamma \cdot \beta^\gamma\), \(\alpha^{\beta+\gamma} = \alpha^\beta \cdot \alpha^\gamma\), \((\alpha^\beta)^\gamma = \alpha^{\beta \cdot \gamma}\).
אין קיפול אחד: \(a^{b^c} = a^{(b^c)} \ne (a^b)^c = a^{b\cdot c}\).
המשפט המרכזי של עוצמות אינסופיות
כאשר לפחות אחת מהקבוצות אינסופית ושתי העוצמות \(\ne 0\):
\[ \alpha \cdot \beta \;=\; \alpha + \beta \;=\; \max(\alpha, \beta). \]
חזקות: אם \(\alpha\) אינסופית ו-\(2 \le \beta \le 2^\alpha\), אז \(\beta^\alpha = 2^\alpha\).
מסקנות שימושיות
- \(\aleph_0 + \aleph_0 = \aleph_0,\;\aleph_0 \cdot \aleph_0 = \aleph_0\)
- \(\aleph + \aleph = \aleph,\;\aleph \cdot \aleph = \aleph\)
- \(\aleph_0^{\aleph_0} = 2^{\aleph_0} = \aleph\)
- \(\aleph_0^{\aleph} = 2^{\aleph}\)
- \(\aleph^{\aleph_0} = 2^{\aleph_0} = \aleph\)
- \(\aleph^{\aleph} = 2^{\aleph}\)
תרגיל 1: שיוויונות בעוצמות
השאלה
הוכיחו או הפריכו לפי אריתמטיקה של עוצמות:
- \(\aleph^{\aleph_0} = \aleph\)
- \(|\mathbb{R}^\mathbb{Q}| = |\mathbb{R} \times \mathbb{Q}|\)
- \(|P(P(\mathbb{Q}))| < |P(\mathbb{R})|\)
סעיף א — נכון
ℵ^{ℵ₀} = (2^{ℵ₀})^{ℵ₀} (כי ℵ = 2^{ℵ₀})
= 2^{ℵ₀ · ℵ₀} (חוק חזקות)
= 2^{ℵ₀} (כי ℵ₀ · ℵ₀ = ℵ₀)
= ℵ. ∎
סעיף ב — נכון
אגף שמאל: \(|\mathbb{R}^\mathbb{Q}| = |\mathbb{R}|^{|\mathbb{Q}|} = \aleph^{\aleph_0} = \aleph\) (לפי סעיף א).
אגף ימין: \(|\mathbb{R} \times \mathbb{Q}| = \aleph \cdot \aleph_0 = \max(\aleph, \aleph_0) = \aleph\).
שני האגפים \(= \aleph\). ∎
סעיף ג — לא נכון, מפריכים
אגף שמאל: \(|P(P(\mathbb{Q}))| = 2^{2^{\aleph_0}}\).
אגף ימין: \(|P(\mathbb{R})| = 2^{\aleph} = 2^{2^{\aleph_0}}\).
שני האגפים שווים ולא קטן ממש. הטענה הופרכה.
תובנה
\(|\mathbb{Q}| = \aleph_0\) ו-\(|\mathbb{R}| = 2^{\aleph_0}\) — נראה הפרש "גדול". אבל אחרי שני יישומי \(P\), שניהם מגיעים לאותה רמה \(2^{2^{\aleph_0}}\).
תרגיל 2: \(|\mathbb{R}\setminus\mathbb{Q}| = \aleph\)
השאלה
הוכיחו: \(|\mathbb{R} \setminus \mathbb{Q}| = \aleph\).
הוכחה. נראה |ℝ∖ℚ| ≤ ℵ ו-|ℝ∖ℚ| ≥ ℵ.
כיוון 1: ℝ∖ℚ ⊆ ℝ ⟹ |ℝ∖ℚ| ≤ |ℝ| = ℵ.
כיוון 2: ℚ ⊆ ℝ ⟹ נכתוב את ℝ כאיחוד זר:
ℝ = ℚ ∪ (ℝ∖ℚ), ו-ℚ ∩ (ℝ∖ℚ) = ∅.
לפי הגדרת חיבור עוצמות (לקבוצות זרות):
|ℝ| = |ℚ| + |ℝ∖ℚ| ⟹ ℵ = ℵ₀ + |ℝ∖ℚ|.
לפי משפט: ℵ₀ + |ℝ∖ℚ| = max(ℵ₀, |ℝ∖ℚ|).
אם |ℝ∖ℚ| ≤ ℵ₀, אז max(ℵ₀, |ℝ∖ℚ|) = ℵ₀ ≠ ℵ — סתירה.
לכן |ℝ∖ℚ| > ℵ₀, ולכן max(ℵ₀, |ℝ∖ℚ|) = |ℝ∖ℚ| = ℵ.
⟹ |ℝ∖ℚ| = ℵ. ∎
אינטואיציה
יש "הרבה יותר" אי-רציונליים מרציונליים. למרות שיש אינסוף של כל אחד — הרציונליים בני-מניה (\(\aleph_0\)), האי-רציונליים בעוצמת הרצף (\(\aleph\)).
תרגיל 3: עוצמות סדרות ופונקציות
השאלה
- מהי עוצמת קבוצת כל הפונקציות המלאות מהטבעיים לטבעיים?
- מהי עוצמת קבוצת כל הסדרות הבינאריות האינסופיות?
- מהי עוצמת קבוצת כל הסדרות האינסופיות של מספרים ממשיים?
סעיף א — \(|\mathbb{N}^\mathbb{N}| = \aleph\)
\(|\mathbb{N}^\mathbb{N}| = \aleph_0^{\aleph_0}\). \(\alpha = \aleph_0\) אינסופית, \(2 \le \aleph_0 \le 2^{\aleph_0} = \aleph\). לפי המשפט: \(\aleph_0^{\aleph_0} = 2^{\aleph_0} = \aleph\).
סעיף ב — \(|\{0,1\}^\mathbb{N}| = \aleph\)
סדרה בינארית אינסופית = פונקציה \(f: \mathbb{N} \to \{0,1\}\). \(|\{0,1\}^\mathbb{N}| = 2^{\aleph_0} = \aleph\).
סעיף ג — \(|\mathbb{R}^\mathbb{N}| = \aleph\)
סדרת ממשיים = \(f: \mathbb{N} \to \mathbb{R}\). \(|\mathbb{R}^\mathbb{N}| = \aleph^{\aleph_0} = \aleph\) (לפי תרגיל 1א).
תובנה
גם אם "מרחיבים" סדרות לטווח של \(\mathbb{R}\) במקום \(\{0,1\}\) — נשארים בעוצמה \(\aleph\). הסיבה: \(\aleph^{\aleph_0}\) מתכווץ ל-\(\aleph\) דרך משפט החזקות.
תרגיל 4: ביטוי עוצמות בעזרת 2-ים ולכל היותר \(\aleph_0\) אחד
השאלה — בטאו רק בעזרת 2-ים, עם לכל היותר \(\aleph_0\) אחד
- \(\aleph^{\aleph}\)
- \((\aleph_0^{\aleph})^{\aleph_0}\)
- \(|\{f: P(\mathbb{N}) \to P(P(\mathbb{N}))\}|\)
- \(|\{0,1\} \times \{0,1,2\} \times \{0,1,2,3\} \times \cdots|\)
סעיף א — \(\aleph^\aleph = 2^{2^{\aleph_0}}\)
ℵ^ℵ = (2^{ℵ₀})^ℵ (כי ℵ = 2^{ℵ₀})
= 2^{ℵ₀ · ℵ} (חוק חזקות)
= 2^ℵ (כי ℵ₀ · ℵ = max = ℵ)
= 2^{2^{ℵ₀}}. ∎
סעיף ב — \((\aleph_0^\aleph)^{\aleph_0} = 2^{2^{\aleph_0}}\)
שלב 1: ℵ₀^ℵ. α=ℵ אינסופית, 2 ≤ ℵ₀ ≤ 2^ℵ.
לפי המשפט: ℵ₀^ℵ = 2^ℵ.
שלב 2: (ℵ₀^ℵ)^{ℵ₀} = (2^ℵ)^{ℵ₀}
= 2^{ℵ · ℵ₀}
= 2^ℵ (ℵ · ℵ₀ = max = ℵ)
= 2^{2^{ℵ₀}}. ∎
סעיף ג — \(|\{f: P(\mathbb{N}) \to P(P(\mathbb{N}))\}| = 2^{2^{\aleph_0}}\)
נסמן \(A = P(\mathbb{N}),\;B = P(P(\mathbb{N}))\): \(|A| = 2^{\aleph_0},\;|B| = 2^{2^{\aleph_0}}\).
|B^A| = |B|^|A| = (2^{2^{ℵ₀}})^{2^{ℵ₀}}
= 2^{2^{ℵ₀} · 2^{ℵ₀}}
= 2^{2^{ℵ₀}} (כי 2^{ℵ₀} · 2^{ℵ₀} = max = 2^{ℵ₀}). ∎
סעיף ד — \(2^{\aleph_0}\)
נסמן \(X = \prod_{n=1}^{\infty} \{0, 1, \ldots, n\}\). הוכחה ע"י חסם דו-כיווני:
- חסם עליון: \(X \subseteq \mathbb{N}^\mathbb{N}\), לכן \(|X| \le \aleph_0^{\aleph_0} = 2^{\aleph_0}\).
- חסם תחתון: \(\{0,1\}^\mathbb{N} \subseteq X\) (סדרות שערכיהן רק 0,1), לכן \(|X| \ge 2^{\aleph_0}\).
\(|X| = 2^{\aleph_0}\). ∎
תרגיל 5: סדרות מתכנסות ולא מתכנסות
השאלה
מהי עוצמת קבוצת כל הסדרות האינסופיות של מספרים ממשיים:
- שמתכנסות למספר סופי?
- המתכנסות ל-0?
- שלא מתכנסות למספר סופי?
כללי: כל הקבוצות \(\subseteq \mathbb{R}^\mathbb{N}\), לכן עליהן \(\le \aleph\). נשאר חסם תחתון.
סעיף א — \(\aleph\)
הסדרות הקבועות \((L, L, L, \ldots)\) ל-\(L \in \mathbb{R}\) מתכנסות ל-\(L\). \(h: \mathbb{R} \to X,\;h(L) = (L,L,\ldots)\) חח"ע. \(\aleph \le |X|\).
סעיף ב — \(\aleph\)
לכל \((b_n) \in \{0,1\}^\mathbb{N}\), הסדרה \((b_n / (n+1))\) מתכנסת ל-0 (חסמה הוא \(1/(n+1) \to 0\)). חח"ע. \(\aleph \le |X|\).
סעיף ג — \(\aleph\)
לכל \(a \ne 1\), הסדרה המתחלפת \((a, 1, a, 1, \ldots)\) לא מתכנסת (תת-סדרת זוגיים \(\to a\), אי-זוגיים \(\to 1\), \(a \ne 1\)). \(h: \mathbb{R} \setminus \{1\} \to X\) חח"ע. \(\aleph = |\mathbb{R} \setminus \{1\}| \le |X|\).
לקח
כשעוצמת היעד \(\le\) עוצמת המקור = \(\aleph\) (בהתאם ל-\(\mathbb{R}^\mathbb{N}\)), כדאי לחפש
חסם תחתון \(\aleph\) ע"י זריקה (embedding) ממש מ-\(\mathbb{R}\) או מ-\(\{0,1\}^\mathbb{N}\).
תרגיל 6: עוצמת קבוצת הבייקציות \(f: \mathbb{Z} \leftrightarrow \mathbb{Z}\)
(מבחן 2022 A, 20 נק׳)
השאלה
מה העוצמה של \(\text{Bij}(\mathbb{Z}) = \{f: \mathbb{Z} \to \mathbb{Z} \mid f \text{ חח"ע ועל}\}\)? הוכיחו.
חסם עליון: \(\text{Bij}(\mathbb{Z}) \subseteq \mathbb{Z}^\mathbb{Z}\)
\(|\text{Bij}(\mathbb{Z})| \le |\mathbb{Z}^\mathbb{Z}| = \aleph_0^{\aleph_0} = \aleph\).
חסם תחתון: בניית \(2^{\aleph_0}\) בייקציות שונות
לכל \(S \subseteq \mathbb{N}\) נגדיר \(h_S: \mathbb{Z} \to \mathbb{Z}\):
- \(h_S(2k) = 2k+1\) אם \(k \in S\).
- \(h_S(2k+1) = 2k\) אם \(k \in S\).
- \(h_S(n) = n\) אחרת (כל \(n\) שליליים, וזוגות \(k \notin S\)).
כל \(h_S\) היא בייקציה (החלפות מקומיות על קבוצות זרות). לכל \(S \ne T\), \(h_S \ne h_T\) (קיים \(k \in S \triangle T\) שמראה זאת). ההתאמה \(S \mapsto h_S\) חח"ע מ-\(P(\mathbb{N})\) אל \(\text{Bij}(\mathbb{Z})\). לכן \(\aleph = 2^{\aleph_0} \le |\text{Bij}(\mathbb{Z})|\).
סיכום
\(\aleph \le |\text{Bij}(\mathbb{Z})| \le \aleph \Longrightarrow |\text{Bij}(\mathbb{Z})| = \aleph\). ∎
תרגיל 7
השאלה
- הגדירו קבוצה סופית לא ריקה \(A\), כך ש-\(P(P(A)) = A \cup P(A) \cup P(P(A))\). הסבירו.
- הוכיחו: לכל \(A, B\) אינסופיות עם \(|A| > |B|\) מתקיים \(|A \setminus B| = |A|\).
סעיף א — \(A = \{\emptyset\}\)
הדרישה שקולה ל-\(A \subseteq P(P(A))\) וגם \(P(A) \subseteq P(P(A))\) (הכיוון השני טריוויאלי כי \(P(P(A)) \subseteq P(P(A))\)).
בדיקה עם \(A = \{\emptyset\}\):
- \(P(A) = \{\emptyset, \{\emptyset\}\}\).
- \(P(P(A)) = \{\emptyset, \{\emptyset\}, \{\{\emptyset\}\}, \{\emptyset, \{\emptyset\}\}\}\).
- \(A \subseteq P(P(A))\): \(\emptyset \in P(P(A))\) ✓.
- \(P(A) \subseteq P(P(A))\): \(\emptyset \in P(P(A))\) ✓, \(\{\emptyset\} \in P(P(A))\) (כי \(\{\emptyset\} \subseteq P(A)\)) ✓.
שני התנאים מתקיימים. ∎
סעיף ב — \(|A \setminus B| = |A|\) (\(A,B\) אינסופיות, \(|A| > |B|\))
הוכחה.
כיוון 1: A∖B ⊆ A ⟹ |A∖B| ≤ |A|.
כיוון 2: A = (A∖B) ∪ (A∩B), זרה.
|A| = |A∖B| + |A∩B|.
A אינסופית ⟹ לפחות אחד מהמחוברים אינסופי, ולכן:
|A| = max(|A∖B|, |A∩B|).
וגם: A∩B ⊆ B ⟹ |A∩B| ≤ |B| < |A|.
אם max = |A∩B|, אז |A| = |A∩B| < |A| — סתירה.
לכן max = |A∖B|, כלומר |A| ≤ |A∖B|.
⟹ |A∖B| = |A|. ∎
לקח
כש"מורידים" מ-\(A\) קבוצה
קטנה יותר ממנו ממש (\(|B| < |A|\)) — נשארים באותה עוצמה. דוגמה: \(|\mathbb{R} \setminus \mathbb{Q}| = \aleph\) (תרגיל 2 הוא מקרה פרטי).
סיכום ונקודות חשובות
טכניקות מפתח
- שיוויון עוצמות ע"י חסם דו-כיווני: \(|X| \le \alpha\) ו-\(|X| \ge \alpha\) ⟹ \(|X| = \alpha\) (קנטור-שרדר-ברנשטיין).
- חסם תחתון \(\alpha\): מצא embedding (פונקציה חח"ע) מקבוצה ידועה בעוצמה \(\alpha\) אל \(X\).
- חסם עליון \(\alpha\): הראה \(X \subseteq Y\) עם \(|Y| = \alpha\), או embedding \(X \hookrightarrow Y\).
- פירוק לאיחוד זר: \(A = (A \cap B) \cup (A \setminus B)\) → חיבור עוצמות.
- חוקי חזקות + max: \((a^b)^c = a^{bc},\;a^{b+c}=a^b a^c\), ומשפט המקסימום פותר רוב המקרים האינסופיים.
שיוויונות שכדאי לזכור בעל-פה
- \(\aleph_0 + \aleph_0 = \aleph_0,\;\aleph_0 \cdot \aleph_0 = \aleph_0\)
- \(\aleph_0^{\aleph_0} = 2^{\aleph_0} = \aleph\)
- \(\aleph^{\aleph_0} = \aleph\)
- \(\aleph^\aleph = 2^\aleph = 2^{2^{\aleph_0}}\)
- \(\aleph^{\aleph_0} \ne \aleph_0^\aleph\): \(\aleph^{\aleph_0} = \aleph\) אבל \(\aleph_0^\aleph = 2^\aleph\) — אחד "בר-מניה", השני "רצף"!
מלכודות נפוצות
- הצרנת "קבוצת פונקציות": "\(f: B \to A\) פונקציה מלאה" \(\Rightarrow\) \(|A^B|\), לא \(|B^A|\).
- \(a^{b^c} \ne (a^b)^c\): אין קיפול אחד! \(a^{b^c} = a^{(b^c)}\), \((a^b)^c = a^{bc}\) — שונים.
- "זרות": פעולות חיבור עוצמות מוגדרות עבור קבוצות זרות. אם לא, יש לקחת עותקים זרים.