1. תזכורת: השוואת עוצמות וסגירות בנות-המניה
השוואת עוצמות
- \(|A| = |B|\) — קיימת ביייקציה \(f: A \leftrightarrow B\). שקול: \(|A| \leq |B|\) וגם \(|B| \leq |A|\) (קנטור-שרדר-ברנשטיין).
- \(|A| \leq |B|\) — קיימת \(f: A \to B\) חח"ע ומלאה. שקול: קיימת \(g: B \twoheadrightarrow A\).
- \(|A| < |B|\) — \(|A| \leq |B|\) וגם לא קיימת ביייקציה.
קבוצה אינסופית
\(A\) אינסופית אם קיימת \(S \subsetneq A\) עם \(S \sim A\). שקול: קיימת \(B \subseteq A\) אינסופית; קיימת \(B \sim A\) אינסופית; \(|\mathbb{N}| \leq |A|\).
בת-מניה ו-\(\aleph_0\)
\(|\mathbb{N}| = \aleph_0\). \(A\) בת-מניה אמ"מ סופית או שקולה ל-\(\mathbb{N}\) (\(|A| \leq \aleph_0\)). סימון: \(A = \{a_n \mid n \in \mathbb{N}\}\).
סגירות מחלקת בנות-המניה
סגורה תחת: \(A \cup B\), איחוד סופי,
איחוד בן-מניה (זיגזג!), \(A \times B\), מכפלה
סופית.
דוגמאות: \(\emptyset, \{4,9,78\}, \mathbb{N}, \mathbb{Z}, \mathbb{Q}\) בנות-מניה.
אזהרה: מכפלה בת-מניה של בנות-מניה לא בהכרח בת-מניה.
תזכורת חשובה: אינדוקציה
ניתן להשתמש באינדוקציה לאיחוד / מכפלה
סופיים בלבד.
לא ניתן לאיחוד / מכפלה בני-מניה (אינסופיים).
2. השאלה: האם \(P(\mathbb{N})\) בת-מניה?
\(P(\mathbb{N})\) = קבוצת כל תתי-הקבוצות של \(\mathbb{N}\). יש בה הרבה דברים — \(\{1,3,4\}\), הזוגיים, האי-זוגיים, הריבועים, הראשוניים, ...
השאלה הטבעית: האם ניתן לסדר את \(P(\mathbb{N})\) בשורה כך שלפני כל איבר יש מס' סופי של איברים? נראה ש-לא!
3. \(P(\mathbb{N})\) - ייצוג כסדרות 0/1
תת-קבוצה \(A \subseteq \mathbb{N}\) ניתנת לתאר כסדרה אינסופית של ביטים: עבור כל \(n\), הביט ה-\(n\) הוא 1 אם \(n \in A\) ואחרת 0.
| \(n=\) | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | ... |
|---|
| \(\{1,3,4\}\): | 0 | 1 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | ... |
| זוגיים: | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | ... |
| אי-זוגיים: | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | ... |
| ריבועים: | 1 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | ... |
סימון
לכן \(P(\mathbb{N})\) ניתנת לסמן גם כ-\(2^{\mathbb{N}}\) — קבוצת כל הסדרות הבינאריות האינסופיות (פונקציות מ-\(\mathbb{N}\) ל-\(\{0,1\}\)).
4. אלכסון קנטור: \(P(\mathbb{N})\) איננה בת-מניה
משפט (קנטור)
\(P(\mathbb{N})\) איננה בת-מניה. בפרט, \(|P(\mathbb{N})| > \aleph_0\).
הוכחת האלכסון (Diagonalization)
בדרך השלילה — נניח ש-\(P(\mathbb{N})\) בת-מניה. אזי קיים סידור \(A_0, A_1, A_2, \ldots\) של תתי-הקבוצות. נסמן \(A_{ij} = 1\) אם \(j \in A_i\) ואחרת 0:
| \(j=\) | 0 | 1 | 2 | 3 | 4 | 5 | 6 | ... |
|---|
| \(A_0\): | 0 | 1 | 0 | 1 | 1 | 0 | 0 | ... |
| \(A_1\): | 1 | 1 | 1 | 0 | 1 | 0 | 1 | ... |
| \(A_2\): | 0 | 1 | 0 | 1 | 0 | 1 | 0 | ... |
| \(A_3\): | 1 | 0 | 1 | 1 | 0 | 1 | 1 | ... |
| ... | ... |
נגדיר \(B \subseteq \mathbb{N}\) ע"י המחרוזת האופיינית — הופכת את האלכסון:
\(B[n] = 1 - A_{nn}\)
כלומר: לקחת את האלכסון של הטבלה (\(A_{00}, A_{11}, A_{22}, \ldots\)) ולהפוך כל ביט. בדוגמה למעלה: אלכסון = 0,1,0,1,... ⟹ \(B = 1, 0, 1, 0, \ldots = \{0, 2, \ldots\}\).
סתירה: \(B \subseteq \mathbb{N}\) ולכן \(B \in P(\mathbb{N})\). לפי הסידור, יש \(k\) כך ש-\(B = A_k\). אבל הביט ה-\(k\) של \(B\) הוא \(B[k] = 1 - A_{kk}\) — שונה מהביט ה-\(k\) של \(A_k\). \(B \neq A_k\). סתירה. ∎
למה זה עובד?
\(B\) "מנצח" כל \(A_k\) במקום ה-\(k\) — לכן לא יכול להיות בסידור. הזוועה: כל ניסיון לסדר את \(P(\mathbb{N})\) חייב לפספס את \(B\).
5. ייצוג מספרים ממשיים בבסיסים
למספר ממשי \(r\) לא תמיד יש ייצוג עשרוני סופי (כמו \(2.35\)) או ייצוג כמנה של טבעיים (כמו \(2/3\)). אבל תמיד יש לו:
- ייצוג עשרוני אינסופי (\(0.3333\ldots\), \(\pi = 3.14159\ldots\)).
- ייצוג בינארי אינסופי (\(0.10101010\ldots\)).
- ייצוג אינסופי בכל בסיס \(k\) טבעי.
המספר המיוצג הוא הגבול של סדרת הרציונליים המתוארת ע"י הרישות הסופיות:
\(0.3333\ldots = \lim(3/10, 33/100, 333/1000, \ldots)\)
משפט: ייחוד הייצוג בבסיס \(k\) (כמעט)
לכל מס' ממשי יש או ייצוג
יחיד בבסיס \(k\), או
בדיוק שניים: באחד יש "0" ממיקום מסוים ואילך, ובאחר "\(k-1\)" ממיקום מסוים ואילך.
דוגמא
עשרוני: \(0.10000\ldots = 0.09999\ldots\). בינארי: \(0.1 = 0.0111\ldots\).
6. \(|\mathbb{R}| = |P(\mathbb{N})|\)
משפט
\(|\mathbb{R}| = |P(\mathbb{N})|\).
נראה \(|[0,1]| \leq |P(\mathbb{N})|\) וגם \(|P(\mathbb{N})| \leq |[0,1]|\) (כי \(|[0,1]| = |\mathbb{R}|\)).
\(|P(\mathbb{N})| \leq |[0,1]|\) - דרך עשרוני
לכל \(I \in P(\mathbb{N})\) (סדרה אינסופית של 0/1), נגדיר \(f(I) = 0.I\) בייצוג עשרוני (כל ביט הוא ספרה). \(f\) חח"ע: שתי סדרות שונות נותנות ייצוגים עשרוניים שונים. ההכפלה לא יכולה להתרחש כי בייצוג עשרוני היא חייבת 9-יות (לא 0-1 בלבד).
\(|[0,1]| \leq |P(\mathbb{N})|\) - דרך בינארי
לכל \(b \in [0,1]\), נסתכל על ייצוג בינארי \(b = 0.I\), ונגדיר \(g(b) = I\) (תת-קבוצה ב-\(P(\mathbb{N})\)). \(g\) על: לכל \(I \in P(\mathbb{N})\) יש לפחות \(b\) ב-\([0,1]\) שמתאים.
קנטור-שרדר-ברנשטיין ⟹ \(|[0,1]| = |P(\mathbb{N})|\). ⟹ \(|\mathbb{R}| = |P(\mathbb{N})|\). ∎
למה לא דרך עשרוני בלבד?
סדרה אינסופית \(0.I\) בעשרוני
מתכנסת לרציונלי רק לחלק קטן (פריודיות מסוימת). חלק גדול מתכנס לאי-רציונליים. לכן הפונקציה \(P(\mathbb{N}) \to \mathbb{Q}\) דרך עשרוני לא תהיה על.
7. עוצמת הרצף \(\aleph = c = 2^{\aleph_0}\)
הגדרה: עוצמת הרצף
\(|\mathbb{R}|\) נקראת
עוצמת הרצף (continuum cardinality), עם שלושה סימונים:
- \(\aleph\) (אָלֶף, ללא אינדקס).
- \(c\) (continuum).
- \(2^{\aleph_0}\) (כי \(|\mathbb{R}| = |P(\mathbb{N})| = |2^{\mathbb{N}}|\)).
8. סגירות מחלקת \(\aleph\) תחת פעולות
משפטים
- איחוד: \(|A| = |B| = \aleph\) ⟹ \(|A \cup B| = \aleph\).
- איחוד סופי: \(|A_1| = \ldots = |A_k| = \aleph\) ⟹ \(|A_1 \cup \ldots \cup A_k| = \aleph\).
- מכפלה: \(|A| = |B| = \aleph\) ⟹ \(|A \times B| = \aleph\).
- מכפלה סופית: \(|A_1| = \ldots = |A_k| = \aleph\) ⟹ \(|A_1 \times \ldots \times A_k| = \aleph\).
- בפרט: \(|\mathbb{R}^k| = \aleph\) לכל \(k\) טבעי. (לישר ולמישור יש אותה עוצמה!)
הוכחת האיחוד \(|A \cup B| = \aleph\)
A ⊆ A∪B ⟹ |A∪B| ≥ ℵ.
A ~ ℝ ~ (0,1] ו-B ~ ℝ ~ (1,2). יש פונ' f, g מ-(0,1], (1,2) על A, B.
נגדיר h: (0,2) → A∪B:
h(x) = f(x) אם x ∈ (0,1]
h(x) = g(x) אם x ∈ (1,2)
h על ⟹ |A∪B| ≤ |(0,2)| = ℵ. קנטור-שרדר-ברנשטיין: |A∪B| = ℵ. ∎
למכפלה: שזירה (interleaving) של ייצוגי המספרים — \((a, b)\) עם \(a = 0.a_0 a_1 a_2\ldots\), \(b = 0.b_0 b_1 b_2\ldots\) ⟹ \(0.a_0 b_0 a_1 b_1 a_2 b_2\ldots\).
9. משפט קנטור: \(|P(S)| > |S|\)
משפט קנטור
לכל קבוצה \(S\), מתקיים \(|P(S)| > |S|\).
הוכחה
שלב 1: \(|S| \leq |P(S)|\). נגדיר \(f: S \to P(S)\) ע"י \(f(x) = \{x\}\) — חח"ע ומלאה.
שלב 2: \(|P(S)| \not\leq |S|\) (בדרך השלילה).
נניח שקיימת f: S → P(S) על.
נגדיר D = {x ∈ S | x ∉ f(x)}. (הגדרה חוקית: D ⊆ S)
מכיוון ש-D ∈ P(S) ו-f על, יש a ∈ S כך ש-D = f(a). (**)
כעת:
• אם a ∈ f(a): לפי הגדרת D, a ∉ D. לפי (**), a ∉ f(a). סתירה.
• אם a ∉ f(a): לפי הגדרת D, a ∈ D. לפי (**), a ∈ f(a). סתירה.
⟹ אין פונקציה על ⟹ |P(S)| > |S|. ∎
דמיון לפרדוקס ראסל
\(D = \{x \in S \mid x \notin f(x)\}\) דומה ל-\(R = \{x \mid x \notin x\}\) של ראסל. אותה אסטרטגיה אלכסונית.
10. פרדוקס קנטור: אין קבוצת כל הקבוצות
קנטור מצא ב-1899 את הפרדוקס הבא של תורת הקבוצות הנאיבית — מבוסס על משפט קנטור:
פרדוקס קנטור
לא קיימת קבוצה של כל הקבוצות.
נניח בדרך השלילה שקיימת קבוצה A של כל הקבוצות.
לפי משפט קנטור: |P(A)| > |A|.
כל איבר ב-P(A) הוא קבוצה (בתורה הנאיבית, כל איבר הוא קבוצה).
לכן כל איבר של P(A) הוא איבר של A. כלומר P(A) ⊆ A.
מכאן |P(A)| ≤ |A|. סתירה. ∎
היסטוריה
ראסל הגיע לפרדוקס שלו (\(R = \{x \mid x \notin x\}\)) בעקבות שקרא את הוכחת קנטור. שני הפרדוקסים הביאו לפיתוח ZFC.
11. השערת הרצף ו-GCH
לפי משפט קנטור, יש אינסוף דרגות של אינסוף:
\(\mathbb{N}, \quad P(\mathbb{N}), \quad P(P(\mathbb{N})), \quad \ldots\)
\(\aleph_0, \quad 2^{\aleph_0}, \quad 2^{2^{\aleph_0}}, \quad \ldots\)
נסמן ב-\(\aleph_1\) את העוצמה הקטנה ביותר שגדולה ממש מ-\(\aleph_0\) (אם יש כזו), ב-\(\aleph_2\) את הבאה וכו'.
השערת הרצף (CH)
\(\aleph_1 = 2^{\aleph_0}\). כלומר, אין "אינסוף נוסף" בין \(\aleph_0\) ל-\(\aleph\): אין קבוצה \(S\) כך ש-\(|\mathbb{N}| < |S| < |\mathbb{R}|\).
השערת הרצף המוכללת (GCH)
לכל \(i\), \(\aleph_{i+1} = 2^{\aleph_i}\). אין עוצמה בין \(|S|\) ל-\(|P(S)|\) לכל קבוצה אינסופית \(S\).
12. אי-תלות ב-ZFC (Independence)
קנטור הציג את ההשערה ב-1878. הילברט קבע אותה כבעיה מס' 1 למאה ה-20.
| שנה | חוקר | תוצאה |
|---|
| 1940 | קורט גדל (Gödel) | השערת הרצף עקבית עם ZFC. |
| 1964 | פול כהן (Cohen) | שלילת ההשערה עקבית עם ZFC. |
המסקנה
השערת הרצף (ו-GCH)
בלתי-תלויות ב-ZFC: יש מערכת תורת קבוצות המרחיבה את ZFC שבה ההשערה נכונה, ויש מערכת אחרת שבה ההשערה לא נכונה.
פירוש:
לא ניתן לטעון (במסגרת ZFC) שיש או שאין עוצמה בין \(\aleph_0\) ל-\(\aleph\).
13. סיכום ההרצאה
\(P(\mathbb{N})\) לא בת-מניה
(אלכסון קנטור)
→
\(|\mathbb{R}| = |P(\mathbb{N})| = \aleph\)
→
סגירות מחלקת \(\aleph\)
→
משפט קנטור
\(|P(S)| > |S|\)
→
CH ⊥ ZFC
דוגמאות לעוצמות מוכרות
| עוצמה | דוגמאות |
|---|
| סופית | \(\emptyset\), \(\{x,y,z\}\), \(\{a, \{b,c,d\}\}\) |
| בת-מניה (\(\aleph_0\)) | זוגיים, \(\mathbb{N}, \mathbb{Z}, \mathbb{N}^k, \mathbb{Q}, \mathbb{Q}^k\) |
| עוצמת הרצף (\(\aleph, c, 2^{\aleph_0}\)) | כל קטע \((a,b)\), \(\mathbb{R}, \mathbb{R}^k, \mathbb{C}\) |
| מעבר ל-\(\aleph\) | \(P(\mathbb{R})\) — בעוצמה \(2^{\aleph}\) |
נקודות מפתח
- אלכסון קנטור: \(P(\mathbb{N})\) איננה בת-מניה. \(B[n] = 1 - A_{nn}\) "מנצח" כל \(A_k\) בסידור.
- \(|\mathbb{R}| = |P(\mathbb{N})| = 2^{\aleph_0}\) — דרך ייצוג בינארי אינסופי.
- עוצמת הרצף: \(\aleph = c = 2^{\aleph_0}\).
- סגירות \(\aleph\): איחוד / מכפלה (סופיים) של קבוצות בעוצמה \(\aleph\) — בעוצמה \(\aleph\). \(|\mathbb{R}^k| = \aleph\).
- משפט קנטור הכללי: \(|P(S)| > |S|\) לכל \(S\). הוכחה אלכסונית עם \(D = \{x \in S \mid x \notin f(x)\}\).
- פרדוקס קנטור: אין קבוצת כל הקבוצות.
- CH: אין עוצמה בין \(\aleph_0\) ל-\(\aleph\). בלתי-תלויה ב-ZFC (גדל 1940, כהן 1964).
מסקנה רחבה
יש
הרבה סוגי אינסוף (\(\aleph_0, \aleph, 2^{\aleph}, \ldots\)). מה שנראה לנו כ-"אינסוף" אחיד מהחיים — הוא בעצם היררכיה אינסופית של עוצמות.