1. רקע מהיר
קבוצה לא בת-מניה
\(A\)
לא בת-מניה אם אינסופית ולא שקולה ל-\(\mathbb{N}\).
עוצמת הרצף
\(|\mathbb{R}| = \aleph = c = 2^{\aleph_0}\). שווה ל-\(|P(\mathbb{N})|\), \(|[0,1]|\), \(|(a,b)|\) לכל \(a < b\), \(|\mathbb{R}^k|\), \(|\mathbb{C}|\).
משפטי סגירות (השתמשו!)
- \(P(\mathbb{N})\) לא בת-מניה, בעוצמה \(\aleph\).
- \(\mathbb{R}\) לא בת-מניה, בעוצמה \(\aleph\).
- כל קטע פתוח / סגור / חצי-פתוח לא טריוויאלי בעוצמת הרצף.
- איחוד סופי של קבוצות בעוצמה \(\aleph\) — בעוצמה \(\aleph\).
- מכפלה קרטזית סופית של קבוצות בעוצמה \(\aleph\) — בעוצמה \(\aleph\).
- (נוכיח בהמשך) איחוד / מכפלה בן-מניה של קבוצות בעוצמה \(\aleph\) — בעוצמה \(\aleph\).
משפט קנטור
לכל \(S\): \(|P(S)| > |S|\). מסקנה: יש מספר אינסופי של עוצמות אינסופיות:
\(|\mathbb{N}| < |P(\mathbb{N})| < |P(P(\mathbb{N}))| < \ldots\)
\(\aleph_0 \quad < \quad 2^{\aleph_0} \quad < \quad 2^{2^{\aleph_0}}\)
2. תרגיל 1: \(|S| \leq |P(S)|\)
השאלה
הוכיחו: לכל קבוצה \(S\), \(|S| \leq |P(S)|\). (זה החלק הראשון של משפט קנטור.)
פתרון
f: S → P(S) ע"י f(x) = {x}.
מלאה: לכל x ∈ S, {x} ⊆ S, ולכן {x} ∈ P(S).
חח"ע: f(x_1) = f(x_2) ⟹ {x_1} = {x_2} ⟹ x_1 = x_2 (משוויון קבוצות).
⟹ |S| ≤ |P(S)|. ∎
הקשר למשפט קנטור
כדי להוכיח \(|P(S)| > |S|\), צריך גם \(|S| \leq |P(S)|\) (כאן) וגם \(|P(S)| \neq |S|\) (האלכסון בהרצאה — שום \(f: S \to P(S)\) לא יכולה להיות על).
3. תרגיל 2: \(|\mathbb{R}| \leq |\mathbb{Z}^2 \times \mathbb{N}^3|\)?
השאלה
הוכיחו או הפריכו: \(|\mathbb{R}| \leq |\mathbb{Z}^2 \times \mathbb{N}^3|\).
פתרון - הפרכה
|ℝ| = ℵ.
|ℤ| = |ℕ| = ℵ₀.
ℤ² × ℕ³ — מכפלה קרטזית סופית של בנות-מניה ⟹ בת-מניה.
⟹ |ℤ² × ℕ³| ≤ ℵ₀.
ℵ > ℵ₀ ⟹ |ℝ| > |ℤ² × ℕ³|.
⟹ לא מתקיים |ℝ| ≤ |ℤ² × ℕ³|. ∎
תובנה
לא משנה כמה תרחיבו מכפלה
סופית של בנות-מניה — תישארו ב-\(\aleph_0\). כדי "לעלות" לעוצמת הרצף צריך פעולה אחרת (\(\mathbb{R}, P(\mathbb{N}), \{0,1\}^{\mathbb{N}}\)).
4. תרגיל 3: \(\left| \bigcup_{n \in \mathbb{N}} (n, n+1) \right| = \aleph\)
השאלה
הוכיחו: \(\left| \bigcup_{n \in \mathbb{N}} (n, n+1) \right| = \aleph\). (זה האיחוד \((0,1) \cup (1,2) \cup (2,3) \cup \ldots\))
פתרון
A = ⋃_{n ∈ ℕ} (n, n+1).
A ⊆ ℝ ⟹ |A| ≤ |ℝ| = ℵ.
(0, 1) ⊆ A ⟹ ℵ = |(0,1)| ≤ |A|.
קנטור-שרדר-ברנשטיין: |A| = ℵ. ∎
תובנה
איחוד
בן-מניה של קבוצות בעוצמה \(\aleph\) — נשאר בעוצמה \(\aleph\). הסיבה: כבר תת-קבוצה אחת \((0,1)\) מספיקה כדי "להגיע" ל-\(\aleph\), ואי אפשר "לעבור" את \(\aleph\) דרך איחוד עם תת-קבוצות של \(\mathbb{R}\).
5. תרגיל 4: \(\mathbb{R}^+ \setminus A\) בעוצמת הרצף
השאלה
\(A\) קבוצה סופית לא ריקה של ממשיים גדולים מ-0. הוכיחו: \(B = \mathbb{R}^+ \setminus A\) (הממשיים שגדולים מ-0 ואינם ב-\(A\)) בעוצמת הרצף.
פתרון
B ⊆ ℝ ⟹ |B| ≤ ℵ.
A סופית, לא ריקה ⟹ קיים a ∈ A הקטן ביותר. (a > 0)
לכן (0, a) ⊆ B (כל איבר בקטע קטן מ-a ⟹ קטן מכל איבר ב-A ⟹ לא ב-A).
⟹ ℵ = |(0, a)| ≤ |B|.
קנטור-שרדר-ברנשטיין: |B| = ℵ. ∎
תיאור B
אם \(A = \{a_1 < a_2 < \ldots < a_n\}\), אז:
\(B = (0, a_1) \cup (a_1, a_2) \cup \ldots \cup (a_{n-1}, a_n) \cup (a_n, \infty)\)
איחוד סופי של קטעים — כל אחד בעוצמה \(\aleph\), ולכן \(B\) בעוצמה \(\aleph\) (איחוד סופי).
6. תרגיל 5: עוצמת קבוצת המעגלים במישור
השאלה
מהי עוצמת קבוצת כל המעגלים במישור?
פתרון
אפיון מעגל: מעגל במישור מאופיין באופן יחיד ע"י \((a, b)\) (מרכז) ו-\(r > 0\) (רדיוס):
\((x - a)^2 + (y - b)^2 = r^2\)
נסמן \(C_{a,b,r}\) = המעגל עם מרכז \((a,b)\) ורדיוס \(r\), ו-\(\mathcal{A}\) = קבוצת כל המעגלים.
f: ℝ × ℝ × ℝ⁺ → 𝒜 ע"י f(a, b, r) = C_{a,b,r}.
מלאה ומוגדרת היטב: כל שלשה (a, b, r) עם r > 0 נותנת מעגל יחיד.
חח"ע: f(a_1, b_1, r_1) = f(a_2, b_2, r_2) ⟹ אותו מעגל ⟹ אותו מרכז ואותו רדיוס
⟹ (a_1, b_1, r_1) = (a_2, b_2, r_2).
על: כל מעגל C_{a,b,r} ∈ 𝒜 ⟹ (a, b, r) ∈ ℝ × ℝ × ℝ⁺ ⟹ f(a,b,r) = C.
⟹ f bijection ⟹ ℝ × ℝ × ℝ⁺ ~ 𝒜.
ℝ × ℝ × ℝ⁺ — מכפלה קרטזית סופית של קבוצות בעוצמה ℵ ⟹ בעוצמה ℵ.
⟹ |𝒜| = ℵ. ∎
למה ℝ⁺?
רדיוס שלילי או 0 לא נותן מעגל (או נקודה במקרה של 0). \(\mathbb{R}^+ \subseteq \mathbb{R}\), ולכן \(|\mathbb{R}^+| = \aleph\) (לפי תרגיל 4 או ישירות).
7. תרגיל 6: \(|P([0,1]) \setminus P((0,1))| > |P(\mathbb{N})|\)?
השאלה
הוכיחו או הפריכו: \(|P([0,1]) \setminus P((0,1))| > |P(\mathbb{N})|\).
(\(P([0,1]) \setminus P((0,1))\) = כל תתי-הקבוצות של \([0,1]\) שמכילות 0 או 1.)
פתרון - הוכחה
נסמן \(A = P([0,1]) \setminus P((0,1))\).
f: P((0,1)) → A ע"י f(S) = S ∪ {0}.
מלאה: f(S) ⊆ [0,1] ומכילה 0 ⟹ f(S) ∈ A. ✓
חח"ע: S_1, S_2 ∈ P((0,1)), S_1 ≠ S_2.
⟹ קיים x עם x ∈ S_1, x ∉ S_2.
x ≠ 0 (כי S_1 ⊆ (0,1)).
⟹ x ∈ S_1 ∪ {0} = f(S_1) ו-x ∉ S_2 ∪ {0} = f(S_2).
⟹ f(S_1) ≠ f(S_2). ✓
⟹ |P((0,1))| ≤ |A|.
|P((0,1))| = 2^|(0,1)| = 2^ℵ = |P(ℝ)|.
לפי משפט קנטור: 2^ℵ > ℵ = |P(ℕ)|.
⟹ |A| ≥ 2^ℵ > ℵ = |P(ℕ)|. ⟹ |A| > |P(ℕ)|. ∎
תובנה
יש קבוצות הרבה יותר גדולות מ-\(P(\mathbb{N})\) — הראשונה היא \(P(\mathbb{R})\) בעוצמה \(2^{\aleph}\). זה רק "הצעד הראשון" במגדל אינסופי של עוצמות.
8. תרגיל 7: \(P(A) \sim \{0,1\}^A\)
השאלה
הוכיחו: לכל קבוצה \(A\), \(P(A) \sim \{0,1\}^A\).
(\(\{0,1\}^A\) = קבוצת כל הפונקציות המלאות \(f: A \to \{0,1\}\).)
פתרון - בניית bijection
g: {0,1}^A → P(A) ע"י g(f) = {a ∈ A | f(a) = 1}.
מלאה ומוגדרת היטב: g(f) ⊆ A ⟹ g(f) ∈ P(A). ✓
חח"ע: f_1, f_2 ∈ {0,1}^A, f_1 ≠ f_2.
⟹ קיים a עם f_1(a) ≠ f_2(a).
ללא אובדן הכלליות, f_1(a) = 0, f_2(a) = 1.
⟹ a ∉ g(f_1) ו-a ∈ g(f_2).
⟹ g(f_1) ≠ g(f_2). ✓
על: לכל S ∈ P(A), נגדיר f_S: A → {0,1}:
f_S(a) = 1 אם a ∈ S, אחרת 0.
f_S ∈ {0,1}^A. g(f_S) = {a | f_S(a)=1} = S. ✓
⟹ g bijection ⟹ P(A) ~ {0,1}^A. ∎
תובנה - שני סימונים, אותה קבוצה
\(P(A)\) ו-\(\{0,1\}^A\) הם שני אופנים לתאר את אותה קבוצה: תת-קבוצה ⟺ פונקציה אופיינית.
זו הסיבה שמסמנים \(|P(\mathbb{N})| = 2^{\aleph_0}\): פורמלית \(P(\mathbb{N}) \sim \{0,1\}^{\mathbb{N}}\), והעוצמה של פונקציות מ-\(\mathbb{N}\) ל-\(\{0,1\}\) היא \(2^{\aleph_0}\).
9. תרגיל 8: עוצמת קבוצת ההשקפות העולם האבגיות
השאלה
- "מילה אבגית" = מחרוזת סופית מאותיות \(\{\text{א, ב, ג}\}\).
- "משפט אבגי" = רצף סופי של מילים אבגיות.
- "דעה אבגית" = סיווג של ׳נכון׳ או ׳לא נכון׳ לכל משפט אבגי.
- "השקפת עולם אבגית" = סיווג של ׳בסדר׳ או ׳לא בסדר׳ לכל דעה אבגית.
מה עוצמת קבוצת כל ההשקפות העולם האבגיות?
פתרון - שלב אחר שלב
שלב 1: \(A\) = מילים אבגיות
A אינסופית: f: ℕ → A ע"י f(n) = "א..." (n אותיות א) — חח"ע. ⟹ |A| ≥ ℵ₀.
A בת-מניה: לכל i ≥ 1, A_i = מילים באורך i. |A_i| = 3^i — סופית.
A = ⋃_{i ∈ ℕ \ {0}} A_i — איחוד בן-מניה של סופיות ⟹ בת-מניה.
⟹ |A| = ℵ₀.
שלב 2: \(B\) = משפטים אבגיים
B = רצפים סופיים של מילים = ⋃_{n ∈ ℕ \ {0}} A^n.
לכל n, A^n = מכפלה קרטזית סופית של בנות-מניה ⟹ בת-מניה.
⟹ B איחוד בן-מניה של בנות-מניה ⟹ B בת-מניה.
B אינסופית כי A ⊆ B. ⟹ |B| = ℵ₀.
שלב 3: \(C\) = דעות אבגיות
דעה = סיווג נכון/לא לכל משפט = פונקציה מ-B ל-{נכון, לא נכון}.
⟹ C ~ {0,1}^B (לפי תרגיל 7: {0,1}^B ~ P(B))
⟹ |C| = |P(B)| = 2^|B| = 2^ℵ₀ = ℵ.
שלב 4: \(D\) = השקפות עולם אבגיות
השקפת עולם = סיווג בסדר/לא לכל דעה = פונקציה מ-C ל-{בסדר, לא בסדר}.
⟹ D ~ {0,1}^C ~ P(C)
⟹ |D| = 2^|C| = 2^ℵ = |P(ℝ)|. ∎
תובנה
כל "שכבה" של פונקציות בוליאניות מעלה את העוצמה: \(\aleph_0 \to 2^{\aleph_0} = \aleph \to 2^{\aleph}\). מגדל קנטור בפעולה!
| שכבה | תיאור | עוצמה |
|---|
| \(A\) | מילים אבגיות | \(\aleph_0\) |
| \(B\) | משפטים אבגיים | \(\aleph_0\) |
| \(C\) | דעות אבגיות | \(\aleph = 2^{\aleph_0}\) |
| \(D\) | השקפות עולם אבגיות | \(2^{\aleph}\) |
10. דף עזר - תבניות הוכחה מהירות
| טענה | שיטה |
|---|
| \(|A| \leq \aleph\) | \(A \subseteq\) קבוצה ידועה בעוצמה \(\aleph\) (\(\mathbb{R}\), קטע, \(P(\mathbb{N})\)) |
| \(|A| \geq \aleph\) | קבוצה ידועה בעוצמה \(\aleph\) ⊆ \(A\), או bijection מקטע |
| \(|A| = \aleph\) | שני הכיוונים + קנטור-שרדר-ברנשטיין |
| \(|A| > \aleph\) (לא ב-\(\aleph\)) | בדרך כלל דרך משפט קנטור — מציגים \(P(B) \subseteq A\) או \(A \supseteq P(B)\) עם \(|B| = \aleph\) |
| סיווגים בוליאניים על \(A\) | \(\sim P(A) \sim \{0,1\}^A\), עוצמה \(2^{|A|}\) |
טריקים נפוצים
- פונקציה אופיינית: \(P(A) \sim \{0,1\}^A\) — תרגיל 7. שימושי כשהשאלה על "סיווג", "החלטה", "כן/לא לכל איבר".
- חיתוך עם תת-קבוצה: כדי להראות \(|A| \geq \aleph\), מצאו קטע פתוח / סגור שמוכל ב-\(A\).
- שלשות / קואורדינטות: גופים גיאומטריים (מעגלים, ישרים, מלבנים) — תאפיינו אותם דרך שלשה / זוג ב-\(\mathbb{R}^k\).
- אזהרה לאינדוקציה: לא משתמשים באינדוקציה לפעולות בני-מניה / קבוצות בעוצמת הרצף.
- דרגות אינסוף: לא לבלבל בין \(\aleph_0\), \(\aleph\), \(2^{\aleph}\) — כל אחד הוא דרגה שונה (משפט קנטור).
סדר העוצמות שראינו
\(0 < 1 < 2 < \ldots < \aleph_0 < \aleph = 2^{\aleph_0} < 2^{\aleph} < \ldots\)
השערת הרצף: אין דבר בין \(\aleph_0\) ל-\(\aleph\). בלתי-תלויה ב-ZFC.