Twierdzenie Cantora-Bernsteina-Schrödera

Z Wikipedii

Masz nowe wiadomości (różnica z poprzednią wersją).

Twierdzenie Cantora-Bernsteina-Schrödera to twierdzenie teorii mnogości, głoszące, że jeśli zbiór A jest równoliczny z pewnym podzbiorem zbioru B oraz zbiór B jest równoliczny z pewnym podzbiorem zbioru A, to zbiory A i B są równoliczne.

Można ten fakt zapisać za pomocą wzoru: jeśli $|A| \leq |B| \and |B| \leq |A| \Rightarrow |B|=|A|$ . Zatem twierdzenie to wyraża słabą antysymetrię relacji porządku na liczbach kardynalnych.

[edytuj] Dowód

Należy pokazać że jeśli $C\subset{B}\subset{A}$ oraz $\,\ |A|=|C|$ to $\,\ |A|=|B|$
Zbiór A jest równoliczny z C więc istnieje bijekcja $f: A \rightarrow {C}$ Dowód twierdzenia polega na skonstruowaniu bijekcji ze zbioru A na B.
Zdefiniujmy rekurencyjnie ciąg zbiorów:
$Z_0=B-C \,\ Z_{n+1}=f(Z_n)$
Łatwo zauważyć że $\bigwedge_{n\in N} Z_n\subset{B}$ oraz $B-C\subset{B}$ .
Niech: $Z=\bigcup_{n\in N} Z_n \subset{B}$
Zdefiniujmy teraz funkcję g w następujący sposób:
$\,\ g(x) = f(x)$ dla $x\not\in Z \and g(x)=x$ dla $x\in Z$
Oczywiście $g: A \rightarrow {B}$ Wystarczy dowieść, że funkcja wyżej określona jest bijekcją na zbiorze B.
Pokażmy najpierw że g jest różnowartościowa. Rozważmy w tym celu 4 przypadki:
W każdym przypadku zakładamy że i dowodzimy że
1. $x_1, x_2\in Z \Rightarrow g(x_1)=x_1\not =x_2=g(x_2)$
2. $x_1, x_2\not \in Z \Rightarrow g(x_1)=f(x_1)\not =f(x_2)=g(x_2)$ , co wynika zróżnowartościowości funkcji f.
3. $x_1\in Z, x_2\not \in Z \Rightarrow g(x_1)=x_1\ \and g(x_2)=f(x_2)$
  Przypuśćmy nie wprost, że $x 1 = f (x 2)$ , wtedy $f(x_2)\in Z \Leftrightarrow f(x_2)\in \bigcup_{n\in N} Z_n\Leftrightarrow \bigvee_{n\in N} f(x_2)\in Z_n$ Jeżeli teraz $n=0 \Rightarrow f(x_2)\in Z_0 \Leftrightarrow f(x_2) \in B-C \Leftrightarrow f(x_2) \in B \and f(x_2)\not\in C$ Jednak funkcja f była bijekcją na zbiór C, a zatem w przypadku gdy n=0 mamy sprzeczność.
  Rozważmy teraz teraz przypadek gdy n>0. Zatem jeżeli: $n>0 \Rightarrow f(x_2) \in Z_n \Leftrightarrow f(x_2) \in f(Z_{n-1}) \Leftrightarrow \bigvee_{z \in Z} f(x_2)=f(z) \Leftrightarrow x_2=z \,\ \and \,\ z \in Z$ Oczywiście jest to sprzeczne z założeniem że $x_2 \not\in Z$ . Zatem uzyskaliśmy sprzeczność i w tym przypadku.
4. $x_1\not \in Z, x_2\in Z$ Oczywiście dowód w tym przypadku jest identyczny jak w (iii).
A zatem z (i)-(iv) wynika że funkcja jest injekcją (jest różnowarościowa).
Ostatnim krokiem dowodu twierdzenia jest pokazanie że funkcja g jest surjekcją (tzn. jest "na" zbiór B). Pokażmy więc, że $\,\ g(A)=B$ . Wiemy że $Z\subset A$ . Mamy zatem:
$\begin{matrix}g(A) & = & g(A-Z \cup Z) & = & g(A-Z)\cup g(Z) & = \\ & = & f(A-Z) \cup Z & = & f(A-Z) \cup Z_0 \cup \bigcup\limits_{n=0}^\infty Z_{n+1} & = \\ & = & f(A-Z) \cup B-C \cup \bigcup\limits_{n=0}^\infty f(Z_{n}) & = & f(A-Z) \cup B-C \cup f(\bigcup\limits_{n=0}^\infty Z_{n}) & = \\ & = & f(A-Z) \cup B-C \cup f(Z) & = & f(A) \cup B-C & = \\ & = & C \cup B-C & = & B & \end{matrix}$
Wykazliśmy zatem że gdy spełnione są założenia twierdzenia, istnieje bijekcja $g: A \rightarrow {B}$ ustalająca równloliczność zbiorów A i B, co kończy dowód.

[edytuj] Przykład zastosowania

Twierdzenie Cantora-Bernsteina pozwala na proste uzasadnienie wielu faktów teorii mocy, co bez tego twierdzenia często pociągało by konieczność przeprowadzania długich i skomplikowanych dowodów. Np. łatwo jest wykazać że dowolny przedział otwarty jest równoliczny ze zbiorem liczb rzeczywistych (równoliczność tę ustala złożenie funkcji liniowej z tangensem). Z twierdzenia Cantora-Bernsteina natychmiastowo otrzymujemy że przedział domknięty również ma moc continuum bo przecież: $(a,b)\subset [a,b]\subset R \,\ gdzie \,\ a<b$