Ten wykład poświęcimy dowodowi twierdzenia sformułowanego przez Cantora, którego dowód pochodzi od Feliksa Bernsteina1 i Ernsta Schrödera2 .
Zwyczajowo to twierdzenie zwane jest twierdzeniem Cantora–Bernsteina.
Uwaga 205. Twierdzenie 204 można sformułować także następująco: Dla dowolnych liczb kardynalnych \(\mathfrak {m}\) i \(\mathfrak {n}\), jeśli \(\mathfrak {m}\leq \mathfrak {n}\) i \(\mathfrak {n}\leq \mathfrak {m}\) to \(\mathfrak {m}=\mathfrak {n}\).
Dowód. Zauważmy, że wystarczy wykazać następujący lemat.
Faktycznie, załóżmy, że mamy wykazany powyższy lemat. Weźmy teraz injekcje \(f: A\hookrightarrow B\) i \(h: B \hookrightarrow A\). Zauważmy, że \(h(B)\sim B\) i \(f(A)\sim A\) oraz \(f(A)\sim h(f(A))\), bo \(f\) i \(h\) są injekcjami. Niech
\(\seteqnumber{0}{11.}{0}\)\begin{gather*} Z:=A,\\ Y:=h(B),\\ X:=h(f(A)). \end{gather*} Wtedy, jak łatwo zauważyć,
\[X\subset Y\subset Z\]
(bo \(h(f(A))\subset h(B)\subset A\)). Zauważmy też, że
\[Z=A\sim f(A)\sim h(f(A))=X.\]
Wówczas, z lematu wynika, że
\[Y\sim Z\]
czyli
\[h(B)\sim A\]
a więc też
\[B\sim A\]
a zatem istnieje bijekcja z \(A\) w \(B\).
Pozostaje więc wykazać Lemat 206. Ponieważ \(\# Z=\# X \) to istnieje bijekcja \(f: Z\bij X\). Zdefiniujmy rekurencyjnie ciąg zbiorów:
\[W_0=Y\setminus X,\ W_{n+1}=f(W_n).\]
Zauważmy, że dla dowolnego \(n\in \N \) mamy \(W_n\subset Y\), dla \(W_0\) jest to oczywiste, dla \(W_n\), \(n>0\) wynika z faktu, że \(f\) prowadzi do \(X\subset Y\). Zdefiniujmy zbiór \(W\subset Y\) jako
\[W:=\bigcup _{n=0}^{\infty }W_n.\]
Zdefiniujmy odwzorowanie \(g: Z\to Y\) wzorem
\[g(x)=\begin {cases} f(x), \ \ x\in Z\setminus W\\ x,\ \ x\in W. \end {cases} \]
Sprawdzimy teraz, że:
1. \(g\) jest injekcją. Weźmy \(x_1, x_2\in Z, x_1\neq x_2.\) Mamy następujące możliwości:
\(\bullet \) \(x_1,x_2\in W\). Wtedy \(g(x_1)=x_1\neq x_2= g(x_2)\).
\(\bullet \) \(x_1,x_2\notin W\). Wtedy \(g(x_1)=f(x_1)\) i \(g(x_2)=f(x_2)\), ale \(f\) jest injekcją, zatem dla \(x_1\neq x_2\) mamy \(f(x_1)\neq f(x_2)\) czyli też \(g(x_1)\neq g(x_2).\)
\(\bullet \) \(x_1\in W\), \(x_2\notin W\). Przypuśćmy, że w tym przypadku \(g(x_1)=g(x_2)\), czyli, z definicji \(g\), \(x_1=f(x_2)\). Skoro \(x_1\in W\) to \(f(x_2)\in W\), zatem istnieje \(n\in \N \) takie, że \(f(x_2)\in W_n\). Jeśli \(f(x_2)\in W_0\), to \(f(x_2)\in Y\setminus X\), czyli \(f(x_2)\notin X\), co daje sprzeczność, bo funkcja \(f\) prowadzi w \(X\). Musi zatem być \(f(x_2)\in W_n\) dla pewnego \(n\geq 1\). Skoro \(f(x_2)\in W_n\) to \(f(x_2)\in f(W_{n-1})\), z definicji obrazu wynika zatem, że istnieje \(w\in W_{n-1}\) takie, że \(f(x_2)=f(w)\), a skoro \(f\) jest injekcją, to \(x_2=w\in W_{n-1}\), ale to oznacza, że \(x_2\in W\), co jest jest sprzeczne z naszym założeniem, że \(x_1\in W\), \(x_2\notin W\).
\(\bullet \) Przypadek \(x_1\notin W\), \(x_2\in W\) dowodzimy analogicznie jak powyżej.
2. \(g\) jest surjekcją. Chcemy sprawdzić, że \(g(Z)=Y\). W serii równości poniżej będziemy korzystać:
(a) z własności obrazu wypisanych w Stwierdzeniu 111,
(b) z definicji \(W\)
(c) z definicji \(g\)
(d) z bijektywności \(f\)
Zapiszmy
\(g(Z)=g(Z\setminus W\cup W)\stackrel {(a)}{=}g(Z\setminus W)\cup g(W)\stackrel {(c)}{=}f(Z\setminus W)\cup W\stackrel {(b)}{=} f(Z\setminus W)\cup W_0\cup \bigcup _{n=0}^{\infty } W_{n+1}\stackrel {(b)}{=} f(Z\setminus W)\cup W_0\cup \bigcup _{n=0}^{\infty } f(W_{n}) \stackrel {(b)}{=} f(Z\setminus W)\cup (Y\setminus X)\cup f(\bigcup _{n=0}^{\infty } W_{n})= f(Z\setminus W)\cup (Y\setminus X)\cup f(W)= f(Z\setminus W)\cup f(W)\cup (Y\setminus X)= f(Z)\cup (Y\setminus X)\stackrel {(d)}{=}X\cup Y\setminus X=Y\). □
Ćwiczenie 208. 1. Wykazać, że odwzorowanie \(\N \times \N \to \N \) dane wzorem
\((k,l)\to 2^k3^l\) jest injekcją.
2. Korzystając z powyższego faktu i z twierdzenia Cantora–Bernsteina wykazać, że \(\N \times \N \sim \N \).