יחידה 11: לכסון¶

משפט קנטור¶

העיקרון הכללי¶

משפט קנטור (כללי)

לכל קבוצה $A$: $|A| < |\mathcal{P}(A)|$

במילים: קבוצת החזקה תמיד גדולה יותר מהקבוצה המקורית.

הוכחה:

$|A| \leq |\mathcal{P}(A)|$: הפונקציה $f: A \to \mathcal{P}(A)$, $f(a) = \{a\}$ היא חח"ע.

$|A| \neq |\mathcal{P}(A)|$: נניח בשלילה שקיים זיווג $g: A \to \mathcal{P}(A)$.

נגדיר $D = \{x \in A \mid x \notin g(x)\}$.

$D \in \mathcal{P}(A)$, לכן מ-$g$ על קיים $d \in A$ כך ש-$g(d) = D$.

האם $d \in D$? - אם $d \in D$ אז לפי הגדרת $D$: $d \notin g(d) = D$. סתירה! - אם $d \notin D$ אז לפי הגדרת $D$: $d \in g(d) = D$. סתירה!

לכן אין זיווג, ו-$|A| < |\mathcal{P}(A)|$. ∎

טכניקת הלכסון (Diagonalization)¶

העיקרון¶

טכניקת הלכסון

נניח בשלילה שקיים זיווג $F: \mathbb{N} \to A$ (כאשר $A \subseteq \mathbb{N} \to X$).

נבנה $h \in A$ כך ש-$h$ שונה מכל שורה ב"מטריצה" של $F$:

$h(0) \neq F(0)(0)$
$h(1) \neq F(1)(1)$
$h(n) \neq F(n)(n)$ לכל $n$

אז $h \in A$ אבל $h \notin \text{Im}(F)$ - סתירה להנחה ש-$F$ על.

ייצוג כמטריצה¶

        0    1    2    3    4    ...
F(0): [ a₀₀  a₀₁  a₀₂  a₀₃  a₀₄  ... ]
F(1): [ a₁₀  a₁₁  a₁₂  a₁₃  a₁₄  ... ]
F(2): [ a₂₀  a₂₁  a₂₂  a₂₃  a₂₄  ... ]
F(3): [ a₃₀  a₃₁  a₃₂  a₃₃  a₃₄  ... ]
...

h:    [ ≠a₀₀ ≠a₁₁ ≠a₂₂ ≠a₃₃ ≠a₄₄ ... ]

$h$ נבנה מהאלכסון, ושונה ממנו בכל מקום!

דוגמאות לשימוש בלכסון¶

דוגמה 1: $|\mathbb{N} \to \{0,1\}| \neq \aleph_0$¶

הוכחה: קבוצת הסדרות הבינאריות אינה בת-מניה

נניח בשלילה שקיים זיווג $F: \mathbb{N} \to (\mathbb{N} \to \{0,1\})$.

נגדיר: $$h = \lambda n \in \mathbb{N}. 1 - F(n)(n)$$

$h \in \mathbb{N} \to \{0,1\}$: אם $F(n)(n) = 0$ אז $h(n) = 1$, ואם $F(n)(n) = 1$ אז $h(n) = 0$.

$h \notin \text{Im}(F)$: נניח בשלילה שקיים $n$ כך ש-$F(n) = h$. אז: $F(n)(n) = h(n) = 1 - F(n)(n)$ - סתירה!

לכן $|\mathbb{N} \to \{0,1\}| \neq \aleph_0$.

דוגמה 2: הפונקציות החח"ע אינן בנות-מניה¶

הוכחה: קבוצת הפונקציות החח\"ע מ-$\mathbb{N}$ ל-$\mathbb{N}$ אינה בת-מניה

יהי $A = \{f \in \mathbb{N} \to \mathbb{N} \mid f \text{ חח"ע}\}$.

נניח בשלילה שקיים זיווג $F: \mathbb{N} \to A$. נגדיר: $$g = \lambda n \in \mathbb{N}. \sum_{i=0}^{n} F(i)(i) + n + 1$$

$g$ חח"ע: לכל $n_1 \neq n_2$, נניח $n_1 > n_2$: $$g(n_2) = \sum_{i=0}^{n_2} F(i)(i) + n_2 + 1 \leq \sum_{i=0}^{n_1} F(i)(i) + n_2 + 1 < g(n_1)$$

סתירה: מ-$F$ על, קיים $n$ כך ש-$F(n) = g$, אבל: $$g(n) = \sum_{i=0}^{n} F(i)(i) + n + 1 \geq F(n)(n) + 1 > F(n)(n) = g(n)$$ סתירה!

מסקנות¶

מסקנה: $\mathbb{R}$ אינה בת-מניה

\[|\mathbb{R}| = |\mathcal{P}(\mathbb{N})| = |\mathbb{N} \to \{0,1\}| > |\mathbb{N}| = \aleph_0\]

מסקנה: קיימות אינסוף עוצמות

\[|\mathbb{N}| < |\mathcal{P}(\mathbb{N})| < |\mathcal{P}(\mathcal{P}(\mathbb{N}))| < \ldots\]

שגיאות נפוצות¶

שגיאה 1: לשכוח להוכיח $h \in A$

בהוכחת לכסון, לא מספיק להגדיר $h$ - צריך להוכיח שהיא אכן איבר בקבוצה $A$!

שגיאה 2: בניית $h$ שלא מהאלכסון

$h$ חייב להיות שונה מ-$F(n)$ במקום ה-$n$ (באלכסון). לא מספיק שהוא שונה באיזשהו מקום.

תרגילים¶

תרגיל 1

הוכיחו בשיטת הלכסון שקבוצת הפונקציות העולות ממש $f: \mathbb{N} \to \mathbb{N}$ אינה בת-מניה.

תרגיל 2

הוכיחו: $|\mathbb{N} \to \mathbb{N}| = |\mathcal{P}(\mathbb{N})|$

תרגיל 3

תהי $A$ קבוצה אינסופית. הוכיחו: אין פונקציה על מ-$A$ ל-$\mathcal{P}(A)$.

מקורות¶

מקורות היחידה

ספר הקורס: פרק ג.3 - לכסון
תרגול 11 - לכסון