\(|\mathbb{N}| \leq |P_2(\mathbb{N})|\): נגדיר \(f: \mathbb{N} \to P_2(\mathbb{N})\) ע"י \(f(n) = \{n\}\). מלאה, חח"ע (\(\{n_1\} = \{n_2\} \Rightarrow n_1 = n_2\)).
\(|P_2(\mathbb{N})| \leq |\mathbb{N}|\): נגדיר \(g: P_2(\mathbb{N}) \to \mathbb{N}\):
g(∅) = 0
g({a}) = 2^a עבור a ∈ ℕ
g({a, b}) = 2^a · 3^b עבור a < b ∈ ℕ
\(g\) מלאה ומוגדרת היטב.
חח"ע (אנליזה לפי מקרים): נניח \(g(A_1) = g(A_2)\). מקרים לפי גודל:
| \(|A_1|, |A_2|\) | ערכי \(g\) | הסיכום |
|---|---|---|
| 0, 1 | \(0\) vs \(2^a\) | סתירה (\(2^a > 0\)) |
| 0, 2 | \(0\) vs \(2^a 3^b\) | סתירה |
| 1, 2 | \(2^{a_1}\) vs \(2^{a_2} 3^{b_2}\) | סתירה (חזקת 3 שונה) |
| 1, 1 | \(2^{a_1} = 2^{a_2}\) | \(a_1 = a_2\) ⟹ \(A_1 = A_2\) |
| 2, 2 | \(2^{a_1} 3^{b_1} = 2^{a_2} 3^{b_2}\) | יחידות הפירוק לראשוניים: \(a_1 = a_2, b_1 = b_2\) |
⟹ \(g\) חח"ע ⟹ \(|P_2(\mathbb{N})| \leq |\mathbb{N}|\). קנטור-שרדר-ברנשטיין: \(\mathbb{N} \sim P_2(\mathbb{N})\). ∎
לא! ב-\(P(\mathbb{N})\) יש איברים אינסופיים (כמו \(\{0,2,4,...\}\)). אינדוקציה מוכיחה רק לכל \(n\) סופי. וגם — בהרצאה הבאה נראה ש-\(P(\mathbb{N})\) איננה בת-מניה.
A אינסופית ⟹ |ℕ| ≤ |A| (משפט מההרצאה). ⟹ קיימת f: ℕ → A מלאה וחח"ע. נגדיר B = Im(f) — תמונת f. B ⊆ A. g: ℕ → B ע"י g(n) = f(n) — bijection (חח"ע מ-f, על מהגדרת B). ⟹ B ~ ℕ ⟹ |B| = ℵ₀ ⟹ B אינסופית בת-מניה. ∎
f: ℕ → A מלאה וחח"ע (מסעיף א').
נגדיר f_1: ℕ_odd → A ע"י f_1(n) = f(n).
f_2: ℕ_even → A ע"י f_2(n) = f(n).
שתיהן מלאות וחח"ע (כי f כזו).
B = Im(f_1), C = Im(f_2). B, C ⊆ A.
B ~ ℕ_odd ~ ℕ ⟹ |B| = ℵ₀. C ~ ℕ_even ~ ℕ ⟹ |C| = ℵ₀.
B ∩ C = ∅: אם x ∈ B ∩ C אז יש n_1 אי-זוגי, n_2 זוגי עם f(n_1) = f(n_2) = x.
f חח"ע ⟹ n_1 = n_2 — סתירה. ∎
כן אבל לא באמצעות אינדוקציה ישירה. הטריק: לחלק את \(\mathbb{N}\) לאינסוף בני-מניה תתי-קבוצות זרות, ולהשתמש ב-\(f\). למשל, לפי המעריך של 2 בפירוק לראשוניים: לכל \(k \in \mathbb{N}\), \(\mathbb{N}_k = \{n \mid \text{המעריך של 2 ב-}n\text{ הוא }k\}\). אזי \(\mathbb{N} = \bigsqcup_k \mathbb{N}_k\), כל \(\mathbb{N}_k\) בת-מניה אינסופית, וכולן זרות. נשלח כל אחת ל-\(A\) דרך \(f\).
נראה ששתיהן בעוצמה \(\aleph_0\), ולכן \(|A| = |B|\).
A ⊆ ℚ ⟹ |A| ≤ |ℚ| = ℵ₀. f: ℕ → A ע"י f(n) = 2 + 1/(n+2). (תמיד ב-(2, 3) כי 0 < 1/(n+2) ≤ 1/2) חח"ע: f(n_1) = f(n_2) ⟹ 1/(n_1+2) = 1/(n_2+2) ⟹ n_1 = n_2. ⟹ |A| ≥ ℵ₀. קנטור-שרדר-ברנשטיין: |A| = ℵ₀.
B ⊆ ℕ ⟹ |B| ≤ ℵ₀. g: ℕ → B ע"י g(n) = 5^(n+1). (מתחלק ב-5; חזקה של 5 לעולם לא מתחלקת ב-7) חח"ע: 5^(n_1+1) = 5^(n_2+1) ⟹ n_1 = n_2. ⟹ |B| ≥ ℵ₀. |B| = ℵ₀. ⟹ |A| = ℵ₀ = |B| ⟹ |A| = |B|. ∎
סך הסימנים: \(26 + 26 + 10 + 1 + 6 = 69\). יהי \(A\) = קבוצת הסיפורים.
\(A\) אינסופית: \(f: \mathbb{N} \to A\) ע"י \(f(n) = \text{"a"} \cdot n\) (\(n\) פעמים האות a). חח"ע — סיפורים שונים באורך שונה.
\(A\) בת-מניה: לכל \(i \geq 1\), \(A_i\) = הסיפורים באורך \(i\). \(|A_i| \leq 69^i\) — סופי. \(A = \bigcup_{i \in \mathbb{N} \setminus \{0\}} A_i\) — איחוד בן-מניה של קבוצות סופיות (כל סופית בת-מניה) ⟹ בן-מניה.
⟹ \(|A| = \aleph_0\). ∎
הבנה: \(P(\mathbb{N}) \setminus P(\mathbb{N}\setminus\{0\})\) = כל תתי-הקבוצות של \(\mathbb{N}\) שמכילות את 0. נסמן \(A = P(\mathbb{N}) \setminus P(\mathbb{N}\setminus\{0\})\) ו-\(B = P(\mathbb{N}\setminus\{0\})\).
נגדיר f: B → A ע"י f(S) = S ∪ {0}.
מלאה ומוגדרת היטב: f(S) ⊆ ℕ, 0 ∈ f(S) ⟹ f(S) ∈ A.
חח"ע: יהיו S_1, S_2 ∈ B, S_1 ≠ S_2.
ללא אובדן הכלליות, יש x ∈ S_1, x ∉ S_2.
שימו לב: x ≠ 0 (כי S_1 ⊆ ℕ \ {0}).
לכן x ∈ S_1 ∪ {0} = f(S_1).
ו-x ∉ S_2 ∪ {0} = f(S_2) (x ≠ 0 ו-x ∉ S_2)
⟹ f(S_1) ≠ f(S_2).
⟹ f חח"ע ⟹ |B| ≤ |A|. ∎
נשתמש בעזר \(C = \mathbb{Q} \times \mathbb{Q} \times \mathbb{Q}\) ונראה \(B \sim C\) ו-\(A \sim C\), ואז טרנזיטיביות.
שלב 1: \(|A| = |\mathbb{Q}| = \aleph_0\) (ידוע מההרצאה).
שלב 2 - \(B \sim C\):
f: C → B ע"י f(a, b, c) = ax² + bx + c.
מלאה: כל (a,b,c) נותן פולינום בצורה הנדרשת.
חח"ע + על: שני פולינומים עם אותם מקדמים זהים, ולהפך
(פולינום קובע באופן יחיד את (a,b,c) — שונים נותנים פולינומים שונים).
⟹ f bijection ⟹ B ~ C.
שלב 3 - \(C\) בעוצמה \(\aleph_0\):
שלב 4 - סיום: \(|A| = \aleph_0 = |C| = |B|\). מטרנזיטיביות (\(A \sim C \sim B\)) ⟹ \(A \sim B\). ∎
| טענה | שיטה |
|---|---|
| \(|A| \leq \aleph_0\) | \(A \subseteq\) בת-מניה ידועה (כמו \(\mathbb{Q}, \mathbb{N}, \mathbb{Z}\)) — או הצגת \(A\) כתוצאה של פעולת סגירה |
| \(|A| \geq \aleph_0\) (\(A\) אינסופית) | \(f: \mathbb{N} \to A\) חח"ע מפורשת |
| \(|A| = \aleph_0\) | שני הכיוונים + קנטור-שרדר-ברנשטיין |
| \(|A| \leq |B|\) | \(f: A \to B\) חח"ע ומלאה, או \(g: B \twoheadrightarrow A\) |
| \(A \sim B\) | בניית bijection מפורש, או הראות \(|A| = |B| = \aleph_0\) (כשרלוונטי) |