Na tym wykładzie naszkicujemy dowód tego, że z Pewnika Wyboru wynika Twierdzenie Zermelo.
Dowód jest prowadzony według jednego z dowodów przedstawionych w podręczniku [3], gdzie odsyłamy Czytelnika zainteresowanego też innymi dowodami.
Przypomnijmy:
Niech dany będzie zbiór \((X,\leq )\) dobrze uporządkowany i funkcja \(f: {\cal P}(X)\setminus \{ X\}\to X\) będzie taka, że \(f(A)\notin A\). Mówimy, że porządek \(\leq \) jest zgodny z \(f\) jeśli dla każdego \(a\in X\) zachodzi
\[a=f({\cal O}(a)),\]
gdzie odcinkiem początkowym wyznaczonym przez element \(a\in X\) nazywamy
\[{\cal O}(a)=\{ x\in X: x\leq a \wedge x\neq a \}.\]
Zachodzi następujące stwierdzenie:
Stwierdzenie 219. Niech \((X,\leq )\) będzie zbiorem liniowo uporządkowanym. Wtedy następujące warunki są równoważne:
(1) \(\leq \) jest dobrym porządkiem.
(2) Jeśli \(\cal O\) jest odcinkiem początkowym (zob. Definicja 152) to istnieje \(a\in X\), taki, że \({\cal O}={\cal O}(a)\).
(3) Żaden ciąg w \(X\) nie jest ciągiem malejącym.
Dowód. Możemy założyć, że \(X\) jest zbiorem niepustym.
\((1)\lra (2)\). Weźmy \(\calo \), właściwy (zatem różny od \(X\)) odcinek początkowy w \(X\). Skoro porządek jest dobry, to w \(X\setminus \calo \) (niepusty!) istnieje element najmniejszy, \(a\). Jeśli \(y\in \calo (a)\) to \(y\in \calo \), bo \(a\) jest najmniejszym spośród elementów nienależących do \(\calo \). Jeśli \(\year \in \calo \) to \(y\leq a \wedge y\neq a\), zatem \(y\in \calo (a)\). Stąd \(\calo =\calo (a)\).
\((2)\lra (3)\). Weźmy ciąg \((x_n)_{n\in \N }\subset X\). Zdefiniujmy \(\calo \) jako zbiór punktów \(X\) mniejszych (lub równych) od wszystkich wyrazów ciągu, \(y\in \calo \iff y\leq x_n, \forall _{n\in \N }\). Zauważmy, że \(\calo \) jest odcinkiem początkowym zbioru \(X\) (bo wraz z każdym elementem zawiera wszystkie od niego mniejsze). Jeśli \(\calo =X\) to ciąg \((x_n)\) musi być stały (równy największemu elementowi \(X\)). Jeśli \(\calo \) jest właściwym odcinkiem początkowym to istnieje \(a\in X\) taki, że \(\calo =\calo (a)\), ale skoro \(a\notin \calo (a)=\calo \), to istnieje element ciągu \(x_N\) taki, że \(x_N< a\). Stąd \(x_N\in \calo \), a stąd \(x_N\leq x_n\) dla wszystkich \(n\), czyli w szczególności \(x_N\leq x_{N+1}\), a zatem ciąg \((x_n)_{n\in \N }\) nie jest malejący.
\((3)\lra (1)\). Całkiem formalny dowód tego wynikania wymaga twierdzenia o definiowaniu przez indukcję z Wykładu 15, tu przedstawimy szkic rozumowania. Niech \(A\) będzie niepustym podzbiorem zbioru \(X\). Weźmy dowolny element \(x_0\in A\). Jeśli ten element jest najmniejszy w \(A\), to skończyliśmy dowód. Jeśli nie, to istnieje element \(x_1\) od niego mniejszy. Jeśli \(x_1\) to nie jest najmniejszy element \(A\) to kontynuujemy postępowanie, konstruując wyrazy \(x_1>x_2>x_3\dots \). Jeśli żaden z elementów \(x_n\) nie jest elementem najmniejszym w \(A\), dostajemy nieskończony ciąg ściśle malejący, sprzeczność. □
Dowód. Powiemy, że podzbiór \(A\) zbioru \(X\) jest zgodny z \(f\), jeśli istnieje na \(A\) dobry porządek \(\leq _A\), zgodny z \(f\).
Przykładowo, łatwo sprawdzić, że dla \(a\in X\) z \(f(\emptyset )=\{a\}\) zbiór \(\{a\}\) jest dobrze uporządkowany i zgodny z \(f\).
Dowód twierdzenia opiera się na serii lematów.
Dowód Lematu 221. Niech \(C\subset A\) będzie jakimś odcinkiem początkowym zbioru \(A\) (z porządkiem z \(A\) zacieśnionym do \(C\)). Aby wykazać, że \(C\) jest zgodny z \(f\) musimy wziąć jakiś odcinek początkowy zbioru \(C\), powiedzmy \({\cal O}_{\leq _C}(c)\) dla pewnego \(c\in C\) (przypomnijmy, że każdy odcinek początkowy jest wyznaczony przez jakiś element zbioru) i sprawdzić, że \(f({\cal O}_{\leq _C}(c))=c.\) Zauważmy, że
\[{\cal O}_{\leq _C}(c)={\cal O}_{\leq _A}(c)\]
bo na \(C\) mamy zacieśnienie porządku z \(A\). W takim razie
\[f({\cal O}_{\leq _C}(c))=f({\cal O}_{\leq _A}(c))=c,\]
gdzie druga nierówność wynika z założenia, że porządek na \(A\) jest zgodny z \(f\). □
Lemat 222. Niech dane będą dwa podzbiory \(A, B\) zbioru \(X\), zgodne z \(f\). Niech \(C\) będzie właściwym odcinkiem początkowym zbioru \((A\leq _A)\) i zbioru \((B,\leq _B)\) (właściwym, czyli \(C\neq A, C\neq B\)). Wówczas istnieje \(c\in A\cap B\) takie, że \(C={\cal O}_{\leq _A}(c)\) i \(C={\cal O}_{\leq _B}(c)\).
Dowód Lematu 222. Skoro \(C\) jest odcinkiem początkowym \(A\) to \(C={\cal O}_{\leq _A}(a)\) dla pewnego \(a\in A\) i tak samo, skoro \(C\) jest odcinkiem początkowym \(B\) to \(C={\cal O}_{\leq _B}(b)\) dla pewnego \(b\in B\). Ponieważ \(A\) jest zgodny z \(f\) to \(f(C)=f({\cal O}_{\leq _A}(a))=a\) i ponieważ \(B\) jest zgodny z \(f\) to \(f(C)=f({\cal O}_{\leq _B}(b))=b\); zatem \(a=b\), więc biorąc \(c:=a=b\) wykazaliśmy lemat. □
Dowód Lematu 223. Niech \(\cal R\) będzie rodziną złożoną ze zbiorów \(R\subset A\cap B\), takich, że \(R\) jest odcinkiem początkowym zarówno \((A,\leq _A)\), jak i \((B,\leq _B)\).
Niech
\[C=\bigcup _{R\in {\cal R}}R.\]
Zauważmy, że z definicji odcinka początkowego wynika, że suma odcinków początkowych jest odcinkiem początkowym. Zatem \(C\) jest odcinkiem początkowym zarówno \(A\) jak i \(B\), czyli \(C\in {\cal R}\).
Zauważmy też, że \(C\) jest też największym w sensie zawierania elementem w \(\cal R\).
Tezę lematu dostaniemy, jeśli wykażemy, że \(C=A\) lub \(C=B\).
Przypuśćmy zatem, że \(C\neq A\) i \(C\neq B\). Zatem \(C\) jest właściwym odcinkiem początkowym dla \(A\) i \(B\), spełnia zatem założenia Lematu 222. Istnieje więc element \(c\in A\cap B\) taki, że
\[C={\cal O}_{\leq _A}(c) \text { i } C={\cal O}_{\leq _B}(c).\]
Wtedy jednak \(c\notin C\), zatem zbiór \(C'=C\cup \{c\}\) jest odcinkiem początkowym i dla \(A\) i dla \(B\), silnie większym od \(C\). Uzyskaliśmy zatem sprzeczność z faktem, że \(C\) jest też największym w sensie zawierania elementem w \(\cal R\), skąd wynika, że musi być \(C=A\) lub \(C=B\), a zatem jeden z tych zbiorów jest odcinkiem początkowym drugiego. □
Dowód Lematu 224. Zauważmy najpierw, że z tego lematu wynika, że jeśli zbiór \(A\subset X\) jest zgodny z \(f\) to \(\leq _A\) jest jedynym dobrym porządkiem na \(A\) zgodnym z \(f\). Faktycznie, gdyby istniały dwa porządki, \(\leq _1,\leq _2\), wystarczy zastosować lemat do \((A,\leq _1)\) i do \((B,\leq _B)=(A,\leq _2)\).
Aby udowodnić nasz lemat zauważmy, że z Lematu 222 wynika, że \({\cal O}_A(y)\) jest zgodny z \(f\). Skoro \(y\notin {\cal O}_A(y)\), to \(y\in B\setminus {\cal O}_A(y)\), zatem \(B\) nie jest odcinkiem początkowym \({\cal O}_A(y)\).
Natomiast, skoro \({\cal O}_A(y)\) i \(B\) są zgodne z \(f\), to na podstawie Lematu 223 jeden z nich jest odcinkiem początkowym drugiego; zatem \({\cal O}_A(y)\) jest odcinkiem początkowym \(B\). W takim razie \({\cal O}_A(y)\) jest odcinkiem początkowym \(A\) i \(B\). Lemat 222 mówi, że w takim razie ten odcinek jest w obu zbiorach wyznaczony przez ten sam element, a w zbiorze \(A\) jest to element \(y\). Zatem
\[{\cal O}_A(y)={\cal O}_B(y),\]
co kończy dowód lematu. □
Kolejny lemat jest ostatnim przed dowodem samego twierdzenia Zermelo.
Dowód Lematu 225.
1. Z Lematu 224 porządek na dowolnym zbiorze \(A\in {\cal R}\) zgodny z \(f\), czyli \(\leq _A\), jest na \(A\) równy porządkowi na \(Y\), zacieśnionemu do \(A\) czyli \(\leq |_A\) (jako \(B\) bierzemy \((A, \leq |_A)\)).
2. Mamy wykazać, że \(\leq \) jest porządkiem liniowym na \(Y\) (czyli, że relacja \(\leq \) jest zwrotna, słabo antysymetryczna, przechodnia i spójna). Niech \(x,y,z\in Y\). Istnieją zatem \(A_x, A_y, A_z\in {\cal R}\) takie, że \(x\in A_x, y\in A_y, z\in A_z\). Ponieważ \(A_x, A_y, A_z\) są zgodne z \(f\) to dla każdych dwóch z nich jeden jest odcinkiem początkowym drugiego. W takim razie, na przykład \(A_x\) i \(B_x\) są odcinkami początkowymi \(A_z\). Stąd, \(x,y,z\in A_z\) a relacja \(\leq \) zacieśniona do \(A_z\) jest relacją porządku liniowego.
3. Chcemy teraz wykazać, że dla każdego zbioru \(A\) z rodziny \(\cal R\) oraz dla \(y\in A\) odcinek początkowy wyznaczony przez \(y\) w \(A\) jest taki sam jak odcinek początkowy wyznaczony przez \(y\) w \(Y\), czyli
\[{\cal O}_Y(y)={\cal O}_A(y).\]
Z definicji porządku na zbiorze \(Y\) mamy wynikanie: \(x<_A y\lra x<_Y y\) (dla \(x\in Y\)). Z drugiej strony, jeśli \(x<_Y y\) to istnieje zbiór \(B\in {\cal R}, y\in B\) taki, że \(x<_B y\). Skoro \(y\in A\cap B\), to z Lematu 224 mamy \(x_B y\iff x<_A y\), co daje wynikanie w drugą stronę.
4. Pokażemy teraz, że porządek \(\leq \) na \(Y\) jest dobry. Gdyby tak nie było, to ze Stwierdzenia 219(3) istniałby w \(Y\) ciąg \((y_n)_{n\in \N }\) malejący w porządku \(\leq \). Weźmy \(y_1\) z tego ciągu. Istnieje zbiór \(A\) z rodziny \(\cal R\) taki, że \(y_1\in A\). Skoro \(y_n<_Y y_1\) to także \(y_n<_A y_1\), czyli \(y_n\) tworzą malejący ciąg elementów z \(A\), a zatem, znowu ze Stwierdzenia 219, porządek na \(A\) nie jest dobry, sprzeczność.
5. Zauważmy, że porządek \(\leq \) jest zgodny z funkcją \(f\). Faktycznie, niech \(y\in Y\). Wówczas \(y \in A\), dla pewnego \(A\in {\cal R}\). Z punktu 3. wiemy, że \({\cal O}_Y(y)={\cal O}_A(y)\) zatem \(f({\cal O}_Y(y))=f({\cal O}_A(y))=y\). □
Możemy teraz przejść do dowodu twierdzenia Zermelo. Z Lematu 225 wynika, że na zbiorze \(Y\) mamy porządek \(\leq \) dobry i zgodny z \(f\). Zatem \(Y\in {\cal R}\), oczywiście \(Y\) jest największym w sensie zawierania elementem \(\cal R\). Z Lematu 224 wynika, że porządek \(\leq \) jest jedynym dobrym porządkiem na \(Y\) zgodnym z \(f\). Wystarczy teraz pokazać, że \(Y=X\).
Przypuśćmy zatem, że \(Y\neq X\). Wówczas istnieje \(z\in X\setminus Y\) takie, że \(f(Y)=z\). Zdefiniujmy \(Z:=Y\cup \{z\}\). Zdefiniujmy na \(Z\) porządek \(\leq _Z\) tak, że \(\leq _Z|_Y=\leq _Y=\leq \) oraz \(\forall _{y\in Y} \ y<_Z z\). Łatwo zobaczyć, że \(\leq _Z\) jest porządkiem liniowym i dobrym na \(Z\). Porządek ten jest też zgodny z \(f\), bo jeśli \(x\in Y\) to \({\cal O}_Y(x)={\cal O}_Z(x)\) z definicji porządku na \(Z\), a zatem \(f({\cal O}_Z(x))=f({\cal O}_Y(x))=x\), a jeśli \(x=z\) to \({\cal O}_Z(x)=Y\) czyli \(f({\cal O}_Z(x))=f(Y)=z=x\) z powyższego wyboru \(z\). To daje nam dobry i zgodny z \(f\) porządek na zbiorze \(Z\), ściśle większym od \(Y\), co jest sprzeczne ze stwierdzonym wyżej faktem, że \(Y\) jest największym w sensie zawierania elementem \(\cal R\). To kończy dowód twierdzenia Zermelo.
□