Tekst źródłowy strony Logika i teoria mnogości/Wykład 12: Twierdzenie o indukcji. Liczby porządkowe. Zbiory liczb porządkowych. Twierdzenie o definiowaniu przez indukcje pozaskończoną

==Wprowadzenie==

W poniższym wykładzie przyjrzymy się dokładnie zbiorom dobrze uporządkowanym. Jedną z
ważniejszych własności tych zbiorów jest to, że prawdziwa jest w nich uogólniona zasada
indukcji zwana "indukcją pozaskończoną". Jest to szczególnie istotne w kontekście
twierdzenia Zermelo które mówi, że każdy zbiór da się dobrze uporządkować. Możemy
dzięki temu przeprowadzać dowody indukcyjne oraz definiować nowe funkcje za pomocą
indukcji pozaskończonej na zbiorach większych niż przeliczalne.

==Dobre uporządkowanie==

Przypomnijmy, że zbiorem ''dobrze uporządkowanym'' nazywamy zbiór częściowo
uporządkowany, w którym każdy niepusty podzbiór ma element najmniejszy. Wynika stąd,
że również w całym zbiorze musi istnieć element najmniejszy, o ile tylko zbiór jest
niepusty.

{{przyklad|2.1.||

Przykładem zbioru dobrze uporządkowanego jest zbiór <math>\displaystyle \mathbb{N}</math> uporządkowany, przez
<math>\displaystyle \subset</math>.
Zasada minimum (patrz 
[[Logika i teoria mnogości/Wykład 7: Konstrukcja von Neumanna liczb naturalnych, twierdzenie o indukcji, zasady minimum, maksimum, definiowanie przez indukcje#twierdzenie_5_2|Wykład 7, Twierdzenie 5.2]]) mówi, że w każdym podzbiorze <math>\displaystyle \mathbb{N}</math> istnieje element najmniejszy, a więc, że ten porządek jest dobry.
}}

{{cwiczenie|2.2||

Udowodnij, że każdy dobry porządek jest porządkiem liniowym.

}}

<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none">  

Rozważ podzbiory dwuelementowe.

</div></div>

<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">  

Niech <math>\displaystyle (X,\leq)</math> będzie dobrym porządkiem. Jeśli <math>\displaystyle X</math> jest pusty lub jednoelementowy, to jest dobrze uporządkowany. W przeciwnym przypadku weźmy dowolne dwa różne elementy <math>\displaystyle x,y \in X</math>. Wtedy <math>\displaystyle \{x,y\} \subset X</math> i istnieje element minimalny w <math>\displaystyle \{x,y\}</math>, a więc <math>\displaystyle x \leq y</math> lub <math>\displaystyle y\leq x</math>. Wobec tego dowolne dwa elementy <math>\displaystyle X</math> są porównywalne.
</div></div>

Zbiory dobrze uporządkowane mają bardzo specyficzną strukturę. Jedną z własności jest istnienie następników dla prawie wszystkich elementów.

{{definicja|2.3.||

W zbiorze uporządkowanym <math>\displaystyle (X,\leq)</math> element <math>\displaystyle y</math> nazywamy ''następnikiem''
elementu <math>\displaystyle x</math>, jeśli <math>\displaystyle x \leq y</math>, <math>\displaystyle x\neq y</math> oraz każdy element silnie większy od <math>\displaystyle x</math>
jest nie mniejszy od <math>\displaystyle y</math> (czyli <math>\displaystyle (x \leq z \wedge x \neq z) \Rightarrow y\leq z</math>).
}}
{{cwiczenie|2.4||

Podaj przykład zbioru uporządkowanego, w którym żaden element nie ma następnika.

}}

<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">  

Zbiór liczb wymiernych uporządkowany naturalną relacją mniejszości ma tę
własność. Przypuśćmy, że istnieje liczba <math>\displaystyle x\in \mathbb{Q}</math>, która ma następnik, oznaczymy go
przez <math>\displaystyle y</math>. Wtedy <math>\displaystyle x<y</math> wobec tego:

<center><math>\displaystyle x<\frac{x+y}{2} < y.
</math></center>

Ponieważ <math>\displaystyle \frac{x+y}{2}</math> jest liczbą wymierną to otrzymujemy sprzeczność z definicją
następnika.
</div></div>

<span id="twierdzenie_2_5">{{twierdzenie|2.5.||

W zbiorze dobrze uporządkowanym każdy element, który nie jest elementem największym, ma następnik.
}}</span>

{{dowod|||

Niech <math>\displaystyle (X,\leq)</math> będzie zbiorem dobrze uporządkowanym. Niech <math>\displaystyle x</math> będzie dowolnym elementem zbioru <math>\displaystyle X</math>, który nie jest elementem największym. Zdefiniujmy zbiór <math>\displaystyle A</math> następująco:

<center><math>\displaystyle A= \{y\in X: x<y\}.
</math></center>

Zbiór <math>\displaystyle A</math> jest niepusty, gdyż <math>\displaystyle x</math> nie jest elementem największym. Ponieważ <math>\displaystyle X</math> jest
dobrze uporządkowany, to w zbiorze <math>\displaystyle A</math> istnieje element najmniejszy, nazwijmy go <math>\displaystyle y</math>.
Pokażemy, że jest następnikiem <math>\displaystyle x</math>. Ponieważ <math>\displaystyle y\in A</math>, to <math>\displaystyle x<y</math>. Weźmy dowolny element
<math>\displaystyle z\in X</math>, który jest silnie większy od <math>\displaystyle x</math>. Wtedy <math>\displaystyle z</math> musi należeć do <math>\displaystyle A</math>, a więc
ponieważ <math>\displaystyle y</math> jest najmniejszy w <math>\displaystyle A</math>, to <math>\displaystyle y\leq z</math>. Wobec tego <math>\displaystyle y</math> jest następnikiem
elementu <math>\displaystyle x</math>.
}}

{{definicja|2.6.||

Element zbioru dobrze uporządkowanego nazywamy ''elementem granicznym'', jeśli nie jest następnikiem, żadnego elementu.
}}
{{cwiczenie|2.7||

Podaj przykład zbioru uporządkowanego liniowo, w którym każdy element ma
następnik, a zbiór nie jest dobrze uporządkowany. Czy zbiór tak uporządkowany może
mieć element najmniejszy?     
}}

<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">  

Przykładem takiego zbioru może być zbiór liczb całkowitych uporządkowany przez naturalną relację mniejszości. Wtedy dla dowolnego elementu <math>\displaystyle x\in \mathbb{Z}</math>, jego następnikiem jest <math>\displaystyle x+1</math>, a zbiór ten nie jest dobrze uporządkowany, gdyż na przykład cały zbiór <math>\displaystyle \mathbb{Z}</math> nie ma elementu najmniejszego.

Można też skonstruować taki zbiór spełniający wymagania ćwiczenia, który ma element minimalny. Rozważmy zbiory <math>\displaystyle A= \mathbb{N}\times \{0\}</math> oraz <math>\displaystyle B= \mathbb{Z} \times \{1\}</math>. Zauważmy, że zbiory te są rozłączne. Zbiór <math>\displaystyle A</math> uporządkujemy relacją <math>\displaystyle \leq_A</math> zdefiniowaną następująco:
<center><math>\displaystyle (x,0) \leq_A (y,0) \Leftrightarrow  x \leq_{\mathbb{N}} y,
</math></center>

gdzie <math>\displaystyle \leq_\mathbb{N}</math> jest naturalną relacją mniejszości na liczbach naturalnych. Analogicznie dla zbioru <math>\displaystyle B</math> zdefiniujemy relację <math>\displaystyle \leq_B</math>:

<center><math>\displaystyle (x,1) \leq_B (y,1) \Leftrightarrow  x \leq_{\mathbb{Z}} y,
</math></center>

gdzie <math>\displaystyle \leq_\mathbb{Z}</math> jest naturalną relacją mniejszości na liczbach całkowitych. Rozważmy teraz zbiór <math>\displaystyle C=A\cup B</math> który uporządkujemy relacją <math>\displaystyle \leq_A \cup \leq_B \cup A \times B</math>. Innymi słowy, w zbiorze <math>\displaystyle C</math> porządek pomiędzy elementami zbioru <math>\displaystyle A</math> jest zgodny z <math>\displaystyle \leq_A</math>, porządek pomiędzy elementami zbioru <math>\displaystyle B</math> jest zgodny z <math>\displaystyle \leq_B</math> oraz każdy element zbioru <math>\displaystyle A</math> jest mniejszy od każdego elementu zbioru <math>\displaystyle B</math>. W zbiorze <math>\displaystyle C</math> każdy element ma następnik, gdyż każdy element zbioru <math>\displaystyle A</math> ma następnik w <math>\displaystyle A</math> i każdy element zbioru <math>\displaystyle B</math> ma następnik w <math>\displaystyle B</math>. Zbiór <math>\displaystyle C</math> nie jest dobrze uporządkowany, gdyż <math>\displaystyle B\subset C</math> nie ma elementu najmniejszego.
</div></div>

Pokażemy teraz, że każdy  zbiór <math>\displaystyle (X,\leq)</math> dobrze uporządkowany jest podobny do pewnej rodziny zbiorów uporządkowanych przez inkluzję.

{{definicja|2.8.||

Niech <math>\displaystyle (X,\leq)</math> będzie zbiorem uporządkowanym. Zbiór <math>\displaystyle A\subset X</math> nazywamy przedziałem początkowym <math>\displaystyle (X,\leq)</math> jeśli

<center><math>\displaystyle \forall_{x\in A} \forall_{y\in X} ( y\leq x \Rightarrow y\in A ).
</math></center>
}}
Czyli <math>\displaystyle A</math> jest przedziałem początkowym, jeśli wraz z każdym swoim elementem zawiera także wszystkie elementy zbioru <math>\displaystyle X</math>, które są od niego mniejsze. Będziemy używać następujących oznaczeń, dla <math>\displaystyle x_0\in X</math> niech:
<center><math>\displaystyle O(x_0)=\{x\in X: x < x_0\}
</math></center>

oraz:

<center><math>\displaystyle \overline{O(x_0)}=\{x\in X: x \leq x_0\}.
</math></center>

Zbiór <math>\displaystyle         \overline{O(x_0)}</math> będziemy nazywać  domkniętym przedziałem początkowym.

<span id="twierdzenie_2_9">{{twierdzenie|2.9.||

Jeśli <math>\displaystyle (X,\leq)</math> będzie zbiorem dobrze uporządkowanym. Wtedy każdy jego przedział
początkowy, różny od <math>\displaystyle X</math>, jest postaci <math>\displaystyle \{x\in X: x < x_0\}</math>, dla pewnego elementu
<math>\displaystyle x_0\in X</math> (czyli każdy przedział początkowy jest postaci <math>\displaystyle O(x_0)</math>).
}}</span>

{{dowod|||

Niech <math>\displaystyle A</math> będzie przedziałem początkowym <math>\displaystyle X</math> różnym od <math>\displaystyle X</math>. Wtedy zbiór
<math>\displaystyle X\setminus A</math> jest niepusty i jest podzbiorem <math>\displaystyle X</math>, więc posiada element najmniejszy,
oznaczmy go przez <math>\displaystyle x_0</math>. Pokażemy, że <math>\displaystyle A=O(x_0)</math>. Przypuśćmy, że istnieje
element <math>\displaystyle y\in X</math> taki, że <math>\displaystyle y\in A</math> oraz  <math>\displaystyle x_0\leq y</math>. Wtedy ponieważ <math>\displaystyle A</math> jest
przedziałem początkowym, to <math>\displaystyle x_0</math> również musiałby być elementem <math>\displaystyle A</math>, co jest sprzeczne
z tym, że <math>\displaystyle x_0\in X\setminus A</math>. Wobec tego wszystkie elementy <math>\displaystyle A</math> są silnie mniejsze
od <math>\displaystyle x_0</math>. Przypuśćmy teraz, że istnieje element <math>\displaystyle y\in X</math>, który jest silnie mniejszy
od <math>\displaystyle x_0</math> i nie należy do <math>\displaystyle A</math>. Wtedy <math>\displaystyle y\in X \setminus A</math> i ponieważ jest silnie
mniejszy od <math>\displaystyle x_0</math>, to dostajemy sprzeczność z faktem, że <math>\displaystyle x_0</math> jest najmniejszy w tym
zbiorze. Wobec tego zbiór <math>\displaystyle A</math> składa się dokładnie z elementów silnie mniejszych od
<math>\displaystyle x_0</math>, co oznacza, że <math>\displaystyle A=O(x_0)</math>.
}}

{{cwiczenie|2.10||

Podaj przykład zbioru dobrze uporządkowanego <math>\displaystyle X</math>, w którym istnieje przedział
początkowy różny od <math>\displaystyle X</math>, który nie jest postaci <math>\displaystyle \{x\in X: x \leq x_0\}</math> (uwaga!
nierówność jest słaba).
}}
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none">
Dodaj jeden element do zbioru liczb naturalnych. 
</div></div>

<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">  

Rozważmy zbiór liczb naturalnych <math>\displaystyle \mathbb{N}</math> oraz jeden element, który nie należy do <math>\displaystyle \mathbb{N}</math>. Oznaczymy go przez <math>\displaystyle \top</math> (w roli <math>\displaystyle \top</math> może występować na przykład <math>\displaystyle \mathbb{N}</math>, ponieważ wiemy, że żaden zbiór nie jest swoim własnych elementem). Zbiór <math>\displaystyle \mathbb{N} \cup \{\top\}</math> oznaczymy przez <math>\displaystyle \mathbb{N}'</math> i uporządkujemy relacją <math>\displaystyle \leq_\mathbb{N} \cup \mathbb{N} \times\{\top\}</math>, gdzie <math>\displaystyle \leq_\mathbb{N}</math> jest naturalnym porządkiem pomiędzy liczbami z <math>\displaystyle \mathbb{N}</math>. Relację tę będziemy oznaczać przez <math>\displaystyle \leq</math> . Tak zdefiniowana relacja zachowuje porządek <math>\displaystyle \leq_\mathbb{N}</math> pomiędzy liczbami naturalnymi oraz określa element <math>\displaystyle \top</math> jako element największy w <math>\displaystyle \mathbb{N}'</math>. Łatwo sprawdzić, że zbiór ten jest dobrze uporządkowany. Pokażemy, że zbiór <math>\displaystyle \mathbb{N}</math> jest odcinkiem początkowym w <math>\displaystyle \mathbb{N}'</math>, który nie jest postaci <math>\displaystyle \{x\in X: x \leq x_0\}</math>. Zbiór <math>\displaystyle \mathbb{N}</math> jest odcinkiem początkowym, gdyż <math>\displaystyle \top </math> jest elementem największym w <math>\displaystyle \mathbb{N}'</math>. Istnieje elementu <math>\displaystyle x_0 \in \mathbb{N}'</math> takiego, że <math>\displaystyle \mathbb{N}=\{x\in X: x \leq x_0\}</math> oznaczałoby, iż istnieje największa liczba naturalna, gdyż <math>\displaystyle x_0</math> musiałby należeć do <math>\displaystyle \mathbb{N}</math>. Wobec tego taki element nie istnieje.
</div></div>

{{cwiczenie|2.11||

Udowodnij, że dla każdego dobrego porządku <math>\displaystyle (X,\leq)</math> istnieje funkcja, która niepustym podzbiorom <math>\displaystyle X</math> przypisuje ich element najmniejszy. Funkcje tę nazywamy <math>\displaystyle \min: \mathcal{P}(X) \setminus \left\{\emptyset\right\} \rightarrow X</math>.

}}

<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">  

Zdefiniujemy zbiór <math>\displaystyle \min</math>  następująco:

<center><math>\displaystyle \min = \{z\in \mathcal{P}(\mathcal{P}(\mathcal{P}(X)\cup X)): \exists_{A\in \mathcal{P}(X)}\exists_{a\in X} [ z=(A,a)
\wedge \forall_{b\in A} a\leq b ] \}.
</math></center>

Istnienie zbioru <math>\displaystyle \min</math> wynika z aksjomatu wyróżniania. Jest to funkcja częściowa, ponieważ istnieje co najwyżej jeden element najmniejszy w każdym podzbiorze <math>\displaystyle A</math>. <math>\displaystyle \min</math> jest funkcją totalną, ponieważ <math>\displaystyle A</math> jest dobrze uporządkowany, a więc w każdym podzbiorze istnieje element najmniejszy.
</div></div>

W poniższym twierdzeniu przedstawiamy konstrukcję rodziny zbiorów uporządkowanej przez <math>\displaystyle \subset</math> podobnej do danego zbioru dobrze uporządkowanego.

<span id="twierdzenie_2_12">{{twierdzenie|2.12||

Niech <math>\displaystyle (X,\leq)</math> będzie zbiorem dobrze uporządkowanym, a <math>\displaystyle \mathcal{R}</math> będzie
zbiorem jego istotnych przedziałów początkowych. Wtedy <math>\displaystyle (X,\leq)</math> jest podobny do
<math>\displaystyle (\mathcal{R},\subseteq)</math>.
}}</span>

{{dowod|||
Zdefiniujmy funkcję <math>\displaystyle f:X \rightarrow \mathcal{R}</math>, tak aby <math>\displaystyle f(x)=O(x)</math>. Pokażemy, że ta
funkcja ustala podobieństwo. Pokażemy po kolei, że jest suriekcją , iniekcją oraz że
jest monotoniczna:
# Suriektywność funkcji <math>\displaystyle f</math> wynika z Twierdzenia 2.9 (patrz [[#twierdzenie_2_9|Twierdzenie 2.9]]).
# Weźmy dowolne <math>\displaystyle x,y \in X</math> takie, że <math>\displaystyle x <y</math>. Wtedy z definicji <math>\displaystyle  x \in O(y)</math> oraz <math>\displaystyle x\notin O(x)</math>, a więc <math>\displaystyle f(x)\neq f(y)</math>.
# Weźmy dowolne <math>\displaystyle x,y \in X</math> takie, że <math>\displaystyle x <y</math>. Weźmy dowolny <math>\displaystyle z\in f(x)</math>.
Oznacza to, że <math>\displaystyle z\in O(x)</math>, a więc <math>\displaystyle z<x</math>. Wtedy również <math>\displaystyle z<y</math>, a więc <math>\displaystyle z\in O(y)=f(y)</math>.
Wobec dowolności wyboru <math>\displaystyle z</math> otrzymujemy <math>\displaystyle f(x) \subset f(z)</math>, a więc funkcja <math>\displaystyle f</math> jest monotoniczna.

}}

Zauważmy, że własność bycia dobrym porządkiem jest przenoszona przez podobieństwo
porządków.

{{cwiczenie|2.13||

Jeśli porządki <math>\displaystyle (X,\leq_X)</math> oraz <math>\displaystyle (Y,\leq_Y)</math> są podobne, to <math>\displaystyle (X,\leq_X)</math> jest dobry wtedy i tylko wtedy, gdy <math>\displaystyle (Y,\leq_Y)</math> jest dobry.
}}

<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">  

Ze względu na symetrię wykażemy implikację tylko w jedną stronę. Niech <math>\displaystyle f:X\rightarrow Y</math> będzie monotoniczną bijekcją. Przypuśćmy, że <math>\displaystyle (X,\leq_X)</math>  jest dobry. Weźmy dowolny niepusty podzbiór <math>\displaystyle A\subset Y</math>. Pokażemy, że jego najmniejszy element to <math>\displaystyle a= f(\min(\vec{f}^{-1}(A)))</math>. Z własności przeciwobrazu otrzymujemy, że <math>\displaystyle a\in A</math>. Weźmy dowolny element <math>\displaystyle b\in A</math>. Ponieważ <math>\displaystyle f</math> jest bijekcją, to istnieje element <math>\displaystyle c\in X</math> taki, że <math>\displaystyle f(c)=b</math>. Oznacza to również, że <math>\displaystyle c\in \vec{f}^{-1}(A)</math>, a wtedy

<center><math>\displaystyle \min(\vec{f}^{-1}(A)) \leq_X c,
</math></center>

wobec tego z monotoniczności <math>\displaystyle f</math> otrzymujemy:

<center><math>\displaystyle a=f(  \min(\vec{f}^{-1}(A))) \leq_Y  f(c)=b,
</math></center>

a więc <math>\displaystyle a\leq b</math>, czyli element <math>\displaystyle a</math> jest najmniejszym elementem <math>\displaystyle A</math>. Wynika stąd, że <math>\displaystyle (Y,\leq_Y)</math> jest dobry.
</div></div>

{{cwiczenie|2.14||

Dla zbiorów  uporządkowanych <math>\displaystyle (X,\leq_X)</math>, <math>\displaystyle (Y,\leq_Y)</math> porządek leksykograficzny <math>\displaystyle \prec \subset X\times Y</math> definiujemy tak, że:

<center><math>\displaystyle (a,b) \prec (c,d) \Leftrightarrow (a\leq_X c) \vee (a=c \wedge b\leq_Y c),
</math></center>

Dla zbiorów <math>\displaystyle \{0,1\},\mathbb{N}, \mathbb{Z}, \mathbb{R}</math> uporządkowanych w naturalny sposób, sprawdź,
czy następujące ich produkty są dobrze uporządkowane:
# <math>\displaystyle \{0,1\} \times \mathbb{N}</math>,
# <math>\displaystyle \mathbb{N} \times \mathbb{N}</math>,
# <math>\displaystyle \mathbb{Z} \times \mathbb{N}</math>,
# <math>\displaystyle \mathbb{N} \times \mathbb{Z}</math>.

}}

<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">  
1. Tak, porządek leksykograficzny na zbiorze <math>\displaystyle \{0,1\} \times \mathbb{N}</math> jest dobrym porządkiem. Rozważmy dowolny niepusty podzbiór <math>\displaystyle A \subset (\{0,1\} \times \mathbb{N})</math>, pokażemy, że istnieje w nim element najmniejszy. Zbiór <math>\displaystyle A</math> możemy podzielić na dwa podzbiory <math>\displaystyle A_0,A_1</math> tak, że <math>\displaystyle A_0= A \cap (\{0\}\times \mathbb{N})</math> oraz <math>\displaystyle A_1= A \cap (\{1\} \times \mathbb{N})</math>. Wtedy zbiory <math>\displaystyle A_0,A_1</math> są rozłączne oraz <math>\displaystyle A_0 \cup A_1= A</math>. Ponadto każdy element ze zbioru <math>\displaystyle A_0</math> jest mniejszy od każdego elementu ze zbioru <math>\displaystyle A_1</math>.

Przypuśćmy, że zbiór <math>\displaystyle A_0</math> jest niepusty. Ponieważ <math>\displaystyle (\{0\}\times \mathbb{N},\prec)</math> jest podobny do <math>\displaystyle (\mathbb{N},\leq)</math>, to <math>\displaystyle (\{0\}\times \mathbb{N},\prec)</math> jest dobrym porządkiem, a więc skoro <math>\displaystyle A_0 \subset (\{0\}\times \mathbb{N},\prec)</math>, to istnieje w <math>\displaystyle A_0</math> element najmniejszy <math>\displaystyle a_0</math>. Ponieważ <math>\displaystyle a_0</math> jest mniejszy od każdego elementu <math>\displaystyle A_1</math>, to jest elementem najmniejszym w <math>\displaystyle A</math>.

Jeśli zbiór <math>\displaystyle A_0</math> jest pusty, to analogiczne rozumowanie dla zbioru <math>\displaystyle A_1</math> pokaże, że w <math>\displaystyle A_1</math> jest element najmniejszy. Ponieważ w takim przypadku <math>\displaystyle A_1=A</math>, to ten element jest najmniejszy w <math>\displaystyle A</math>.

2. Tak, porządek leksykograficzny na zbiorze <math>\displaystyle \mathbb{N} \times \mathbb{N}</math> jest dobrym porządkiem. Pokażemy, że jego każdy niepusty podzbiór ma element najmniejszy. Niech <math>\displaystyle A\subset \mathbb{N} \times \mathbb{N}</math> będzie niepusty. Niech <math>\displaystyle B= A_L</math>, czyli <math>\displaystyle B</math> jest zbiorem liczb naturalnych które występują na pierwszej współrzędnej jakiejś pary ze zbioru <math>\displaystyle A</math>. Ponieważ <math>\displaystyle B\subset \mathbb{N}</math> to w <math>\displaystyle B</math> istnieje element najmniejszy w sensie naturalnego porządku w <math>\displaystyle \mathbb{N}</math>, oznaczmy go przez <math>\displaystyle b</math>. Rozważmy teraz zbiór <math>\displaystyle A_b=A \cap (\{b\} \times \mathbb{N})</math>. Zbiór ten jest niepusty, ze względu na wybór elementu <math>\displaystyle b</math>. Porządek <math>\displaystyle (A_{\{b\} \times \mathbb{N}},\prec)</math> jest podobny do <math>\displaystyle (\mathbb{N},\leq)</math>, wobec tego istnieje w nim element najmniejszy, oznaczmy go przez <math>\displaystyle a</math>. Pokażemy, że <math>\displaystyle a</math> jest najmniejszy w <math>\displaystyle a</math>. Weźmy dowolny element <math>\displaystyle x\in A</math>. Jeśli pierwsza współrzędna <math>\displaystyle x</math> jest różna od <math>\displaystyle b</math>, to z konstrukcji <math>\displaystyle b</math> wynika, że jest większa od <math>\displaystyle b</math> wobec tego z definicji porządku <math>\displaystyle \prec</math> otrzymujemy <math>\displaystyle a\prec x</math>. Jeśli pierwsza współrzędna <math>\displaystyle x</math> jest równa <math>\displaystyle b</math>, to <math>\displaystyle x\in A_b</math> i z konstrukcji <math>\displaystyle a</math> wynika, że <math>\displaystyle a\prec x</math>.

3. Nie jest dobry. Zbiór <math>\displaystyle \mathbb{Z} \times \{0\}</math> nie ma elementu najmniejszego. Gdyby miał, to musiałby być postaci <math>\displaystyle (x,0)</math>, a wtedy <math>\displaystyle x</math> byłby najmniejszym elementem <math>\displaystyle \mathbb{Z}</math>, a taki nie istnieje.

4. Nie jest dobry. Zbiór <math>\displaystyle \{0\} \times \mathbb{Z}</math> nie ma elementu najmniejszego, z tych samych powodów co zbiór w poprzednim punkcie.

</div></div>

{{cwiczenie|2.15||

Rozważmy dwa porządki <math>\displaystyle \ll,\prec</math> na zbiorze <math>\displaystyle \mathbb{N} \times \mathbb{N}</math> zdefiniowane w następujący sposób:

<center><math>\displaystyle (a,b)\prec(c,d) \Leftrightarrow (a< c) \vee (a=c \wedge b\leq d)
</math></center>

<center><math>\displaystyle (a,b)\ll (c,d) \Leftrightarrow (a=b=0) \vee (\neg(a=b=0) \wedge ((a <c) \vee (a=c \wedge d\leq b))).
</math></center>

Czy porządki te są podobne?  
}}

<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none">  

Tylko jeden z nich jest dobry.
</div></div>

<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">  

W poprzednim ćwiczeniu pokazaliśmy, że porządek <math>\displaystyle \prec</math> jest dobry. Pokażemy teraz, że <math>\displaystyle \ll</math> nie jest. Będzie to oznaczało, że nie są podobne, gdyż własność bycia dobrym porządkiem jest przenoszona przez podobieństwo.

Rozważmy zbiór <math>\displaystyle \{1\} \times \mathbb{N}</math>. Przypuśćmy, że istnieje w nim element minimalny <math>\displaystyle (1,a)</math>. Z definicji porządku <math>\displaystyle \ll</math> wynika, że <math>\displaystyle (1,a+1)\ll (1,a)</math>. Ponieważ <math>\displaystyle (1,a+1)\in \{1\} \times \mathbb{N}</math>, to <math>\displaystyle (1,a)</math> nie może być elementem minimalnym w tym zbiorze. Wobec tego porządek <math>\displaystyle \ll</math> nie jest dobry.
</div></div>

{{cwiczenie|2.16||

Czy porządek leksykograficzny na zbiorze <math>\displaystyle \{0,1\}^*</math> jest dobrym porządkiem. (Zbiór <math>\displaystyle \{0,1\}^*</math> to zbiór wszystkich skończonych ciągów złożonych z 0 i 1. Porządek leksykograficzny na takim zbiorze definiujemy jako <math>\displaystyle x\prec y</math>, jeśli <math>\displaystyle x</math> jest prefiksem <math>\displaystyle y</math>  lub jeśli na pierwszej współrzędnej, na której się różnią w <math>\displaystyle x</math> występuje 0, a w <math>\displaystyle y</math> występuje 1.)  
}}

<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none">  

Porządek ten przypomina trochę porządek na liczbach wymiernych.

</div></div>

<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">  

Porządek ten nie jest dobry. Niech <math>\displaystyle A</math> będzie zbiorem wszystkich ciągów postaci <math>\displaystyle 0^n 1</math>, gdzie <math>\displaystyle 0^n</math> oznacza ciąg zer długości <math>\displaystyle n</math>. Przypuśćmy, że w zbiorze <math>\displaystyle A</math> istnieje element najmniejszy, musi być postaci <math>\displaystyle 0^{n_0} 1</math>, dla pewnego <math>\displaystyle n_0 \in \mathbb{N}</math>. Wtedy jednak ciąg <math>\displaystyle 0^{n_0+1} 1</math> jest od niego mniejszy, gdyż na pierwszej różniącej ich współrzędnej (<math>\displaystyle n_0+1</math>) pierwszy z nich ma 1, a drugi 0. Wobec tego w <math>\displaystyle A</math> nie istnieje element najmniejszy i porządek ten nie jest dobry.
</div></div>

==Zasada indukcji==

Zdefiniujemy teraz zasadę indukcji, która będzie obowiązywała w zbiorach dobrze
uporządkowanych.

{{definicja|3.1.||

Niech <math>\displaystyle (X,\leq)</math>  będzie liniowym porządkiem. W  <math>\displaystyle (X,\leq)</math> obowiązuje
''zasada indukcji'', jeśli dla dowolnego zbioru <math>\displaystyle Z</math> takiego, że:
# <math>\displaystyle Z \subset X</math>,
# <math>\displaystyle Z\neq \emptyset</math>,
# dla dowolnego <math>\displaystyle x\in X</math>, jeśli <math>\displaystyle \{y\in X: y < x\} \subset Z</math>, to <math>\displaystyle x\in Z</math>.

zachodzi <math>\displaystyle Z=X</math>.
}}
W wykładzie o liczbach naturalnych udowodniliśmy  twierdzenie o
indukcji (patrz [[Logika i teoria mnogości/Wykład 7: Konstrukcja von Neumanna liczb naturalnych, twierdzenie o indukcji, zasady minimum, maksimum, definiowanie przez indukcje#twierdzenie_3_1| Wykład 7, Twierdzenie 3.1]]), z którego wynika, że zasada indukcji  obowiązuje w <math>\displaystyle (\mathbb{N},\leq)</math>. W
poniższym twierdzeniu dowodzimy analogiczne twierdzenie, dla wszystkich zbiorów dobrze
uporządkowanych.

<span id="twierdzenie_3_2">{{twierdzenie|3.2.||

W każdym zbiorze dobrze uporządkowanym obowiązuje zasada indukcji.
}}</span>

{{dowod|||

Niech <math>\displaystyle (X,\leq)</math> będzie dobrym porządkiem. Niech <math>\displaystyle Z</math> będzie dowolnym zbiorem takim, że:
# <math>\displaystyle Z \subset X</math>,
# element najmniejszy <math>\displaystyle X</math> należy do <math>\displaystyle Z</math>,
# dla dowolnego <math>\displaystyle x\in X</math> jeśli <math>\displaystyle \{y\in X: y < x\} \subset Z</math> to <math>\displaystyle x\in Z</math>.

Pokażemy, że <math>\displaystyle Z=X</math>. Niech <math>\displaystyle A=X \setminus Z</math>. Dla dowodu niewprost przypuśćmy, że
<math>\displaystyle A\neq \emptyset</math>. W takim przypadku w zbiorze <math>\displaystyle A</math> istnieje element najmniejszy <math>\displaystyle a</math>.
Skoro <math>\displaystyle a</math> jest najmniejszy w <math>\displaystyle A</math>, to każdy element <math>\displaystyle b\in X</math>, dla którego <math>\displaystyle b <a</math> musi
należeć do <math>\displaystyle Z</math> (nie może należeć do <math>\displaystyle A</math> więc należy do <math>\displaystyle X\setminus A =Z</math>). Wtedy
wiemy, że <math>\displaystyle \{b\in X: b < a\}\subset Z</math>, a więc z trzeciej własności zbioru <math>\displaystyle Z</math>
otrzymujemy <math>\displaystyle a\in Z</math>, a więc dostaliśmy sprzeczność (bo <math>\displaystyle a \in A \cap Z</math>, a te zbiory
są rozłączne).
}}

Okazuje się, że dobre porządki są nawet bardziej związane z zasadą indukcji. Wyrazem
tego jest poniższe twierdzenie.

<span id="twierdzenie_3_3">{{twierdzenie|3.3.||

Każdy porządek liniowy, w którym istnieje element najmniejszy i obowiązuje zasada indukcji jest dobry.
}}</span>

{{dowod|||

Niech <math>\displaystyle (X,\leq)</math> będzie liniowym porządkiem, w którym istnieje element
najmniejszy <math>\displaystyle \bot</math> oraz obowiązuje zasada indukcji. Niech  <math>\displaystyle A\subset X</math> będzie
podzbiorem <math>\displaystyle X</math>, w którym nie ma elementu najmniejszego. Zdefiniujmy zbiór <math>\displaystyle Z</math> jako
zbiór tych elementów <math>\displaystyle X</math>, które są mniejsze od wszystkich elementów z <math>\displaystyle A</math>, czyli:

<center><math>\displaystyle Z= \{z\in X: \forall_{a\in A} z < a\}.
</math></center>

Zbiór <math>\displaystyle Z</math> jest niepusty, gdyż <math>\displaystyle \bot \in Z</math> (<math>\displaystyle \bot</math> nie może należeć do <math>\displaystyle A</math>, gdyż byłby
najmniejszy). Pokażemy, że dla dowolnego <math>\displaystyle x\in X</math>, jeśli <math>\displaystyle \{y\in X: y<x \} \subset Z</math>,
to <math>\displaystyle x\in Z</math>. Przypuśćmy, że tak nie jest. Wtedy dla pewnego <math>\displaystyle x_0\in X</math> mamy <math>\displaystyle \{y\in
X: y<x_0 \} \subset Z</math> oraz <math>\displaystyle x_0\notin Z</math>. Wynika stąd, że istnieje element <math>\displaystyle a\in A</math>
taki, że <math>\displaystyle a\leq x_0</math>, ponieważ jednak żaden element mniejszy od <math>\displaystyle x_0</math> nie należy do
<math>\displaystyle A</math>, to <math>\displaystyle a=x_0</math>, a więc <math>\displaystyle x_0\in A</math>. Z tego samego powodu i z faktu, że porządek jest
liniowy otrzymujemy, że element <math>\displaystyle x_0</math> jest najmniejszy w <math>\displaystyle A</math>, co jest sprzeczne z
założeniem, że w <math>\displaystyle A</math> nie ma elementu najmniejszego. Wobec tego konieczne jest, aby
<math>\displaystyle x\in Z</math>.

Pokazaliśmy, że zbiór <math>\displaystyle Z</math> spełnia założenia zasady indukcji. Ponieważ zasada ta
obowiązuje w <math>\displaystyle (X,\leq)</math>, to otrzymujemy <math>\displaystyle Z=X</math>. Wynika stąd, że zbiór <math>\displaystyle A</math> musi być
pusty. Wobec tego każdy niepusty podzbiór <math>\displaystyle X</math> ma element najmniejszy, a więc
<math>\displaystyle (X,\leq)</math> jest dobrym porządkiem.
}}

Twierdzenie o definiowaniu przez indukcję udowodnione dla liczb naturalnych również
ma swój odpowiednik dla dobrych porządków. Mówi ono, że jeśli wyspecyfikujemy sposób
konstrukcji wartości funkcji na argumentach <math>\displaystyle (x,b)</math> na podstawie wartości <math>\displaystyle x,b</math> oraz
wartości tej funkcji dla wszystkich <math>\displaystyle (y,b)</math> takich, że <math>\displaystyle y <x</math>, to wyznaczymy
jednoznacznie funkcję <math>\displaystyle h</math> odpowiadającą tej specyfikacji. Twierdzenie to, nazywane
jest twierdzeniem o definiowaniu przez indukcję pozaskończoną, gdyż najważniejsze
zastosowania ma właśnie dla zbiorów  nieskończonych.

{{twierdzenie|3.4. [o definiowaniu przez indukcję pozaskończoną]||

Niech <math>\displaystyle (X,\leq)</math> będzie dobrym porządkiem.
Przez <math>\displaystyle PF(P,Q)</math> oznaczamy zbiór wszystkich funkcji częściowych ze zbioru <math>\displaystyle P</math>
do <math>\displaystyle Q</math>.
Pokażemy, że dla każdej funkcji <math>\displaystyle g:PF(X \times
B,C)\times X \times B \rightarrow C</math> istnieje dokładnie jedna funkcja <math>\displaystyle h:X \times B \rightarrow C</math>,
dla której:

<center><math>\displaystyle 
h(x,b)= g( h \cap (O(x) \times B \times C) ,x,b). \quad \quad \quad (3.1)
</math></center>

}}

{{dowod|||

Dowód przebiega analogicznie jak dla liczb naturalnych. Rozważmy następujący zbiór

<center><math>\displaystyle H=\{e \in PF(X \times B,C): \exists_{a\in X} [(1) \wedge (2)]\},
</math></center>

gdzie <math>\displaystyle (1)</math> i <math>\displaystyle (2)</math> oznaczają odpowiednio:
# <math>\displaystyle e:\overline{O(a)} \times B \rightarrow C</math>,
# <math>\displaystyle \forall_{x\in \overline{O(a)}}\forall_{b\in B}\; e(x,b)= g( e \cap (O(x) \times B \times C) ,x,b)</math>.

Innymi słowy, <math>\displaystyle H</math> jest zbiorem funkcji częściowych określonych na przedziałach
początkowych <math>\displaystyle X</math>, spełniających równość 3.1.

Pokażemy, że dla każdych dwóch funkcji częściowych <math>\displaystyle h_1, h_2 \in H</math> jedna z nich jest rozszerzeniem drugiej. Przypuśćmy, że tak nie jest. Weźmy funkcje <math>\displaystyle h_1, h_2 \in H</math> określone odpowiednio na zbiorach <math>\displaystyle \overline{O(a_1)} \times B, \overline{O(a_2)} \times B</math>, które różnią się na pewnym argumencie, na którym obie są określone. Bez straty ogólności możemy założyć, że <math>\displaystyle a_1\leq a_2</math>. Rozważmy zbiór <math>\displaystyle D=\{y\in \overline{O(a_1)}: \exists_{b\in B} h_1(y,b) \neq h_2(y,b)</math>. Zbiór <math>\displaystyle D</math> jest podzbiorem <math>\displaystyle X</math>. Skoro funkcje się różnią na jakimś argumencie, to jest <math>\displaystyle D</math> niepusty, a więc zawiera element najmniejszy, oznaczmy go przez <math>\displaystyle z</math>. Skoro <math>\displaystyle z</math> jest najmniejszy, to dla <math>\displaystyle v<z</math> dla wszystkich <math>\displaystyle b\in B</math> funkcje muszą być równe. Czyli:

<center><math>\displaystyle h_1\cap (O(z) \times B \times C) =     h_2\cap (O(z) \times B \times C),
</math></center>

wobec tego dla dowolnego <math>\displaystyle b\in B</math> mamy:

<center><math>\displaystyle g(h_1\cap (O(z) \times B \times C),z,b) =  g(   h_2\cap (O(z) \times B \times C),z,b).
</math></center>

I skoro obie funkcje są określone na <math>\displaystyle z</math> i należą do <math>\displaystyle H</math>, to dla dowolnego <math>\displaystyle b\in B</math> z
warunku (2) otrzymamy <math>\displaystyle h_1(z,b)=h_2(z,b)</math>. Otrzymaliśmy więc sprzeczność z faktem, że
<math>\displaystyle z\in D</math>. Wobec tego <math>\displaystyle D</math> jest pusty i <math>\displaystyle h_2</math> jest rozszerzeniem <math>\displaystyle h_1</math>.

Pokażemy teraz, że dla każdego <math>\displaystyle a\in X</math> istnieje w <math>\displaystyle H</math> funkcja określona na
<math>\displaystyle \overline{O(a)} \times B</math>. Niech <math>\displaystyle A \subset X</math> będzie zbiorem tych elementów <math>\displaystyle y\in X</math>,
dla których nie istnieje w <math>\displaystyle H</math> funkcja określona na <math>\displaystyle \overline{O(y)}  \times B</math>. Załóżmy
dla dowodu niewprost, że ten zbiór jest niepusty. Jako podzbiór zbioru dobrze
uporządkowanego posiada element najmniejszy, oznaczmy go przez <math>\displaystyle z</math>. Niech <math>\displaystyle H_z</math>
będzie zbiorem funkcji częściowych z <math>\displaystyle H</math> określonych na domkniętych przedziałach
początkowych silnie mniejszych od <math>\displaystyle \overline{O(z)}</math>, ponieważ <math>\displaystyle z</math> jest najmniejszy w <math>\displaystyle A</math>,
to na każdym takim przedziale jest określona jakaś funkcja należąca do <math>\displaystyle H</math>. Określimy
funkcję <math>\displaystyle h_z</math> jako:

<center><math>\displaystyle h_z= \bigcup H_z \cup \bigcup_{b\in B} \{((z,b),g(\bigcup H_z,z,b))\}.
</math></center>

Zauważmy <math>\displaystyle \bigcup H_z</math> jest funkcją częściową, gdyż dla każdych dwóch funkcji z <math>\displaystyle H_z</math>
jedna z nich jest rozszerzeniem drugiej. Z powyższej definicji wynika, że
<math>\displaystyle h_z:\overline{O(z)} \times B \rightarrow C</math>. Wobec tego <math>\displaystyle h_z</math> spełnia pierwszy warunek
przynależności do zbioru <math>\displaystyle H</math>. Pokażemy, że  spełnia również drugi. Weźmy dowolny
<math>\displaystyle x\in \overline{O(z)}</math> oraz <math>\displaystyle b\in B</math>. Rozważymy dwa przypadki.

: 1. Jeśli <math>\displaystyle x=z</math>, to:
<center><math>\displaystyle h_z(z,b)= g(\bigcup H_z,b,z)</math></center>
i ponieważ <math>\displaystyle h_z \cap (O(z) \times B \times C)= \bigcup H_z</math>, to:
<center><math>\displaystyle h_z(z,b)= g(h_z \cap (O(z) \times B \times C),z,b).
</math></center>
: 2. W pozostałym przypadku <math>\displaystyle x<z</math>. Wtedy <math>\displaystyle (x,h_z(x)) \in \bigcup H_z</math>, a więc musi należeć do którejś z funkcji z <math>\displaystyle H_z</math>, nazwijmy tę funkcję <math>\displaystyle h_x</math>. Ponieważ <math>\displaystyle h_x \in H</math>, to:
<center><math>\displaystyle h_z(x,b)=h_x(x,b)= g(h_x \cap (O(x) \times B \times C),z,b).
</math></center>

Skoro <math>\displaystyle h_x \in H_z</math> to <math>\displaystyle h_x\subset \bigcup H_z</math>, a więc <math>\displaystyle h_x\subset h_z</math>. Ponieważ
jednak <math>\displaystyle h_x</math> jest określona na całym zbiorze <math>\displaystyle O(x) \times B</math>, to:

<center><math>\displaystyle h_z(x,b)=g(h_x \cap (O(x) \times B \times C),x,b)=g( h_z  \cap (O(x) \times B \times C),x,b).
</math></center>

Stąd otrzymujemy:

<center><math>\displaystyle h_z(x,b)= g(h_z \cap (O(x) \times B \times C),z,b).
</math></center>

Wobec tego funkcja <math>\displaystyle h_z</math> spełnia także drugi warunek przynależności do <math>\displaystyle H</math>, a więc
<math>\displaystyle h_z\in H</math>. Ponieważ <math>\displaystyle h_z:\overline{O(z)}  \times B \rightarrow C</math> to otrzymaliśmy sprzeczność z
<math>\displaystyle z\in A</math>. Wobec tego zbiór <math>\displaystyle A</math> musi być pusty. Czyli dla każdego <math>\displaystyle a\in X</math> istnieje w
<math>\displaystyle H</math> funkcja określona na <math>\displaystyle \overline{O(a)} \times B</math>.

Pokażemy, że szukaną funkcją <math>\displaystyle h</math> jest <math>\displaystyle \bigcup H</math>. Ponieważ elementy zbioru <math>\displaystyle H</math> są
funkcjami częściowymi i zbiór <math>\displaystyle H</math> jest uporządkowanymi przez inkluzję, to <math>\displaystyle h</math> jest
funkcją częściową. Ponieważ dla każdego <math>\displaystyle x\in X</math> istnieje w <math>\displaystyle H</math> funkcja <math>\displaystyle h_x:
\overline{O(x)} \times B \rightarrow C</math>, to <math>\displaystyle h</math> jest określona na wszystkich elementach <math>\displaystyle X \times
B</math>. Stąd otrzymujemy <math>\displaystyle h:X\times  B \rightarrow C</math>. Ze sposobu konstrukcji <math>\displaystyle h</math> wynika
również, że spełniona jest równość 3.1.

Pozostało pokazać, że <math>\displaystyle h</math> jest jedyną taką funkcją. Przypuśćmy, że istnieje funkcja
<math>\displaystyle h':X \times B \rightarrow C</math> różna od <math>\displaystyle h</math>, która spełnia równość 3.1. Niech
<math>\displaystyle D=\{x\in X: \exists_{b\in B} \; h(x,b)\neq h'(x,b)\}</math>. Ponieważ <math>\displaystyle D</math> jest niepustym
podzbiorem <math>\displaystyle X</math>, to posiada element najmniejszy <math>\displaystyle z</math>. Ponieważ <math>\displaystyle z</math> jest najmniejszy w
<math>\displaystyle D</math>, to:

<center><math>\displaystyle h\cap O(z) \times B \times C=      h'\cap O(z) \times B \times C.
</math></center>

Ustalmy dowolne <math>\displaystyle b\in B</math>. Wtedy:

<center><math>\displaystyle g((h\cap O(z) \times B \times C),z,b)=  g((h'\cap O(z) \times B \times C),z,b).
</math></center>

Ponieważ obie funkcje spełniają 3.1, to lewa strona powyższej równości
jest równa <math>\displaystyle h(z,b)</math>, a prawa <math>\displaystyle h'(z,b)</math>. Wynika stąd, że <math>\displaystyle h(z,b)= h'(z,b)</math>, co wobec
dowolności wyboru <math>\displaystyle b</math> jest sprzeczne z przynależnością <math>\displaystyle z</math> do zbioru <math>\displaystyle D</math>. Wynika
stąd, że zbiór <math>\displaystyle D</math> musi być pusty, a więc funkcje <math>\displaystyle h</math> i <math>\displaystyle h'</math> muszą być równe.
}}

{{cwiczenie|3.5||

Udowodnij, że każdy zbiór nieskończony można podzielić na dwa równoliczne rozłączne podzbiory.  
}}

<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none">  

Uporządkuj dobrze zbiór i użyj indukcji pozaskończonej. 
</div></div>

<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">  

Idea następującego rozwiązania jest bardzo prosta. Na początek uporządkujemy dobrze zbiór <math>\displaystyle X</math>, a potem za pomocą definiowania przez indukcję określimy  funkcję <math>\displaystyle h</math>, przypisując na przemian 0 i 1 na "kolejnych" elementach <math>\displaystyle X</math>. Elementom <math>\displaystyle X</math>, które nie mają poprzedników przypiszemy 0, ich następnikom przypiszemy 1, ich następnikom 0, itd. Poniżej przedstawiamy formalizację tego pomysłu.

Niech <math>\displaystyle X</math> będzie dowolnym zbiorem nieskończonym. Z twierdzenia Ernsta Zermelo (patrz [[Logika i teoria mnogości/Wykład 11: Zbiory dobrze uporządkowane. Lemat Kuratowskiego Zorna i twierdzenie Zermelo, przykłady#twierdzenie_3_4|Wykład 11, Twierdzenie 3.4]]) wynika, że zbiór <math>\displaystyle X</math> można dobrze uporządkować. Niech więc <math>\displaystyle (X,\leq)</math> będzie dobrym porządkiem. Zaczniemy od zdefiniowania funkcji <math>\displaystyle h:X \rightarrow \{0,1\}</math> dla której relacja <math>\displaystyle \sim_{h}</math> wyznaczy szukany podział zbioru <math>\displaystyle X</math>. Funkcje <math>\displaystyle h</math> zdefiniujemy przez indukcję pozaskończoną za pomocą  funkcji <math>\displaystyle g: PF(X,\{0,1\}) \times X \rightarrow \{0,1\}</math> zdefiniowanej następująco (przez <math>\displaystyle y'</math> oznaczamy następnik elementu <math>\displaystyle y</math> w <math>\displaystyle (X,\leq)</math>):

<center><math>\displaystyle g=\{(f,x,a) \in PF(X,\{0,1\}) \times X \times \{0,1\}:
[\exists_{y\in X} (y'=x \wedge \exists_{p\in f} (p=(y,0)\wedge a=1)) XOR
(a=0)]\}.
</math></center>

W ten zawikłany sposób zdefiniowaliśmy funkcję <math>\displaystyle g</math>, która częściowej funkcji <math>\displaystyle f</math> oraz elementowi <math>\displaystyle x</math> przypisuje wartość <math>\displaystyle 1</math>, jeśli <math>\displaystyle x</math> jest następnikiem jakiegoś elementu <math>\displaystyle y</math> w <math>\displaystyle (X,\leq)</math> oraz funkcja <math>\displaystyle f</math> jest określona na <math>\displaystyle y</math> i przypisuje mu wartość 0. W przeciwnym przypadku <math>\displaystyle g</math> przypisuje wartość 0. Z definicji <math>\displaystyle g</math> wynika, że jest funkcją totalną.

Za pomocą definiowania przez indukcję zdefiniujemy teraz funkcję <math>\displaystyle h</math> jako funkcję spełniającą:

<center><math>\displaystyle h(x)= g( h \cap (O(x) \times \{0,1\}),x).
</math></center>

Zobaczmy, jak działa <math>\displaystyle h</math>. Dla elementu najmniejszego <math>\displaystyle \bot</math> zbiór <math>\displaystyle h \cap (O(\bot) \times \{0,1\})</math> jest pusty, wobec czego <math>\displaystyle h(\bot)=0</math>. Jeśli element <math>\displaystyle x\in X</math> nie jest następnikiem żadnego elementu, to  z definicji <math>\displaystyle g</math> wynika, że <math>\displaystyle h(x)=0</math>. Dla elementu <math>\displaystyle x</math> będącego następnikiem <math>\displaystyle y</math> funkcja częściowa <math>\displaystyle h \cap (O(x) \times \{0,1\})</math> jest określona na <math>\displaystyle y</math> i wtedy:
# <math>\displaystyle h(x)=1</math>, gdy <math>\displaystyle h(y)=0</math>;
# <math>\displaystyle h(x)=0</math>, gdy <math>\displaystyle h(y)=1</math>.

Funkcja <math>\displaystyle h</math> wyznacza rozkład zbioru <math>\displaystyle X</math> na dwa rozłączne zbiory <math>\displaystyle \vec{h}^{-1}{\{1\}}</math>
oraz <math>\displaystyle \vec{h}^{-1}{\{0\}}</math>. Pokażemy, że te zbiory są bijektywne.

Zdefiniujmy funkcję częściową <math>\displaystyle e \subset X^2</math> następująco:

<center><math>\displaystyle e= \{(a,b) \in X\times X; f(a)=0 \wedge a'=b\}.
</math></center>

Ponieważ każdy element <math>\displaystyle X</math> ma co najwyżej jeden następnik, to <math>\displaystyle e</math> jest w istocie
funkcją częściową. Ponieważ <math>\displaystyle X</math>  jest uporządkowany liniowo, to każdy element jest
następnikiem co najwyżej jednego elementu. Wynika stąd, że <math>\displaystyle e</math> jest iniekcją.
Rozważymy trzy przypadki:

1. Jeśli w <math>\displaystyle X</math> nie ma elementu największego, to każdy element ma następnik, a więc dziedziną funkcji <math>\displaystyle e</math> jest cały zbiór <math>\displaystyle \vec{h}^{-1}{\{0\}}</math>. Pokażemy, że <math>\displaystyle e</math> jest suriekcją na zbiór <math>\displaystyle \vec{h}^{-1}{\{1\}}</math>. Weźmy dowolny element <math>\displaystyle b\in \vec{h}^{-1}{\{1\}}</math>, wtedy <math>\displaystyle h(b)=1</math> i z definicji funkcji <math>\displaystyle h</math> wynika, że element <math>\displaystyle b</math> jest następnikiem pewnego elementu <math>\displaystyle a \in \vec{h}^{-1}{\{0\}}</math>, wobec tego para <math>\displaystyle (a,b)\in e</math>, a więc <math>\displaystyle e</math> jest suriekcją. Wobec tego funkcja <math>\displaystyle e</math> jest bijekcją pomiędzy zbiorami <math>\displaystyle \vec{h}^{-1}{\{0\}}</math> oraz <math>\displaystyle \vec{h}^{-1}{\{1\}}</math>

2. Jeśli w <math>\displaystyle X</math> jest element największy <math>\displaystyle \top</math> i <math>\displaystyle h(\top)=1</math>, to każdy element <math>\displaystyle x</math>, dla którego <math>\displaystyle h(x)=0</math>, ma następnik, a więc dziedziną funkcji <math>\displaystyle e</math> jest cały zbiór <math>\displaystyle \vec{h}^{-1}{\{0\}}</math>. Dokładnie analogicznie do poprzedniego przypadku pokazujemy, że <math>\displaystyle e</math> jest suriekcją, wobec czego jest również bijekcją.

3. W pozostałym przypadku, w <math>\displaystyle X</math> istnieje element największy <math>\displaystyle \top</math> oraz <math>\displaystyle h(\top)=0</math>. Wtedy z poprzednich przypadków wynika, że funkcja <math>\displaystyle e</math> jest bijekcją pomiędzy zbiorami <math>\displaystyle \vec{h}^{-1}{\{0\}} \setminus \{\top\}</math> a <math>\displaystyle \vec{h}^{-1}{\{1\}}</math>. Ponieważ zbiór <math>\displaystyle X</math> jest nieskończony to obydwa zbiory <math>\displaystyle \vec{h}^{-1}{\{0\}} \setminus \{\top\}</math>,  <math>\displaystyle \vec{h}^{-1}{\{1\}}</math> są nieskończone. Wobec tego <math>\displaystyle \vec{h}^{-1}{\{0\}} \setminus \{\top\}</math> jest równoliczny z <math>\displaystyle \vec{h}^{-1}{\{0\}}</math>, co świadczy o tym, że istnieje bijekcja pomiędzy <math>\displaystyle \vec{h}^{-1}{\{0\}}</math> a <math>\displaystyle \vec{h}^{-1}{\{1\}}</math>.

</div></div>

Pokażemy teraz ważne twierdzenie, które mówi, że dla dowolnych dwóch zbiorów dobrze uporządkowanych jeden z nich jest podobny do przedziału początkowego drugiego.

<span id="twierdzenie_3_6">{{twierdzenie|3.6.||

Niech <math>\displaystyle (X,\leq_X)</math>, <math>\displaystyle (Y,\leq_Y)</math> będą dobrymi porządkami. Wtedy przynajmniej
jedno z poniższych zdań jest prawdziwe:
# istnieje przedział początkowy <math>\displaystyle P\subset X</math> taki, że <math>\displaystyle (P,\leq_X \cap P\times
P)</math> jest podobny do <math>\displaystyle (Y,\leq_Y)</math>,
# istnieje przedział początkowy <math>\displaystyle S \subset Y</math> taki, że <math>\displaystyle (S,\leq_Y \cap S\times
S)</math> jest podobny do <math>\displaystyle (X,\leq_X)</math>.

}}</span>

{{dowod|||

Niech <math>\displaystyle \top</math> będzie elementem nienależącym do <math>\displaystyle Y</math> (w roli <math>\displaystyle \top</math> może wystąpić
<math>\displaystyle Y</math>, ze względu na przejrzystość dowodu decydujemy się na oznaczenie <math>\displaystyle \top</math>).
Rozważmy zbiór <math>\displaystyle Z=Y\cup \{\top\}</math>, który uporządkujemy relacją <math>\displaystyle \leq_Z = [\leq_Y \cup
(Y \times\{\top\})]</math>, czyli <math>\displaystyle \top</math> jest większy od wszystkich elementów <math>\displaystyle Y</math>.
Zauważmy, że <math>\displaystyle (Z,\leq_Z)</math> jest dobrym porządkiem.

Zdefiniujmy funkcję <math>\displaystyle g:PF(X,Z) \rightarrow Z</math>
następująco, dla dowolnej funkcji częściowej <math>\displaystyle r \in PF(X,Z)</math>  niech

<center><math>\displaystyle g(r)= \min((Z\setminus \vec{r}(X)) \cup \{\top\}).
</math></center>

Pokażemy, że funkcja <math>\displaystyle g</math> jest monotoniczna (funkcje częściowe porządkujemy za
pomocą inkluzji). Dla dowolnych dwóch funkcji częściowych <math>\displaystyle s,r \in  PF(X,Z)</math>
takich, że <math>\displaystyle s \subset r</math> mamy:

<center><math>\displaystyle \aligned \vec{s}(X) \subset     \vec{r}(X) \\
Z \setminus \vec{s}(X) \supset Z\setminus     \vec{r}(X)\\
g(s)= \min_Z(Z \setminus \vec{s}(X)) \leq  \min_Z(Z\setminus     \vec{r}(X))= g(r).
\endaligned</math></center>

Z twierdzenia o definiowaniu przez indukcję wynika, że istnieje funkcja <math>\displaystyle h:X\rightarrow
Y</math>, dla której

<center><math>\displaystyle h(x)= g( h \cap (O(x) \times Z) ).
</math></center>

Łatwo pokazać, że funkcja <math>\displaystyle h</math> jest monotoniczna. Dla dowolnych <math>\displaystyle x,y \in X</math> dla
których <math>\displaystyle x\leq_X y</math> mamy:

<center><math>\displaystyle \aligned O(x) \subset O(y) \\
h \cap (O(x) \times Z) \subset h \cap (O(y) \times Z)
\endaligned</math></center>

i z monotoniczności funkcji <math>\displaystyle g</math> otrzymujemy:

<center><math>\displaystyle h(x) = g( h \cap (O(x) \times Z) ) \subset g( h \cap (O(y) \times Z) )= h(y).
</math></center>

Pokażemy, że dla każdego <math>\displaystyle x\in X</math> prawdą jest, że <math>\displaystyle \vec{h}(\overline{O(x)})
=\overline{O(h(x))}</math>. Ustalmy dowolny element <math>\displaystyle x\in X</math>. Z monotoniczności <math>\displaystyle h</math> dostajemy
prawie natychmiast <math>\displaystyle \vec{h}(\overline{O(x)}) \subset \overline{O(h(x))}</math>. Dla pokazania
inkluzji w drugą stronę, weźmy dowolny element <math>\displaystyle y \in \overline{O(h(x))}</math>. Wtedy <math>\displaystyle  y
\leq_Y h(x)</math>. Przypuśćmy dla dowodu nie wprost, że <math>\displaystyle y\notin \vec{h}(\overline{O(x)})</math>
wtedy <math>\displaystyle y <_Y h(x)</math> oraz <math>\displaystyle y\in (Z \setminus \vec{h}(O(x)) \cup \{\top\})</math> co
jest sprzeczne z definicją funkcji <math>\displaystyle h</math> w punkcie <math>\displaystyle x</math>, bo element <math>\displaystyle h(x)</math> miał być
najmniejszy w tym  zbiorze. Pokazaliśmy więc inkluzje w obie strony. Wobec dowolności
wyboru <math>\displaystyle x\in X</math> dowiedliśmy żądaną własność.

Pokażemy, że dla różnych elementów <math>\displaystyle x,y\in X</math>, jeśli wartości <math>\displaystyle h(x),h(y)</math> są równe
sobie, to są równe <math>\displaystyle \top</math>. Weźmy dowolne różne elementy <math>\displaystyle x,y\in X</math>, dla których
<math>\displaystyle h(x)=h(y)</math>. Bez straty ogólności możemy założyć, że <math>\displaystyle x\leq_X y</math>. Wtedy:

<center><math>\displaystyle h(y)= \min_Z((Z \setminus \vec{h}(O(y))) \cup \{\top\}).
</math></center>

Ponieważ <math>\displaystyle x \in O(y)</math>, to <math>\displaystyle h(x)\notin Z \setminus \vec{h}(O(y))</math>, a więc
skoro <math>\displaystyle h(x)=h(y)</math>, to <math>\displaystyle h(y)</math> musi należeć do <math>\displaystyle \{\top\}</math>, czyli <math>\displaystyle h(y)=h(x)=\top</math>.

Rozważymy teraz dwa przypadki.

: 1. Jeśli <math>\displaystyle \top \notin \vec{h}(X)</math>, to <math>\displaystyle h</math> jest iniekcją. Zauważmy, że
<math>\displaystyle X=\bigcup_{x\in X} \overline{O(x)}</math>. Ponieważ <math>\displaystyle \vec{h}(\overline{O(x)}) =\overline{O(h(x))}</math>, to

<center><math>\displaystyle \vec{h}(X)=     \vec{h}(\bigcup_{x\in X} \overline{O(x)})=        \bigcup_{x\in X}
\vec{h}(\overline{O(x)})= \bigcup_{x\in X} \kPPoczD(h{x}).
</math></center>

A więc <math>\displaystyle \vec{h}(X)</math>, jako suma przedziałów początkowych, jest przedziałem początkowym.
Wobec tego <math>\displaystyle h:X \rightarrow Z</math> jest monotoniczną iniekcją, której obrazem jest istotny
przedział początkowy <math>\displaystyle Z</math>, a więc również przedział początkowy <math>\displaystyle Y</math>. Wobec tego <math>\displaystyle X</math>
jest podobny do przedziału początkowego <math>\displaystyle Y</math>.

: 2. Jeśli <math>\displaystyle \top \in \vec{h}(X)</math>, to niech <math>\displaystyle v\in X</math> będzie takim elementem, że
<math>\displaystyle h(v)=\top</math>. Rozważymy zbiór <math>\displaystyle A=\{ x \in X: h(x)\neq \top\}</math>. Z monotoniczności <math>\displaystyle h</math>
wynika, że <math>\displaystyle A</math> jest odcinkiem początkowym <math>\displaystyle X</math>. Ponieważ <math>\displaystyle \vec{h}(\overline{O(v)})= Z</math> to
<math>\displaystyle \vec{h}(A)=Y</math>. Wobec tego funkcja <math>\displaystyle h</math> zawężona do zbioru <math>\displaystyle A</math> jest monotoniczną
bijekcją w zbiór <math>\displaystyle Y</math>. Wynika stąd, że <math>\displaystyle A</math> jest podobny do <math>\displaystyle Y</math>. Ponieważ <math>\displaystyle A</math> jest
przedziałem początkowym, to <math>\displaystyle Y</math> jest podobny do pewnego przedziału początkowego <math>\displaystyle X</math>.

}}

Z powyższego twierdzenia wynika bardzo ważny następujący wniosek:

<span id="twierdzenie_3_7">{{twierdzenie|3.7.||

Każde dwa zbiory są porównywalne na moc. Czyli dla dowolnych zbiorów <math>\displaystyle x,y</math>, prawdą jest, że

<center><math>\displaystyle x \leq_m y \vee y \leq_m x.
</math></center>

}}</span>

{{dowod|||

Z Twierdzenia 3.6 (patrz [[#twierdzenie_3_6|Twierdzenie 3.6.]]) wynika, że dowolne zbiory dobrze uporządkowane można porównywać na moc. Z twierdzenia Ernsta Zermelo (patrz [[Logika i teoria mnogości/Wykład 11: Zbiory dobrze uporządkowane. Lemat Kuratowskiego Zorna i twierdzenie Zermelo, przykłady#twierdzenie_3_4|Wykład 11, Twierdzenie 3.4]]) wynika, że dowolne zbiory <math>\displaystyle x,y</math>  można dobrze uporządkować. Wobec tego dowolne zbioru można porównywać na moc.
}}

<span id="twierdzenie_3_8">{{twierdzenie|3.8.||
Żaden zbiór dobrze uporządkowany nie jest podobny do swojego istotnego przedziału początkowego.
}}</span>

{{dowod|||

Niech <math>\displaystyle (X,\leq)</math> będzie dobrym porządkiem. Przypuśćmy, że istnieje przedział
początkowy    <math>\displaystyle A\subsetneq X</math>, który uporządkowany relacją <math>\displaystyle \leq \cap A</math> jest podobny
do <math>\displaystyle X</math>. Niech <math>\displaystyle f:A\cap X</math> będzie funkcją podobieństwa, niech <math>\displaystyle C= \{x\in X: f(x) <
x\}</math>. Skoro <math>\displaystyle A\subsetneq X</math>, to <math>\displaystyle C</math> jest zbiorem niepustym, a więc ma element
najmniejszy, oznaczmy go przez <math>\displaystyle c</math>. Wtedy <math>\displaystyle f(c) <c</math>, a więc ponieważ <math>\displaystyle c</math> jest
najmniejszy w zbiorze <math>\displaystyle C</math>, to <math>\displaystyle f(f(c)) \geq f(c)</math>. Rozważmy dwa przypadki:
# <math>\displaystyle f(f(c))=f(c)</math>, wtedy <math>\displaystyle f</math> nie jest iniekcją, a więc dostaliśmy sprzeczność.
# <math>\displaystyle f(f(c)) > f(c)</math>, a więc <math>\displaystyle f</math> nie jest monotoniczna i dostaliśmy sprzeczność.

}}

==Liczby porządkowe==

W poprzednim rozdziale pokazaliśmy, że dla dowolnych dwóch zbiorów dobrze
uporządkowanych jeden z nich jest podobny do odcinka początkowego drugiego.

Powiemy, że dobre porządki <math>\displaystyle A</math> i <math>\displaystyle B</math> są ''tego samego typu'', jeśli <math>\displaystyle A</math> jest
podobny do <math>\displaystyle B</math>.

Łatwo wykazać, że każdy dobry porządek jest tego samego typu co on sam, jeśli <math>\displaystyle A</math>
jest tego samego typu co <math>\displaystyle B</math>, to <math>\displaystyle B</math> jest tego samego typu co <math>\displaystyle A</math> oraz że, jeśli <math>\displaystyle A</math>
jest tego samego typu co <math>\displaystyle B</math> i <math>\displaystyle B</math> jest tego samego typu co  <math>\displaystyle C</math>, to <math>\displaystyle A</math> jest tego
samego typu co <math>\displaystyle C</math>. Te trzy własności dokładnie odpowiadają wymaganiom jakie stawiamy
relacji, aby była relacją równoważności. Może się wydawać kuszące zdefiniowanie
relacji podobieństwa. Niestety takie próby skazane są na niepowodzenie, gdyż taka
relacja musiałaby być określona na zbiorze wszystkich dobrych porządków, a taki zbiór
(podobnie jak zbiór wszystkich zbiorów) nie istnieje. Co więcej dla ustalonego
niepustego zbioru dobrze uporządkowanego nie istnieje nawet zbiór dobrych porządków,
które są tego samego typu co on. W podejściach do teorii mnogości, które dopuszczają
pojęcie klasy, mówi się o typach porządkowych jako o klasach. W przypadku rozważanej
teorii ZFC nie możemy definiować klas, które nie są zbiorami. Zamiast tego wyróżnimy
pewne porządki, które będą reprezentować wszystkie porządki podobne do nich. Porządki
te, będące czymś w rodzaju reprezentantów "klas" podobieństwa, nazwiemy liczbami
porządkowymi. Poniższa definicja liczb porządkowych pochodzi od [[Biografia Neumann, John|Johna von Neumanna]]. Jest to
formalizacja idei aby liczba porządkowa była zbiorem liczb porządkowych od niej
mniejszych.

{{definicja|4.1.||

Zbiór <math>\displaystyle X</math> nazwiemy liczbą porządkową, jeśli  ma następujące własności:
# <math>\displaystyle \forall_{x,y\in X} \;x \in y \vee y\in x \vee x=y</math>.
# <math>\displaystyle \forall_{x\in X} \;x\subset X</math>.
}}
Najprostszym przykładem liczby porządkowej jest zbiór pusty. W poniższym ćwiczeniu
pokazujemy, jak można konstruować kolejne liczby porządkowe.

{{cwiczenie|4.2||

Udowodnij, że jeśli <math>\displaystyle X</math> jest liczbą porządkową, to <math>\displaystyle X \cup \{X\}</math> jest liczbą porządkową.

}}

<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">  

Pokażemy, że zbiór  <math>\displaystyle X \cup \{X\}</math> spełnia własności liczb porządkowych.

# Weźmy dowolne <math>\displaystyle x,y\in X \cup \{X\}</math> takie, że <math>\displaystyle y\neq x</math>. Jeśli <math>\displaystyle x,y \in X</math>, to ponieważ <math>\displaystyle X</math> jest liczbą porządkową, otrzymujemy <math>\displaystyle x\in y</math> lub <math>\displaystyle y\in x</math>. W pozostałym przypadku jeden z tych elementów jest równy <math>\displaystyle X</math>. Ze względu na symetrię sytuacji przypuśćmy, że <math>\displaystyle x=X</math>. Wtedy ponieważ <math>\displaystyle y \in X \cup \{X\}</math> i <math>\displaystyle y\neq x=X</math>, to <math>\displaystyle y\in X</math>, a więc <math>\displaystyle y\in x</math>. Pokazaliśmy więc, że dla każdych dwóch różnych elementów zbioru <math>\displaystyle X \cup \{X\}</math> jeden z nich jest elementem drugiego.
# Weźmy dowolny <math>\displaystyle x\in X</math>. Rozważymy dwa przypadki:

# <math>\displaystyle x\in X</math>. Wtedy ponieważ <math>\displaystyle X</math> jest liczbą porządkową, to <math>\displaystyle x\subset X</math>, a więc tym bardziej <math>\displaystyle x\subset X\cup \{X\}</math>.
# <math>\displaystyle x\in \{X\}</math>. Wtedy <math>\displaystyle x=X</math>, a więc również <math>\displaystyle x\subset X</math>.

Wobec tego każdy <math>\displaystyle x</math> ze zbioru <math>\displaystyle X \cup \{X\}</math> jest jego podzbiorem.

Zbiór <math>\displaystyle X \cup \{X\}</math> spełnia własności w definicji liczb porządkowych, a więc jest liczbą porządkową.
</div></div>

Z twierdzenia udowodnionego w poprzednim ćwiczeniu możemy wywnioskować, że każda
liczba naturalna jest liczbą porządkową. Nie koniec na tym, zauważmy, że cały <math>\displaystyle \mathbb{N}</math>
też jest liczbą porządkową (patrz  [[Logika i teoria mnogości/Wykład 7: Konstrukcja von Neumanna liczb naturalnych, twierdzenie o indukcji, zasady minimum, maksimum, definiowanie przez indukcje#twierdzenie_4_1|Wykład 7, Twierdzenie 4.1]]), a więc także <math>\displaystyle \mathbb{N} \cup \{\mathbb{N}\}</math> oraz <math>\displaystyle \mathbb{N} \cup \{\mathbb{N}\} \cup
\{\mathbb{N} \cup \{\mathbb{N}\}\}</math>, itd.

<span id="twierdzenie_4_3">{{twierdzenie|4.3.||

Każdy element liczby porządkowej jest liczbą porządkową.
}}</span>

{{dowod|||

Niech <math>\displaystyle X</math> będzie liczbą porządkową i niech <math>\displaystyle x\in X</math>. Z drugiej własności liczb
porządkowych otrzymujemy <math>\displaystyle x\subset X</math>. Pokażemy, że <math>\displaystyle x</math> spełnia warunki bycia liczbą
porządkową:

# Weźmy dowolne różne elementy <math>\displaystyle a,b \in x</math>. Wtedy ponieważ <math>\displaystyle x\subset X</math>, to <math>\displaystyle a,b \in X</math>. Skoro <math>\displaystyle X</math> jest liczbą porządkową, to <math>\displaystyle a\in b</math> lub <math>\displaystyle b\in a</math>. Zbiór <math>\displaystyle x</math> spełnia więc pierwszy warunek bycia liczbą porządkową.
# Weźmy dowolny element <math>\displaystyle a \in x</math>. Ponieważ <math>\displaystyle x\subset X</math>, to <math>\displaystyle a\in X</math> i z drugiej własności liczb porządkowych otrzymujemy <math>\displaystyle a\subset X</math>. Przypuśćmy, że <math>\displaystyle a \nsubseteq x</math>, wtedy istnieje <math>\displaystyle b\in a</math> taki, że <math>\displaystyle b\notin x</math>. Ponieważ jednak <math>\displaystyle a\subset X</math>, to <math>\displaystyle b\in X</math>; zatem z drugiej własności liczb porządkowych otrzymujemy <math>\displaystyle b=x</math> lub <math>\displaystyle x \in b</math>. W pierwszym przypadku otrzymujemy <math>\displaystyle x\in a \in x</math> a w drugim <math>\displaystyle x \in x</math>.

Obydwa te przypadki prowadzą do sprzeczności z aksjomatem regularności. Wobec tego,
konieczne jest, aby <math>\displaystyle a\subset x</math>.

}}

Z powyższego twierdzenia natychmiast wynika następujący fakt, z którego będziemy
często korzystać.

{{fakt|4.1.||

Dla dowolnej liczby porządkowej <math>\displaystyle X</math> oraz elementów <math>\displaystyle x,y\in X</math>, jeśli <math>\displaystyle x\in y</math>, to <math>\displaystyle x \subset y</math>.
}}

Jeśli liczby porządkowe mają reprezentować "klasy" podobnych dobrych porządków, to
same powinny być dobrymi porządkami. Dowodzimy tego w następnym twierdzeniu.

<span id="twierdzenie_4_4">{{twierdzenie|4.4.||

Każdy zbiór będący liczbą porządkową jest dobrze uporządkowany relacją inkluzji.
}}</span>

{{dowod|||

Rozważmy zbiór <math>\displaystyle X</math> będący liczbą porządkową. Skoro dla każdych dwóch różnych
elementów <math>\displaystyle x,y\in X</math> mamy <math>\displaystyle x\in y</math> lub <math>\displaystyle y\in x</math>, to z poprzedniego twierdzenia
otrzymujemy <math>\displaystyle x\subset y</math> lub <math>\displaystyle y \subset x</math>. A więc <math>\displaystyle X</math> jest uporządkowany liniowo
przez relację inkluzji.

Pokażemy teraz, że w każdym podzbiorze <math>\displaystyle A\subset X</math> istnieje element najmniejszy
ze względu na inkluzję. Weźmy dowolny taki zbiór <math>\displaystyle A</math>. Z aksjomatu regularności (patrz [[Logika i teoria mnogości/Wykład 4: Teoria mnogości ZFC. Operacje na zbiorach#Aksjomat_Regularności|Wykład 4, Aksjomat Regularności]]) wynika, że istnieje element <math>\displaystyle a\in A</math> taki, że <math>\displaystyle a \cap A =\emptyset</math>.
Pokażemy, że <math>\displaystyle a</math>  należy do każdego elementu <math>\displaystyle b\in A</math>, który jest różny od <math>\displaystyle a</math>. Weźmy
dowolny taki element <math>\displaystyle b</math>. Wiemy, że jest różny od <math>\displaystyle a</math>, a więc z pierwszej własności
liczb porządkowych otrzymujemy <math>\displaystyle a\in b</math> lub <math>\displaystyle b\in a</math>. Przypuśćmy, że <math>\displaystyle b\in a</math>, wtedy,
ponieważ <math>\displaystyle b\in A</math>, to również <math>\displaystyle b\in a\cap A</math>, co prowadzi do sprzeczności, ponieważ ten
zbiór jest niepusty. Wobec tego konieczne jest, aby <math>\displaystyle a\in b</math>. Z drugiej własności
liczb porządkowych otrzymujemy, że <math>\displaystyle a\subset b</math>. Wobec czego pokazaliśmy, że dla
dowolnego <math>\displaystyle b\in A</math> mamy <math>\displaystyle a \subset b</math>, co znaczy że, <math>\displaystyle a</math> jest najmniejszym w sensie
inkluzji elementem <math>\displaystyle A</math>.
}}

<span id="twierdzenie_4_5">{{twierdzenie|4.5.||

Każdy przedział początkowy liczby porządkowej jest liczbą porządkową.
}}</span>

{{dowod|||

Jeśli przedział początkowy jest zbiorem pustym, to jest liczbą początkową.
Zajmiemy się więc tylko niepustymi. Weźmy dowolną liczbę porządkową <math>\displaystyle X</math>. Niech
<math>\displaystyle A</math> będzie jej niepustym przedziałem początkowym. Pokażemy, że <math>\displaystyle A</math> jest liczbą
porządkową.

# Własność pierwsza wynika natychmiast z faktu, że <math>\displaystyle A \subset X</math>.
# Weźmy dowolną liczbę <math>\displaystyle x\in A</math>. Skoro <math>\displaystyle X</math> jest liczbą porządkową, to <math>\displaystyle x\subset
X</math>. Weźmy dowolny element <math>\displaystyle z\in x</math>, wynika stąd, że <math>\displaystyle z\subset x</math>, a więc skoro <math>\displaystyle A</math>
jest przedziałem początkowym to <math>\displaystyle z \in A</math>.

}}

<span id="cwiczenie_4_6">{{cwiczenie|4.6||

Niech <math>\displaystyle X</math> będzie liczbą porządkową. Udowodnij, że dla dowolnych elementów <math>\displaystyle x,y
\in X</math>, jeśli <math>\displaystyle x\subsetneq y</math>, to <math>\displaystyle x\in y</math>.  
}}</span>

<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none">  

Spróbuj nie wprost. 
</div></div>

<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">  

Dla dowodu nie wprost przypuśćmy, że <math>\displaystyle x\subseteq y</math> oraz <math>\displaystyle x\notin y</math>. Ponieważ zbiór <math>\displaystyle X</math> jest liczbą porządkową, to dla każdych dwóch różnych elementów <math>\displaystyle X</math> jeden jest elementem drugiego. Ponieważ <math>\displaystyle x\neq y</math> i <math>\displaystyle x\notin y</math>, to konieczne jest, aby <math>\displaystyle y\in x</math>, ale z faktu, że <math>\displaystyle x\subset y</math>, otrzymujemy <math>\displaystyle y\in y</math>, co prowadzi do sprzeczności z aksjomatem regularności. Wobec tego <math>\displaystyle x</math> musi być elementem <math>\displaystyle y</math>.
</div></div>

Z powyższego ćwiczenia wynika następujący fakt.

<span id="fakt_4_2">{{fakt|4.2.||

Każdy element liczby porządkowej jest liczbą porządkową.
}}</span>

{{cwiczenie|4.7||

Udowodnij, że <math>\displaystyle \emptyset</math> jest elementem każdej niepustej liczby porządkowej.

}}

<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">  

Niech <math>\displaystyle X</math> będzie niepustą liczbą porządkową. Z aksjomatu regularności wynika, że w <math>\displaystyle X</math> istnieje element <math>\displaystyle x</math>, dla którego <math>\displaystyle x \cap X=\emptyset</math>. Ponieważ jednak <math>\displaystyle X</math> jest liczbą porządkową, to <math>\displaystyle x\subset X</math>, wobec czego <math>\displaystyle x</math> musi być zbiorem pustym.
</div></div>

<span id="twierdzenie_4_8">{{twierdzenie|4.8.||

Dla każdych dwóch liczb porządkowych jedna jest podzbiorem drugiej.
}}</span>

{{dowod|||

Dowiedliśmy już, że liczby porządkowe są dobrze uporządkowane przez inkluzję. Wobec tego z Twierdzenia 3.6 (patrz [[#twierdzenie_3_6|Twierdzenie 3.6.]]) wynika, że dla każdych dwóch liczb porządkowych jedna z nich jest podobna do przedziału początkowego drugiej. Ponieważ przedziały początkowe liczb porządkowych są liczbami porządkowymi, to wystarczy wykazać, że każde podobieństwo liczb porządkowych uporządkowanych inkluzją jest identycznością.

Weźmy liczby porządkowe <math>\displaystyle X,Y</math> i przypuśćmy, że funkcja <math>\displaystyle f:X \rightarrow Y</math> jest
podobieństwem pomiędzy porządkami <math>\displaystyle (X,\subset)</math> i <math>\displaystyle (Y,\subset)</math>. Pokażemy, że <math>\displaystyle f</math>
jest identycznością.

Niech <math>\displaystyle A\subset X</math> będzie zbiorem <math>\displaystyle x\in X</math>, dla których <math>\displaystyle f(x)\neq x</math>. Jeśli <math>\displaystyle A=
\emptyset</math>, to funkcja <math>\displaystyle f</math> jest identycznością. Dla dowodu niewprost załóżmy więc, że
<math>\displaystyle A\neq \emptyset</math>. Ponieważ <math>\displaystyle X</math> jest dobrze uporządkowany, to w zbiorze <math>\displaystyle A</math> istnieje
element najmniejszy, oznaczmy go przez <math>\displaystyle a</math>.

Pokażemy, że <math>\displaystyle f(a) \supset a</math>. Weźmy dowolny element <math>\displaystyle b\in a</math>, wtedy <math>\displaystyle b\subset a</math>  i
z monotoniczności <math>\displaystyle f</math> otrzymujemy <math>\displaystyle f(b) \subset f(a)</math>, ponieważ jednak <math>\displaystyle b\notin A</math>, to
<math>\displaystyle f(b)=b</math>, a więc <math>\displaystyle b\in f(a)</math>. Wobec dowolności wyboru <math>\displaystyle b</math> dostajemy <math>\displaystyle a\subset f(a)</math>.

Skoro <math>\displaystyle a\neq f(a)</math>, to istnieje element <math>\displaystyle z\in f(a)</math>, który nie należy do <math>\displaystyle a</math>. Ponieważ
<math>\displaystyle f(a)\in Y</math>, to również <math>\displaystyle z\in Y</math>. Funkcja <math>\displaystyle f</math> jest bijekcją, więc musi istnieć <math>\displaystyle b\in X</math>,
dla którego <math>\displaystyle f(b)=z</math>. Łatwo zauważyć, że <math>\displaystyle  b\neq a</math>, gdyż <math>\displaystyle f(b)=z\ \in f(a)</math>. Element
<math>\displaystyle b</math> nie może być elementem <math>\displaystyle a</math>, gdyż wtedy <math>\displaystyle f(b)=b</math> i <math>\displaystyle z=b \in a</math>. Wobec tego <math>\displaystyle a</math> musi
być elementem <math>\displaystyle b</math>, ale wtedy <math>\displaystyle a \subset b</math> i z monotoniczności <math>\displaystyle f</math> dostajemy <math>\displaystyle f(a)
\subset f(b)</math>, co jest sprzeczne z faktem <math>\displaystyle f(b) \in f(a)</math> (bo wtedy <math>\displaystyle f(b)\in f(b)</math>).

Pokazaliśmy, że założenie o niepustości zbioru <math>\displaystyle A</math> prowadzi do sprzeczności. Zbiór
ten musi więc być pusty co oznacza, że funkcja <math>\displaystyle f</math> jest identycznością. Wobec tego,
każde dwie podobne liczby porządkowe są sobie równe.
}}

Powyższe twierdzenie mówi, że każde dwie liczby porządkowe są porównywalne przez
inkluzję. Przez analogię do liczb naturalnych używamy jednak dla liczb porządkowych
oznaczenia <math>\displaystyle x \leq y</math>, zamiast <math>\displaystyle x\subset y</math>.

Z powyższego twierdzenia wynika, że każdy zbiór liczb porządkowych jest uporządkowany
liniowo przez inkluzję.

{{cwiczenie|4.9||

Udowodnij, że każdy zbiór liczb porządkowych jest dobrze uporządkowany inkluzją.

}}

<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">  

Niech <math>\displaystyle X</math> będzie zbiorem liczb porządkowych, i niech <math>\displaystyle A</math> będzie niepustym podzbiorem <math>\displaystyle X</math>. Weźmy dowolny element <math>\displaystyle a\in A</math> oraz zbiór <math>\displaystyle A'=\{x\in A: x \in a\}</math>.
Rozważymy dwa przypadki:

# Jeśli zbiór <math>\displaystyle A'</math> jest pusty, to dla dowolnego elementu <math>\displaystyle b\in A</math> mamy <math>\displaystyle b\notin a</math>, a więc <math>\displaystyle b \supset a</math> (ponieważ <math>\displaystyle X</math> jest uporządkowany liniowo przez inkluzję, a <math>\displaystyle b\subsetneq a</math> prowadziłoby do <math>\displaystyle b\in a</math>). Wtedy element <math>\displaystyle a</math> jest elementem najmniejszym <math>\displaystyle A</math>.
# Jeśli zbiór <math>\displaystyle A'</math> jesteś niepusty, to ponieważ jest podzbiorem liczby porządkowej <math>\displaystyle a</math>, to istnieje w nim element najmniejszy, oznaczmy go przez <math>\displaystyle c</math>. Wtedy dla dowolnego elementu <math>\displaystyle b\in A</math>. Jeśli <math>\displaystyle b\in A'</math>, to <math>\displaystyle c\subset b</math>. W przeciwnym przypadku <math>\displaystyle b \notin a</math>. Wtedy <math>\displaystyle b \supset a</math> i skoro <math>\displaystyle c\in a \subset b</math>, to <math>\displaystyle c \subset b</math>. Wynika stąd, że <math>\displaystyle c</math> jest najmniejszym elementem rodziny <math>\displaystyle A</math>.

</div></div>

{{twierdzenie|4.10. [Antynomia Burali-Forti]||

Nie istnieje zbiór liczb porządkowych.
}}

{{dowod|||

Dla dowodu nie wprost przypuśćmy, że taki zbiór istnieje, nazwijmy go <math>\displaystyle X</math>. Pokażemy,
że <math>\displaystyle X</math> jest liczbą porządkową. W poprzednich ćwiczeniach pokazaliśmy, że <math>\displaystyle X</math> jest
dobrze uporządkowany, przez inkluzję.

# Niech <math>\displaystyle x,y</math> będą różnymi elementami <math>\displaystyle X</math>. Wtedy <math>\displaystyle x\subsetneq y</math> lub <math>\displaystyle y\subsetneq x</math>. Z Ćwiczenia 4.6 (patrz [[#cwiczenie_4_6|Ćwiczenie 4.6]]) wynika, że w pierwszym przypadku mamy <math>\displaystyle x \in y</math>, a w drugim <math>\displaystyle y\in x</math>. Więc zbiór <math>\displaystyle X</math> spełnia pierwszy z warunków bycia liczbą porządkową.
# Weźmy dowolny element <math>\displaystyle x</math> ze zbioru <math>\displaystyle X</math>. Z Faktu 4.2 (patrz [[#fakt_4_2|Fakt 4.2.]]) wiemy, że każdy element <math>\displaystyle y</math> należący do zbioru <math>\displaystyle x</math> jest liczbą porządkową. Ponieważ do <math>\displaystyle X</math> należą wszystkie liczby porządkowe, to <math>\displaystyle x\subset X</math>. A więc <math>\displaystyle X</math> spełnia drugi warunek bycia liczbą porządkową.

Wobec powyższych faktów zbiór <math>\displaystyle X</math> jest liczbą porządkową, a więc musi być własnym
elementem. Otrzymaliśmy więc sprzeczność.
}}

W ostatnim twierdzeniu w tym rozdziale pokażemy, że każdy dobry porządek jest podobny
do pewnej liczby porządkowej, a więc każda "klasa" podobnych dobrych porządków ma
swojego reprezentanta, który jest liczbą porządkową.

<span id="twierdzenie_4_11">{{twierdzenie|4.11.||

Każdy zbiór dobrze uporządkowany jest podobny do pewnej liczby porządkowej.
}}</span>

{{dowod|||

Dla dowodu nie wprost załóżmy, że istnieje dobry porządek <math>\displaystyle (X,\leq)</math>, który nie jest podobny do żadnej liczby porządkowej. Z Twierdzenia 3.6 (patrz [[#twierdzenie_3_6|Twiedzenie 3.6.]]) wynika, że każda liczba porządkowa jest podobna do jakiegoś przedziału początkowego <math>\displaystyle X</math>. Używając aksjomatu zastępowania z (patrz [[Logika i teoria mnogości/Wykład 4: Teoria mnogości ZFC. Operacje na zbiorach#Schemat_Aksjomatu_Zastępowania|Wykład 4, Aksjomat Zastępowania]]) pokażemy, że istnieje wtedy zbiór liczb porządkowych.

Niech <math>\displaystyle \phi(o,p)</math> będzie formułą o zmiennych wolnych <math>\displaystyle o,p</math>, która będzie spełniona
wtedy i tylko wtedy, gdy <math>\displaystyle o</math> jest dobrym porządkiem, <math>\displaystyle p</math> jest liczbą porządkową i <math>\displaystyle o</math>
jest podobne do <math>\displaystyle p</math>. Nie jest trudno napisać taką formułę, ale nie jest ona krótka,
dlatego ten fragment dowodu pozostawiamy czytelnikowi. Ponieważ dwie liczby
porządkowe są podobne wtedy i tylko wtedy, gdy są równe, to do każdy dobry porządek <math>\displaystyle o</math>
jest podobny do co najwyżej jednej liczby porządkowej. Wobec tego dla dowolnego <math>\displaystyle o</math>
można dobrać co nawyżej jedno <math>\displaystyle p</math> takie, aby formuła <math>\displaystyle \phi(o,p)</math> była prawdziwa. To
znaczy że dla formuły <math>\displaystyle \phi(o,p)</math> przesłanka aksjomatu zastępowania jest spełniona.
Wobec tego prawdą jest również:

<center><math>\displaystyle \forall_x \exists_y \forall_p (p\in y \Leftrightarrow (\exists_o o\in x \wedge \phi(o,p))
</math></center>

Biorąc za <math>\displaystyle x</math> zbiór odcinków początkowych <math>\displaystyle X</math>, dostaniemy, że istnieje zbiór <math>\displaystyle y</math>
taki, że <math>\displaystyle p</math> należy do <math>\displaystyle y</math> wtedy i tylko wtedy, gdy istnieje <math>\displaystyle o</math> będący odcinkiem
początkowym <math>\displaystyle X</math>, dla którego prawdziwa jest formuła <math>\displaystyle \phi(o,p)</math>. Oznacza to dokładnie,
że istnieje zbiór wszystkich liczb porządkowych podobnych do przedziałów początkowych
<math>\displaystyle X</math>. Skoro założyliśmy, że każda liczba porządkowa jest podobna do pewnego przedziału
początkowego <math>\displaystyle X</math>, to istnieje zbiór liczb porządkowych. Otrzymaliśmy więc sprzeczność
z Twierdzeniem 4.10 (patrz [[#twierdzenie_4_10|Twierdzenie 4.10.]]).
}}

Najmniejszą nieskończoną liczbę porządkową będziemy oznaczać przez <math>\displaystyle \omega</math>. W
naszym podejściu <math>\displaystyle \omega</math> jest po prostu zbiorem <math>\displaystyle \mathbb{N}</math>, który jest dobrze
uporządkowany przez inkluzję. Przyjęło się jednak używać oznaczenia <math>\displaystyle \omega</math> dla
podkreślenia, że mówimy o dobrym uporządkowaniu. Będziemy mówić, że zbiór częściowo
uporządkowany jest ''typu'' <math>\displaystyle \omega</math>, jeśli jest podobny do
<math>\displaystyle (\mathbb{N},\subset_\mathbb{N})</math>. Podobnie dla dowolnej innej liczby porządkowej <math>\displaystyle x</math> powiemy, że
zbiór częściowo uporządkowany jest typu <math>\displaystyle x</math>, jeśli jest podobny do <math>\displaystyle (x,\subset_x)</math>

{{cwiczenie|4.12||

Udowodnij, że dla dowolnych rozłącznych dobrych porządków <math>\displaystyle (A,\leq_A),
(B,\leq_B)</math> następujące zbiory są dobrymi porządkami:

# <math>\displaystyle (A,\leq_A) \oplus (B,\leq_B) =(A\cup B, \leq_A \cup \leq_B \cup A \times B)</math>, czyli na zbiorach <math>\displaystyle A,B</math> porządki są takie, jak w zbiorach wyjściowych, a do tego każdy element zbioru <math>\displaystyle A</math> jest mniejszy od każdego elementu zbioru <math>\displaystyle B</math>.
# <math>\displaystyle (A,\leq_A) \otimes (B,\leq_B)= (A \times B, \leq_{A \times B})</math>, gdzie <math>\displaystyle \leq_{A \times B}</math> jest porządkiem leksykograficznym, czyli

<center><math>\displaystyle (a_1,b_1) \leq_{A \times B} (a_2,b_2) \Leftrightarrow (a_1<_A a_2) \vee (a_1=a_2\wedge b_1\leq_A b_2).
</math></center>

}}

<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">  
: 1. Weźmy dowolny niepusty podzbiór <math>\displaystyle X\subset A \cup B</math>. Pokażemy, że istnieje w nim element najmniejszy. Rozważmy dwa przypadki:

: a) Jeśli <math>\displaystyle X\cap A \neq \emptyset</math>, to w tym zbiorze istnieje element najmniejszy, oznaczmy go przez <math>\displaystyle x_0</math>. Element ten jest również najmniejszym elementem w zbiorze <math>\displaystyle X</math>, gdyż jest mniejszy od wszystkich elementów <math>\displaystyle X\cap A</math> oraz należy do <math>\displaystyle A</math>, a więc z definicji porządku na <math>\displaystyle A\cup B</math> jest mniejszy od wszystkich elementów z <math>\displaystyle B</math>, w szczególności od elementów z <math>\displaystyle X\cap B</math>.

: b) Jeśli <math>\displaystyle X\cap A = \emptyset</math>, to <math>\displaystyle X\subset B</math> i wobec tego istnieje w <math>\displaystyle X</math> element, który jest najmniejszy w <math>\displaystyle X</math>, względem porządku <math>\displaystyle \leq_B</math>. Element ten jest najmniejszy w całym zbiorze <math>\displaystyle X</math>, ponieważ porządek na całym zbiorze <math>\displaystyle A\cup B</math> jest rozszerzeniem porządku na <math>\displaystyle B</math> tak, że wszystkie elementy zbioru <math>\displaystyle A</math> są mniejsze od każdego elementu zbioru <math>\displaystyle B</math>.

: 2. Weźmy dowolny niepusty podzbiór <math>\displaystyle X\subset A \times B</math>. Pokażemy, że istnieje w nim element najmniejszy. Rozważmy zbiór <math>\displaystyle X_L</math> (jest to zbiór składający się z lewych współrzędnych par ze zbioru <math>\displaystyle X</math>).  Zbiór ten jest podzbiorem <math>\displaystyle A</math> i ponieważ <math>\displaystyle X</math> jest niepusty, to <math>\displaystyle X_L</math> również. Skoro <math>\displaystyle A</math> jest dobrze uporządkowany relacją <math>\displaystyle \leq_A</math>, to w <math>\displaystyle X_L</math> istnieje element najmniejszy względem <math>\displaystyle \leq_A</math> oznaczmy go przez <math>\displaystyle a_0</math>. Rozważmy teraz zbiór <math>\displaystyle B_0=\{b\in B: (a_0,b)\in X\}</math>. Ponieważ <math>\displaystyle a_0\in X_L</math>, to zbiór <math>\displaystyle B_0</math> musi być niepusty. <math>\displaystyle B_0</math> jest podzbiorem <math>\displaystyle B</math>, wobec czego musi istnieć w tym zbiorze element najmniejszy, oznaczmy go przez <math>\displaystyle b_0</math>. Pokażemy, że <math>\displaystyle (a_0,b_0)</math> jest najmniejszym elementem zbioru <math>\displaystyle X</math>. Weźmy dowolny element <math>\displaystyle (a_1,b_1)</math> zbioru  <math>\displaystyle X</math>. Ponieważ <math>\displaystyle a_0</math> jest najmniejszy w <math>\displaystyle X_L</math>, to mamy <math>\displaystyle a_0 \leq_A a_1</math>. Jeśli <math>\displaystyle a_0 < a_1</math>, to z definicji porządku <math>\displaystyle \leq_{A \times B}</math> otrzymujemy <math>\displaystyle (a_0,b_0) \leq_{A \times B} (a_1,b_1)</math>. W przeciwnym przypadku mamy <math>\displaystyle a_0=a_1</math>, wtedy <math>\displaystyle b_1 \in B_0</math> i ponieważ <math>\displaystyle b_0</math> jest najmniejszy w tym zbiorze, to otrzymujemy <math>\displaystyle b_0 \leq_b b_1</math>. Wobec tego zgodnie z definicją <math>\displaystyle \leq_{A \times B}</math> mamy <math>\displaystyle (a_0,b_0) \leq_{A \times B} (a_1,b_1)</math>. Wynika stąd, że element <math>\displaystyle (a_0,b_0)</math> jest najmniejszy w <math>\displaystyle X</math>. Wobec dowolności wybory <math>\displaystyle X</math> otrzymujemy, że zbiór <math>\displaystyle A\times B</math> jest dobrze uporządkowany relacją <math>\displaystyle \leq_{A \times B}</math>.

</div></div>

Powyższe konstrukcje łatwo zaadaptować do operowania na zbiorach, które nie są
rozłączne. W miejsce <math>\displaystyle A</math> wystarczy wziąć zbiór <math>\displaystyle \{0\} \times A</math>, a w miejsce <math>\displaystyle B</math> zbiór
<math>\displaystyle \{1\} \times B</math>. Wtedy będziemy mieli zagwarantowaną rozłączność. Porządek na tak
zmienionych zbiorach łatwo przenieść z wyjściowych zbiorów poprzez naturalną bijekcję
pomiędzy nimi (czyli <math>\displaystyle [(0,a_1) \leq_{\{0\} \times A }(0,a_2)] \Leftrightarrow a_1\leq_A a_2</math>). W
dalszej części będziemy sie posługiwać tak zmodyfikowanymi konstrukcjami, nie dbając o
rozłączność zbiorów. Zdefiniujemy  teraz arytmetykę na liczbach porządkowych.

{{definicja|4.13.||

Niech <math>\displaystyle a,b</math> będą liczbami porządkowymi. Wtedy:
# Liczbę porządkową podobną do  <math>\displaystyle (a,\subset) \oplus (b,\subset)</math> będziemy oznaczać przez <math>\displaystyle a+b</math>.
# Liczbę porządkową podobną do  <math>\displaystyle (a,\subset) \otimes (b,\subset)</math> będziemy oznaczać przez <math>\displaystyle a \cdot b</math>.
}}
{{cwiczenie|4.14||

Sprawdź, czy prawdziwe są następujące własności liczb porządkowych:
# <math>\displaystyle 1+\omega= \omega</math>.
# <math>\displaystyle \omega +1 \neq \omega</math>.
# <math>\displaystyle \omega + \omega = 2 \cdot \omega</math>.
# <math>\displaystyle a < b \Rightarrow a+c < b+c</math>.
# <math>\displaystyle b+a= c+a \Rightarrow b=c</math>.
# <math>\displaystyle a+b= a+c \Rightarrow b=c</math>.
# <math>\displaystyle a \cdot b= a \cdot c \Rightarrow b=c</math>.
# <math>\displaystyle x \cdot y = y \cdot x</math>.

}}

<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">  
: 1. Równość jest prawdziwa. Zgodnie z definicją dodawania <math>\displaystyle 1+\omega</math> to liczba porządkowa odpowiadająca zbiorowi liczb naturalnych z dodanym jednym elementem jako
najmniejszym, oznaczymy go przez <math>\displaystyle \bot</math>. Łatwo zauważyć, że funkcja
<math>\displaystyle f:\mathbb{N}\cup\{\bot\} \rightarrow \mathbb{N}</math> określona w następujący sposób:

<math>f(\bot) = 0 \\ F(n)& = n+1, \quad dla \quad \displaystyle n\in \mathbb{N}</math>

: jest monotoniczną bijekcją. Wobec tego częściowe porządki są podobne, a więc odpowiadają jednej liczbie porządkowej <math>\displaystyle \omega</math>.

: 2. Równość nie jest prawdziwa. Łatwo zauważyć, że w porządku <math>\displaystyle \omega+1</math> istnieje element największy, a w <math>\displaystyle \omega</math> nie.

: 3. Równość jest prawdziwa. Zgodnie z rozszerzeniem konstrukcji z ćwiczenia na zbiory, które nie muszą być rozłączne, porządki <math>\displaystyle (\omega,\leq) \oplus (\omega,\leq)</math> oraz <math>\displaystyle (\{0,1\},\leq) \times (\omega,\leq)</math> są dokładnie identyczne, a więc odpowiadają tej samej liczbie porządkowej.

: 4. Implikacja nie jest prawdziwa. Na przykład mamy <math>\displaystyle 0<1</math>, ale nieprawda, że <math>\displaystyle 0+\omega < 1+\omega</math>, gdyż te liczby są równe.

: 5. Implikacja nie jest prawdziwa. Sytuacja jest analogiczna do poprzedniego punktu. Mamy <math>\displaystyle 0+\omega=1+\omega</math>, ale nieprawda, że <math>\displaystyle 0=1</math>.

: 6. Implikacja jest prawdziwa. Przypuśćmy, że <math>\displaystyle a,b,c</math> są liczbami porządkowymi, takimi że <math>\displaystyle a+b= a+c</math>. Niech <math>\displaystyle (A,\leq_A),(B,\leq_B),(C,\leq_C)</math> będą rozłącznymi porządkami podobnymi odpowiednio do <math>\displaystyle (a,\subset),(b,\subset),(c,\subset)</math>. Równość <math>\displaystyle a+b=a+c</math> implikuje, że porządki <math>\displaystyle (A,\leq_A)\oplus (B,\leq_B)</math> i <math>\displaystyle (A,\leq_A)\oplus(C,\leq_C)</math> są podobne. Niech <math>\displaystyle f</math> będzie monotoniczną bijekcją z <math>\displaystyle A\cup B</math> w <math>\displaystyle A\cup C</math>. Ponieważ żaden dobry porządek nie jest podobny do swojego istotnego przedziału początkowego, to <math>\displaystyle \vec{f}(A)=A</math>, wobec tego <math>\displaystyle \vec{f}(B)=C</math>. Skutkiem tego <math>\displaystyle f\cap B\times C</math> jest podobieństwem pomiędzy porządkami <math>\displaystyle (B,\leq_B), (C,\leq_C)</math>. W efekcie odpowiadające im liczby porządkowe są równe, czyli <math>\displaystyle b=c</math>.

: 7. Implikacja nie jest prawdziwa. Pokażemy, że <math>\displaystyle \omega \cdot 2= \omega \cdot 1</math>, podczas gdy <math>\displaystyle 1\neq 2</math>. Ponieważ <math>\displaystyle \omega \cdot 1 =\omega</math>, to pokażemy, że również <math>\displaystyle \omega \cdot 2=\omega</math>. Zdefiniujmy funkcję <math>\displaystyle f:\omega \times 2 \rightarrow \omega</math> następująco:

<center><math>\displaystyle f(n,x)= 2 \cdot n+x.
</math></center>

: Ponieważ <math>\displaystyle x\in \{0,1\}</math>, to <math>\displaystyle f</math> jest bijekcją. Udowodnimy, że <math>\displaystyle f</math> jest monotoniczna. Weźmy dowolne różne pary <math>\displaystyle (n,a),(m,b) \in \omega \times 2</math> takie, że <math>\displaystyle (n,a)\leq_{\omega \times 2}(m,b)</math>. Rozważymy dwa przypadki:

: a) Jeśli <math>\displaystyle n<m</math>, to:
<center><math>\displaystyle f(n, x)= 2\cdot n+x \leq 2\cdot n+1 < 2\cdot (n+1) \leq 2 \cdot m \leq  2 \cdot m +b=f(m,b).
</math></center>

: b) W przeciwnym przypadku mamy <math>\displaystyle n=m</math> oraz <math>\displaystyle a<b</math>. Wobec tego <math>\displaystyle a</math> musi być równe 0, a <math>\displaystyle b</math> równe 1. Wtedy

<center><math>\displaystyle f(n,x)=2\cdot n = 2\cdot m \leq 2\cdot m+1 =f(m,b).
</math></center>

: 8. Równość nie jest prawdziwa. Pokażemy, że <math>\displaystyle 2 \cdot \omega  \neq \omega  \cdot 2</math>. W poprzednim punkcie pokazaliśmy, że <math>\displaystyle \omega \cdot 2=\omega</math>. Rozważmy zbiór <math>\displaystyle (2,\subset) \otimes (\omega,\subset)</math>. Weźmy zbiór <math>\displaystyle \{0\} \times \omega</math>, który jest podzbiorem <math>\displaystyle 2\times \omega</math>. Łatwo zauważyć, że <math>\displaystyle \{0\} \times \omega</math> jest istotnym odcinkiem początkowym <math>\displaystyle (2,\subset) \otimes (\omega,\subset)</math>, który w dodatku jest podobny do <math>\displaystyle \omega</math>. Wobec tego porządki <math>\displaystyle (\omega,\subset)</math> oraz <math>\displaystyle (2,\subset) \otimes (\omega,\subset)</math> nie mogą być podobne, a więc również <math>\displaystyle \omega \neq 2\cdot \omega</math>.

</div></div>

{{cwiczenie|4.15||

Udowodnij, że liczba porządkowa <math>\displaystyle x</math> jest skończona wtedy i tylko wtedy, gdy relacja <math>\displaystyle \subset_x^{-1}</math> (czyli <math>\displaystyle \supset_x</math>) jest dobrym porządkiem na <math>\displaystyle x</math>. 
}}

<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">  

Na początek zauważmy, że każda skończona liczba porządkowa ma powyższą własność. Niech <math>\displaystyle n</math> będzie skończoną liczbą porządkową. Wiemy, że <math>\displaystyle n</math> jest dobrze uporządkowany przez inkluzję. Wystarczy wykazać, że jest dobrze uporządkowany przez odwróconą inkluzję, a więc że każdy niepusty podzbiór <math>\displaystyle n</math> ma element największy. Ta własność wynika jednak z udowodnionej w Wykładzie 7 Zasady Maksimum (patrz [[Logika i teoria mnogości/Wykład 7: Konstrukcja von Neumanna liczb naturalnych, twierdzenie o indukcji, zasady minimum, maksimum, definiowanie przez indukcje#twierdzenie_5_3|Wykład 7, Zasada Maksimum]] ). Rozważmy teraz nieskończoną liczbę porządkową <math>\displaystyle x</math>. Skoro <math>\displaystyle x</math> jest nieskończona to <math>\displaystyle \omega</math> musi być podobna do przedziału początkowego <math>\displaystyle x</math>. Ponieważ w <math>\displaystyle \omega</math> nie ma elementu największego, to zbiór <math>\displaystyle x</math> nie może być dobrze uporządkowany przez odwrotną inkluzję.
</div></div>