14. Dobre porządki, liczby porządkowe

Jak zauważyliśmy w poprzednim rozdziale, każdy niepusty podzbiór $\mathbb{N}$ ma element najmniejszy. Z tej zasady minimum wynika zasada indukcji porządkowej. Dlatego wyróżnia się liniowe porządki spełniające tę zasadę.

Definicja 14.1   Załóżmy, że $\leq$ jest liniowym porządkiem na zbiorze $X$. Mówimy wtedy, że $X$ jest dobrze uporządkowany przez $\leq$, gdy każdy niepusty podzbiór $X$ ma element najmniejszy.

Przykładem zbioru dobrze uporządkowanego jest $\mathbb{N}$ ze zwykłym porządkiem $\leq$ (zasada minimum). Inny przykład to zbiór liczb

$$Z^*=\{1-{1\over n+1}:n\in{\mathbb{N}}\}\cup\{2-{1\over n+1}:n\in{\bf N}\},$$

ze zwykłym porządkiem $\leq$.

Gdy $\leq$ jest porządkiem na zbiorze $X$, przez $<$ oznaczamy relację określoną wzorem

$$x<y\Leftrightarrow x\leq y\land x\neq y.$$

Każda relacja porządku w tym rozdziale będzie oznaczana przez $\leq$. Dlatego będziemy mówili, że zbiór $X$ jest dobrym [liniowym] porządkiem, mając na myśli, że jest dobrze [liniowo] uporządkowany przez pewną relację $\leq$.

Załóżmy, że $X$ jest dobrym porządkiem. Wtedy dla każdego elementu $x$, który nie jest największy w $X$, istnieje element $x'\in X$, który jest najmniejszy w zbiorze wszystkich elementów $X$ większych od $x$. Zatem $x'>x$ i między nimi nie ma już żadnego innego elementu. Element $x'$ nazywamy następnikiem elementu $x$, zaś element $x$ poprzednikiem elementu $x'$. Może się też zdarzyć, że dany element $x\in X$ nie ma poprzednika. Wtedy taki element nazywamy granicznym, o ile nie jest najmniejszym elementem w całym zbiorze $X$. Przykładem elementu granicznego w zbiorze $Z^*$ jest liczba $1$.

Uwaga 14.2   Zbiór $X$ jest dobrym porządkiem $\Leftrightarrow$ nie istnieje nieskończony malejący ciąg elementów zbioru $X$.

Dowód. $\Rightarrow.$ Nie wprost. Jeśli $(a_n)$ jest malejącym ciągiem elementów $X$, to zbiór $\{a_n:n\in{\mathbb{N}}\}$ nie ma elementu najmniejszego, przecząc dobremu uporządkowaniu zbioru $X$.

$\Leftarrow$. Nie wprost. Załóżmy, że $A\subseteq X$ jest niepusty i nie ma elementu najmniejszego. Definiujemy rekurencyjnie malejący ciąg $(a_n)$ elementów zbioru $X$.

Niech $a_0$ będzie jakimkolwiek elementem zbioru $A$. Jeśli $a_n\in A$ jest już określony, to na mocy założenia dowodu nie wprost, $a_n$ nie jest najmniejszy w $A$. Zatem definiujemy $a_{n+1}$ jako dowolny element zbioru $A$ mniejszy niż $a_n$.

Istnienie ciągu malejącego $(a_n)$ przeczy jednak założeniom uwagi. $\Box$

W powyższym dowodzie używaliśmy pewnika wyboru (w którym miejscu ?). Ważną konsekwencją pewnika wyboru jest też następujący fakt.

Twierdzenie 14.3   Każdy zbiór można dobrze uporządkować.

W zbiorze dobrze uporządkowanym obowiązuje zasada minimum. Jej konsekwencją jest pewien wariant zasady indukcji porządkowej, zwany zasadą indukcji pozaskończonej. Nazwa bierze się stąd, że w kroku indukcyjnym dla dowodu $\varphi(x)$ zakładamy prawdziwość $\varphi(y)$ dla wszystkich $y<x$, których może być nieskończenie wiele.

Twierdzenie 14.4 (Zasada indukcji pozaskończonej)   Załóżmy, że $X$ jest dobrze uporządkowany. Wtedy dla dowolnej funkcji zdaniowej $\varphi(x),x\in X$ prawdziwe jest zdanie

$$\varphi(x_0)\land(\forall x)((\forall y<x)\varphi(y)\Rightarrow\varphi(x))\Rightarrow(\forall x\in X)\varphi(x).$$

Tu $x_0$ oznacza najmniejszy element zbioru $X$.

Dowód. Podobny jak w rozdziale 13. $\Box$

Te dwa twierdzenia uzasadniają zainteresowanie zbiorami dobrze uporządkowanymi. Zbiory takie odgrywają fundamentalną rolę w teorii mnogości.

Definicja 14.5   Załóżmy, że zbiory $X$ i $Y$ są liniowo uporządkowane.
(1) Zbiór $A\subseteq X$ nazywamy odcinkiem początkowym zbioru $X$, gdy wraz z każdym elementem $x$ należą do niego również wszystkie elementy mniejsze od $x$. Symbolicznie znaczy to, że

$$(\forall x\in A)(\forall y\in X)(y<x\Rightarrow y\in A).$$

Gdy $A\neq X$, mówimy, że $A$ jest właściwym odcinkiem początkowym zbioru $X$.
(2) Mówimy, że $f:X\to Y$ jest izomorfizmem porządkowym, gdy $f$ jest bijekcją i dla dowolnych $x,y\in X$ mamy $x\leq y\Leftrightarrow f(x)\leq f(y)$.
(3) Mówimy, że $X$ i $Y$ są izomorficzne, gdy istnieje między nimi izomorfizm porządkowy.

Izomorfizm jest relacją równoważności na klasie zbiorów liniowo uporządkowanych, podobnie jak równoliczność jest relacją równoważności na klasie wszystkich zbiorów. My będziemy zajmować się klasami izomorfizmu zbiorów dobrze uporządkowanych. Klasy zbiorów równolicznych odpowiadają liczbom kardynalnym. W przypadku dobrych porządków klasom izomorfizmu odpowiadają liczby porządkowe (zwane też typami porządkowymi). Dokładniej, w teorii mnogości dla dobrych porządków $X$ konstruuje się zbiory $ot(X)$, zwane liczbami porządkowymi, takie że dla wszystkich dobrych porządków $X,Y$ mamy

$X$ i $Y$ są izomorficzne $\Leftrightarrow ot(X)=ot(Y)$.

Liczby porządkowe oznaczamy małymi greckimi literami $\alpha,\beta,\gamma,\dots$

Załóżmy, że $X$ jest dobrym porządkiem oraz $x\in X$. Wtedy zbiór $o(x)=\{y\in X:y<x\}$ jest właściwym odcinkiem początkowym $X$, wyznaczonym przez $x$. Na odwrót, gdy $A$ jest właściwym odcinkiem początkowym zbioru $X$, to $A=o(x)$, gdzie $x$ jest najmniejszym elementem zbioru $X\setminus A$ (ćwiczenie).

Lemat 14.6   Załóżmy, że $X$ i $Y$ są dobrymi porządkami.
(1) Jeśli $X$ i $Y$ są izomorficzne, istnieje tylko jeden izomorfizm między nimi. W tym izomorfizmie każdy odcinek początkowy zbioru $X$ przechodzi na odcinek początkowy zbioru $Y$.
(2) $X$ nie jest izomorficzny z żadnym swoim właściwym odcinkiem początkowym.

Dowód. (1) Załóżmy, że $f:X\to Y$ i $g:X\to Y$ są izomorfizmami. Pokażemy, że

$(*)$

dla każdego $x\in X, f(x)=g(x)$.

Najpierw podamy kilka własności izomorfizmów zbiorów dobrze uporządkowanych.

(a)

Niech $x_0$ będzie najmniejszym elementem $X$. Wtedy $f(x_0)$ jest najmniejszym elementem $Y$.

By to udowodnić, oznaczmy przez $y_0$ najmniejszy element zbioru $Y$. Skoro $f$ jest ``na'', znajdujemy element $x_1\in X$ taki, że $f(x_1)=y_0$. Mamy $x_0\leq x_1$, więc skoro $f$ jest izomorfizmem, to również $f(x_0)\leq f(x_1)=y_0$. Ale $f(x_0)\in Y$ i $y_0$ jest najmniejszy w $Y$, więc $f(x_0)\leq y_0$ pociąga $f(x_0)=y_0$.

(b)

$f$ przekształca każdy odcinek początkowy $o(x)$ zbioru $X$ na odcinek początkowy $o(f(x))$ zbioru $Y$.

Dowód pozostawiamy jako ćwiczenie.

Dowód $(*)$ przeprowadzimy przez indukcję pozaskończona. W tym celu rozważmy dowolny element $x_1\in X$ i załóżmy, że dla wszystkich $x'<x_1$ mamy $f(x')=g(x')$, czyli w szczególności $f[o(x_1)]=g[o(x_1)]$. Udowodnimy, że $f(x_1)=g(x_1)$.

Na mocy (b), $f[o(x_1)]$ jest odcinkiem początkowym $Y$ postaci $o(y_1)$, gdzie $f(x_1)=y_1$. (b) zachodzi również dla izomorfizmu $g$, zatem $g[o(x_1)]$ jest odcinkiem początkowym $Y$ postaci $o(y_2)$, gdzie $g(x_1)=y_2$. Jednak $o(y_1)=o(y_2)$, więc $y_1=y_2$, czyli $f(x_1)=g(x_1)$, co kończy dowód (1).

(2) Nie wprost. Przypuśćmy, że $x\in X$ i $f:X\to o(x)$ jest izomorfizmem. Wtedy $x>f(x)$. Z definicji izomorfizmu dostajemy, że

$$x>f(x)>f^2(x)>f^3(x)>\dots$$

Istnienie takiego malejącego ciągu przeczy uwadze 14.2. $\Box$

Podobnie jak w przypadku liczb kardnynalnych, liczby porządkowe możemy porównywać. Kluczowe jest tu spostrzeżenie, że jeśli $X$ jest dobrym porządkiem, to każdy jego podzbiór też jest dobrym porządkiem (względem relacji $\leq$ na $X$).

Definicja 14.7   Niech $\alpha,\beta$ będą liczbami porządkowymi. Wtedy $\alpha\leq\beta\Leftrightarrow$ pewien zbiór $Y$ typu $\beta$ zawiera odcinek początkowy typu $\alpha$.

Oczywiście jeżeli $\alpha\leq\beta$, to każdy zbiór $Y$ typu $\beta$ zawiera odcinek początkowy typu $\alpha$. Ponadto piszemy $\alpha<\beta$, gdy $\alpha\leq\beta$ i $\alpha\neq\beta$. Kolejny lemat pokazuje, że $\leq$ jest liniowym porządkiem na klasie wszystkich liczb porządkowych.

Lemat 14.8 (1)   (zwrotność) $\alpha\leq\alpha$.
(2) (przechodniość) Jeśli $\alpha\leq\beta$ i $\beta\leq\gamma$, to $\alpha\leq\gamma$.
(3) (antysymetryczność) Jeśli $\alpha\leq\beta$ i $\beta\leq\alpha$, to $\alpha=\beta$.
(4) (spójność) $\alpha\leq\beta$ lub $\beta\leq\alpha$.

Dowód. (1) jest oczywiste. (2) jest łatwe.

(3) Nie wprost. Niech $X$ będzie dobrym porządkiem typu $\alpha$. Przypuśćmy, że $\alpha\neq\beta$ i $\alpha\leq\beta\leq\alpha$. Znaczy to, że $\alpha<\beta<\alpha$. Warunek ten pociąga, że $X$ jest izomorficzny z pewnym swoim odcinkiem początkowym, co przeczy lematowi 14.6(2).

(4) Dowód przypomina dowód spójności porządku na liczbach kardynalnych, nie używa jednak pewnika wyboru.

Niech $X$ będzie dobrym porządkiem typu $\alpha$, zaś $Y$ dobrym porządkiem typu $\beta$. Udowodnimy, że jeden z tych dobrych porządków jest izomorficzny z odcinkiem początkowym drugiego lub oba są izomorficzne. Niech

$T=\{A\subseteq X: A$ jest odcinkiem początkowym $X$ i istnieje isomorfizm $f_A$ między $A$ i pewnym odcinkiem początkowym zbioru $Y\}$.

Oczywiście zbiór $T$ jest liniowo uporządkowany przez inkluzję $\subseteq$. Z lematu 14.6 wynika, że dla $A\in T$ izomorfizm $f_A$ jest jedyny. Dlatego gdy $A\subseteq B\in T$, to $f_B$ jest rozszerzeniem $f_A$ (tzn. $f_A\subseteq f_B$). Niech

$$X'=\bigcup T, f=\bigcup_{A\in T}f_A\mbox{ oraz } Y'=Rng(f)=\bigcup_{A\in T}Rng(f_A).$$

Widzimy, że $X'$ i $Y'$ są odcinkami początkowymi zbiorów $X$ i $Y$ oraz $f$ jest izomorfizmem między $X'$ i $Y'$.

Przypadek 1. $X'=X$ i $Y'=Y$. Wtedy $X$ i $Y$ są izomorficzne, więc $\alpha=\beta$.

Przypadek 2. Jeden ze zbiorów $X',Y'$ jest równy $X$ lub $Y$ odpowiednio. Wtedy bądź $X=X'$ jest izomorficzny z odcinkiem początkowym $Y'$ zbioru $Y$ (i $\alpha\leq\beta$), bądź $Y=Y'$ jest izomorficzny z odcinkiem początkowym $X'$ zbioru $X$ (i $\beta\leq\alpha$).

Przypadek 3. $X\neq X'$ i $Y\neq Y'$. W tym przypadku dojdziemy do sprzeczności (co zakończy dowód). Wybieramy $x\in X$ i $y\in Y$ takie, że $X'=o(x)$ i $Y'=o(y)$. Wtedy zbiór $A=X'\cup\{x\}$ jest odcinkiem początkowym zbioru $X$, izomorficznym z odcinkiem początkowym $Y'\cup\{y\}$ zbioru $Y$ (poprzez funkcję $f_A$ rozszerzającą $f$ i taką, że $f_A(x)=y$). Zatem $A\in T$, więc $A\subseteq X'$, sprzeczność. $\Box$

Wniosek 14.9 (1)   Dla każdej liczby porządkowej $\alpha$, liczby porządkowe $<\alpha$ tworzą zbiór dobrze uporządkowany typu $\alpha$ (zbiór ten oznaczamy przez $o(\alpha)$).
(2) Każdy niepusty zbiór liczb porządkowych zawiera element najmniejszy.

Dowód. (1) Niech $X$ będzie dobrym porządkiem typu $\alpha$. Dla każdego $x\in X$ niech $\beta(x)$ będzie typem porządkowym zbioru $o(x)$. Wówczas $\beta(x)<\alpha$ i każda liczba porządkowa $\beta<\alpha$ jest typem porządkowym jedynego odcinka początkowego zbioru $X$.

Dlatego po pierwsze istnieje zbiór $o(\alpha)$ liczb porządkowych mniejszych od $\alpha$. Fakt ten jest konsekwencją tak zwanego aksjomatu zastępowania (który omówimy w następnym rozdziale). Po drugie, funkcja $F:X\to o(\alpha)$ jest izomorfizmem porządkowym. Zatem zbiór $o(\alpha)$ jest dobrze uporządkowany przez $\leq$.

(2) Niech $Z$ będzie pewnym niepustym zbiorem liczb porządkowych. Niech $\alpha\in Z$. Jeśli $\alpha$ nie jest najmniejszy w $Z$, to wszystkie elementy $Z$ mniejsze od $\alpha$ leżą w zbiorze $Z\cap o(\alpha)$, który jest podzbiorem dobrego porządku $o(\alpha)$. Dlatego zawiera on element najmniejszy. $\Box$.

Kolejna uwaga przypomina antynomię Russella.

Uwaga 14.10   Nie istnieje zbiór wszystkich liczb porządkowych.

Dowód. Nie wprost. Przypuśćmy, że $Z$ jest zbiorem wszystkich liczb porządkowych. Wówczas $Z$ jest dobrze uporządkowany przez relację $\leq$. Niech $\alpha$ będzie typem porządkowym zbioru $Z$. Wtedy $\alpha\in Z$ i na mocy wniosku 14.9, zbiór $o(\alpha)$ ma również typ $\alpha$. Zatem $\alpha<\alpha$, sprzeczność z lematem 14.8(3). $\Box$

Na liczbach porządkowych definiujemy działania dodawania i mnożenia.

Definicja 14.11   Niech $\alpha$ i $\beta$ będą liczbami porządkowymi.
(1) Sumą $\alpha+\beta$ nazywamy typ porządkowy zbioru $X\cup Y$, gdzie $ot(X)=\alpha, ot(Y)=\beta$ i $X\cap Y=\emptyset$, zaś zbiór $X\cup Y$ porządkujemy w ten sposób, że na częściach $X$ i $Y$ zachowujemy ich uporządkowanie i dodatkowo kładziemy $x\leq y$ dla wszystkich $x\in X$ i $y\in Y$.
(2) Iloczynem $\alpha\cdot\beta$ nazywamy typ porządkowy zbioru $X\times Y$, gdzie $ot(X)=\beta,\ ot(Y)=\alpha$, zaś porządek $\leq$ na zbiorze $X\times Y$ określony jest w sposób leksykograficzny:

$$\langle x,y\rangle\leq\langle x',y'\rangle\Leftrightarrow x<x'\lor(x=x'\land y\leq y').$$

Przykłady.

Konstrukcja liczb porządkowych w teorii mnogości ma dodatkową własność, że $o(\alpha)=\alpha$, to znaczy liczba $\alpha$ jest wręcz równa zbiorowi liczb od niej mniejszych.

Zwróćmy uwagę, że wynika stąd, że najmniejsza liczba porządkowa (tzn. typ porządkowy zbioru pustego) to zbiór pusty $\emptyset$, druga liczba porządkowa to $\{\emptyset\}$, czyli $1$, i ogólniej $n$-ta liczba porządkowa to zbiór $\{0,1,\dots,n-1\}$, czyli liczba naturalna $n$.

Typ porządkowy zbioru liczb naturalnych $\mathbb{N}$ ze zwykłym porządkiem oznaczamy przez $\omega$. Widzimy więc, że w istocie $\omega=\{0,1,2,\dots\}={\mathbb{N}}$.

Zgodnie z terminologią wprowadzoną na początku rozdziału dzielimy liczby porządkowe na następniki (tzn. takie liczby, które mają poprzednik), liczby graniczne (tzn. liczby bez poprzednika, różne od zera) i zero (pierwszą liczbę porządkową).

Widzimy, że następnik liczby $\alpha$ to typ porządkowy zbioru $o(\alpha)$ powiększonego o dodatkowy największy element. Zatem jest to liczba $\alpha+1=\alpha\cup\{\alpha\}$. Zwróćmy uwagę na podobieństwo z definicją liczby $n+1$.

Typ porządkowy zbioru $Z^*$ z początku rozdziału to $\omega+\omega$. Istotnie, zbiór ten jest sumą dwóch porządkowych kopii zbioru liczb naturalnych, ułożonych jedna za drugą.

Dodawanie i mnożenie liczb naturalnych nie jest przemienne. Na przykład $1+\omega=\omega$, jeśli bowiem na początku zbioru liczb naturalnych dopiszemy jeden element, to typ porządkowy zbioru się nie zmieni. Z drugiej strony liczba $\omega+1$ jest następnikiem $\omega$. Zatem $1+\omega\neq\omega+1$.

Podobnie $2\cdot\omega=\omega$. Istotnie, jest to typ porządkowy $\omega$ kopii porządku dwuelementowego, ułożonych jedna za drugą. Z drugiej strony $\omega\cdot 2=\omega+\omega$ jest typem porządkowym dwóch kopii zbioru $\omega$ ułożonych jedna za drugą. Widzimy więc, że $\omega\cdot 2\neq 2\cdot\omega$.

Bez pewnika wyboru (używając tylko aksjomatu zastępowania) można udowodnić istnienie nieprzeliczalnej liczby porządkowej. Najmniejszą nieprzeliczalną liczbę porządkową oznaczamy przez $\omega_1$, zaś jej moc przez $\aleph_1$. Zatem hipoteza continuum mówi, że $2^{\aleph_0}=\aleph_1$. Moce nieskończonych liczb porządkowych nazywamy alefami. Dokładniej, alefy są to wręcz liczby porządkowe $\alpha\geq\omega$ takie, że $\alpha$ nie jest równoliczna z żadną mniejszą liczbą porządkową (tzn. z żadnym swoim odcinkiem początkowym).

Przy założeniu pewnika wyboru każdy zbiór można dobrze uporządkować, a więc wtedy każda liczba kardynalna jest alefem.

Można udowodnić, że alefy nie tworzą zbioru. Możemy je ponumerować kolejnymi liczbami porządkowymi: dla liczby porządkowej $\alpha$, $\aleph_{\alpha}$ to $\alpha$-ty alef.