1. סיכום קצר: תורת הקבוצות הנאיבית מול האקסיומטית
תורת הקבוצות הנאיבית
"כל דבר הוא קבוצה". תשתית נוחה לבניית יסודות המתמטיקה (איחוד, חיתוך, קבוצת חזקה, זוג סדור, וכו'), אבל מובילה לפרדוקסים:
- פרדוקס ראסל: \(S = \{x \mid x \notin x\}\) — לא שייכת ולא לא-שייכת לעצמה.
- פרדוקס קנטור: אין קבוצה של כל הקבוצות (אילו הייתה כזו \(A\), היה \(P(A) \subseteq A\), בסתירה למשפט קנטור).
תורת הקבוצות האקסיומטית — ZFC
מצמצמת את התורה הנאיבית כדי למנוע פרדוקסים. מגדירה באופן פורמלי מה בהכרח קבוצה ומה לא יכול להיות קבוצה. מערכת האקסיומות הנמצאת בשימוש הנרחב ביותר היא ZFC, המגדירה ש:
- יש קבוצה ריקה,
- יש קבוצה אינסופית,
- לא ייתכן קבוצה השייכת לעצמה,
- יש איחוד, חיתוך, קבוצת חזקה, ...
קבוצות "מותרות" אך לא הכרחיות
קבוצות מסוימות עשויות להתקיים לפי המערכת ZFC, אך לא הכרחיות במערכת — כגון
השערת הרצף (CH).
2. שימוש זהיר ב-set builder notation
באופן פורמלי, יסודות המתמטיקה מוגדרים מעל ZFC. יחד עם זאת, ברוב ענפי המתמטיקה (ובפרט במדעי המחשב), ניתן להשתמש באופן כמעט חופשי בתורת הקבוצות הנאיבית — שכן הקבוצות בהן דנים הינן תתי-קבוצות של קבוצות תקינות.
יש רק לשים דגש מיוחד על אופן השימוש ב-set builder notation:
לא נכון
\(\{x \mid x \text{ satisfies some property}\}\) — עלול להוביל לפרדוקסים.
נכון, עבור קבוצה מוגדרת \(A\)
\(\{x \in A \mid x \text{ satisfies some property}\}\)
תרגיל: אילו מההגדרות תקינות?
| הגדרה | תקינה? | הסבר |
|---|
| \(\{x \in P(\mathbb{N}) \mid x \in x\}\) | ✓ תקין | שווה ל-\(\emptyset\) (ZFC לא מאפשר \(x \in x\)) |
| \(\{x \mid x \notin x\}\) | ✗ לא תקין | פרדוקס ראסל |
| \(\{x \subseteq \mathbb{N} \mid x \notin x\}\) | ✓ תקין | שווה ל-\(P(\mathbb{N})\) — כל תת-קבוצה של \(\mathbb{N}\) |
| \(\{x \mid x \in x\}\) | ✗ לא תקין | אין הגבלה על \(x\) |
3. עוצמות והשוואת עוצמות
עוצמה (Cardinality)
המושג של "גודל" של קבוצה, אשר בקבוצות סופיות הינו מספר האיברים, מורחב למושג
עוצמה, אשר מתייחס הן לקבוצות סופיות והן לקבוצות אינסופיות.
העוצמה של קבוצה \(A\) מסומנת ב-\(|A|\).
עוצמה היא יישות אבסטרקטית — מספר. נתייחס לעוצמה \(\alpha\) (למשל, \(0, 3, 15, \aleph_0, \aleph\)) כתכונה המשותפת לכל הקבוצות בגודל \(\alpha\).
השוואת עוצמות
- \(|A| \leq |B|\) אמ"מ קיימת \(f: A \to B\) חח"ע ומלאה. שקול: קיימת \(g: B \twoheadrightarrow A\) על.
- \(|A| = |B|\) אמ"מ \(|A| \leq |B|\) ו-\(|A| \geq |B|\). לפי קנטור-שרדר-ברנשטיין, שקול לקיום \(f: A \leftrightarrow B\) חח"ע ועל.
- \(|A| < |B|\) אמ"מ \(|A| \leq |B|\) ו-\(|A| \neq |B|\).
מסתבר
ישנם גדלים — עוצמות —
שונים של אינסוף.
4. קבוצות אינסופיות, בנות-מניה, ועוצמת הרצף
קבוצה אינסופית — הגדרות שקולות
\(A\) אינסופית אם מתקיימת אחת:
- קיימת \(S \subsetneq A\) עם \(|S| = |A|\),
- קיימת קבוצה אינסופית \(B \subseteq A\),
- \(|\mathbb{N}| \leq |A|\) (קיימת \(f: \mathbb{N} \to 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}\) בנות מניה.
\(P(\mathbb{N})\) איננה בת-מניה — אלכסון קנטור
הוכחה (תזכורת מהרצאה 4): מניחים סידור \(A_0, A_1, \ldots\) של תתי הקבוצות. בונים \(B[n] = 1 - A_n[n]\). אזי \(B\) שונה מכל \(A_k\) באינדקס ה-\(k\) — סתירה.
עוצמת הרצף \(\aleph = c = 2^{\aleph_0}\)
\(|\mathbb{R}| = |P(\mathbb{N})| = |\{0,1\}^{\mathbb{N}}| = 2^{\aleph_0}\).
סימונים מקובלים: \(\aleph\) (אָלֶף), \(c\) (continuum), \(2^{\aleph_0}\).
5. דרגות של אינסוף, CH, GCH, אי-תלות ב-ZFC
לפי משפט קנטור, קיימות אינסוף דרגות של אינסוף:
\(\mathbb{N}, \; P(\mathbb{N}), \; P(P(\mathbb{N})), \; \ldots\)
\(\aleph_0, \; 2^{\aleph_0}, \; 2^{2^{\aleph_0}}, \; \ldots\)
השערת הרצף (Continuum Hypothesis — CH)
אין אף קבוצה \(S\) כך ש-\(|\mathbb{N}| < |S| < |\mathbb{R}|\). באופן שקול: \(\aleph_1 = 2^{\aleph_0}\).
השערת הרצף המוכללת (GCH)
לא קיימות קבוצות אינסופיות \(S, S'\) כך ש-\(|S| < |S'| < |2^S|\). כלומר \(\aleph_{i+1} = 2^{\aleph_i}\) לכל \(i\).
אי-תלות (גדל וכהן)
השערת הרצף (וכן GCH)
בלתי-תלויות ב-ZFC: יש מערכת המרחיבה את ZFC בה ההשערה נכונה (גדל, 1940), ויש מערכת אחרת בה ההשערה לא נכונה (כהן, 1964).
תרגיל: אילו מהטענות נכונות?
| טענה | נכונה? | הסבר |
|---|
| \(|\mathbb{N}| \neq |\mathbb{R}|\) | ✓ | \(\aleph_0 \neq \aleph\) (קנטור) |
| \(|\mathbb{R}| = |P(\mathbb{Q})|\) | ✓ | \(\aleph = 2^{\aleph_0}\); \(|P(\mathbb{Q})|=2^{\aleph_0}\) |
| \(|\mathbb{Q}| \neq |P(\mathbb{N})|\) | ✓ | \(\aleph_0 \neq 2^{\aleph_0}\) |
| \(|P(\mathbb{N})| < |P(\mathbb{R})|\) | ✓ | \(2^{\aleph_0} < 2^{\aleph}\) ממשפט קנטור |
6. דוגמאות לעוצמות של קבוצות מוכרות
| עוצמה | דוגמאות |
|---|
| סופית | \(|\emptyset| = 0\); \(|\{x,y,z\}| = 3\); \(|\{a, \{b,c,d\}\}| = 2\) |
| אינסופית בת-מניה (\(\aleph_0\)) | הזוגיים, \(\mathbb{N}, \mathbb{Z}, \mathbb{N}^k, \mathbb{Q}, \mathbb{Q}^k\) |
| עוצמת הרצף (\(2^{\aleph_0}, \aleph, c\)) | כל קטע ממשי \((x,y)\), \(\mathbb{R}, \mathbb{R}^k, \mathbb{C}\) |
| מעבר לעוצמת הרצף | \(P(\mathbb{R})\), עם \(|P(\mathbb{R})| = 2^{\aleph}\) |
7. אריתמטיקת עוצמות — הגדרת הפעולות
הגדרה
בהינתן עוצמות \(\alpha\) ו-\(\beta\), תהינה \(A\) ו-\(B\)
קבוצות זרות כך ש-\(\alpha = |A|\) ו-\(\beta = |B|\). נגדיר:
- \(\alpha + \beta = |A \cup B|\) (חיבור).
- \(\alpha \cdot \beta = |A \times B|\) (כפל).
- \(\alpha^\beta = |A^B|\), כאשר \(A^B = \{f \mid f \text{ פונקציה מלאה מ-}B\text{ ל-}A\}\) (חזקה).
הקשרים בין עוצמות
- \(\alpha = \beta \iff |A| = |B|\)
- \(\alpha \leq \beta \iff |A| \leq |B|\)
- \(\alpha < \beta \iff |A| < |B|\)
- \(\max(\alpha, \beta) = \alpha\) אם \(|B| \leq |A|\), אחרת \(\beta\).
דוגמא: \(\aleph + \aleph_0 = \aleph\)
הטבעיים \(\mathbb{N}\) זרים לממשיים השליליים \(\mathbb{R}^-\).
\(\aleph + \aleph_0 = |\mathbb{R}^- \cup \mathbb{N}|\).
מתקיים \(\mathbb{R}^- \subseteq (\mathbb{R}^- \cup \mathbb{N}) \subseteq \mathbb{R}\), ולכן \(\aleph \leq \aleph + \aleph_0 \leq \aleph\).
\(\therefore \aleph + \aleph_0 = \aleph\). ✓
8. הפעולות מוגדרות היטב
בהגדרה בחרנו קבוצות זרות \(A, B\) כלשהן. השאלה: האם זה בסדר? אולי תוצאה שונה תהיה לבחירה אחרת?
הפעולות מוגדרות היטב
לכל \(A, A', B, B'\) זרות (בכל זוג) עם \(|A| = |A'|\) ו-\(|B| = |B'|\), מתקיים:
- \(|A \cup B| = |A' \cup B'|\)
- \(|A \times B| = |A' \times B'|\)
- \(|A^B| = |A'^{B'}|\)
הוכחה: שיוויונות אלו נובעים ישירות
מקיום פונקציות שקילות בין \(A\) ל-\(A'\) ובין \(B\) ל-\(B'\) — מהן מורכבים פונקציות שקילות בין הצדדים.
9. עשרה שיוויונות בסיסיים
משפט. לכל עוצמות \(\alpha, \beta, \gamma\):
| 1. | \(\alpha + \beta = \beta + \alpha\) | קומוטטיביות חיבור |
| 2. | \((\alpha + \beta) + \gamma = \alpha + (\beta + \gamma)\) | אסוציאטיביות חיבור |
| 3. | \(\alpha + 0 = \alpha\) | איבר נייטרלי |
| 4. | \(\alpha \cdot \beta = \beta \cdot \alpha\) | קומוטטיביות כפל |
| 5. | \((\alpha \cdot \beta) \cdot \gamma = \alpha \cdot (\beta \cdot \gamma)\) | אסוציאטיביות כפל |
| 6. | \(\alpha \cdot 1 = \alpha\) | איבר נייטרלי |
| 7. | \(\alpha \cdot (\beta + \gamma) = \alpha\beta + \alpha\gamma\) | פילוג |
| 8. | \((\alpha \cdot \beta)^\gamma = \alpha^\gamma \cdot \beta^\gamma\) | חוק חזקות |
| 9. | \(\alpha^{\beta+\gamma} = \alpha^\beta \cdot \alpha^\gamma\) | חוק חזקות |
| 10. | \((\alpha^\beta)^\gamma = \alpha^{\beta\gamma}\) | חוק חזקות |
איך מוכיחים?
כל שיוויון נובע מבניית פונקציית שקילות בין הקבוצות המתאימות. שתי דוגמאות מפורטות בסעיפים הבאים.
10. הוכחה: \(\alpha(\beta+\gamma) = \alpha\beta + \alpha\gamma\)
נתון: \(|A| = \alpha\), \(|B| = \beta\), \(|C| = \gamma\), \(B\) ו-\(C\) זרות.
- אגף שמאל: \(|A \times (B \cup C)| = \alpha(\beta+\gamma)\).
- אגף ימין: \(|(A \times B) \cup (A \times C)| = \alpha\beta + \alpha\gamma\) (זרות, כי \(B,C\) זרות).
בנייה
מגדירים \(f: A \times (B \cup C) \to (A \times B) \cup (A \times C)\) ע"י
\(f(a, t) = (a, t), \quad t \in B \Rightarrow f(a,t) \in A \times B; \;\; t \in C \Rightarrow f(a,t) \in A \times C.\)
חח"ע
בהינתן \((a_1, t_1) \neq (a_2, t_2)\): אם \(a_1 \neq a_2\) ההפרש ברכיב הראשון. אחרת \(t_1 \neq t_2\), ונפצל למקרים לפי האם \(t_i \in B\) או \(t_i \in C\) — בכל מקרה \(f\) מחזירה זוגות שונים (לפעמים אפילו בקבוצות זרות).
על
לכל \((a,b) \in A \times B\) יש \((a,b) \in A \times (B \cup C)\) כך ש-\(f(a,b) = (a,b)\). דומה ל-\(A \times C\).
לכן \(f\) שקילות, ומכאן \(\alpha(\beta+\gamma) = \alpha\beta + \alpha\gamma\). \(\blacksquare\)
11. הוכחה: \((\alpha\beta)^\gamma = \alpha^\gamma \cdot \beta^\gamma\)
נתון: \(|A| = \alpha\), \(|B| = \beta\), \(|C| = \gamma\).
- אגף שמאל: \(|(A \times B)^C|\) — פונקציות מלאות מ-\(C\) ל-\(A \times B\).
- אגף ימין: \(|A^C \times B^C|\) — זוגות \((h, t)\) של פונקציות מלאות \(h: C \to A\), \(t: C \to B\).
בנייה
מגדירים \(f\) שמעבירה כל \(g: C \to A \times B\) לזוג הפרויקציות \((h, t)\):
\(\forall c \in C: \; g(c) = (a_c, b_c) \;\;\Longrightarrow\;\; h(c) = a_c, \;\; t(c) = b_c.\)
חח"ע
אם \(g_1 \neq g_2\), קיים \(c\) כך ש-\((a_1, b_1) = g_1(c) \neq g_2(c) = (a_2, b_2)\). אז \(h_1(c) \neq h_2(c)\) או \(t_1(c) \neq t_2(c)\), ובכל מקרה \(f(g_1) \neq f(g_2)\).
על
בהינתן זוג \((h, t)\), נגדיר \(g(c) = (h(c), t(c))\) — פונקציה מלאה מ-\(C\) ל-\(A \times B\), ו-\(f(g) = (h, t)\).
לכן \(f\) שקילות, ומכאן \((\alpha\beta)^\gamma = \alpha^\gamma \cdot \beta^\gamma\). \(\blacksquare\)
12. שמירה על יחס הסדר \(\leq\)
משפט
אם \(\alpha \leq \alpha'\) ו-\(\beta \leq \beta'\), אז:
- \(\alpha + \beta \leq \alpha' + \beta'\)
- \(\alpha \cdot \beta \leq \alpha' \cdot \beta'\)
- \(\alpha^\beta \leq \alpha'^{\beta'}\)
אי-שיוויונות אלו נובעים ישירות מהפונקציות המלאות והחח"ע בין \(A\) ל-\(A'\) ובין \(B\) ל-\(B'\).
13. תכונות עוצמות אינסופיות
\(\aleph_0\) היא העוצמה האינסופית הקטנה ביותר
לכל עוצמה אינסופית \(\alpha\) מתקיים \(\aleph_0 \leq \alpha\).
רעיון: בוחרים אינדוקטיבית איברים שונים \(a_0, a_1, a_2, \ldots \in A\); הפונקציה \(f(n) = a_n\) חח"ע ומלאה.
שיוויונות בסיסיים
- \(\aleph_0 + \aleph_0 = \aleph_0\)
- \(\aleph_0 \cdot \aleph_0 = \aleph_0\) (\(|\mathbb{N} \times \mathbb{N}| = \aleph_0\))
- \(\aleph + \aleph = \aleph\)
- \(\aleph \cdot \aleph = \aleph\) (\(|\mathbb{R}^2| = \aleph\) — לישר ולמישור אותה עוצמה!)
משפט כללי (ללא הוכחה)
לכל עוצמות \(\alpha, \beta\) כאשר לפחות אחת אינסופית:
\(\alpha + \beta = \max(\alpha, \beta)\)
\(\alpha \cdot \beta = \max(\alpha, \beta) \quad (\text{אם } \alpha, \beta \neq 0)\)
המשפט עוצמתי: אריתמטיקת עוצמות אינסופיות "קורסת" — חיבור וכפל כולם נותנים את המקסימום. ההבדלים מהותיים רק ב
חזקות.
14. מסקנה: \(\beta^\alpha = 2^\alpha\)
מסקנה
אם \(\alpha\) אינסופית ו-\(2 \leq \beta \leq 2^\alpha\), אז \(\beta^\alpha = 2^\alpha\).
הוכחה
נסחב משני הצדדים בחזקת \(\alpha\):
\(2^\alpha \;\leq\; \beta^\alpha \;\leq\; (2^\alpha)^\alpha \;=\; 2^{\alpha \cdot \alpha} \;=\; 2^\alpha\)
(השתמשנו ב-\(\alpha \cdot \alpha = \alpha\) לעוצמה אינסופית, וב-\((\alpha^\beta)^\gamma = \alpha^{\beta\gamma}\).)
לפי קנטור-שרדר-ברנשטיין: \(\beta^\alpha = 2^\alpha\). \(\blacksquare\)
דוגמא חשובה: \(\aleph^{\aleph_0} = \aleph\)
\(2 \leq \aleph_0 \leq 2^{\aleph_0} = \aleph\), ו-\(\alpha = \aleph_0\) אינסופית.
לפי המסקנה: \(\aleph_0^{\aleph_0} \leq \aleph^{\aleph_0} \leq (2^{\aleph_0})^{\aleph_0} = 2^{\aleph_0 \cdot \aleph_0} = 2^{\aleph_0} = \aleph\).
\(\therefore \aleph^{\aleph_0} = \aleph\) —
עוצמת קבוצת הסדרות האינסופיות של ממשיים שווה לעוצמת הרצף עצמה!
15. משפט קנטור-שרדר-ברנשטיין — הוכחה מלאה
משפט (Cantor-Schröder-Bernstein)
אם \(|A| \leq |B|\) ו-\(|B| \leq |A|\), אז \(|A| = |B|\).
כלומר: אם יש \(f: A \to B\) ו-\(g: B \to A\) חח"ע ומלאות, אז יש גם \(h: A \leftrightarrow B\).
הבנייה
- \(D = g(B) \subseteq A\) — תמונת \(g\). מאחר ש-\(g\) חח"ע, מתקיים \(B \sim D\) (\(g\) שקילות בין \(B\) ל-\(D\)).
- \(C = A \setminus D\).
- אם נמצא \(m: A \leftrightarrow D\), אז \(h = g^{-1} \circ m\) הוא בייקציה \(A \leftrightarrow B\).
- נשים לב: \(t = g \circ f: A \to D\) חח"ע ומלאה (אך אולי לא על).
לכן מספיק להוכיח את הלמה:
למה
עבור קבוצות זרות \(C, D\) עם פונקציה מלאה וחח"ע \(t: C \cup D \to D\), קיימת בייקציה \(m: C \cup D \leftrightarrow D\).
הוכחת הלמה — בנייה איטרטיבית
A = C ∪ D
\(C_0 = C\)
\(C_1 = t(C_0)\)
\(C_2 = t(C_1)\)
⋮
\(D \setminus \bigcup_i C_i\)
→ m →
D
\(C_1\) (קיבל את \(C_0\))
\(C_2\) (קיבל את \(C_1\))
\(C_3\) ⋮
\(D \setminus \bigcup_i C_i\) (זהות)
m מלאה
ישירות מההגדרה — מטפלת בכל \(x \in C \cup D\).
m חח"ע
"ענף ה-\(t\)" מעביר \(C_i \to C_{i+1}\) (זרות, כי \(t\) חח"ע ו-\(C_i\) זרות). "ענף הזהות" שומר את \(x \in D \setminus \bigcup C_i\) — וזה לא יוצר התנגשות עם הענף הראשון, שמסתיים תמיד באיזשהו \(C_{i+1}\).
m על
יהי \(y \in D\):
- אם \(y \in C_{i+1}\) עבור \(i \geq 0\), אז \(y = t(x)\) עבור \(x \in C_i\), ולכן \(m(x) = y\).
- אחרת \(y \in D \setminus \bigcup_i C_i\), ואז \(m(y) = y\).
\(\therefore m: C \cup D \leftrightarrow D\) בייקציה. \(\blacksquare\)
משחזרים את CSB
עבור \(A, B\) המקוריות: \(C = A \setminus D\), \(D = g(B)\), \(t = g \circ f: A \to D\). הלמה נותנת בייקציה \(m: A = C \cup D \leftrightarrow D\). \(g^{-1}: D \leftrightarrow B\), אז \(h = g^{-1} \circ m: A \leftrightarrow B\). \(\blacksquare\)
16. סיכום ונקודות מפתח
- ZFC מצמצמת את התורה הנאיבית כדי למנוע פרדוקסים. ב-set builder notation: \(\{x \in A \mid P(x)\}\) תקין; \(\{x \mid P(x)\}\) — לא.
- השוואת עוצמות: \(|A| \leq |B| \iff \exists f: A \hookrightarrow B \iff \exists g: B \twoheadrightarrow A\).
- אריתמטיקת עוצמות: \(\alpha + \beta = |A \cup B|\), \(\alpha \cdot \beta = |A \times B|\), \(\alpha^\beta = |A^B|\) — מוגדר היטב על קבוצות זרות.
- 10 שיוויונות בסיסיים — קומוטטיביות, אסוציאטיביות, פילוג, חוקי חזקות.
- הסדר נשמר: \(\alpha \leq \alpha' \wedge \beta \leq \beta' \Rightarrow \alpha+\beta \leq \alpha'+\beta'\), וכן לכפל וחזקה.
- עוצמות אינסופיות: \(\aleph_0 \leq \alpha\) לכל \(\alpha\) אינסופית. \(\alpha + \beta = \alpha \cdot \beta = \max(\alpha, \beta)\) (אחת אינסופית).
- חזקות: \(\alpha\) אינסופית ו-\(2 \leq \beta \leq 2^\alpha\) \(\Rightarrow\) \(\beta^\alpha = 2^\alpha\). בפרט \(\aleph^{\aleph_0} = \aleph\).
- קנטור-שרדר-ברנשטיין: \(|A| \leq |B| \wedge |B| \leq |A| \Rightarrow |A| = |B|\). הוכחה: \(D = g(B)\), \(C = A \setminus D\), \(t = g \circ f\); \(C_{i+1} = t(C_i)\); \(m = t\) על \(\bigcup C_i\), זהות אחרת.
מבט קדימה
ראינו שאריתמטיקת עוצמות אינסופיות פשוטה מהצפוי (\(\max\)). כעת יש לנו את הכלי המלא להוכיח שיוויונות עוצמה — קנטור-שרדר-ברנשטיין הוא "הסכין השוויצרית" של ההוכחות בתחום.