Aksjomat wyboru i twierdzenia mu równoważne

Tę część wykładu zaczniemy od przytoczenia aksjomatu wyboru w postaci, w jakiej został wprowadzony w wykładzie 4 "Teoria mnogości ZFC. Operacje na zbiorach".

Aksjomat Wyboru. Następująca formuła jest prawdziwa:

\( \forall x\; ( \emptyset\notin x\land \forall y\forall z\; (z\in x\land y\in x) \Longrightarrow (z=y \lor z\cap y = \emptyset)) \Longrightarrow \exists w \forall v\;(v\in x \Longrightarrow \exists u\;v\cap w=\{u\}). \)

Rysunek 1

Aksjomat ten mówi, że jeśli \( x \) jest rodziną niepustych, parami rozłącznych zbiorów, to istnieje zbiór mający z każdym elementem \( x \) dokładnie jeden element wspólny. Zbiór \( w \), którego istnienie gwarantuje aksjomat wyboru, "wybiera" z każdego elementu rodziny dokładnie jeden element (rysynek 1). Zbiory jako pionowe, nieregularne obszary, zbiór wybierający jako poziomy zbiór przecinający każdy z nich na dokładnie jednym elemencie.

W dalszej części wykładu prezentujemy kilka twierdzeń równoważnych aksjomatowi wyboru. To znaczy, że na gruncie aksjomatyki ZF, bez aksjomatu wyboru, założenie prawdziwości któregokolwiek z tych twierdzeń implikuje prawdziwość aksjomatu wyboru i vice versa. Bardzo istotną częścią dowodów jest wykazanie, że twierdzenia te są dokładnie równoważne aksjomatowi wyboru na gruncie ZF. Na gruncie aksjomatyki ZFC twierdzenia te dają się udowodnić przy użyciu aksjomatu wyboru.

Aby wykazać równoważność między aksjomatem wyboru a poniższymi twierdzeniami, pokażemy, że każde twierdzenie implikuje następne i że ostatnie implikuje aksjomat wyboru. Jest to najprostszy sposób na wykazanie równoważności.

Twierdzenia dotyczące zbiorów

Pierwsze, równoważne aksjomatowi wyboru, twierdzenie mówi o istnieniu funkcji wybierającej. W aksjomacie wyboru, z rodziny zbiorów wybieraliśmy elementy przez utworzenie zbioru. Aby możliwe było wybranie dokładnie jednego elementu z każdego zbioru, niezbędne było założenie o rozłączności tych zbiorów. Poniższe twierdzenie mówi o istnieniu funkcji wybierającej elementy ze zbiorów.

Twierdzenie 3.1.

Dla dowolnej rodziny niepustych zbiorów istnieje funkcja, która każdemu zbiorowi w tej rodzinie przyporządkowuje któryś z jego elementów. Formalnie

\( \forall x\; \emptyset\notin x \Longrightarrow \exists f\; f:x \rightarrow \bigcup x \land( \forall y\; y\in x \Longrightarrow f(y)\in y). \)

Poniżej przedstawiamy dowód, na gruncie ZF, że aksjomat wyboru implikuje powyższe twierdzenie.

Dowód

Aksjomat wyboru implikuje Twierdzenie 3.1 (patrz Twierdzenie 3.1.) Ustalmy dowolny, niezawierający zbioru pustego, zbiór \( x \). Skonstruujemy zbiór \( x_1 \), do którego stosować będziemy aksjomat wyboru. Zbiór

\( x_1 = \{\{y\}\times y\,:\, y\in x\} \)

jest rodziną zbiorów parami rozłącznych - elementy pochodzące z różnych zbiorów \( x \) różnią się w \( x_1 \) na pierwszej współrzędnej. Do zbioru \( x_1 \) stosujemy aksjomat wyboru i otrzymujemy zbiór \( w\subset x\times \bigcup x \). Ponieważ z każdego zbioru \( x_1 \) wybraliśmy dokładnie jeden element, to \( w \) jest funkcją z \( x \) do \( \bigcup x \). Definicja \( x_1 \) gwarantuje również, że \( w(y)\in y \) dla każdego \( y\in x \). Wnioskujemy, że \( w \) może być wzięte jako \( f \) i że aksjomat wyboru implikuje Twierdzenie 3.1 (patrz Twierdzenie 3.1.).

Kolejny fakt, równoważny aksjomatowi wyboru, przedstawiamy w formie ćwiczenia:

Ćwiczenie 3.1

Wykaż, że stwierdzenie "dla każdej surjekcji \( f:x \rightarrow y \) istnieje iniekcja \( g:y \rightarrow
x \) taka, że \( f\circ g \) jest funkcją identycznościową na \( y \)" jest równoważne aksjomatowi wyboru na gruncie ZF.

Rozwiązanie

Pokażmy najpierw, że z aksjomatu wyboru wynika powyższe stwierdzenie. Ustalmy dowolną surjekcję \( f:x \rightarrow y \) i zdefiniujmy zbiór \( z \) w następujący sposób:

\( z = \{w\subset x\,:\, \exists v\; v\in y \land w = \vec{f}^{-1}(\{v\})\}. \)

Jest to zbiór składający się z przeciwobrazów singletonów z \( y \). Ponieważ \( f \) jest surjekcją \( \emptyset\notin z \), a ponieważ \( f \) jest funkcją każde dwa różne elementy \( z \) przecinają się pusto. W związku z tym do zbioru \( z \) możemy zastosować aksjomat wyboru i otrzymać zbiór \( u \) mający dokładnie jeden element wspólny z każdym elementem \( z \), wtedy

\( g = \{(v,w)\in y\times x\,:\, v\in y \;\land\; w\in x\;\land\; \{w\} = \vec{f}^{-1}(\{v\})\cap u\} \)

jest funkcją przekształcającą \( y \) w \( x \) i taką, że \( f\circ g \) jest identycznością na \( y \). Fakt, że \( g \) jest funkcją jest oczywisty z definicji i z własności \( u \). Aby dowieść własności złożenia ustalmy \( v\in y \), wtedy \( g(v)=w \) implikuje \( w\in\vec{f}^{-1}(\{v\}) \), czyli \( f(w) = v \), co dowodzi implikacji.

Aby wykazać, że stwierdzenie implikuje aksjomat wyboru ustalmy dowolny zbiór \( x \) taki, że \( \emptyset\notin x \), oraz, że każde dwa różne elementy zbioru \( x \) są rozłączne. Zdefiniujmy funkcję \( f:\bigcup x \rightarrow x \) tak, że

\( f(w) = z \iff w\in z. \)

Relacja \( f \) jest funkcją, ponieważ każdy element \( \bigcup x \) należy do dokładnie jednego zbioru w \( x \) i jest surjekcją, ponieważ \( \emptyset \notin x \). Na mocy powyższego stwierdzenia istnieje funkcja \( g:x \rightarrow \bigcup x \) taka, że \( f\circ g \) jest identycznością na \( x \). Ustalmy \( z\in x \), wtedy \( f(g(z)) = z \) wtedy i tylko wtedy, kiedy \( g(z)\in z \), a ponieważ \( g \) jest funkcją, to zbiór \( \vec{g}(x) \) jest zbiorem, który z każdym elementem \( x \) ma dokładnie jeden element wspólny. Czyli ze stwierdzenia powyżej wynika aksjomat wyboru.

Twierdzenia dotyczące porządków

Kolejne dwa twierdzenia dotyczą częściowych porządków. Pierwsze z nich gwarantuje istnienie maksymalnych łańcuchów.

Twierdzenie 3.2. [Zasada maksimum Felixa Hausdorff'a]

W każdym zbiorze częściowo uporządkowanym istnieje maksymalny, pod względem inkluzji, łańcuch. Zgodnie z przyjętą strategią postępowania wykażemy, że Twierdzenie 3.1 implikuje zasadę maksimum Felixa Hausdorffa.

Dowód

Twierdzenie 3.1 implikuje zasadę maksimum Felixa Hausdorffa. Dowód tej implikacji opiera się na Twierdzeniu Bourbakiego-Witta z Wykładu 10 (patrz Twierdzenie Bourbakiego-Witta). Ustalmy dowolny zbiór częściowo uporządkowany \( (A,\sqsubseteq) \). Jeśli \( A=\emptyset \), to zbiór ten posiada dokładnie jeden łańcuch i fakt jest dowiedziony. Jeśli \( A\neq\emptyset \), oznaczmy przez \( (B,\subset) \) zbiór częściowo uporządkowany składający się z łańcuchów w \( (A,\sqsubseteq) \) uporządkowanych przez inkluzję

\( B = \{C\subset A\,:\, C \) jest uporządkowany liniowo przez \( \sqsubseteq\}. \)

Zbiór częściowo uporządkowany \( (B,\subset) \) jest łańcuchowo zupełny. Aby to pokazać, ustalmy dowolny, uporządkowany liniowo przez inkluzję zbiór \( D\subset B \). Jeśli \( \bigcup D \) należy do \( B \), to jest to niewątpliwie supremum zbioru \( D \). Aby wykazać, że \( \bigcup D \) jest elementem \( B \), należy wykazać, że jest on uporządkowany liniowo przez \( \sqsubseteq \). Weźmy dwa elementy \( \bigcup D \) - \( x \) i \( y \). Istnieje \( C_x\in D \) i \( C_y\in D \) takie, że \( x\in C_x \), a \( y\in C_y \). Ponieważ \( D \) jest łańcuchem, to, bez straty ogólności, możemy założyć, że \( C_x\subset C_y \). Wtedy, zarówno \( x \) jak i \( y \), należą do \( C_y \) i ponieważ \( C_y\in B \), wnioskujemy, że \( x \) i \( y \) są porównywalne. Wykazaliśmy, że dowolne dwa elementy \( \bigcup D \) są porównywalne, czyli że \( \bigcup D \) jest uporządkowany liniowo przez \( \sqsubseteq \).

Na mocy Twierdzenia 3.1 definiujemy funkcję wyboru \( f \) dla zbioru \( \mathcal{P}(A)\setminus\{\emptyset\} \) zwracającą, dla każdego niepustego podzbioru \( A \), jego element. Twierdzenie Bourbakiego-Witta będziemy stosować do funkcji \( g \) przeprowadzającej \( B \) w \( B \) i zdefiniowanej następująco:

\( g(C)=\left\{\begin{array}{lll} C\cup \{f(C')\}, & \quad \textrm{jeśli } C', \textrm{zbiór elementów porównywalnych z każdym elementem } C, \textrm{jest niepusty} \\ C , & \quad \textrm{w przeciwnym przypadku}. \end{array} \right. \)

Funkcja \( g \) dostaje jako argument łańcuch w \( (A,\sqsubseteq) \) oznaczony przez \( C \) i przy pomocy funkcji \( f \) rozszerza (jeśli jest to możliwe) \( C \) o jeden element porównywalny ze wszystkimi elementami \( C \), otrzymując w ten sposób nowy, większy łańcuch.

Zbiór \( (B,\subset) \) i funkcja \( g \) spełniają założenia Twierdzenia Bourbakiego-Witta i, na jego mocy, istnieje punkt stały \( g \), czyli zbiór \( D \) taki, że \( g(D) = D \). To gwarantuje, że zbiór \( D' \) elementów porównywalnych z każdym elementem \( D \) jest pusty, czyli że \( D \) jest maksymalnym pod względem inkluzji łańcuchem w \( A \).

Równoważną wersję zasady Felixa Hausdorffa pozostawiamy jako ćwiczenie.

Ćwiczenie 3.2

Wykaż, na gruncie ZF, że następujące stwierdzenie jest równoważne zasadzie Felixa Hausdorffa: "W każdym zbiorze częściowo uporządkowanym każdy łańcuch jest zawarty w maksymalnym, pod względem inkluzji, łańcuchu".

Rozwiązanie

Aby udowodnić zasadę maksimum Felixa Hausdorffa używając powyższego stwierdzenia, wystarczy, dla dowolnego zbioru częściowo uporządkowanego znaleźć jeden łańcuch i z faktu że jest on zawarty w łańcuchu maksymalnym wynika, że łańcuch maksymalny istnieje. Dla dowolnego zbioru częściowo uporządkowanego możemy znaleźć jego podzbiór \( (\emptyset,\emptyset) \), który jest łańcuchem i w związku z tym jest zawarty w jakimś łańcuchu maksymalnym, co należało wykazać.

Aby wykazać powyższe stwierdzenie używając zasady Felixa Hausdorffa, ustalmy dowolny zbiór częściowo uporządkowany \( (A,\sqsubseteq) \) i dowolny łańcuch \( C\subset A \). Rozważmy zbiór \( B\subset A \) taki, że

\( B = \{a\in A : a \) jest porównywalne z każdym elementem \( {C}\}. \)

Ponieważ \( C \) jest łańcuchem, mamy \( C\subset B \). Zastosujmy zasadę Hausdorff'a do zbioru \( B \) uporządkowane przez \( \sqsubseteq \) zawężone do \( B \). Gwarantuje ona istnienie łańcucha maksymalnego \( D \) w \( B \). Ponieważ każdy z elementów zbioru \( C \) był porównywalny z każdym elementem zbioru \( B \) (i w szczególności z każdym elementem zbioru \( D \)), to \( D\cup C \) jest łańcuchem i maksymalność \( D \) gwarantuje \( C\subset D \). Pozostaje wykazać, że \( D \) jest maksymalnym łańcuchem w \( A \). Gdyby tak nie było to istniało by \( a\in A\setminus D \) porównywalne z każdym elementem \( D \). Wtedy \( a \) byłoby porównywalne z każdym elementem \( C \) i w związku z tym \( a\in B \) i \( a\in B\setminus D \), co przeczy maksymalności \( D \) w \( B \). W związku z tym \( D \) jest maksymalnym łańcuchem w \( A \) i zawiera \( C \) - stwierdzenie zostało dowiedzione.

Kolejne z równoważnych aksjomatowi wyboru twierdzeń nosi nazwę Lematu Maxa Augusta Zorna. Nazwa ta ma korzenie historyczne i dlatego pozostawiamy ją w tym brzmieniu.

Twierdzenie 3.3. [Lemat Maxa Augusta Zorna]

Jeśli w pewnym zbiorze częściowo uporządkowanym, każdy łańcuch jest ograniczony od góry, to istnieje w nim element maksymalny.

Dowodzimy kolejną implikację

Dowód

Zasada maksimum Felixa Hausdorffa implikuje Lemat Maxa Augusta Zorna. Dowód tej implikacji jest bardzo prosty. Wybierzmy dowolny zbiór częściowo uporządkowany spełniający założenia Lematu Maxa Augusta Zorna, czyli taki, że każdy łańcuch jest w nim ograniczony od góry. Na mocy zasady maksimum Felixa Hausdorffa istnieje w tym zbiorze łańcuch maksymalny pod względem inkluzji. Łańcuch ten posiada ograniczenie górne, które musi być elementem łańcucha i równocześnie elementem maksymalnym zbioru. Jeśliby tak nie było, to dodając element istotnie większy od tego ograniczenia do łańcucha danego przez zasadę maksimum Hausdorffa, uzyskalibyśmy łańcuch istotnie większy pod względem inkluzji.

Kolejne ćwiczenie mówi o istnieniu maksymalnego antyłańcucha.

Ćwiczenie 3.3

Udowodnij, używając lematu Maxa Augusta Zorna, że w każdym zbiorze częściowo uporządkowanym istnieje antyłańcuch maksymalny pod względem inkluzji.

Rozwiązanie

Ustalmy dowolny niepusty (twierdzenie jest trywialne dla zbiorów pustych) zbiór częściowo uporządkowany \( (A,\sqsubseteq) \). Zdefiniujmy zbiór

\( B = \{C\subset A : C \) jest antyłańcuchem w \( A\} \)

i uporządkujmy go relacją inkluzji. Aby móc zastosować do \( (B,\subset) \) lemat Maxa Augusta Zorna, wykażemy, że każdy łańcuch ma majorantę. Ustalmy w tym celu dowolny łańcuch \( B' \) w \( (B,\subset) \). Najprostszym kandydatem na majorantę \( B' \) względem inkluzji jest \( \bigcup B' \) - wykażemy, że \( \bigcup B' \) jest antyłańcuchem w \( (A,\sqsubseteq) \). Niewątpliwie \( \bigcup B'\subset A \). Ustalmy dwa dowolne elementy \( x \) i \( y \) w \( \bigcup B' \), wtedy istnieje \( C_x\in B' \) i \( C_y \in B' \) takie, że \( x\in C_x \) i \( y\in C_y \). Ponieważ \( B' \) jest łańcuchem w sensie inkluzji, to \( C_x \) i \( C_y \) są porównywalne i możemy, bez straty ogólności założyć, że \( C_x\subset C_y \) i w związku z tym \( x\in C_y \). Ponieważ \( C_y\in B'\subset B \), to \( C_y \) jest antyłańcuchem, czyli elementy \( x \) i \( y \) są nieporównywalne w \( A,\sqsubseteq) \). Wykazaliśmy, że dowolne dwa elementy \( \bigcup B' \) są nieporównywalne, czyli, że \( \bigcup B' \) jest antyłańcuchem i należy do \( B \). Wnioskujemy, że każdy łańcuch w \( (B,\subset) \) ma majorantę.

Na podstawie lematu Maxa Augusta Zorna wnioskujemy, że \( (B,\subset) \) posiada element maksymalny - jest to, poszukiwany przez nas, maksymalny w sensie inkluzji antyłańcuch.

Poniższe ćwiczenie dotyczy rozszerzeń porządków.

Ćwiczenie 3.4

Wykaż, używając lematu Maxa Augusta Zorna, że każdy częściowy porządek da się rozszerzyć do porządku liniowego. To znaczy, że dla każdego zbioru częściowo uporządkowanego \( (A,\sqsubseteq) \) istnieje liniowy porządek \( ≼ \) na \( A \) taki, że

\( x \sqsubseteq y \Longrightarrow x ≼ y. \)

dla dowolnych \( x \) i \( y \) w \( A \).

Rozwiązanie

Ustalmy dowolny porządek częściowy \( (A,\sqsubseteq) \) na niepustym zbiorze \( A \) (porządek pusty na zbiorze pustym jest liniowy). Niech zbiór \( B \) będzie zbiorem porządków rozszerzających \( \sqsubseteq \) na \( A \)

\( B = \{r \subset A \times A : r \) jest porządkiem częściowym na \( A \) rozszerzającym \( \sqsubseteq\}. \)

uporządkowanym przez inkluzję. Formalnie, każdy element zbioru \( B \) jest nadzbiorem relacji \( \sqsubseteq \).

Wykażemy teraz, że w zbiorze \( B \), uporządkowanym przez inkluzję, każdy łańcuch ma majorantę. Niech \( D \) będzie niepustym łańcuchem, wtedy, standardowo, kandydatem na majorantę łańcucha \( D \) jest zbiór \( \bigcup D \). Relacja \( \bigcup D \) jest niewątpliwie nadzbiorem \( \sqsubseteq \), bo istnieje element \( D \) który jest takim nadzbiorem. Relacja ta jest przechodnia, bo jeśli \( (a,b)\in\bigcup D \) i \( (b,c)\in\bigcup D \), to \( (a,b)\in C \in D \) i \( (b,c)\in C'\in D \) dla pewnych \( C \) i \( C' \). Ponieważ \( D \) było łańcuchem, bez straty ogólności możemy założyć, że \( C\subset C' \) i w związku z tym obie pary są elementami \( C' \) i przechodniość \( C' \) gwarantuje, że \( (a,c)\in C'\subset \bigcup D \). Antysymetrii dowodzimy w identyczny sposób, co pozwala nam stwierdzić, że \( \bigcup D\in B \) i, że każdy łańcuch w \( B \) ma majorantę.

Niech relacja \( \,\rho\, \) będzie, gwarantowanym przez lemat Maxa Augusta Zorna, elementem maksymalnym w \( (B,\subset) \). Jeśli \( \,\rho\, \) jest porządkiem liniowym, to jest to poszukiwane rozszerzenie liniowe \( \sqsubseteq \) i dowód jest zakończony. Pokażemy, że przypadek kiedy \( \,\rho\, \) nie jest porządkiem liniowym prowadzi do sprzeczności. Załóżmy, że \( \,\rho\, \) nie jest porządkiem liniowym, czyli, że istnieją dwa elementy \( a \) i \( b \) nieporównywalne w \( \,\rho\, \). Zdefiniujmy

\( \uparrow a= \{c\in A\,:\, a\,\rho\, c\} \)

oraz

\( \downarrow b= \{c\in A\,:\, c\,\rho\, b\}. \)

Zauważmy że przecięcie zbiorów \( \uparrow a \) i \( \downarrow b \) jest puste (w przeciwnym przypadku otrzymalibyśmy z przechodniości \( a\,\rho\, b \)), co więcej żaden element \( \downarrow b \) nie może być nad (w \( \,\rho\, \)) żadnym elementem \( \uparrow a \) (z tego samego powodu). Zdefiniujmy nową relację

\( x\,\rho'\, y \iff x\,\rho\, y \lor (x\in \downarrow b \land y\in\uparrow a). \)

Relacja \( \,\rho'\, \) jest oczywiście zwrotna (ponieważ zawiera \( \,\rho\, \)). Aby dowieść antysymetrii załóżmy, że \( x\,\rho'\, y \) i \( y\,\rho'\, x \). Jeśli w obu przypadkach pierwsza część alternatywy jest prawdą, to, na mocy antysymetrii \( \,\rho\, \) mamy \( x=y \). W obu przypadkach prawdą nie może być druga część alternatywy, bo wtedy \( x\in\uparrow a \cap \downarrow b \) co wykluczyliśmy. Pozostaje możliwość, że \( x\,\rho\, y \) i \( y\in\downarrow b \land x\in\uparrow a \) - którą jednak też wykluczyliśmy wcześniej. W dowodzie przechodniości, zakładając \( x\,\rho'\, y \) i \( y\,\rho'\, z \), wszystkie przypadki trywializują się podobnie jak w antysymetrii, za wyjątkiem przypadku kiedy \( x\,\rho\, y \) i \( y\in\downarrow b \land z\in\uparrow a \) (i przypadku dualnego, kiedy \( x\in\downarrow b \land y\in\uparrow a \) i \( y\,\rho\, z \)). Ale wtedy z przechodniości \( \,\rho\, \) wnioskujemy, że \( x\in\downarrow b \) (lub, że \( z\in\uparrow a \)) i że \( x\,\rho'\, z \). Pokazaliśmy, że \( \,\rho'\, \) jest częściowym porządkiem na \( A \). Niewątpliwie \( \,\rho'\, \) rozszerza \( \sqsubseteq \) (ponieważ jest nadzbiorem \( \rho \) rozszerzającej \( \sqsubseteq \)). Równocześnie \( b\,\rho'\, a \) dla elementów, które były nieporównywalne w \( \,\rho\, \). Sprzeczność z maksymalnością \( \,\rho\, \) pozwala zakończyć dowód niewprost.

W Wykładzie 5 "Para uporządkowana, iloczyn kartezjański, relacje, domykanie relacji, relacja równoważności, rozkłady zbiorów" pokazaliśmy, że dla dowolnej relacji istnieje najmniejsza relacja równoważności zawierająca tą relację. W poniższym ćwiczeniu pokażemy, że dla niektórych relacji istnieje maksymalna, pod względem inkluzji, relacja równoważności zawarta w nich

Ćwiczenie 3.5

Użyj lematu Maxa Augusta Zorna, aby wykazać, że dla każdej relacji \( \rho \subset A\times A \), jeśli \( 1_{A}\subset\rho \), to istnieje maksymalna pod względem inkluzji relacja równoważności zawarta w \( \rho \).

Rozwiązanie

Ustalmy niepusty zbiór \( A \) (twierdzenie jest trywialne dla zbioru pustego). Podobnie jak w poprzednich przypadkach lemat Maxa Augusta Zorn'a stosować będziemy do zbioru uporządkowanego przez inkluzję. Zbiorem tym jest

\( B = \{\delta\ \subset A\times A: \delta\ \subset\ \rho\ \land \delta \) jest relacją równoważności na \( A\}. \)

Zbiór \( B \) niewątpliwie nie jest pusty, ponieważ \( 1_{A}\in B \). Jeśli zbiór \( B \) uporządkowany przez inkluzję spełnia założenia lematu Maxa Augusta Zorn'a, to jego element maksymalny jest niewątpliwe maksymalną w sensie inkluzji relacją równoważności zawartą w \( \,\rho\, \). Pozostaje wykazać, że każdy łańcuch w \( (B,\subset) \) posiada ograniczenie górne.

Ustalmy dowolny niepusty łańcuch \( D\subset B \). Musimy wykazać, że \( \bigcup D \) jest relacją równoważności i, że \( \bigcup D\subset \,\rho\, \). Ponieważ każdy element \( D \) jest elementem \( B \) i w związku z tym podzbiorem \( \,\rho\, \), to również ich unia jest podzbiorem \( \,\rho\, \). Wykażemy teraz, że \( \bigcup D \) jest relacją równoważności. Relacja ta jest niewątpliwie zwrotna, ponieważ istnieje element \( D \) i jest on zwrotny. Jest przechodnia, bo dla \( (a,b)\in\bigcup D \) i \( (b,c)\in\bigcup D \) mamy \( (a,b)\in C\in D \) i \( (b,c)\in C'\in D \) dla pewnych \( C,C' \). Zbiory \( C \) i \( C' \) są porównywalne w sensie inkluzji więc, bez straty ogólności zakładamy, że \( C\subset C' \) i w związku z tym obie pary należą do \( C' \). Ponieważ relacja \( C' \), jako element \( B \), jest przechodnia, to \( (a,c)\in C'\subset \bigcup D \) co dowodzi przechodniości. Dla dowodu symetrii ustalmy dowolne \( (a,b)\in\bigcup D \) wtedy dla pewnego \( C\in D \) mamy \( (a,b)\in C \) i, ponieważ \( C \) jest symetryczna, \( (b,a)\in C\subset \bigcup D \) czego należało dowieść. Wykazaliśmy że w zbiorze częściowo uporządkowanym \( (B,\subset) \) każdy łańcuch ma majorantę, więc istniejący, na podstawie lematu Maxa Augusta Zorna, element maksymalny jest poszukiwaną przez nas relacją równoważności.

Kolejny warunek równoważny dotyczy zbiorów dobrze uporządkowanych.

Twierdzenie Ernsta Zermelo

Twierdzenie Zermelo jest jedną z równoważnych postaci aksjomatu wyboru, w którą wyjątkowo trudno uwierzyć.

Twierdzenie 3.4. [Zermelo]

Dla każdego zbioru istnieje relacja, która jest dobrym porządkiem na tym zbiorze. Kolejny dowód to

Dowód

Lemat Maxa Augusta Zorna implikuje Twierdzenie Ernsta Zermelo. Ustalmy dowolny zbiór niepusty \( A \) (dla zbioru pustego porządek pusty porządkuje go dobrze). Rozważmy zbiór \( B \) składający się z podzbiorów \( A \), które mogą być dobrze uporządkowane, wraz z dobrymi porządkami

\( B = \{(C,\sqsubseteq)\,:\, C\subset A \land \sqsubseteq \) jest dobrym porządkiem na \( C \} \) i zdefiniujmy relację na elementach \( B \) w następujący sposób

\(\begin{array}{ll} \displaystyle (C,\sqsubseteq) ≼ (C',\sqsubseteq') \iff & C\subset C' \land \begin{cases}\forall c \forall d\ (c\in C\land d\in C) \Longrightarrow (c\sqsubseteq d \iff c\sqsubseteq' d) \textrm{ oraz } \\ \forall c \forall d\ (c\in C\land d\in C'\setminus C) \Longrightarrow c\sqsubseteq' d \end{cases} \end{array}\)

czyli dwa elementy \( B \) są porównywalne wtedy i tylko wtedy, jeśli zbiory, na których, są określone są porównywalne w sensie inkluzji i porządek zdefiniowany na większym zbiorze jest rozszerzeniem porządku zdefiniowanego na mniejszym przez dodanie elementów większych od wszystkich zastanych. Aby zastosować Lemat Maxa Augusta Zorna do zbioru częściowo uporządkowanego \( (B, ≼ ) \) musimy wykazać, że każdy łańcuch w tym zbiorze ma ograniczenie górne.

Niech \( D\subset B \) będzie łańcuchem w sensie \( ≼ \). Zdefiniujmy \( C_0 \) jako unię wszystkich pierwszych współrzędnych elementów \( D \) i \( \sqsubseteq_0 \) jako unię drugich współrzędnych elementów \( D \). Niewątpliwie \( C_0\subset A \). Ponieważ \( D \) jest łańcuchem w sensie \( ≼ \), to relacja \( \sqsubseteq_0 \) jest porządkiem liniowym na \( C_0 \). Aby wykazać, że \( \sqsubseteq_0 \) jest dobrym porządkiem na \( C_0 \), ustalmy dowolny \( E\subset C_0 \). Niewątpliwie istnieje element \( (C,\sqsubseteq)\in D \) taki, że \( E\cap C\neq\emptyset \). Ponieważ \( (C,\sqsubseteq)\in B \), to \( C \) jest dobrze uporządkowany przez \( \sqsubseteq \) i w związku z tym \( E\cap C \) posiada element najmniejszy w \( C,\sqsubseteq) \) - oznaczmy go przez \( x \). Element \( x \) będzie również najmniejszym elementem \( E \) w \( C_0 \). Aby to wykazać, ustalmy \( y\in E \). Jeśli \( y\in C \), to niewątpliwie \( x\sqsubseteq y \) i w związku z tym \( x\sqsubseteq_0 y \). Jeśli \( y\notin C \), to \( y \in C'\setminus C \) dla jakiegoś \( (C',\sqsubseteq')\in D \). Ponieważ \( D \) jest łańcuchem wnioskujemy, że \( C\subset C' \) i na mocy definicji \( ≼ \), że \( x\sqsubseteq' y \), czyli \( x\sqsubseteq_0 y \), co należało wykazać.

Stosując Lemat Maxa Augusta Zorna wnioskujemy, że w zbiorze częściowo uporządkowanym \( (B, ≼ ) \) istnieje element maksymalny \( (D,\sqsubseteq) \). Jeśli \( D = A \), to \( \sqsubseteq \) jest wymaganym dobrym porządkiem na \( A \). Aby wykazać, że tak musi być, załóżmy niewprost, że \( D ⊊ A \), czyli że istnieje \( d\in A\setminus D \). Wtedy zbiór \( D\cup\{d\} \) wraz z dobrym porządkiem \( \sqsubseteq' \) zdefiniowanym jako

\( a\sqsubseteq' b \iff b=d \lor (a\in D\land b\in D \land a\sqsubseteq b) \)

jest większy w sensie relacji \( ≼ \), co przeczy maksymalności \( D \). Uzyskana w dowodzie niewprost sprzeczność kończy rozumowanie.

Twierdzenie Ernsta Zermelo jest sprzeczne z intuicją wielu matematyków. Gwarantuje ono między innymi istnienie dobrego porządku na liczbach rzeczywistych, czyli takiego liniowego uporządkowania liczb rzeczywistych, w którym każdy zbiór posiada element najmniejszy. Porządek taki jest trudnym do wyobrażenia konceptem matematycznym.

Aby zamknąć ciąg rozumowań, wystarczy wykazać, że Twierdzenie Zermelo implikuje aksjomat wyboru.

Dowód

Twierdzenie Zermelo implikuje aksjomat wyboru. Niech \( x \) będzie dowolnym zbiorem spełniającym założenia aksjomatu wyboru, to znaczy takim, że \( \emptyset\notin x \) i że wszystkie elementy \( x \) są parami rozłączne. Niech \( \sqsubseteq \) będzie istniejącym, na podstawie Twierdzenia Zermelo, dobrym uporządkowaniem zbioru \( \bigcup x \). Zbiór wybierający po jednym elemencie z każdego elementu \( x \) otrzymujemy, stosując zasadę wycinania do \( \bigcup x \)

\( w = \{y\in\bigcup x\,:\, \exists z\; y\in z\in x \land y \) jest najmniejszym elementem \( z \) względem relacji \( \sqsubseteq\}. \)

Zbiór \( w \) posiada po dokładnie jednym elemencie wspólnym z każdym zbiorem \( z\in x \) - jest to element najmniejszy w \( z \) względem dobrego uporządkowania \( \bigcup x \).

Nasze rozumowanie wykazało, że wszystkie powyższe fakty są równoważne na gruncie ZF. Jak wspomnieliśmy na początku, aksjomat wyboru jest kontrowersyjnym aksjomatem. Niektóre z równoważnych mu stwierdzeń są intuicyjnie oczywiste, inne przeczą intuicji. Podsumujemy rozdział żartem autorstwa Jerrego Bona:

The Axiom of Choice is obviously true; the Well Ordering Principle is obviously false; and who can tell about Max August Zorn's Lemma? (Aksjomat wyboru jest oczywiście prawdziwy; twierdzenie Ernsta Zermelo jest oczywiście fałszem; lemat Zorn'a kto wie?)

Informatyka MIMUW