Twierdzenie Cantora-Bernsteina-Schrödera

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

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

Jeśli oraz to

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 był 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].

Dowód 1

Udowodnijmy najpierw następujący lemat.

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:

Łatwo zauważyć, że dla wszystkich Połóżmy i zdefiniujmy funkcję w następujący sposób:

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
(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

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:

Wykazaliśmy zatem prawdziwość lematu.

Dowód twierdzenia

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.

Dowód 2 (Banach, Tarski)

Poniżej rodzina wszystkich podzbiorów zbioru jest oznaczana przez

Definicja

Niech będą dane zbiory Powiemy, że funkcja jest monotoniczna, jeśli dla każdych zbiorów takich że zachodzi

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

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

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

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

Lemat B

Niech będą dane zbiory X, Y i funkcje Wówczas odwzorowanie dane wzorem

jest monotoniczne.

Dowód lematu

Niech Wówczas więc i Zatem:

Czyli z definicji funkcji

Dowód twierdzenia

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:

Wówczas na mocy lematu B jest to funkcja monotoniczna, a zatem z lematu A wynika istnienie zbioru takiego że co zachodzi gdy Czyli:

Ponieważ jest iniekcją, możemy zdefiniować funkcję w następujący sposób:

Funkcja jest suriekcją. Istotnie,

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.

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ż: gdzie

Przypisy

  1. Skupień, Zdzisław: Prosty dowód twierdzenia Cantora-Bernsteina, „Roczniki Polskiego Towarzystwa Matematycznego. Seria II: Wiadomości Matematyczne” XXXV (1999), s. 49–53. pdf.
  2. Skupień, Zdzisław: Twierdzenie Cantora-Bernsteina – dowody znane-nieznane, „Roczniki Polskiego Towarzystwa Matematycznego,.. Seria II: Wiadomości Matematyczne” XXXIX (2003), s. 85–94. pdf.
  3. 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.
  4. Mańka, R; Wojciechowska, Agnieszka: O dwóch twierdzeniach Cantora, „Roczniki Polskiego Towarzystwa Matematycznego. Seria II: Wiadomości Matematyczne” XXV (1984), s. 191–198.