Aksjomat wyboru

Ten rozdział poświęcony jest konsekwencjom aksjomatu wyboru. Jest to aksjomat, który wywołał dużą ilość kontrowersji. Wielu znanych matematyków poddawało go w wątpliwość. W chwili obecnej znakomita większość uważa, że aksjomat wyboru jest prawdziwy, nawet jeśli niektóre z jego konsekwencji są nieintuicyjne.

W tym rozdziale przedstawiamy szereg twierdzeń, które są równoważne lub wynikają z aksjomatu wyboru. Zanim przejdziemy do wypowiedzi tych faktów, wprowadzimy jeszcze jeden termin.

Dobre uporządkowanie

Zbiór uporządkowany [math]\left( X, \le \right)[/math] nazywamy zbiorem dobrze uporządkowanym, gdy każdy niepusty podzbiór [math]X[/math] ma element najmniejszy względem rozpatrywanego porządku [math]\le[/math]. Mówimy wtedy, że zbiór [math]X[/math] jest dobrze uporządkowany przez [math]\le[/math], oraz, że [math]\le[/math] jest dobrym porządkiem na zbiorze [math]X[/math].

Przykładem zbioru dobrze uporządkowanego może być [math]\mathbb{N}[/math] z naturalnym porządkiem. Zasada minimum mówi, że każdy niepusty podzbiór [math]\mathbb{N}[/math] ma liczbę najmniejszą, a więc [math]\mathbb{N}[/math] jest dobrze uporządkowany.

Fakt: Każdy zbiór dobrze uporządkowany jest również liniowo uporządkowany.

Dowód:

Niech [math]\left( X, \le\right)[/math] będzie zbiorem dobrze uporządkowanym. Pokażemy, że jest również zbiorem liniowo uporządkowanym przez [math]\le[/math]. Jeśli [math]X[/math] jest pusty lub jednoelementowy, to jest liniowo uporządkowany, W przeciwnym wypadku istnieją co najmniej dwa elementy [math]X[/math]. Weźmy więc dowolne dwa różne elementy [math]X[/math] - [math]x[/math] i [math]y[/math]. Rozważmy [math]\left\{ x,y\right\}[/math]. Jest to dwuelementowy podzbiór [math]X[/math]. A ponieważ [math]X[/math] jest dobrze uporządkowany, to istnieje element najmniejszy [math]a\in\left\{ x,y\right\}[/math]. Jeśli [math]a=x[/math], to [math]x\lt y[/math]. W przeciwnym przypadku [math]a=y[/math], i wtedy [math]y\lt x[/math]. A więc elementy [math]x[/math] i [math]y[/math] są porównywalne. Z dowolności wyboru takich elementów, otrzymujemy, że [math]X[/math] jest liniowo uporządkowany przez [math]\le[/math].[math]\square[/math]

Aksjomat wyboru

Zaczniemy od przytoczenia aksjomatu wyboru:

Dla dowolnej rodziny zbiorów [math]\mathbb{X}[/math] niepustych i rozłącznych to aksjomat wyboru głosi, że istnieje selektor tej rodziny zbiorów, tzn. taki zbiór [math]S[/math], że:

dla dowolnego zbioru [math]A\in \mathbb{X} : \ \ A \cap S=\left\{ a\right\}.[/math]

tzn. selektor to zbiór [math]S[/math], który ma po dokładnie jednym elemencie wspólnym z każdym zbiorem tej rodziny.

Intuicyjnie to znaczy, że mając rodzinę rozłącznych zbiorów możemy utworzyć zbiór wybierając po jednym elemencie z każdego zbioru.

Będziemy zmierzać do dowodu twierdzenia Zermelo, że każdy zbiór da się dobrze uporządkować. Poza tym dowodem będziemy prezentować (na razie) tylko krótkie, proste dowody.

Twierdzenia dotyczące zbiorów

Pierwsze równoważne aksjomatowi wyboru twierdzenie mówi o funkcji wybierającej elementy ze zbiorów.

Dla dowolnej rodziny zbiorów [math]\mathbb{X}[/math] zbiorów niepustych istnieje funkcja wyboru, tzn. funkcja [math]f:\mathbb{X} \rightarrow \bigcup \mathbb{X}[/math], taka, że [math]f\left( A\right) \in A[/math], dla każdego zbioru [math]A\in\mathbb{X}.[/math]

Czyli mając rodzinę zbiorów niepustych możemy utworzyć funkcję, która tak: bierze zbiór niepusty i wybiera z niego jeden element, bierze następny zbiór niepusty i wybiera z niego jeden element, itd. dla dowolnego zbioru tej rodziny.

Zwróćmy uwagę, że co prawda funkcja ma spełniać [math]f\left( A\right) \in A[/math], czyli przypisana wartość [math]f\left( A\right)[/math] zbiorowi [math]A[/math] ma być elementem tego zbioru, ale ciężko powiedzieć którym, nie jest to jawnie powiedziane niestety. Ale korzystając z aksjomatu wyboru można wykazać, że taka funkcja istnieje (choć ciężko ją opisać wzorem jawnym).

Kolejne równoważne aksjomatowi wyboru twierdzenie to:

Dla dowolnych zbiorów [math]X,Y[/math], oraz dowolnej funkcji [math]f[/math] z [math]X[/math] 'na' zbiór [math]Y[/math], istnieje funkcja [math]g:Y \rightarrow X[/math] taka, że złożenie [math]f\circ g[/math] funkcji [math]g[/math] z funkcją [math]f[/math] jest równe [math]I_Y[/math]- jest identycznością na zbiorze [math]Y[/math].

To twierdzenie jest równoważne aksjomatowi wyboru.

Aby to objaśnić, rozważmy funkcję [math]f:X \rightarrow Y[/math], która jest 'na' zbiór [math]Y[/math]; i rozważmy rodzinę [math]\mathbb{B}[/math] wszystkich przeciwobrazów zbiorów jednoelementowych z [math]Y[/math]. Takie przeciwobrazy są zawsze niepuste. Aby się o tym przekonać to niech [math]y\in Y[/math]. Wtedy ponieważ [math]f[/math] jest 'na' [math]Y[/math], to [math]y=f(x)[/math] przy pewnym [math]x\in X[/math]. A zatem [math]x\in \stackrel{ \rightarrow }{f ^{-1} }\left\{ y\right\}[/math], czyli [math]\stackrel{ \rightarrow }{f ^{-1} }\left\{ y\right\}[/math] jest niepusty. Takie przeciwobrazy są również rozłączne. Utwórzmy przypisanie [math]g[/math] w poniższy sposób: [math]y\in Y \stackrel{g}{\rightarrow} x\in \stackrel{ \rightarrow }{f ^{-1} }\left\{ y\right\}[/math], czyli elementowi [math]y\in Y[/math] przypisujemy element jego przeciwobrazu. Jeśli tak zrobimy, to w wyniku złożenia takiej funkcji [math]g[/math] z naszą funkcją [math]f[/math], element [math]y[/math] powróci, czyli złożenie [math]f\circ g[/math] będzie mieć punkt stały, tzn. [math]\left( f\circ g\right) (y)=y.[/math] Jeśli elementowi [math]y\in Y[/math] przypisalibyśmy (znowu, przypisanie niech nazywa się [math]g[/math]) element zbioru [math]X[/math] spoza [math]\stackrel{ \rightarrow }{f ^{-1} }\left\{ y\right\}[/math], to złożenie [math]f\circ g[/math] nie będzie mieć punktu stałego dla [math]y[/math], czyli [math]\left( f\circ g\right) (y) \neq y[/math], czyli [math]f\circ g[/math] nie będzie identycznością na [math]Y[/math]. Jeśli dla każdego [math]y\in Y[/math] będziemy mu przypisywać element jego przeciwobrazu, to łatwo przypuścić, że złożenie [math]f\circ g[/math] będzie mieć w każdym punkcie punkt stały, stąd będzie identycznością na [math]Y[/math]. Tyle tylko, że aby możliwe było utworzenie funkcji [math]g[/math] musimy wybrać dokładnie jeden element z wielu (na ogół) elementów jego przeciwobrazu. I tak dla każdego [math]y\in Y[/math] (przypominam [math]X,Y[/math] to dowolne zbiory, [math]f[/math] to dowolna funkcja 'na')- dlatego to jest równoważne aksjomatowi wyboru- zobacz ilustrację obok. Dowód podamy później.

Twierdzenia dotyczące porządków

Kolejne równoważne aksjomatowi wyboru twierdzenie to twierdzenie o maksymalnym łańcuchu:

W każdym zbiorze uporządkowanym [math]\left( X, \le\right)[/math] istnieje maksymalny łańcuch pod względem inkluzji.

Czyli w zbiorze uporządkowanym zawsze możemy znaleźć maksymalny łańcuch. Niestety, to o wiele trudniejszy problem niż jego brzmienie, ze względu na bogactwo zbiorów uporządkowanych, ich złożoność i możliwą nieskończoność. Jednak takie zadziwiające twierdzenie jest prawdziwe przy założeniu aksjomatu wyboru ( jest mu równoważne).

Poniższe twierdzenie jest równoważne twierdzeniu o maksymalnym łańcuchu, (a więc również aksjomatowi wyboru):

W każdym zbiorze uporządkowanym każdy łańcuch jest podzbiorem pewnego większego łańcucha maksymalnego.

To twierdzenie mówi, że jeśli mamy zbiór uporządkowany [math]\left( X, \le \right)[/math] oraz łańcuch [math]A \subset X[/math], to możemy dobrać do tego łańcucha większy łańcuch pod względem inkluzji, maksymalny.

Dowód jednego wynikania jest bardzo prosty( tego w tył akurat):

Załóżmy przytoczone twierdzenie. Pokazujemy twierdzenie o maksymalnym łańcuchu. Weźmy dowolny zbiór uporządkowany. Pokażemy że istnieje w nim łańcuch maksymalny pod względem inkluzji. Najpierw znajdźmy jeden łańcuch- zawsze możemy znaleźć łańcuch pusty. A więc mamy jeden łańcuch, i ponieważ do tego łańcucha możemy dobrać większy łańcuch pod względem inkluzji maksymalny (na mocy zakładanego twierdzenia), no to mamy łańcuch maksymalny, co należało pokazać.[math]\square[/math]

Dowód wynikania w drugą stronę jest znacznie trudniejszy, więc go podamy później.

Kolejne równoważne aksjomatowi wyboru twierdzenie, to słynny Lemat Zorna:

Jeśli w zbiorze uporządkowanym [math]\left( X, \le \right)[/math] każdy łańcuch ma ograniczenie górne, to istnieje w [math]\left( X, \le \right)[/math] element maksymalny.

Dzięki temu twierdzeniu możemy uzyskać element maksymalny zbioru uporządkowanego. Łatwo pokazać, że Lemat Zorna jest równoważny twierdzeniu o maksymalnym łańcuchu.

Aby pokazać lemat Zorna, weźmy dowolny zbiór uporządkowany [math]\left( X, \le \right)[/math] taki, że każdy łańcuch jest ograniczony od góry. Pokażemy, że istnieje w [math]\left( X, \le \right)[/math] element maksymalny. Na mocy twierdzenia o maksymalnym łańcuchu znajdujemy maksymalny łańcuch pod względem inkluzji, nazwijmy go [math]A[/math]. Łańcuch ten ( jak każdy) posiada ograniczenie górne (nazwijmy je [math]a[/math]), które jest porównywalne z każdym elementem [math]A[/math], więc ponieważ [math]A[/math] jest maksymalnym łańcuchem to musi [math]a\in A[/math], a więc jest elementem [math]A[/math] i jest większe (słabo) od każdego elementu [math]A[/math] , zatem jest elementem największym [math]A[/math], i ten element największy [math]a[/math] w [math]A[/math], jest równocześnie elementem maksymalnym w całym [math]\left( X, \le \right)[/math]. Gdyby tak nie było, to istniałby element [math]a\lt b[/math]. Ponieważ element [math]b[/math] jest większy od największego elementu [math]A[/math], to [math]b\not\in A[/math]. Zatem [math]A\cup \left\{ b\right\}[/math] jest łańcuchem (co łatwo sprawdzić) istotnie większym od [math]A[/math] pod względem inkluzji, co przeczy maksymalności [math]A[/math]. Uzyskana sprzeczność kończy dowód. [math]\square[/math]

Jako przykład zastosowania Lematu Zorna udowodnimy twierdzenie o maksymalnym antyłańcuchu:

W każdym zbiorze uporządkowanym [math]\left( X, \le \right)[/math] istnieje maksymalny antyłańcuch pod względem inkluzji.

Czyli w zbiorze uporządkowanym możemy również zawsze znaleźć maksymalny antyłańcuch.

Dowód:

Ustalmy dowolny zbiór uporządkowany [math]\left( X, \le \right).[/math] Rozważmy rodzinę wszystkich antyłańcuchów:

[math]\mathbb{B}=\left\{ A\subset X\Bigl| \ A \hbox{ jest antyłańcuchem w } \left( X, \le \right)\right\}[/math]

i uporządkujmy ją inkluzją. Wykażemy, że każdy łańcuch w [math]\left( \mathbb{B}, \subset \right)[/math] ma ograniczenie górne.

Ustalmy w tym celu dowolny łańcuch [math]\mathbb{A}.[/math] Jako ograniczenie górne kładziemy [math]\bigcup\mathbb{A}[/math], wpierw jednak musimy zapewnić, że [math]\bigcup\mathbb{A} \in \mathbb{B}[/math]( ograniczenie górne musi być elementem zbioru uporządkowanego). Suma rodziny [math]\mathbb{A}[/math]- rodziny antyłańcuchów, podzbiorów [math]X[/math] będzie podzbiorem [math]X[/math]. Aby wykazać, że [math]\bigcup\mathbb{A}[/math] jest antyłańcuchem, weźmy dowolne dwa różne elementy [math]x,y\in\bigcup\mathbb{A}[/math]. Wtedy [math]x\in C[/math] dla pewnego zbioru [math]C\in\mathbb{A}[/math], oraz [math]y\in D[/math] dla pewnego zbioru [math]D\in\mathbb{A}[/math]. Ponieważ [math]\mathbb{A}[/math] jest łańcuchem pod względem inkluzji, to [math]C\subset D[/math] lub [math]D\subset C[/math]. Jeśli [math]C\subset D[/math], to [math]x,y\in D[/math]. Podobnie, w przeciwnym wypadku, jeśli [math]D\subset C[/math] to [math]x,y\in C[/math]. Czyli [math]x,y[/math] są w [math]D[/math] lub [math]x,y[/math] są w [math]C[/math]. Ponieważ [math]C,D\in\mathbb{A}[/math], zbiory [math]C,D[/math] są antyłańcuchami, więc ponieważ [math]x,y[/math] są różnymi elementami takiego antyłańcucha, wnioskujemy, że elementy [math]x,y[/math] są nieporównywalne. Pokazaliśmy, że dowolne dwa różne elementy [math]\bigcup\mathbb{A}[/math] są nieporównywalne, czyli [math]\bigcup\mathbb{A}[/math] jest antyłańcuchem, i należy do [math]\mathbb{B}[/math]. Ponieważ [math]\bigcup\mathbb{A}[/math] jest nadzbiorem każdego zbioru rodziny [math]\mathbb{A}[/math], czyli [math]\bigcup\mathbb{A}[/math] jest większa pod względem inkluzji od każdego zbioru [math]C\in\mathbb{A}[/math], stąd [math]\bigcup\mathbb{A}[/math] jest ograniczeniem górnym dla [math]\mathbb{A}[/math], tego łańcucha. Z dowolności wyboru zbioru [math]\mathbb{A}[/math] każdy łańcuch w [math]\left( \mathbb{B}, \subset \right)[/math] ma ograniczenie górne.

Stosując lemat Zorna wnioskujemy, że w zbiorze [math]\left( \mathbb{B}, \subset \right)[/math] jest element maksymalny. Jest to poszukiwany maksymalny antyłańcuch pod względem inkluzji.[math]\square[/math]

W sposób analogiczny (a nawet prostszy) można udowodnić przy pomocy Lematu Zorna dowieść twierdzenie o maksymalnym łańcuchu.

Twierdzenie Zermelo

Kolejne równoważne aksjomatowi wyboru twierdzenie to twierdzenie Zermelo. Mówi ono, że każdy zbiór da się dobrze uporządkować.

Twierdzenie Zermelo:

Dla każdego zbioru [math]X[/math] ( jeśli mamy dowolny zbiór, to można go dobrze uporządkować), a więc istnieje relacja w zbiorze [math]X[/math], która jest dobrym porządkiem na tym zbiorze.

Kolejny dowód to: Lemat Zorna [math]\Longrightarrow[/math] Twierdzenie Zermelo.

DOWÓD:

Ustalmy dowolny niepusty zbiór [math]X[/math]. (Dla zbioru pustego relacja pusta jest dobrym porządkiem na zbiorze pustym. Zbiór pusty jest liniowo uporządkowany, i zbiór pusty jest dobrze uporządkowany przez ten porządek pusty, gdyż każdy niepusty podzbiór zbioru pustego (a nie ma takich), więc każdy niepusty podzbiór zbioru pustego- będzie spełniał to co chcemy- czyli ma element najmniejszy, a więc jest to dobry porządek na zbiorze pustym, czyli zbiór pusty da się dobrze uporządkować). Dalej więc [math]X[/math] będzie dowolnym niepustym zbiorem.

Rozważmy rodzinę:

[math]\mathbb{B}=\left\{ \left( C,\sqsubseteq\right)\Bigl| \ \ C \subset X \wedge \sqsubseteq \hbox{ jest dobrym porządkiem na } C\right\}.[/math]

Będziemy mówić, że jest to rodzina wszystkich podzbiorów zbioru [math]X[/math] dobrze uporządkowanych wraz z dobrymi porządkami. Tam są wszystkie podzbiory zbioru [math]X[/math] dobrze uporządkowane, każdy element [math]\mathbb{B}[/math] jest podzbiorem [math]X[/math] dobrze uporządkowanym (wraz z dobrym porządkiem), ale nie wiemy, które konkretnie podzbiory [math]X[/math] załapują się jako elementy tej rodziny, czyli czy są dobrze uporządkowane. Nie wiemy na przykład czy istnieje chociaż jeden dobry porządek na całym zbiorze [math]X[/math]. Tego nie wiemy, i na razie się nie dowiemy, gdyż to chcemy właśnie pokazać (dopiero się dowiemy gdy zakończymy ten dowód). Określmy przepiękną relację [math]\preccurlyeq[/math] na elementach [math]\mathbb{B}[/math] jako:

[math]\left( C,\sqsubseteq \right) \preccurlyeq \left( C',\sqsubseteq' \right) \Longleftrightarrow C\subset C' \wedge \begin{cases} \bigwedge\limits_{x,y\in C} (x\sqsubseteq y \leftrightarrow x\sqsubseteq' y) \textrm{ oraz } \\ \ x\in C,y\in C'\setminus C\ \Longrightarrow x\sqsubseteq' y \end{cases}.[/math]

Relacja porządku na dobrych porządkach

Czyli jeden zbiór dobrze uporządkowany jest mniejszy od drugiego zbioru dobrze uporządkowanego dokładnie wtedy, gdy pierwszy zbiór na którym jest określony pierwszy dobry porządek jest mniejszy pod względem inkluzji od drugiego zbioru na którym jest określony drugi dobry porządek, i porządek na większym zbiorze jest rozszerzeniem porządku na mniejszym zbiorze, przez dodanie elementów większych od wszystkich zastanych. Mówiąc prościej dobry porządek jest większy od danego dobrego porządku, gdy jest jego rozszerzeniem, ale dodając wyłącznie elementy większe od danych. To tak naprawdę bardzo naturalne, co ilustruje rysunek obok.

Wykazujemy najpierw, że jest to relacja porządku na [math]\mathbb{B}.[/math]

1.Zwrotność, czyli czy [math](C,\sqsubseteq) \preccurlyeq (C,\sqsubseteq)[/math]. A więc niewątpliwie [math]C \subset C[/math], dla dowolnych [math]x,y\in C[/math] mamy [math]x\sqsubseteq y \Leftrightarrow x\sqsubseteq y[/math] oczywiście, i jeśli [math]x\in C, y\in C \setminus C=\left\{ \right\}[/math] więc warunek [math]x\sqsubseteq y[/math] będzie pusto spełniony, a więc (jako całość) będzie spełniony, a więc mamy, że[math](C,\sqsubseteq) \preccurlyeq (C,\sqsubseteq)[/math].

2.Antysymetria. Niech [math](C,\sqsubseteq) \preccurlyeq (C',\sqsubseteq')[/math] i [math](C',\sqsubseteq') \preccurlyeq (C,\sqsubseteq)[/math]. Z tego wynika, że [math]C \subset C'[/math] oraz [math]C' \subset C[/math], a więc [math]C=C'[/math]. Pokażemy że [math]\left( \sqsubseteq\right) =\left( \sqsubseteq'\right)[/math], to jednak łatwo wynika z warunku [math]\bigwedge\limits_{x,y\in C} (x\sqsubseteq y \Leftrightarrow x\sqsubseteq' y)[/math] i faktu, że te relacje są określone na tym samym zbiorze. A więc [math]\left( \sqsubseteq\right) =\left( \sqsubseteq'\right)[/math], i co za tym idzie [math](C,\sqsubseteq) = (C',\sqsubseteq')[/math], co kończy dowód antysymetrii.

3. Przechodniość. Niech [math](C,\sqsubseteq) \preccurlyeq (C',\sqsubseteq')[/math] i [math](C',\sqsubseteq') \preccurlyeq (C'',\sqsubseteq'')[/math]. Pokażemy że [math](C,\sqsubseteq) \preccurlyeq (C'',\sqsubseteq'')[/math]. Pierwsze założenie daje [math]C \subset C'[/math], drugie podobnie [math]C' \subset C''[/math], a więc z przechodniości inkluzji [math]C \subset C''[/math], co jest pierwszym z trzech warunków na to, by [math](C,\sqsubseteq) \preccurlyeq (C'',\sqsubseteq'')[/math]. Mamy dla dowolnych [math]x,y[/math] w [math]C[/math] mamy [math]x\sqsubseteq y \Leftrightarrow x\sqsubseteq' y[/math], a także dla dowolnych [math]x,y[/math] w [math]C'[/math] mamy [math]x\sqsubseteq' y \Leftrightarrow x\sqsubseteq'' y[/math]. Ponieważ [math]C \subset C'[/math], więc dla dowolnych [math]x,y[/math] w [math]C[/math] mamy [math]x\sqsubseteq' y \Leftrightarrow x\sqsubseteq'' y[/math]. Możemy zatem to połączyć (pierwszy i trzeci z tych wniosków), i otrzymać, że dla dowolnych [math]x,y[/math] w [math]C[/math] mamy [math](x\sqsubseteq y \Leftrightarrow x\sqsubseteq'' y)[/math], co jest drugim sprawdzanym warunkiem. Niech [math]x\in C, y\in C''\setminus C[/math]. Pokażemy, że [math]x\sqsubseteq'' y[/math]. Ponieważ [math]x\in C \subset C'[/math], to [math]x\in C'[/math], i jeśli, [math]y\in C''\setminus C'[/math], to [math]x\sqsubseteq'' y[/math], co chciałem wykazać. Pozostaje zatem do rozważenia przypadek gdy: [math]y\not\in C''\setminus C'[/math] i [math]y\in C''\setminus C[/math] (założenia), czyli [math]y \in C'', y\not\in C, y \in C'[/math], mamy więc [math]x\in C,y\in C'\setminus C[/math], więc wnioskujemy, że [math]x\sqsubseteq' y[/math], i ponieważ [math]\sqsubseteq''[/math] rozszerza [math]\sqsubseteq'[/math], a więc [math]x\sqsubseteq'' y[/math], co było trzecim ostatnim warunkiem. A więc [math](C,\sqsubseteq) \preccurlyeq (C'',\sqsubseteq'')[/math].[math]\square[/math]

A więc [math]\left( \mathbb{B},\preccurlyeq\right)[/math] jest zbiorem uporządkowanym. Aby móc zastosować do takiego zbioru uporządkowanego Lemat Zorna musimy wykazać, że każdy łańcuch w [math]\left( \mathbb{B},\preccurlyeq\right)[/math] ma ograniczenie górne.

Niech [math]\mathbb{D}\subset \mathbb{B}[/math] będzie łańcuchem w sensie [math]\preccurlyeq[/math]. Zdefiniujmy:

[math]S= \bigcup\left\{ C\subset X\Bigl| \ \ \bigvee\limits_{ R\subset X\times X} \left( C,R\right) \in\mathbb{D} \right\}[/math] oraz [math]\le := \bigcup\left\{ R\subset X \times X\Bigl| \ \ \bigvee\limits_{ C\subset X } \left( C,R\right) \in\mathbb{D} \right\}.[/math]

Tzn. zbiór [math]S[/math] to suma wszystkich zbiorów dobrze uporządkowanych z łańcucha [math]\mathbb{D}[/math], a [math]\le[/math] jest sumą tych dobrych porządków określonych na tych zbiorach. Nim sprawdzimy, że [math]\left( S, \le \right)[/math] jest ograniczeniem górnym tego łańcucha musimy zapewnić niestety, że [math]\left( S, \le \right) \in \mathbb{B}.[/math] Niewątpliwie [math]S\subset X[/math]. jako suma rodziny podzbiorów [math]X[/math]. Ponieważ elementy [math]\mathbb{D}[/math] są zbiorami dobrze uporządkowanymi (a więc i liniowo) , ponieważ [math]\mathbb{D}[/math] jest łańcuchem w sensie [math]\preccurlyeq[/math], więc tzn. między innymi, że dla dowolnych takich dwóch liniowych porządków jeden jest rozszerzeniem drugiego, więc w myśl twierdzenia z rozdziału Zbiory Uporządkowane ( pod koniec) [math]\le[/math] jest liniowym porządkiem na swoim polu. Łatwo się przekonać, że tym polem jest dokładnie zbiór [math]S[/math]. Aby wykazać, że [math]\le[/math] jest dobrym porządkiem na [math]S[/math], weźmy dowolny niepusty zbiór [math]A\subset S.[/math] Ponieważ [math]A[/math] jest niepustym podzbiorem sumy zbiorów, więc istnieje zbiór [math](C,\sqsubseteq) \in \mathbb{D}[/math], taki, że [math]C \cap A \neq \left\{ \right\}[/math] , że ten zbiór [math]A[/math] ten zbiór [math]C[/math] przecina. Ponieważ [math](C,\sqsubseteq) \in \mathbb{D} \subset \mathbb{B}[/math], to [math](C,\sqsubseteq)[/math] jest zbiorem dobrze uporządkowanym, w związku z czym zbiór [math]C \cap A[/math] ma element najmniejszy w [math](C,\sqsubseteq)[/math], oznaczmy go przez [math]x[/math]. Element najmniejszy [math]x[/math] w [math]C \cap A[/math] jest elementem tego zbioru, a więc jest również elementem [math]A- x\in A[/math]. Element [math]x[/math] będzie również elementem najmniejszym [math]A[/math] w [math]\left( S, \le \right).[/math] Aby to wykazać, niech [math]y\in A.[/math] Jeśli [math]y\in C[/math], to [math]y\in C \cap A[/math], a ponieważ [math]x[/math] jest elementem najmniejszym w [math]C \cap A \neq \left\{ \right\}[/math] względem [math]\sqsubseteq[/math], to [math]x\sqsubseteq y[/math], a więc tymbardziej ([math](C,\sqsubseteq) \in \mathbb{D}[/math]), a więc [math]x \le y[/math], A więc [math]x[/math] jest mniejszy od [math]y[/math]. Jeśli [math]y\not\in C[/math], ponieważ przecież [math]y\in A[/math], więc [math]y\in C'[/math] dla pewnego [math](C',\sqsubseteq')\in\mathbb{D}[/math], wtedy również [math]y\in C' \setminus C.[/math] Ponieważ [math]\mathbb{D}[/math] jest łańcuchem elementy [math](C',\sqsubseteq')\in\mathbb{D}[/math] oraz [math](C,\sqsubseteq) \in \mathbb{D}[/math], są porównywalne, przypadek [math](C',\sqsubseteq')\preccurlyeq (C,\sqsubseteq)[/math] zajść nie może, bo on prowadzi do [math]C' \subset C[/math], co stoi w sprzeczności z tym, że [math]y\in C' \setminus C[/math], wobec czego musi zajść relacja w drugą stronę, czyli [math](C,\sqsubseteq)\preccurlyeq (C',\sqsubseteq')[/math] , więc stosując trzecią część definicji do [math]x\in C[/math] oraz [math]y\in C' \setminus C[/math] wnioskujemy, że [math]x\sqsubseteq'y,[/math] a więc tym bardziej [math]x \le y[/math], a więc również [math]x[/math] jest mniejszy od [math]y[/math]. Wnioskujemy, że [math]x[/math] jest najmniejszym elementem [math]A[/math], względem [math]\le[/math]. Z dowolności wyboru zbioru [math]A[/math], każdy niepusty podzbiór [math]S[/math] ma element najmniejszy, względem [math]\le[/math]. A więc [math]\left( S, \le \right)[/math] jest zbiorem dobrze uporządkowanym, mamy też [math]S\subset X[/math], zatem mamy podzbiór zbioru [math]X[/math] dobrze uporządkowany, a więc element zbioru [math]\mathbb{B}[/math]. Należy teraz sprawdzić, że taki element [math]\left( S, \le \right)[/math] jest ograniczeniem górnym tego łańcucha. W tym celu niech [math](C,\sqsubseteq) \in \mathbb{D}.[/math] Należy pokazać, że [math](C,\sqsubseteq) \preccurlyeq \left( S, \le \right)[/math]. Z własności sumy spełniony jest punkt pierwszy w definicji [math]\preccurlyeq[/math], tzn. [math]C\subset S.[/math] Jak również spełniony jest punkt drugi na podobnej zasadzie. Aby sprawdzić punkt trzeci to niech [math]x\in C, y\in S \setminus C.[/math] Wtedy [math]y\not\in C[/math], więc w sposób analogiczny jak wcześniej sprawdzamy, że [math]x \le y[/math]. A więc spełniony jest również punkt trzeci, więc [math](C,\sqsubseteq) \preccurlyeq \left( S, \le \right)[/math], i z dowolności wyboru [math](C,\sqsubseteq)[/math] elementu [math]\mathbb{D}[/math] otrzymujemy, że [math]\left( S, \le \right)[/math] jest ograniczeniem górnym dla [math]\mathbb{D}[/math]- tego łańcucha, i z dowolności wyboru łańcucha [math]\mathbb{D}[/math] każdy łańcuch w [math]\left( \mathbb{B},\preccurlyeq\right)[/math] ma ograniczenie górne.

Stosując Lemat Zorna wnioskujemy, że w zbiorze uporządkowanym [math]\left( \mathbb{B},\preccurlyeq\right)[/math] jest element maksymalny. Taki element maksymalny jest elementem zbioru uporządkowanego [math]\mathbb{B}[/math], czyli w tym wypadku podzbiorem zbioru [math]X[/math] dobrze uporządkowanym, oznaczmy go [math]\left( C,\sqsubseteq\right)[/math]. Jeśli zatem [math]C=X[/math], to ten dobry porządek [math]\sqsubseteq[/math] na zbiorze [math]C[/math] równym [math]X[/math] świadczy o tym, że zbiór [math]X[/math] da się dobrze uporządkować. Pozostaje przyjąć dla dowodu nie wprost, że tak nie jest. Przypominam, element maksymalny [math]\left( C,\sqsubseteq\right)[/math] jest podzbiorem zbioru [math]X[/math] dobrze uporządkowanym. Przypuszczamy dla dowodu nie wprost, że jest on określony na istotnym podzbiorze [math]X[/math]. Istnieje wtedy element [math]a\in X \setminus C[/math]. Ustalmy taki element [math]a[/math]. A wtedy zbiór [math]C \cup \left\{ a\right\}[/math] wraz z dobrym porządkiem określonym jako :

[math]x\sqsubseteq' y \iff y=a \lor (x\in C\land y\in C \land x\sqsubseteq y).[/math]

Jest to zbiór [math]C[/math] z dodanym jednym elementem [math]a[/math] jako największym. Jest to dobry porządek, gdyż [math]\sqsubseteq[/math] był dobrym porządkiem na [math]C[/math], zatem [math]\left( C \cup \left\{ a\right\},\sqsubseteq'\right)[/math] jest również zbiorem dobrze uporządkowanym, podzbiorem zbioru [math]X[/math] dobrze uporządkowanym, zatem jest elementem [math]\mathbb{B}[/math]. I jest elementem silnie większym w sensie [math]\preccurlyeq[/math] od elementu maksymalnego [math]\left( C,\sqsubseteq\right)[/math]. Jest od niego różny, bo jest określony na innym zbiorze, na większym zbiorze o jeden element [math]a[/math], zatem są to różne zbiory dobrze uporządkowane, i [math]\left( C \cup \left\{ a\right\},\sqsubseteq'\right)[/math] jest większy od [math]\left( C,\sqsubseteq\right)[/math] w sensie [math]\preccurlyeq[/math], gdyż jest jego rozszerzeniem przez dodanie jednego elementu [math]a[/math] większego od wszystkich zastanych, więc jest większy względem [math]\preccurlyeq[/math]. A ponieważ [math]\left( C,\sqsubseteq\right)[/math] był elementem maksymalnym, to nie ma w [math]\mathbb{B}[/math] elementów od niego silnie większych. Otrzymaliśmy więc sprzeczność, która kończy rozumowanie.[math]\square[/math]

Znaczenie tego twierdzenia podamy później.