1. תזכורת: שקילות, סדר עוצמות, סופי/אינסופי
קבוצות שקולות \(A \sim B\)
\(|A| = |B|\) אם קיימת
פונקציית שקילות (bijection) בין \(A\) ל-\(B\) — מלאה, חח"ע ועל.
סדר עוצמות \(|A| \leq |B|\)
קיימת
פונקציה מלאה וחח"ע מ-\(A\) ל-\(B\). שקול: קיימת פונקציה (חלקית) מ-\(B\)
על \(A\).
אנטי-סימטרי לפי משפט קנטור-שרדר-ברנשטיין: \(|A| \leq |B|\) ו-\(|B| \leq |A|\) \(\Rightarrow\) \(|A| = |B|\).
סופי / אינסופי
אינסופית: \(A\) שקולה לתת-קבוצה ממש שלה.
סופית: לא אינסופית.
משפטים: \(A \subseteq B\) ו-\(A\) אינסופית \(\Rightarrow\) \(B\) אינסופית. \(A \sim B\) ו-\(A\) אינסופית \(\Rightarrow\) \(B\) אינסופית.
2. \(\mathbb{N}\) - האינסוף הקטן ביותר
משפט מרכזי
קבוצה \(A\) הינה אינסופית אמ"מ \(|\mathbb{N}| \leq |A|\). כלומר: לכל קבוצה אינסופית קיימת פונקציה מלאה וחח"ע \(f: \mathbb{N} \to A\).
הכיוון הקל: \(|\mathbb{N}| \leq |A|\) \(\Rightarrow\) \(A\) אינסופית
קיימת f:ℕ→A מלאה וחח"ע. תהי K = f(ℕ) התמונה.
f': ℕ→K, f'(n)=f(n) — bijection ⟹ K שקולה ל-ℕ ⟹ K אינסופית (משפט שקילות).
K ⊆ A ⟹ A אינסופית (משפט הכלה).
הכיוון הקשה (אינטואיטיבית)
\(A_0 = A\). \(A_0\) אינסופית, אז קיימת \(A_1 \subsetneq A_0\) עם \(A_1 \sim A_0\); נבחר \(a_0 \in A_0 \setminus A_1\). \(A_1\) גם אינסופית, אז קיימת \(A_2 \subsetneq A_1\) עם \(A_2 \sim A_1\); נבחר \(a_1 \in A_1 \setminus A_2\). וכך הלאה. נקבל \(\{a_0, a_1, a_2, \ldots\} \subseteq A\) כסדרה אינסופית של איברים שונים — מציבה bijection \(\mathbb{N} \to \{a_0, a_1, \ldots\}\).
המשמעות
\(\mathbb{N}\) הוא ה-"אינסוף הקטן ביותר": כל קבוצה אינסופית מכילה עותק של \(\mathbb{N}\). אין דבר שהוא "קצת יותר אינסופי מסופי אבל פחות מ-\(\mathbb{N}\)".
3. אינדוקציה - עקרון, תבנית, אינדוקציה חזקה
עקרון האינדוקציה
יהי \(P(n)\) פרדיקט (תכונה) של מספרים טבעיים. אם:
- בסיס: \(P(0)\) מתקיים.
- צעד: לכל \(n \in \mathbb{N}\), אם \(P(n)\) אז \(P(n+1)\).
אזי \(P(n)\) מתקיים לכל \(n \in \mathbb{N}\).
תבנית הוכחה - שלושה שלבים
- הצהרה: "נוכיח באינדוקציה על \(n\) ש-\(P(n)\) מתקיים לכל \(n \in \mathbb{N}\)" (הגדרה מדויקת של \(P(n)\)).
- בסיס: הוכחה ש-\(P(0)\) מתקיים.
- צעד: הנחה \(P(n)\) (הנחת האינדוקציה) ⟹ הוכחה של \(P(n+1)\).
אינדוקציה חזקה
במקום להניח רק \(P(n)\), מותר להניח \(P(m)\) לכל \(m \leq n\). שאר השלבים זהים.
דוגמא: סדרת קבוצות יורדת
יהיו \(A_0 \supseteq A_1 \supseteq A_2 \supseteq \ldots\) (\(A_{n+1} \subseteq A_n\) לכל \(n\)). אזי לכל \(i < j\), \(A_j \subseteq A_{i+1}\).
הוכחה (אינדוקציה על \(k = j - i\)):
- בסיס \(k=1\): \(A_{i+1} \subseteq A_{i+1}\). ✓
- צעד: \(A_{i+k+1} \subseteq A_{i+k} \subseteq A_{i+1}\) (הנחה + יחס יורד). ✓
4. \(\aleph_0\) וקבוצה בת-מניה
הגדרה: \(\aleph_0\)
העוצמה של הטבעיים: \(|\mathbb{N}| = \aleph_0\) (אָלֶף-אֶפֶס).
קבוצה בת-מניה (Countable)
\(A\) בת-מניה אם היא
סופית או
שקולה ל-\(\mathbb{N}\). שקול: \(|A| \leq \aleph_0\).
אינטואיציה: ניתן
לסדר את איברי \(A\) בשורה כך שלפני כל איבר יש מס' סופי של איברים: \(a_0, a_1, a_2, \ldots\)
לא בת-מניה (Uncountable)
אינסופית ולא שקולה ל-\(\mathbb{N}\). דוגמאות (בהרצאה הבאה): \(\mathbb{R}\), \(P(\mathbb{N})\).
סימון
\(A = \{a_n \mid n \in \mathbb{N}\}\) — סימון לקבוצה בת-מניה. ה-\(a_n\) לא חייבים להיות שונים, ולא חייבים לכסות את כל \(\mathbb{N}\) (פונקציה חלקית מותרת).
דוגמאות
- \(\emptyset\) בת-מניה (\(|\emptyset| = 0\)).
- \(\{3, 4\}\) בת-מניה (\(|\{3,4\}| = 2\)).
- \(\mathbb{N}\) בת-מניה (\(\aleph_0\)).
- \(\mathbb{Z}\) בת-מניה (\(\aleph_0\), הוכח בהרצאה 2).
- \(\mathbb{Q}\) בת-מניה (יוכח בהמשך).
- \(\mathbb{R}\)? \(P(\mathbb{N})\)? לא בנות-מניה (יוכח בהרצאה 4).
5. אינדוקציה בקבוצות בנות-מניה
בכל קבוצה בת-מניה ניתן להפעיל אינדוקציה על הסידור \(A = \{a_n \mid n \in \mathbb{N}\}\): מוכיחים את התכונה לאיבר ה-0 (בסיס) ואת הצעד מ-\(a_n\) ל-\(a_{n+1}\).
מה אינדוקציה כן מוכיחה
- תכונות של איחוד סופי או מכפלה סופית של קבוצות (\(k\) סופי, גדל מ-\(k\) ל-\(k+1\)).
- תכונות של איברים בקבוצה בת-מניה.
מה אינדוקציה לא מוכיחה
- טענות על איחוד / מכפלה בני-מניה (אינסופיים) של פעולה. אינדוקציה מוכיחה את התכונה לכל \(k\) סופי, אבל לא ל-"גבול".
- דוגמא: \(\bigcup_{i=0}^{k} \{i\}\) סופית לכל \(k\), אבל \(\bigcup_{i \in \mathbb{N}} \{i\} = \mathbb{N}\) אינסופית!
- טענות על קבוצות שאינן בנות-מניה (אין סידור באמצעות \(\mathbb{N}\)).
6. סגירות מחלקת בנות-המניה תחת פעולות
הגדרה: סגירות לפעולה (Closure)
תהי קבוצה (או מחלקה) \(S\), ופעולה \(op\) על איברי \(S\). \(S\)
סגורה ל-\(op\) אם הפעלת \(op\) על איברי \(S\) מוגדרת תמיד ותוצאתה גם ב-\(S\).
דוגמאות
| קבוצה | פעולה | סגורה? |
|---|
| \(\mathbb{N}\) | \(+\), \(\cdot\) | כן |
| \(\mathbb{N}\) | \(-\), \(/\) | לא (\(5-7\), \(3/2\)) |
| \(\mathbb{R}\) | \(+\), \(\cdot\), \(-\) | כן |
| \(\mathbb{R}\) | \(/\), \(\sqrt{\cdot}\) | לא (\(1/0\), \(\sqrt{-1}\)) |
| קבוצות | \(\cup\) | כן |
| קבוצות | \(\setminus\) (הפרש) | כן |
השאלה המרכזית של ההרצאה: האם מחלקת הקבוצות בנות-המניה סגורה תחת פעולות בסיסיות (איחוד, מכפלה)?
7. איחוד שתי בנות-מניה ואיחוד סופי
משפט: איחוד שתי בנות-מניה
אם \(A\) ו-\(B\) בנות-מניה אז \(A \cup B\) בת-מניה.
A, B בנות-מניה ⟹ קיימות f:ℕ→A, g:ℕ→B על.
נגדיר h:ℕ → A ∪ B:
h(n) = f(n/2) אם n זוגי
h(n) = g((n-1)/2) אם n אי-זוגי
h מוגדרת היטב ועל A∪B (כי f, g שתיהן על) ⟹ |A∪B| ≤ ℵ₀.
אינטואיציה: זיגזג בין שתי הקבוצות — \(a_0, b_0, a_1, b_1, a_2, b_2, \ldots\)
משפט: איחוד סופי
לכל \(k \in \mathbb{N}\), אם \(A_0, \ldots, A_{k-1}\) בנות-מניה אז \(\bigcup_{i=0}^{k-1} A_i\) בת-מניה.
הוכחה (אינדוקציה על \(k\)): בסיס \(k=1\) — \(A_0\) בת-מניה. צעד: \((A_0 \cup \ldots \cup A_k) \cup A_{k+1} = B \cup A_{k+1}\) — איחוד שתי בנות-מניה ⟹ בת-מניה לפי המשפט הקודם.
הוכחה ישירה: \(h(n) = f_{n \bmod k}(\lfloor n/k \rfloor)\) — מחלקת את \(\mathbb{N}\) ל-\(k\) "פסים" שכל אחד ממנה את אחת מ-\(A_i\).
8. איחוד בן-מניה - הוכחת הזיגזג
משפט (חשוב!)
איחוד בן-מניה של בנות-מניה הוא בן-מניה. כלומר, אם \(A_0, A_1, A_2, \ldots\) בנות-מניה, אז \(A = \bigcup_{i \in \mathbb{N}} A_i\) בת-מניה.
שימו לב!
לא ניתן להוכיח באינדוקציה. אינדוקציה עובדת לכל \(k\) סופי, אבל לא ל-"גבול האינסופי". צריך הוכחה
ישירה.
הוכחה אינטואיטיבית - הזיגזג
נסדר את האיברים בטבלה אינסופית, שורה לכל קבוצה \(A_i\):
| \(A_0\): | \(a_{0,0}\) | \(a_{0,1}\) | \(a_{0,2}\) | \(a_{0,3}\) | ... |
| \(A_1\): | \(a_{1,0}\) | \(a_{1,1}\) | \(a_{1,2}\) | \(a_{1,3}\) | ... |
| \(A_2\): | \(a_{2,0}\) | \(a_{2,1}\) | \(a_{2,2}\) | \(a_{2,3}\) | ... |
| \(A_3\): | \(a_{3,0}\) | \(a_{3,1}\) | \(a_{3,2}\) | \(a_{3,3}\) | ... |
נעבור על האיברים באלכסונים סופיים: \(a_{0,0}, a_{0,1}, a_{1,0}, a_{0,2}, a_{1,1}, a_{2,0}, \ldots\) — כל אלכסון סופי, ויש בני-מניה אלכסונים, ולכן נמנה את כל האיברים.
הוכחה פורמלית - Cantor pairing
נגדיר ביייקציה \(g: \{\langle i,j \rangle \mid i,j \in \mathbb{N}\} \to \mathbb{N}\):
\(g(\langle i, j \rangle) = \dfrac{(i+j)(i+j+1)}{2} + i\)
אזי \(g^{-1}: \mathbb{N} \to \{\langle i,j \rangle\}\) ביייקציה. הפונקציה \(h: \mathbb{N} \to A\) ע"י \(h(n) = a_{g^{-1}(n)}\) — על. ⟹ \(|A| \leq \aleph_0\).
9. מכפלה קרטזית ומכפלה סופית
משפט: \(A \times B\)
אם \(A\) ו-\(B\) בנות-מניה אז \(A \times B\) בת-מניה.
הוכחה: \(A = \{a_i\}\), \(B = \{b_j\}\), אזי \(A \times B = \{\langle a_i, b_j \rangle \mid i,j \in \mathbb{N}\}\). אותה הוכחה כמו לאיחוד הבן-מניה — ביייקציה זיגזג בין \(\{\langle i,j \rangle\}\) ל-\(\mathbb{N}\) נותנת מנייה.
משפט: מכפלה סופית
לכל \(k\), אם \(A_0, \ldots, A_k\) בנות-מניה אז \(A_0 \times \ldots \times A_k\) בת-מניה.
הוכחה (אינדוקציה על \(k\)): \((A_0 \times \ldots \times A_k) \times A_{k+1} = B \times A_{k+1}\) — מכפלה של שתי בנות-מניה ⟹ בת-מניה.
אזהרה!
מכפלה
בת-מניה של בנות-מניה
לא בהכרח בת-מניה. דוגמא נגדית: \(\{0,1\}^{\mathbb{N}}\) שקולה ל-\((0,1]\) שאינה בת-מניה (תוכיחו בהרצאה הבאה).
10. הרציונליים \(\mathbb{Q}\) בני-מניה
משפט
\(\mathbb{Q}\) בת-מניה.
הוכחה 1 - איחוד בן-מניה של בנות-מניה
לכל \(i \in \mathbb{N}\): \(A_i = \{i / z \mid z \in \mathbb{Z} \setminus \{0\}\}\) — שקולה ל-\(\mathbb{Z} \setminus \{0\}\), ולכן בת-מניה.
\(\mathbb{Q} = \bigcup_{i \in \mathbb{N}} A_i\) — איחוד בן-מניה של בנות-מניה ⟹ בת-מניה.
הוכחה 2 - דרך מכפלה
\(\mathbb{Z} \times (\mathbb{Z} \setminus \{0\})\) — מכפלת בנות-מניה ⟹ בת-מניה.
נגדיר \(f: \mathbb{Z} \times (\mathbb{Z} \setminus \{0\}) \to \mathbb{Q}\) ע"י \(f(x, y) = x/y\). \(f\) פונקציה על \(\mathbb{Q}\). ⟹ \(|\mathbb{Q}| \leq |\mathbb{Z} \times \mathbb{Z}| \leq \aleph_0\).
11. סיכום ההרצאה
\(\mathbb{N}\) הקטן ביותר
→
אינדוקציה
→
\(\aleph_0\) וקבוצה בת-מניה
→
סגירות לפעולות
→
\(\mathbb{Q}\) בת-מניה
נקודות מפתח
- \(|\mathbb{N}| = \aleph_0\) — האינסוף הקטן ביותר. כל קבוצה אינסופית מקיימת \(\aleph_0 \leq |A|\).
- \(A\) בת-מניה אמ"מ סופית או שקולה ל-\(\mathbb{N}\), כלומר \(|A| \leq \aleph_0\). סימון: \(A = \{a_n \mid n \in \mathbb{N}\}\).
- אינדוקציה: בסיס + צעד \(P(n) \Rightarrow P(n+1)\). אינדוקציה חזקה: מותר להניח \(P(m)\) לכל \(m \leq n\).
- אינדוקציה תופסת רק תכונות של איברים סופיים — לא של פעולה אינסופית.
- מחלקת בנות-המניה סגורה תחת:
- איחוד שתי / סופי / בן-מניה של בנות-מניה (זיגזג!).
- מכפלה קרטזית של שתי / מכפלה סופית של בנות-מניה.
- מכפלה בת-מניה של בנות-מניה — לא בהכרח בת-מניה!
- \(\mathbb{Z}, \mathbb{Q}, \mathbb{N}^k, \mathbb{Q}^k\) כולן בנות-מניה.
לפני הבא
בהרצאה 4: יש קבוצות אינסופיות גדולות יותר מ-\(\mathbb{N}\). \(P(\mathbb{N})\) ו-\(\mathbb{R}\) אינן בנות-מניה. אלכסון קנטור.