1. Strona główna
  2. Wstęp do Matematyki
  3. 07. Twierdzenie Cantora-Bernsteina

07. Twierdzenie Cantora-Bernsteina

 

Twierdzenie Cantora-Schrodera-Bernsteina
 

1. Porównywanie mocy

Mówimy, że moc zbioru $A$ jest mniejsza lub równa mocy zbioru $B$, ozn. $|A|\leq |B|$, jeśli istnieje funkcja różnowartościowa z $A$ w $B$.

2. Kraty zupełne

Częściowy porządek $\langle P,\leq\rangle$ nazywamy kratą zupełną, jeśli dla każdego niepustego podzbioru $A\subset P$ istnieje najmniejsze ograniczenie górne i najmniejsze ograniczenie dolne.

Theorem 1. Następujące warunki są równoważne dla danego częściowego porządku $\langle P,\leq\rangle$:

  1. $\langle P,\leq\rangle$ jest kratą zupełną,
  2. dla każdego niepustego podzbioru $A\subset P$ istnieje najmniejsze ograniczenie górne,
  3. dla każdego niepustego podzbioru $A\subset P$ istnieje najmniejsze ograniczenie dolne.

Zauważmy, że kraty zupełne muszą mieć element największy i najmniejszy, co wynika z zastosowania definicji kraty do całego zbioru $P$.

Przykłady krat zupełnych.

Definition 1. Niech $\langle P,\leq_P\rangle$, $\langle Q,\leq_Q\rangle$ Odwzorowanie $f:P\to Q$ nazywamy monotonicznym, jeśli dla każdych $a,b\in P$, $a\leq_P b$ zachodzi $f(a)\leq_Q f(b)$.

Przykłady odwzorowań monotonicznych.

Theorem 2. (Knaster-Tarski) Niech $\langle P,\leq\rangle$ będzie kratą zupełną i niech $f:P\to P$ będzie odwzorowaniem monotonicznym. Wtedy istnieje najmniejszy punkt stały $f$, to znaczy element $p_0\in P$ taki, że $f(p_0)=p_0$ oraz jeśli $f(p)=p$, to $p_0\leq p$.

Proof. Niech $X = \{ p\in P: f(p)\leq p\}$. Wtedy $X$ jest zbiorem niepustym, gdyż element największy w $\langle P,\leq\rangle$ należy do $X$. Weźmy $p_0$, najmniejsze ograniczenie dolne zbioru $X$. Wtedy $f(p_0)=p_0$. Istotnie, w przeciwnym razie $f(p_0)>p_0$ lub $f(p_0)<p_0$. W pierwszym przpyadku dla każdego $p\in X$ zachodzi $p_0\leq p$, a zatem $f(p_0)\leq f(p)\leq p$. Wynikałoby z tego, że $f(p_0)$ jest ograniczeniem dolnym zbioru $X$ większym od $p_0$, sprzeczność. W drugim przypadku $f(p_0)<p_0$, a zatem $f(f(p_0))\leq f(p_0)$ z monotoniczności $f$. Wynikałoby z tego, że $f(p_0)\in X$, co jednak byłoby sprzeczne z przypuszczeniem, że $p_0$ jest mniejsze od wszystkich elementów $X$.

Pozostaje zauważyć, że jeśli $p_1$ jest punktem stałym $f$, to $p_1\in X$. Zatem $p_0\leq p_1$, czyli $p_0$ istotnie jest najmniejszym punktem stałym.

3. Lemat Banacha

Theorem 3. (lemat Banacha) Jeśli $f:A\to B$ i $g:B\to A$ to istnieją rozłączne zbiory $A_1,A_2\subset A$ oraz rozłączne zbiory $B_1,B_2\subset B$ takie, że

(1)
\[ A_1\cup A_2 = A,\ B_1\cup B_2 = B,\\ f[A_1] = B_1,\ g[B_2] = A_2. \]

Proof. Dowód tego twierdzenia jest oparty o twierdzenie Knastera-Tarskiego o punkcie stałym. Definiujemy odwozorowanie $\phi:{\mathcal P}(A)\to {\mathcal P}(A)$ zadane wzorem,

(2)
\[\phi(X) = A\setminus g[B\setminus f[X]]. \]

Jeśli $X\subset Y$, to $f[X]\subset f[Y]$. Po przejściu do dopełnień dostajemy $B\setminus f[Y]\subset B\setminus f[X]$ i dalej $g[B\setminus f[Y]]\subset g[B\setminus f[X]]$. Zatem po ponownym przejściu do dopełnień dostajemy $A\setminus g[B\setminus f[X]]\subset A\setminus g[B\setminus f[Y]]$, co dowodzi, że $\phi(X)\subset \phi(Y)$, czyli $\phi$ jest odwzorowaniem monotonicznym. Niech $A_1$ będzie (najmniejszym) punktem stałym $\phi$, $A_2=A\setminus A_1$ i niech $B_1 = f[A_1]$, $B_2=B\setminus f[A_1]$. Wtedy $\phi(A_1)=A_1$, to znaczy

(3)
\[A_1 = A\setminus g[B\setminus f[A_1]] = A\setminus g[B_2]. \]

Z powyższej równości wynika, że $g[B_2]=A\setminus A_1 = A_2$.

4. Twierdzenie Cantora-Bernsteina

Theorem 4. Jeśli $|A|\leq |B|$ oraz $|A|\leq |B|$ to $|A|=|B|$.

Proof. Niech $f:A\to B$ i $g:B\to A$ będą funkcjami różnowartościowymi. Z lematu Banacha wynika istnienie zbiorów $A_1,A_2,B_1,B_2$ takich, że $A_1\cup A_2 = A$, $B_1\cup B_2 = B$, $f[A_1] = B_1$, $g[B_2] = A_2$. Bijekcję $h:A\to B$ definiujemy wzorem

(4)
\[ h(x) = \begin{cases} f(x) & \quad \text{jeśli } x\in A_1,\\ g^{-1}(x) & \quad \text{jeśli } x\in A_2.\\ \end{cases} \]
Created with Madoko.net.