Тема 8

Сравняване на множества по мощност. Теорема на Кантор-Шрьодер-Бернщайн

Сравняване на мощности

Дефиниция: Казваме, че мощността на $A$ не надминава мощността на $B$, ако съществува инекция $f : A \to B$.

(1)

\begin{align} \bar{\bar A} \le \bar{\bar B} \leftrightharpoons \exists f : A \to B \And f \mbox{ inective} \end{align}

Пак обърнете внимание, че само по себе си записа $\bar{\bar A}$ не означава нищо (поне за сега). Т.е още не сме дефинирали какво точно е мощност, но чрез дадените дефиниции можем да заключаваме кога 2 множества са равни по мощност и кога мощността на едното не надминава мощността на другото.

Теорема(на Кантор-Шрьодер-Берщрайн):

(2)

\begin{align} \bar{\bar A} \le \bar{\bar B} \And \bar{\bar B} \le \bar{\bar A} \Rightarrow \bar{\bar A} = \bar{\bar B} \end{align}

Доказателство: На пръв поглед може да изглежда супер очевидно - но ако пробвате да го докажете използвайки само теоремите и аксиомите до сега много ще се озорите.
Ще направим едно от най-елегантните доказателства на това твърдение, с използването на лемата на Тарски за неподвижна точка.
Нека $f: A \to B \And g : B \to A$ са инекции.
Нека $F : \mathcal{P}(A) \to \mathcal{P}(A)$ е изображение:

(3)

\begin{align} F(X) = A \setminus g[B \setminus f[X]] \quad \forall X \in \mathcal{P}(A) \end{align}

Ще докажем, че $F$ е монотонна. Нека $x_1 \subseteq x_2 \subseteq A$

(4)

\begin{align} \begin{array}{rcccl} x_1 &\subseteq& x_2 &\subseteq& A \\ f[x_1] &\subseteq& f[x_2] &\subseteq& B\\ B \setminus f[x_2] &\subseteq& B \setminus f[x_1] &\subseteq& B\\ g[B\setminus f[x_2]] &\subseteq& g[B\setminus f[x_1]] &\subseteq& A \\ A \setminus g[B \setminus f[x_1]] &\subseteq& A\setminus g[B \setminus f[x_2]] \\ F(x_1) &\subseteq& F(x_2) \\ \end{align}

Така получихме, че $F$ е монотонна. Според лемата на Тарски съществува неподвижна точка $X \subseteq A : \quad F(X) = X$.
Нека $X_0$ е една такава неподвижна точка. Тогава:

(5)

\begin{eqnarray} & & X_0 = A \setminus g[ B \setminus f[X_0]] \\ &\Rightarrow& A \setminus X_0 = g[ B \setminus f[X_0]] \end{eqnarray}

Да дефинираме изображението $h = (f \upharpoonright X_0) \cup (g^{-1}(A \setminus X_0))$.
Лесно се проверява, че това е функция, инективна и сюрективна. С това теоремата е доказана.

Свойство: $\bar{\bar A} \le \overline{\overline{A_1}} \And \bar{\bar B} \le \overline{\overline{B_1}} \And A \cap B = \varnothing \And A_1 \cap B_1 = \varnothing \Rightarrow \overline{\overline{A \cup B}} \le \overline{\overline{A_1 \cup B_1}}$

Дефиниция: 2 функции $f$ и $g$ се наричат съвместими, ако $h = f \cup g$ също е функция.

Твърдение: $f, g$ са съвместими, т.с.т.к. $f \upharpoonright (\mathrm{Dom}f \cap \mathrm{Dom}g) = g \upharpoonright (\mathrm{Dom}f \cap \mathrm{Dom}g)$

Твърдение: Нека $F$ e множество от функции, всеки 2 от които са съвместими. Тогава $\cup F$ е функция : $\mathrm{Dom}(\cup F) = \cup \{ \mathrm{Dom}(f) | f \in F \}$

Дефиниция: $\bar{\bar A} < \bar{\bar B} \leftrightharpoons \bar{\bar A} \le \bar{\bar B} \And \bar{\bar A} \ne \bar{\bar B}$

Теорема(на Кантор): $\bar{\bar A} < \overline{\overline{\mathcal{P}(A)}}$

Доказателство: Да допуснем, че има сюрекция $f : A \to \mathcal{P}(A)$.
Да си образуваме множеството $B_0 = \{ x | x \in A \And x \notin f(x) \}$.
Тъй като $f$ е сюрекция, то за $B_0 \subseteq A \quad \exists x_0 : (x_0 \in A \And f(x_0) = B_0)$.

1. $x_0 \in B_0 \Rightarrow x_0 \in f(x_0) \Rightarrow x_0 \notin B_0$
2. $x_0 \notin B_0 \Rightarrow x_0 \notin f(x_0) \Rightarrow x_0 \in B_0$

Противоречие и в 2^та случая с което теоремата е доказана.

Твърдение: $A \neq \varnothing \Rightarrow \lnot \exists B : \forall x(x \in B \And \bar{\bar x} = \bar{\bar A} )$

Доказателство: Допускаме, че съществува такова $B$. Нека си вземем едно такова и го кръстим $B_0$.
Построяваме $B' = \{ x | x \in B_0 \And \exists a (x = A \times \{ a \} \}$.
Сега образуваме $\mathrm{Rng}(\cup B')$. Лесно се проверява, че това е множество на всички множества. Противоречие!

Твърдение: $\lnot \exists M : \forall x \exists ! y (y \in M \And \bar{\bar x} = \bar{\bar y} )$ т.е няма множество, в което да влиза по един представител от всеки клас на еквивалентност спрямо релацията 'равномощност'.

Доказателство: Доказва се $\forall a (\bar{\bar a} \le \overline{\overline{\cup M}})$. Т.е мощността на обединението на това множество е горна граница на мощностите на всички множества (което разбира се е противоречие, защото от всяка мощност може да се намери по-голяма чрез степеннуване ($\mathcal P$)).