Twierdzenie Cantora-Bernsteina-Schrödera

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj
Ujednoznacznienie Ten artykuł dotyczy twierdzenia o zbiorach równolicznych. Zobacz też: inne twierdzenia noszące nazwisko Cantora.

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[edytuj | edytuj kod]

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 I[edytuj | edytuj kod]

Udowodnimy najpierw następujący lemat.

Lemat[edytuj | edytuj kod]

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: A \longrightarrow  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,\ldots. Połóżmy Z=\bigcup\limits_{n=0}^\infty Z_n \subseteq B i zdefiniujmy funkcję g: A \longrightarrow B w następujący sposób:

g(x) = \left\{\begin{array}{ll}f(x) &{\rm dla}\ x\in A\setminus Z \\ x &{\rm 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óżnowarościowa.

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

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

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

Wykazaliśmy zatem prawdziwość lematu.

Dowód twierdzenia[edytuj | edytuj kod]

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:X\longrightarrow Y oraz g:Y\longrightarrow 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 II (Banach, Tarski)[edytuj | edytuj kod]

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

Definicja[edytuj | edytuj kod]

Niech będą dane zbiory X, Y. Powiemy, że funkcja \varphi\colon 2^X \rightarrow 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)[edytuj | edytuj kod]

Niech X będzie zbiorem oraz niech \varphi\colon 2^X \rightarrow 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[edytuj | edytuj kod]

Niech będą dane zbiory X, Y i funkcje f: X \rightarrow Y, g: Y \rightarrow 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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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.

Przypisy

  1. Skupień, Zdzisław: Prosty dowód twierdzenia Cantora-Bernsteina, "Roczniki Polskiego Towarzystwa Matematycznego seria II: Wiadomości Matematyczne" XXXV (1999), strony 49-53. pdf
  2. Skupień, Zdzisław: Twierdzenie Cantora-Bernsteina — dowody znane-nieznane, "Roczniki Polskiego Towarzystwa Matematycznego seria II: Wiadomości Matematyczne" XXXIX (2003), strony 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), strony 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), strony 191-198.