Twierdzenie Cantora-Bernsteina-Schrödera

Twierdzenie Cantora-Bernsteina-Schrödera – 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.

Dla zbiorów $A,B$ napiszemy, że $|A|\leqslant |B|,$ ilekroć zbiór $A$ jest równoliczny z pewnym podzbiorem zbioru $B.$ Przy tych oznaczeniach możemy wyrazić twierdzenie Cantora-Bernsteina-Schrödera w następujący sposób symboliczny:

Jeśli $|A|\leqslant |B|$ oraz $|B|\leqslant |A|,$ to $|B|=|A|.$

Formułując jeszcze inaczej, twierdzenie to wyraża słabą antysymetrię relacji porządku na liczbach kardynalnych:

Jeśli $\kappa \leqslant \lambda$ oraz $\lambda \leqslant \kappa ,$ to $\kappa =\lambda .$

Historia i źródła

Twierdzenie było sformułowane po raz pierwszy przez Georga Cantora w 1883 i 1895 (bez dowodu). Pierwszy kompletny dowód został podany przez Feliksa Bernsteina w 1897. Inną próbę dowodu przedstawił Ernst Schröder w 1898, zawierała ona jednak lukę. W literaturze matematycznej istnieje szereg różnych dowodów tego twierdzenia, te z początkowego okresu rozwoju teorii mnogości albo wymagały dodatkowych założeń, albo były niepełne albo bardzo skomplikowane. Dla bardziej kompletnej dyskusji historii tego twierdzenia oraz przeglądu różnych dowodów odsyłamy czytelnika do publikacji Zdzisława Skupienia (zobacz też Jerzy Mioduszewski) oraz artykułu R. Mańki i Agnieszki Wojciechowskiej.

Dowód 1

Udowodnijmy najpierw następujący lemat.

Lemat

Jeżeli $C\subseteq B\subseteq A$ oraz $|A|=|C|,$ to $|A|=|B|$.

Dowód lematu:

Przypuśćmy, że $C\subseteq B\subseteq A$ oraz zbiór $A$ jest równoliczny z $C.$ Zatem możemy ustalić bijekcję $f\colon A\to C.$

Naszym celem jest skonstruowanie bijekcji ze zbioru $A$ na $B.$ Poniżej obraz zbioru $X\subseteq A$ przez funkcję $f$ jest oznaczany przez $f[X]$ (tak więc $f[X]=\{f(x):x\in X\}$).

Zdefiniujmy rekurencyjnie ciąg zbiorów:

$Z_{0}=B\setminus C,\quad Z_{n+1}=f[Z_{n}].$

Łatwo zauważyć, że $Z_{n}\subseteq B$ dla wszystkich $n=0,1,2,\dots$ Połóżmy $Z=\bigcup \limits _{n=0}^{\infty }Z_{n}\subseteq B$ i zdefiniujmy funkcję $g\colon A\to B$ w następujący sposób:

$g(x)=\left\{{\begin{array}{l}f(x)&\mathrm {dla} \ x\in A\setminus Z\\x&\mathrm {dla} \ x\in Z\end{array}}\right..$

Powyższa formuła poprawnie definiuje funkcję z $A$ w $B$ i naszym celem jest wykazanie, że jest ona bijekcją (z $A$ na $B$).

Pokażmy najpierw, że $g$ jest różnowartościowa. W tym celu załóżmy, że $x_{1}\neq x_{2}$ są elementami zbioru $A.$ Dowodzimy, że $g(x_{1})\neq g(x_{2}),$ rozważając 4 przypadki.

(i) Jeśli $x_{1},x_{2}\in Z,$ to $g(x_{1})=x_{1}\neq x_{2}=g(x_{2}).$

(ii) Jeśli $x_{1},x_{2}\notin Z,$ to $g(x_{1})=f(x_{1})\neq f(x_{2})=g(x_{2}),$ co wynika z różnowartościowości funkcji f.

(iii) Przypuśćmy teraz, że $x_{1}\in Z,$ ale $x_{2}\notin Z.$ Załóżmy nie wprost, że $g(x_{1})=g(x_{2}).$ Zauważmy, że w aktualnym przypadku mamy $g(x_{1})=x_{1}$ oraz $g(x_{2})=f(x_{2}),$ a więc $f(x_{2})=x_{1}\in Z.$ Stąd $f(x_{2})\in Z_{n}$ dla pewnego $n\in {\mathbb {N} }.$ Jeżeli teraz $n=0,$ czyli $f(x_{2})\in Z_{0},$ to $f(x_{2})\in B\setminus C,$ czyli w szczególności $f(x_{2})\notin C.$ Jednak funkcja $f$ była bijekcją na zbiór $C,$ zatem otrzymaliśmy sprzeczność. Rozważmy teraz przypadek, gdy $n>0.$ Wówczas $f(x_{2})\in Z_{n}=f[Z_{n-1}],$ a zatem dla pewnego $z\in Z_{n-1}$ mamy $f(x_{2})=f(z).$ Ponieważ $f$ jest różnowartościowa, otrzymujemy $x_{2}=z$ a stąd $x_{2}\in Z_{n-1}.$ Oczywiście jest to sprzeczne z założeniem, że $x_{2}\notin Z,$ czyli uzyskaliśmy sprzeczność i w tym przypadku.

(iv) Jeśli $x_{1}\notin Z,$ ale $x_{2}\in Z,$ to argumentacja identyczna z przedstawioną w (iii) dowodzi, że $g(x_{1})\neq g(x_{2}).$

A zatem z (i)-(iv) wynika, że funkcja $g$ jest różnowartościowa.

Ostatnim krokiem dowodu lematu jest pokazanie, że funkcja $g\colon A\to B$ jest suriekcją, czyli że $g[A]=B.$

Wiemy, że $Z\subseteq B\subseteq A.$ Mamy zatem:

${\begin{aligned}g[A]&=g[(A\setminus Z)\cup Z]\\&=g[A\setminus Z]\cup g[Z]\\&=f[A\setminus Z]\cup Z\\&=f[A\setminus Z]\cup Z_{0}\cup \bigcup \limits _{n=0}^{\infty }Z_{n+1}\\&=f[A\setminus Z]\cup (B\setminus C)\cup \bigcup \limits _{n=0}^{\infty }f[Z_{n}]\\&=f[A\setminus Z]\cup (B\setminus C)\cup f{\big [}\bigcup \limits _{n=0}^{\infty }Z_{n}{\big ]}\\&=f[A\setminus Z]\cup (B\setminus C)\cup f[Z]\\&=f[A]\cup (B\setminus C)\\&=C\cup (B\setminus C)\\&=B.\end{aligned}}$

Wykazaliśmy zatem prawdziwość lematu.

Dowód twierdzenia

Aby udowodnić twierdzenie, przypuśćmy, że zbiór $X$ jest równoliczny z pewnym podzbiorem zbioru $Y$ oraz zbiór $Y$ jest równoliczny z pewnym podzbiorem zbioru $X.$ Zatem możemy znaleźć funkcje różnowartościowe $f\colon X\to Y$ oraz $g\colon Y\to X.$ Połóżmy $A=X,\ B=g[Y]$ oraz $C=g{\big [}f[X]{\big ]}.$ Wówczas zbiory $A,B,C$ spełniają założenia lematu, więc możemy wywnioskować, iż zbiory $A=X$ i $B$ są równoliczne. Ponieważ zbiory $B$ i $Y$ są równoliczne (o czym świadczy np. funkcja $g$), otrzymujemy, że zbiory $X$ i $Y$ są równoliczne.

Dowód 2 (Banach, Tarski)

Poniżej rodzina wszystkich podzbiorów zbioru $X$ jest oznaczana przez $2^{X}.$

Definicja

Niech będą dane zbiory $X,Y.$ Powiemy, że funkcja $\varphi \colon 2^{X}\to 2^{Y}$ jest monotoniczna, jeśli dla każdych zbiorów $A,B\in 2^{X},$ takich że $A\subseteq B$ zachodzi $\varphi (A)\subseteq \varphi (B).$

Lemat A (twierdzenie Knastera-Tarskiego o punkcie stałym)

Niech $X$ będzie zbiorem oraz niech $\varphi \colon 2^{X}\to 2^{X}$ będzie funkcją monotoniczną. Wówczas odwzorowanie $\varphi$ ma taki punkt stały $D$ (to znaczy istnieje $D\in 2^{X},$ że $\varphi (D)=D$).

Dowód lematu

Zdefiniujmy rodzinę zbiorów ${\mathcal {D}}=\{A\subseteq X:A\subseteq \varphi (A)\}.$ Twierdzimy, że suma

$D=\bigcup _{A\in {\mathcal {D}}}A$

jest punktem stałym odwzorowania $\varphi .$ Aby się o tym przekonać, zauważmy, iż dla każdego $A\in {\mathcal {D}}$ zachodzi $A\subseteq D,$ więc z monotoniczności $\varphi$ wynika, że $\varphi (A)\subseteq \varphi (D).$ Zatem

$\bigcup _{A\in {\mathcal {D}}}A\subseteq \bigcup _{A\in {\mathcal {D}}}\varphi (A)\subseteq \varphi (D),$

a stąd $D\subseteq \varphi (D).$

Korzystając kolejny raz z monotoniczności, dostajemy $\varphi (D)\subseteq \varphi (\varphi (D)),$ więc $\varphi (D)\in {\mathcal {D}}.$ Wobec tego $\varphi (D)$ musi zawierać się w sumie rodziny ${\mathcal {D}},$ czyli $\varphi (D)\subseteq D.$

Zachodzą więc obie inkluzje $D\subseteq \varphi (D)$ i $\varphi (D)\subseteq D,$ więc $D$ jest punktem stałym odwzorowania $\varphi .$

Lemat B

Niech będą dane zbiory X, Y i funkcje $f\colon X\to Y,$ $g\colon Y\to X.$ Wówczas odwzorowanie $\varphi \colon 2^{X}\to 2^{X}$ dane wzorem

$\varphi (A)=X-g[Y-f[A]]$

jest monotoniczne.

Dowód lematu

Niech $A\subseteq B\subseteq X.$ Wówczas $f[A]\subseteq f[B],$ więc $Y-f[A]\supseteq Y-f[B]$ i $g[Y-f[A]]\supseteq g[Y-f[B]].$ Zatem:

$X-g[Y-f[A]]\subseteq X-g[Y-f[B]].$

Czyli z definicji funkcji $\varphi ,$ $\varphi (A)\subseteq \varphi (B).$

Dowód twierdzenia

Niech X i Y spełniają założenia twierdzenia i niech $f\colon X\to Y$ oraz $g\colon Y\to X$ będą funkcjami różnowartościowymi. Zdefiniujmy odwzorowanie $\varphi$ jak w lemacie B:

$\varphi \colon 2^{X}\to 2^{X}\colon A\mapsto \varphi (A)=X-g[Y-f[A]].$

Wówczas na mocy lematu B jest to funkcja monotoniczna, a zatem z lematu A wynika istnienie zbioru $D,$ takiego że $\varphi (D)=D,$ co zachodzi gdy $D=X-g[Y-f[D]].$ Czyli:

$X-D=g[Y-f[D]].$

Ponieważ $g$ jest iniekcją, możemy zdefiniować funkcję $h\colon X\to Y$ w następujący sposób:

$h(x)={\begin{cases}g^{-1}(x)&x\in X-D\\f(x)&x\in D\end{cases}}$

Funkcja $h$ jest suriekcją. Istotnie,

$h[X]=h[D]\cup h[X-D]=f[D]\cup (Y-f[D])=Y.$

Aby wykazać iniektywność $h,$ należy wziąć dwa elementy $x\in D$ i $y\in X-D$ i pokazać, że $h(x)\neq h(y)$ (rozpatrywanie innych przypadków jest trywialne ze względu na iniektywność $f$ i $g$). Pamiętając, że $X-D=g[Y-f[D]],$ mamy, iż $h(y)\in Y-f(D).$ Jednocześnie $h(x)=f(x)\in f[D],$ więc $h(y),h(x)$ należą do rozłącznych podzbiorów, zatem nie mogą być równe. W związku z tym $h$ jest bijekcją pomiędzy zbiorami $X$ i $Y,$ a co za tym idzie, zbiory te są równoliczne.

Przykład zastosowania

Twierdzenie Cantora-Bernsteina pozwala na proste uzasadnienie wielu faktów teorii mocy, co bez tego twierdzenia często pociągałoby konieczność przeprowadzania długich i skomplikowanych dowodów. Przykładowo ł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.$