Twierdzenie Cantora-Bernsteina-Schrödera – twierdzenie teorii mnogości głoszące, że jeśli zbiór
jest równoliczny z pewnym podzbiorem zbioru
oraz zbiór
jest równoliczny z pewnym podzbiorem zbioru
to zbiory
i
są równoliczne.
Dla zbiorów
napiszemy, że
ilekroć zbiór
jest równoliczny z pewnym podzbiorem zbioru
Przy tych oznaczeniach możemy wyrazić twierdzenie Cantora-Bernsteina-Schrödera w następujący sposób symboliczny:
- Jeśli
oraz
to ![{\displaystyle |B|=|A|.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8f8e4b95c2b748133a8164fae9a3b3f6f60c044b)
Formułując jeszcze inaczej, twierdzenie to wyraża słabą antysymetrię relacji porządku na liczbach kardynalnych:
- Jeśli
oraz
to ![{\displaystyle \kappa =\lambda .}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c36ba8d7fb7cd845ab82692b970ff160ff8cc9b0)
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[1][2] (zobacz też Jerzy Mioduszewski[3]) oraz artykułu R. Mańki i Agnieszki Wojciechowskiej[4].
Udowodnijmy najpierw następujący lemat.
Jeżeli
oraz
to
.
Dowód lematu:
Przypuśćmy, że
oraz zbiór
jest równoliczny z
Zatem możemy ustalić bijekcję
Naszym celem jest skonstruowanie bijekcji ze zbioru
na
Poniżej obraz zbioru
przez funkcję
jest oznaczany przez
(tak więc
).
Zdefiniujmy rekurencyjnie ciąg zbiorów:
![{\displaystyle Z_{0}=B\setminus C,\quad Z_{n+1}=f[Z_{n}].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ad80d7b63351a7bf405d88dbd92b5e7a6049b31d)
Łatwo zauważyć, że
dla wszystkich
Połóżmy
i zdefiniujmy funkcję
w następujący sposób:
![{\displaystyle g(x)=\left\{{\begin{array}{l}f(x)&\mathrm {dla} \ x\in A\setminus Z\\x&\mathrm {dla} \ x\in Z\end{array}}\right..}](https://wikimedia.org/api/rest_v1/media/math/render/svg/082b07a387437780f7043c56c374628982d1999e)
Powyższa formuła poprawnie definiuje funkcję z
w
i naszym celem jest wykazanie, że jest ona bijekcją (z
na
).
Pokażmy najpierw, że
jest różnowartościowa. W tym celu załóżmy, że
są elementami zbioru
Dowodzimy, że
rozważając 4 przypadki.
- (i) Jeśli
to ![{\displaystyle g(x_{1})=x_{1}\neq x_{2}=g(x_{2}).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/dca551972f5c08f69032c707d4913adec66963e1)
- (ii) Jeśli
to
co wynika z różnowartościowości funkcji f.
- (iii) Przypuśćmy teraz, że
ale
Załóżmy nie wprost, że
Zauważmy, że w aktualnym przypadku mamy
oraz
a więc
Stąd
dla pewnego
Jeżeli teraz
czyli
to
czyli w szczególności
Jednak funkcja
była bijekcją na zbiór
zatem otrzymaliśmy sprzeczność. Rozważmy teraz przypadek, gdy
Wówczas
a zatem dla pewnego
mamy
Ponieważ
jest różnowartościowa, otrzymujemy
a stąd
Oczywiście jest to sprzeczne z założeniem, że
czyli uzyskaliśmy sprzeczność i w tym przypadku.
- (iv) Jeśli
ale
to argumentacja identyczna z przedstawioną w (iii) dowodzi, że ![{\displaystyle g(x_{1})\neq g(x_{2}).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9f8d881680db6ce7c5d5e058e6a81870805faa20)
A zatem z (i)-(iv) wynika, że funkcja
jest różnowartościowa.
Ostatnim krokiem dowodu lematu jest pokazanie, że funkcja
jest suriekcją, czyli że
Wiemy, że
Mamy zatem:
![{\displaystyle {\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/99946f083cfc8dd0d919473cbf3b5c0979c550e9)
Wykazaliśmy zatem prawdziwość lematu.
Aby udowodnić twierdzenie, przypuśćmy, że zbiór
jest równoliczny z pewnym podzbiorem zbioru
oraz zbiór
jest równoliczny z pewnym podzbiorem zbioru
Zatem możemy znaleźć funkcje różnowartościowe
oraz
Połóżmy
oraz
Wówczas zbiory
spełniają założenia lematu, więc możemy wywnioskować, iż zbiory
i
są równoliczne. Ponieważ zbiory
i
są równoliczne (o czym świadczy np. funkcja
), otrzymujemy, że zbiory
i
są równoliczne.
Poniżej rodzina wszystkich podzbiorów zbioru
jest oznaczana przez
Niech będą dane zbiory
Powiemy, że funkcja
jest monotoniczna, jeśli dla każdych zbiorów
takich że
zachodzi
Niech
będzie zbiorem oraz niech
będzie funkcją monotoniczną. Wówczas odwzorowanie
ma taki punkt stały
(to znaczy istnieje
że
).
Dowód lematu
Zdefiniujmy rodzinę zbiorów
Twierdzimy, że suma
![{\displaystyle D=\bigcup _{A\in {\mathcal {D}}}A}](https://wikimedia.org/api/rest_v1/media/math/render/svg/37fc23ddc161312a0e23976cb3c8e96fdc58452e)
jest punktem stałym odwzorowania
Aby się o tym przekonać, zauważmy, iż dla każdego
zachodzi
więc z monotoniczności
wynika, że
Zatem
![{\displaystyle \bigcup _{A\in {\mathcal {D}}}A\subseteq \bigcup _{A\in {\mathcal {D}}}\varphi (A)\subseteq \varphi (D),}](https://wikimedia.org/api/rest_v1/media/math/render/svg/81e34ce5336daef4e9653e633dd497f427f08cbf)
a stąd
Korzystając kolejny raz z monotoniczności, dostajemy
więc
Wobec tego
musi zawierać się w sumie rodziny
czyli
Zachodzą więc obie inkluzje
i
więc
jest punktem stałym odwzorowania
Niech będą dane zbiory X, Y i funkcje
Wówczas odwzorowanie
dane wzorem
![{\displaystyle \varphi (A)=X-g[Y-f[A]]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ae37100a0c41351253d8cc56b9e50d18fd5c5d2e)
jest monotoniczne.
Dowód lematu
Niech
Wówczas
więc
i
Zatem:
![{\displaystyle X-g[Y-f[A]]\subseteq X-g[Y-f[B]].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5c62247aadc49226fb5220b440fd425f2fafb59f)
Czyli z definicji funkcji
Niech X i Y spełniają założenia twierdzenia i niech
oraz
będą funkcjami różnowartościowymi. Zdefiniujmy odwzorowanie
jak w lemacie B:
![{\displaystyle \varphi \colon 2^{X}\to 2^{X}\colon A\mapsto \varphi (A)=X-g[Y-f[A]].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3ddd9d857bc263957373b08d129f7879e087e93a)
Wówczas na mocy lematu B jest to funkcja monotoniczna, a zatem z lematu A wynika istnienie zbioru
takiego że
co zachodzi gdy
Czyli:
![{\displaystyle X-D=g[Y-f[D]].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b53997c6c0488557403ac2b1aadcf110ae7a6591)
Ponieważ
jest iniekcją, możemy zdefiniować funkcję
w następujący sposób:
![{\displaystyle h(x)={\begin{cases}g^{-1}(x)&x\in X-D\\f(x)&x\in D\end{cases}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b47f37f124167d191d7a45dbac3f182c9de984ec)
Funkcja
jest suriekcją. Istotnie,
![{\displaystyle h[X]=h[D]\cup h[X-D]=f[D]\cup (Y-f[D])=Y.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a51306ab8a2ff5d7b473ba6c5534bb4134ba2e34)
Aby wykazać iniektywność
należy wziąć dwa elementy
i
i pokazać, że
(rozpatrywanie innych przypadków jest trywialne ze względu na iniektywność
i
). Pamiętając, że
mamy, iż
Jednocześnie
więc
należą do rozłącznych podzbiorów, zatem nie mogą być równe. W związku z tym
jest bijekcją pomiędzy zbiorami
i
a co za tym idzie, zbiory te są równoliczne.
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ż:
gdzie
- ↑ Skupień, Zdzisław: Prosty dowód twierdzenia Cantora-Bernsteina, „Roczniki Polskiego Towarzystwa Matematycznego. Seria II: Wiadomości Matematyczne” XXXV (1999), s. 49–53. pdf.
- ↑ Skupień, Zdzisław: Twierdzenie Cantora-Bernsteina – dowody znane-nieznane, „Roczniki Polskiego Towarzystwa Matematycznego,.. Seria II: Wiadomości Matematyczne” XXXIX (2003), s. 85–94. pdf.
- ↑ Mioduszewski, Jerzy: Listy do Redakcji. W sprawie artykułu Z. Skupienia, „Roczniki Polskiego Towarzystwa Matematycznego. Seria II: Wiadomości Matematyczne” XXXVII (2001), s. 181–182 pdf.
- ↑ Mańka, R; Wojciechowska, Agnieszka: O dwóch twierdzeniach Cantora, „Roczniki Polskiego Towarzystwa Matematycznego. Seria II: Wiadomości Matematyczne” XXV (1984), s. 191–198.