Тема 9

Теорема на Кантор за Степенно множество. Крайно и безкрайно. Изброими множества

---

страницата се нуждае от дописване/преглеждане

---

приемаме че знаем какво е естествено число - евентуално ще допълним после

Изброими множества

Дефиниция: $\omega = \{ 0, 1, 2, \cdots \}$ - множеството на естесвените числа.
Дефиниция: $A$ е крайно $\leftrightharpoons (\exists n \in \omega)(\bar{\bar A} = \overline{\overline{\{ 0, 1, \cdots n-1 \}}})$
Дефиниция: $A$ е най-много изброимо $\leftrightharpoons A$ е крайно или $A$ е изброимо.
Дефиниция: $A$ е безкрайно $\leftrightharpoons A$ не е крайно.

Твърдение: Ако $A$ е безкрайно, то съществува $A_1 \subseteq A$ такова, че $A_1$ крайно.
Доказателство: ще използваме аксиомата за избор (май)
$A$ е безкрайно, тогава съществува поне един елемент $a_0 \in A$.
Доп. че $A \setminus \{ a_0 \} = \varnothing$. Тогава излиза, че $A$ е крайно. От тук $\exists a_1 \in A \setminus \{ a_0 \}$

Нека за някое естествено число $a_0, a_1, \cdots a_n$ са 2 по 2 различни елементи от $A$. Да разгледаме множеството $A \setminus \{ a_0, a_1, \cdots, a_n \}$.

• то не е празно, иначе излиза, че $A$ е крайно.
• $\exists a_{n+1} \in A \setminus \{ a_0, a_1, \cdots, a_n \} \And a_{n+1} \ne a_i \quad i = \overline{1,n}$

По индукция получаваме редицата $a_0, a_1, \cdots, a_n, \cdots$.
Дефинираме функцията $f : \omega \to A : f(n) = a_n$. $\mathrm{Dom} f = \omega \quad \mathrm{Rng} f \subseteq A$ и $f$ е инекция.
Т.е доказахме, че във всяко безкрайно множество се влага изброимо.

Крайните множества притежават някой свойства:

• $\bar{\bar A} = \bar{\bar B} \iff$ иамт равен брой елементи
• $A \subseteq B \And A \ne B \Rightarrow \bar{\bar A} \ne \bar{\bar B}$

При естествените числа не е точно така:

• $\omega \times \omega \sim \omega$ - доказва се като се номерират елементите на правоъгълна таблица със размери безкрайност:

По индукция се доказва и

(1)

\begin{align} \bigcup_{n\in\omega} \omega^n \sim \omega \end{align}

Следствие: Нека $\forall n \in \omega$ $A_n$ е най-много изброимо. Тогава $\underset{n \in \omega}\bigcup A_n$ е най-много изброимо. Ако съществува $n : A_n$ изброимо, тогава и $\underset{n \in \omega }\bigcup A_n$ е изброимо.

Твърдение: Нека $J$ е множество от отворени интервали от реални числа. Нека $j_1 \ne j_2 \in J \Rightarrow j_1 \cap j_2 = \varnothing$. Тогава $J$ е най-много изброимо.

Доказателство: Нека $j \in J$ е произволен и $j = (\alpha, \beta) \quad \alpha< \beta$. Със сигурност в този интервал има поне едно рационално число $r_j : r_j \in \mathbb Q \And r_j \in (\alpha, \beta)$. Дефинираме си функцията $f : J \to \mathbb Q$. Тя е инекция, защото интервалите са непресичащи се. Така получихме, че $\bar{\bar J} \le \bar{\bar {\mathbb Q}}$. Т.е $J$ е или крайно или изброимо.

Твърдение: Нека $M$ е отворено множество във $\mathbb R^2$. Можем да поставим не повече от изброимо много отворени непресичащи се множества в равината.
Доказва се аналогично на горното

Дефиниция: капиталистическо габърче с размер $x$.
Задача: Колко капиталистически габърчета с размер 1 може да се разхвърлят в равнината, така че никой 2 от тях да не се пресичат.
Задача: Колко капиталистически габърчета с произволен реален размер може да се разхвърлят в равнината, така че никой 2 от тях да не се пресичат.
Дефиниция: комунистическо габърче.
Задача: Колко комунистически габърчета може да се разхвърлят в равнината, така че никой 2 от тях да не се пресичат.

Твърдение: Нека $f : I \to \mathbb R$ е монотонна. $I$ е краен/безкраен интервал. Тогава $f$ има изброим брой точки на прекъсване.
Доказателство: Във всяка точка, в която равнината е прекъсната функцията има определен скок, (или - интервал по $y$ в който не е дефинирана). Тъй като тези интервали не се пресичат то има максимум изброимо много - т.е точките на прекъсване са изброимо много.

Твърдение: Нека $A$ е безкрайно и $B$ е най-много изброимо. Тогава $A \cup B \sim A$.
Доказателство: Нека $B_1 = B \setminus A$. Тогава $B_1$ е най-много изброимо. Ако е празно, тогава твърдението е доказано.
Да си изберем изброимо подмножество $A_1 \subseteq A$. Ще дефинираме следната инекция:

(2)

\begin{align} f : A \cup B_1 \to A \quad f(x) = \begin{cases} x & x \in A \setminus A_1\\ a_{2n} & x = a_n\\ a_{2n+1} & x = b_n \end{cases} \end{align}

Можем да го запишем и с формула: $A \cup B \sim (A \setminus A_1) \cup (A_1 \cup B) \sim A \setminus A_1 \cup A_1 \sim A$

Дефиниция: Изброима редица (от тип $\omega$) от елементи на $A$ е функция $f: \omega \to A$.
Дефиниция: Крайна редица от елементи от $A$ е функция $f : \{ 0, 1, \cdots, n-1 \} \to A$.

Изброимите редици от 0 и 1 са ${}^\omega 2 \sim \mathcal{P}(\omega)$.
Доказателство че ${}^\omega 2$ не е изброимо: Диагонален метод на Кантор.

Твърдение: $\mathbb R \sim {}^\omega 2$.
Доказателство: Всяка редица от 0 и 1 отговаря на число в интервала $(0, 1)$ записано във двоична система. Някой числа обаче имат 2 записа:
$0. \cdots 1000\cdots = 0.\cdots0111\cdots$. Числата с 2 записа са еквивалентни на крайна редица от 0 и 1, от където следва че са изброимо много. Т.е прибавянето на изброимо множество не променя мощността (според предното твърдение).

Твърдение: $\mathbb R ^2 \sim \mathbb R$.
Доказателство: Ще докажем равносилното $(0, 1) \times (0, 1) \sim (0, 1)$.
За всеки 2 реални числа $\alpha = 0.\alpha_1\alpha_2\cdots$ и $\beta = 0.\beta_1\beta_2\cdots$ съществува реално число $\gamma = 0.\alpha_1\beta_1\alpha_0\beta_2\cdots$ в интервала $(0, 1)$. T.е $f : (0, 1) \times (0, 1) \to (0, 1) : f(\alpha, \beta) = \gamma$ е инекция (не може да се получи 2 пъти едно число с различно представяне, защото за това трябва и 2те изходни да завършват на 999… а ние изибраме другия запис на всяко такова число).

Твърдение: ${}^{}^C({}^B A) \sim {}^{C \times B}{A}$
Задача: Намерете мощността на всички функции от $\mathbb R$ във $\mathbb R$.
Решение:

(3)

\begin{align} {}^{\mathbb R}{\mathbb R} \sim {}^{({}^\omega 2)}({}^\omega 2) \sim {}^{(\omega \times {}^\omega 2)}2 \sim {}^{{}^\omega 2} 2 \sim {}^{\mathbb R} 2 \sim \mathcal P(\mathbb R) \end{align}

Задача: Колко е мощността на всички непрекъснати функции $f : \mathbb R \to \mathbb R$.
Решение: Нека $f : \mathbb R \to \mathbb R$ и $g : \mathbb R \to \mathbb R$ са непрекъснати.
Ще докажем, че $f \upharpoonright \mathbb Q = g \upharpoonright \mathbb Q \iff f = g$. Т.е ако рестрикциите на 2те функции спрямо $\mathbb Q$ съвпадат, и самите функции съвпадат (все пак да не забравяме че става дума само за непрекъснати функции).
Обратната посока е очевидна (щом 2 функции съвпадат, всяка тяхна рестрикция върху едно и също множество също съвпада).

Нека $x_0 \in \mathbb R$ е произволно. Тогава за всяка редица $r_0, r_1, \cdots, r_n, \cdots$ от рационални числа, такава че $\{ r_n \} \to x_0$ получаваме:

(4)

\begin{align} f(x_0) \overset{\underset{(1)}{}}= \lim_{n\to\infty} f(r_n) \overset{\underset{(2)}{}}= \lim_{n\to\infty} g(r_n) \overset{\underset{(1)}{}}= g(x_0) \end{align}

където (1) е от дефиницията на Хайне за непрекъснатост, а (2) следва от факта, че функциите съвпадат във всички рационални точки, т.е 2те граници са върху еднакви редици, следователно са равни.
С това показахме, че за всяко реално число $x_0 \Rightarrow f(x_0) = g(x_0)$, с което доказахме твърдението.

Сега да си кръстим с $F$ множеството от всички непрекъснати функции $\mathbb R \to \mathbb R$:

(5)

\begin{align} \bar{\bar F} \le \overline{\overline{{}^{\mathbb Q} \mathbb R}} = \overline{\overline{{}^\omega({}^\omega 2)}} = \overline{\overline{{}^{\omega \times \omega} 2}} = \overline{\overline{{}^\omega 2}} = \overline{\overline{\mathbb R}} \end{align}

Освен това, ако за всяко реално число вземем константната фукция, получаваме $\overline{\overline F} \ge \overline{\overline{\mathbb R}}$.
По теоремата на Кантор-Шрьодер-Берщрайн получаваме $\overline{\overline F} = \overline{\overline{\mathbb R}}$.

Твърдение: Мощността на всички редици от реални числа: ${}^\omega \mathbb R \sim {}^\omega ({}^\omega 2) \sim {}^{\omega \times \omega} 2 \sim {}^\omega 2 \sim \mathbb R$
Твърдение: Мощността на всички функции $\mathbb R \to \omega$.

(6)

\begin{eqnarray} \left{}\begin{matrix} \overline{\overline{{}^{\mathbb R} \omega}} \le \overline{\overline{{}^{\mathbb R} \mathbb R}} = \overline{\overline{\mathcal{P} (\mathbb R)}} \\ \overline{\overline{\mathcal{P}(\mathbb R)}} = \overline{\overline{{}^{\mathbb R} 2}} \le \overline{\overline{{}^{\mathbb R} \omega}} \end{matrix}\right\} \Rightarrow {}^{\mathbb R} \omega \sim \mathcal{P}(\mathbb R) \end{eqnarray}