Na tym wykładzie powrócimy do relacji częściowego porządku. Sformułujemy Lemat Kuratowskiego1–Zorna2. Wykażemy, że ten Lemat wynika z Twierdzenia Zermelo (o dobrym uporządkowaniu).
Na kolejnym wykładzie zobaczymy, że zachodzi wynikanie: z Lematu Kuratowskiego–Zorna wynika Pewnik Wyboru, a jeszcze później naszkicujemy dowód Twierdzenia Zermelo przy założeniu Pewnika Wyboru. Zauważmy, zatem, że Lemat Kuratowskiego–Zorna jest równoważny Pewnikowi Wyboru, można go zatem przyjąć jako jeden z aksjomatów Teorii Mnogości.
Zacznijmy od przypomnienia.
Niech zbiór \((X,\preccurlyeq ) \) będzie zbiorem częściowo uporządkowanym (to znaczy relacja \(\preccurlyeq \) jest zwrotna, przechodnia, słabo antysymetryczna, zobacz Definicja 128). Przypomnijmy, że podzbiór \(L\subset X\) nazywamy łańcuchem, jeśli \((L,\preccurlyeq |_L)\) jest zbiorem uporządkowanym liniowo (Definicja 146). Przypomnijmy, że element \(M\in X\) nazywamy majorantą zbioru \(A\subset X\) jeśli dla każdego \(x\in A\) zachodzi \(x\leq M\) (Definicja 138), a element \(a\in X\) nazywamy elementem maksymalnym zbioru \(X\), jeśli dla dowolnego \(x\in X\) zachodzi wynikanie \(a\leq x\Longrightarrow a=x\) (Definicja 132).
Dla zbioru \(X\) uporządkowanego liniowo odcinkiem początkowym tego zbioru wyznaczonym przez punkt \(a\in X\) nazywamy
\[{\cal O}(a)=\{ x\in X: x\leq a \wedge x\neq a \},\]
zobacz Definicja 152.
Mówimy, że \((X,\leq )\) jest uporządkowany dobrze gdy każdy niepusty podzbiór zbioru \(X\) ma element najmniejszy (w sensie porządku \(\leq \)), zobacz Definicja 150.
Niech teraz \((X,\leq )\) będzie zbiorem dobrze uporządkowanym. Weźmy funkcję \(f: {\cal P}(X)\setminus \{X\} \to X\) taką, że \(f(A) \in X\setminus A\) (jej istnienie wynika z Pewnika Wyboru). Mówimy, że porządek \(\leq \) jest zgodny z \(f\) jeśli dla każdego \(a\in X\) zachodzi \(a=f({\cal O}(a)).\) Przypomnijmy teraz Twierdzenie Zermelo (Twierdzenie 155):
Zakładając to Twierdzenie wykażemy teraz Lemat Kuratowskiego–Zorna. Następnie, na kolejnym wykładzie, zobaczymy – bardzo istotne – zastosowania tego Lematu. Dzięki niemu możemy wykazać, że każda przestrzeń wektorowa ma bazę, że moce dwóch dowolnych zbiorów można ze sobą porównać lub, na wykładzie ze Wstępu do Algebry, że w każdym pierścieniu istnieje ideał maksymalny.
Dowód. Wprowadźmy oznaczenia. Niech \(L\) będzie łańcuchem w \(X\), niech dla tego łańcucha \(M(L)\) oznacza zbiór majorant \(L\) w \(X\). Z założenia \(\bullet \) wynika, że \(M(L)\) jest zbiorem niepustym. Weźmy funkcję \(f:{\cal P}(X)\setminus \{X\}\to X\) taką, że dla dowolnego \(A\subsetneq X\) mamy \(f(A)\in X\setminus A\) oraz dodatkowo \(f(L)\in M(L)\setminus \{L\}\) o ile \(L\) jest łańcuchem i \(M(L)\setminus L\neq \emptyset \).
Dla dowodu Lematu Kuratowskiego–Zorna wykażemy trzy pomocnicze lematy.
Dowód Lematu 211. Niech \(x\) będzie majorantą łańcucha, czyli \(x\in M(L)\). Skoro \(M(L)\subset L\) to \(x\in L\). Z definicji majoranty mamy zatem, że dla każdego \(y\in L\) zachodzi \(y\preccurlyeq x\). To dokładnie oznacza, że \(x\) jest elementem największym w \(L\). Pozostaje zobaczyć, że \(x\) jest też elementem maksymalnym w \(X\). Weźmy zatem \(z\in X\) i załóżmy, że \(x\leq z\). Skoro dla każdego \(y\in L\) mamy \(y\preccurlyeq x\) to także \(y\preccurlyeq z, \forall _{y\in L}\), a zatem \(z\) jest majorantą \(L\). Skoro z założenia \(M(L)\subset L\) to \(z\in L\), a zatem \(z\leq x\), bo \(x\) jest największym elementem \(L\). W takim razie \(x=z\) i wykazaliśmy, że \(x\) jest elementem maksymalnym w \(X\). □
Mamy teraz dwie możliwości.
Możliwość I: Porządek \(\preccurlyeq \) jest porządkiem liniowym na \(X\). Wówczas \(X\) jest łańcuchem. Z założenia, ten łańcuch ma majorantę \(x_0\in X\), oraz wszystkie majoranty tego łańcucha są w \(X\). Możemy zatem skorzystać z Lematu 211, z którego dostajemy, że \(x_0\) jest elementem największym w \(X\), a więc i maksymalnym w \(X\). To dowodzi naszej tezy.
Możliwość II: Porządek \(\preccurlyeq \) nie jest porządkiem liniowym na \(X\). Ten przypadek jest bardziej skomplikowany. Wykorzystamy twierdzenie Zermelo, które mówi w szczególności, że na zbiorze \(X\) możemy wprowadzić dobry porządek. Oznaczmy go \(\leq \). Zdefiniujmy podzbiór \(X\):
\[Y:=\{ y\in X: D_{\leq }(y) \text { nie jest $\preccurlyeq $-ÅĆaÅĎcuchem w~$X$} \},\]
gdzie \(D_{\leq }(y)\) oznacza domknięty odcinek początkowy wyznaczony przez punkt \(y\) względem dobrego porządku \(\leq \), zobacz Definicja 152.
Wykażemy następujący lemat.
Dowód Lematu 212. Weźmy zbiór \(Z\), który nie jest \(\preccurlyeq \)-łańcuchem (taki zbiór istnieje, bo porządek \(\preccurlyeq \) nie jest liniowy). Istnieją zatem \(x,y\in Z\) nieporównywalne względem \(\preccurlyeq \), natomiast \(x,y\) są porównywalne względem porządku \(\leq \) (który jest w szczególności porządkiem liniowym). Bez zmniejszenia ogólności możemy przyjąć, że \(x\leq y\). Wtedy \(x\in D_{\leq }(y)\) oraz \(D_{\leq }(y)\) nie jest \(\preccurlyeq \)-łańcuchem (bo \(x,y\) nie są porównywalne względem \(\preccurlyeq \).) Z definicji \(Y\) mamy, że \(y\in Y\), a zatem \(y\in Z\cap Y\); w szczególności mamy także \(Y\neq \emptyset \). □
Zbiór \(Y\) jest niepustym podzbiorem zbioru dobrze uporządkowanego \((X,\leq )\). Niech \(y_1\) oznacza najmniejszy (w sensie porządku \(\leq \)) element zbioru \(Y\). Zdefiniujmy pewien odcinek początkowy:
\[L_1:={\cal O}_{\leq }(y_1).\]
Zauważmy, że \(L_1\neq \emptyset \). Faktycznie, skoro \(y_1\in Y\) to domknięty odcinek początkowy \(D_{\leq }(y_1)\) nie jest \(\preccurlyeq \)-łańcuchem, zatem istnieje co najmniej jeden element \(x\in D_{\leq }(y_1)\) nieporównywalny względem \(\preccurlyeq \) z \(y_1\), czyli \(\# D_{\leq }(y_1)\geq 2\), skąd \(\# {\cal O}_{\leq }(y_1)\geq 1\), czyli \({\cal O}_{\leq }(y_1)=L_1\neq \emptyset \).
Co więcej, zauważmy też, że
\[L_1\cap Y=\emptyset .\]
Faktycznie, \(L_1={\cal O}_{\leq }(y_1)=\{x\in X:x< y_1 \}\) (\(<\) oznacza jak zwykle „mniejsze lub równe i różne”), zatem ponieważ \(y_1\) jest najmniejszym elementem \(Y\), to żaden z elementów \(L_1\) nie może należeć do \(Y\).
W takim razie \(L_1\) jest \(\preccurlyeq \)-łańcuchem. Gdyby bowiem \(L_1\) nie był \(\preccurlyeq \)-łańcuchem, to miałby – z Lematu 212 – niepuste przecięcie z \(Y\).
Udowodnimy teraz trzeci (i ostatni) lemat.
Dowód Lematu 213. Dla dowodu nie wprost przypuśćmy, że \(M(L_1)\setminus \{L_1\}\neq \emptyset \). Wówczas, z określenia funkcji \(f\) mamy
\[f(L_1)\in M(L_1)\setminus \{L_1\}.\]
Porządek \(\leq \) jest zgodny z \(f\), zatem
\[f(L_1)=f({\cal O}_{\leq }(y_1))=y_1\]
a zatem
\[y_1\in M(L_1)\setminus \{L_1\}.\]
W takim razie \(y_1\) jest majorantą (w porządku \(\preccurlyeq \) ) \(L_1\), zatem dla wszelkich \(y\in L_1\) mamy \(y\leq y_1\). Stąd wynika następująca obserwacja:
Obserwacja. \(D_{\leq }(y_1)\) jest \(\preccurlyeq \)-łańcuchem.
Faktycznie, z powyższego wynika, że \(y_1\) jest porównywalny z każdym elementem \({\cal O}_{\leq }(y_1)\). Przypuśćmy, że w \(D_{\leq }(y_1)\) istnieją \(y_2,y_3\) (różne od \(y_1\)) nieporównywalne względem \(\preccurlyeq \). Te elementy są porównywalne względem \(\leq \), możemy przyjąć, że \(y_3\leq y_2\), zatem \(D_{\leq }(y_2)\) zawiera element \(y_3\) nieporównywalny względem \(\preccurlyeq \) z \(y_2\), czyli \(D_{\leq }(y_2)\) nie jest \(\preccurlyeq \)-łańcuchem, czyli \(y_2\in Y\). Z drugiej strony \(L_1={\cal O}_{\leq }(y_1)\supset D_{\leq }(y_2)\) i, jak zobaczyliśmy wyżej, \(L_1\cap Y=\emptyset \), co daje sprzeczność.
Skoro \(D_{\leq }(y_1)\) jest \(\preccurlyeq \)-łańcuchem, to, z definicji \(Y\), \(y_1\notin Y\), co daje sprzeczność z faktem, że \(y_1\) jest (najmniejszym) elementem \(Y\). Tym sposobem zakończyliśmy dowód Lematu 213. □
Aby zakończyć dowód całego twierdzenia (Lematu Kuratowskiego–Zorna) wystarczy zauważyć, że właśnie wykazaliśmy, że
\[M_{\preccurlyeq }(L_1)\subset L_1,\]
zatem na podstawie Lematu 211 \(L_1\) ma element największy, który jest maksymalny w \(X\). Zatem w \(X\) istnieje element maksymalny. □
Uwaga 214. Zauważmy, że w założeniach Twierdzenia 210 jest zdanie „każdy łańcuch w \(X\) ma majorantę w \(X\)”. Istotne jest, żeby majoranta łańcucha z \(X\) należała do \(X\), w przeciwnym razie Twierdzenie nie musi zachodzić. Rozważmy na przykład \(X=(0,1)\) z naturalnym porządkiem. Każdy łańcuch z tego przedziału ma majorantę w \(\R \), ale nie każdy ma majorantę w \(X\), przykładowo \(\{1-\frac {1}{n}: n\in \N \}\) nie ma majoranty w \((0,1)\); i oczywiście w \(X\) nie ma elementu maksymalnego.