Dobre porządki, liczby porządkowe

Jak zauważyliśmy w poprzednim rozdziale, każdy niepusty podzbiór

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

jest liniowym porządkiem na zbiorze

. Mówimy wtedy, że

jest

dobrze uporządkowany przez

, gdy każdy niepusty podzbiór

ma element najmniejszy.

Przykładem zbioru dobrze uporządkowanego jest

ze zwykłym porządkiem

(zasada minimum). Inny

przykład to zbiór liczb

ze zwykłym porządkiem

.

Gdy

jest porządkiem na zbiorze

, przez

oznaczamy relację określoną wzorem

Każda relacja porządku w tym rozdziale będzie oznaczana przez

. Dlatego będziemy mówili, że zbiór

jest dobrym [liniowym] porządkiem, mając na myśli, że jest dobrze [liniowo] uporządkowany przez pewną
relację

.

Załóżmy, że

jest dobrym porządkiem. Wtedy dla każdego elementu , który nie jest największy w

,

istnieje element

, który jest najmniejszy w zbiorze wszystkich elementów

większych od .

Zatem

i między nimi nie ma już żadnego innego elementu. Element

nazywamy następnikiem

elementu , zaś element poprzednikiem elementu

. Może się też zdarzyć, że dany element

nie ma poprzednika. Wtedy taki element nazywamy granicznym, o ile nie jest najmniejszym elementem w
całym zbiorze

. Przykładem elementu granicznego w zbiorze

jest liczba .

Uwaga 14..2 Zbiór

jest dobrym porządkiem

nie istnieje nieskończony malejący ciąg elementów

zbioru

.

Dowód.

Nie wprost. Jeśli

jest malejącym ciągiem elementów

, to zbiór

nie ma

elementu najmniejszego, przecząc dobremu uporządkowaniu zbioru

.

. Nie wprost. Załóżmy, że

jest niepusty i nie ma elementu najmniejszego. Definiujemy

rekurencyjnie malejący ciąg

elementów zbioru

.

Niech

będzie jakimkolwiek elementem zbioru

. Jeśli

jest już określony, to na mocy

założenia dowodu nie wprost,

nie jest najmniejszy w

. Zatem definiujemy

jako dowolny

element zbioru

mniejszy niż

.

Istnienie ciągu malejącego

przeczy jednak założeniom uwagi.

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

zakładamy prawdziwość

dla wszystkich

, których może być

nieskończenie wiele.

Twierdzenie 14..4 (Zasada indukcji pozaskończonej) Załóżmy, że

jest dobrze uporządkowany. Wtedy

dla dowolnej funkcji zdaniowej

prawdziwe jest zdanie

Tu

oznacza najmniejszy element zbioru

.

Dowód. Podobny jak w rozdziale 13.

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

i

są liniowo uporządkowane.

(1) Zbiór

nazywamy odcinkiem początkowym zbioru

, gdy wraz z każdym elementem należą

do niego również wszystkie elementy mniejsze od . Symbolicznie znaczy to, że

Gdy

, mówimy, że

jest właściwym odcinkiem początkowym zbioru

.

(2) Mówimy, że

jest izomorfizmem porządkowym, gdy jest bijekcją i dla dowolnych

mamy

.

(3) Mówimy, że

i

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
konstruuje się zbiory

, zwane liczbami porządkowymi, takie że dla wszystkich dobrych porządków

mamy

i

są izomorficzne

.

Liczby porządkowe oznaczamy małymi greckimi literami

Załóżmy, że

jest dobrym porządkiem oraz

. Wtedy zbiór

jest

właściwym odcinkiem początkowym

, wyznaczonym przez . Na odwrót, gdy

jest właściwym

odcinkiem początkowym zbioru

, to

, gdzie jest najmniejszym elementem zbioru

(ćwiczenie).

Lemat 14..6 Załóżmy, że

i

są dobrymi porządkami.

(1) Jeśli

i

są izomorficzne, istnieje tylko jeden izomorfizm między nimi. W tym izomorfizmie każdy

odcinek początkowy zbioru

przechodzi na odcinek początkowy zbioru

.

(2)

nie jest izomorficzny z żadnym swoim właściwym odcinkiem początkowym.

Dowód. (1) Załóżmy, że

i

są izomorfizmami. Pokażemy, że

dla każdego

.

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

(a)

Niech

będzie najmniejszym elementem

. Wtedy

jest najmniejszym elementem

.

By to udowodnić, oznaczmy przez

najmniejszy element zbioru

. Skoro jest ``na'', znajdujemy

element

taki, że

. Mamy

, więc skoro jest izomorfizmem, to również

. Ale

i

jest najmniejszy w

, więc

pociąga

.

(b)

przekształca każdy odcinek początkowy

zbioru

na odcinek początkowy

zbioru

.

Dowód pozostawiamy jako ćwiczenie.

Dowód

przeprowadzimy przez indukcję pozaskończona. W tym celu rozważmy dowolny element

i załóżmy, że dla wszystkich

mamy

, czyli w szczególności

. Udowodnimy, że

.

Na mocy (b),

jest odcinkiem początkowym

postaci

, gdzie

. (b) zachodzi

również dla izomorfizmu , zatem

jest odcinkiem początkowym

postaci

, gdzie

. Jednak

, więc

, czyli

, co kończy dowód (1).

(2) Nie wprost. Przypuśćmy, że

i

jest izomorfizmem. Wtedy

. Z definicji

izomorfizmu dostajemy, że

Istnienie takiego malejącego ciągu przeczy uwadze 14.2.

Podobnie jak w przypadku liczb kardnynalnych, liczby porządkowe możemy porównywać. Kluczowe jest
tu spostrzeżenie, że jeśli

jest dobrym porządkiem, to każdy jego podzbiór też jest dobrym porządkiem

(względem relacji

na

).

Definicja 14..7 Niech

będą liczbami porządkowymi. Wtedy

pewien zbiór

typu

zawiera odcinek początkowy typu .

Oczywiście jeżeli

, to każdy zbiór

typu zawiera odcinek początkowy typu . Ponadto

piszemy

, gdy

i

. Kolejny lemat pokazuje, że

jest liniowym porządkiem na klasie

wszystkich liczb porządkowych.

Lemat 14..8 (1) (zwrotność)

.

(2) (przechodniość) Jeśli

i

, to

.

(3) (antysymetryczność) Jeśli

i

, to

.

(4) (spójność)

lub

.

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

(3) Nie wprost. Niech

będzie dobrym porządkiem typu . Przypuśćmy, że

i

.

Znaczy to, że

. Warunek ten pociąga, że

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

będzie dobrym porządkiem typu , zaś

dobrym porządkiem typu . Udowodnimy, że jeden z

tych dobrych porządków jest izomorficzny z odcinkiem początkowym drugiego lub oba są izomorficzne.
Niech

jest odcinkiem początkowym

i istnieje isomorfizm

między

i

pewnym odcinkiem początkowym zbioru

.

Oczywiście zbiór

jest liniowo uporządkowany przez inkluzję

. Z lematu 14.6 wynika, że dla

izomorfizm

jest jedyny. Dlatego gdy

, to

jest rozszerzeniem

(tzn.

). Niech

Widzimy, że

i

są odcinkami początkowymi zbiorów

i

oraz jest izomorfizmem między

i

.

Przypadek 1.

i

. Wtedy

i

są izomorficzne, więc

.

Przypadek 2. Jeden ze zbiorów

jest równy

lub

odpowiednio. Wtedy bądź

jest

izomorficzny z odcinkiem początkowym

zbioru

(i

), bądź

jest izomorficzny z

odcinkiem początkowym

zbioru

(i

).

Przypadek 3.

i

. W tym przypadku dojdziemy do sprzeczności (co zakończy dowód).

Wybieramy

i

takie, że

i

. Wtedy zbiór

jest

odcinkiem początkowym zbioru

, izomorficznym z odcinkiem początkowym

zbioru

(poprzez funkcję

rozszerzającą i taką, że

). Zatem

, więc

, sprzeczność.

Wniosek 14..9 (1) Dla każdej liczby porządkowej , liczby porządkowe

tworzą zbiór dobrze

uporządkowany typu (zbiór ten oznaczamy przez

).

(2) Każdy niepusty zbiór liczb porządkowych zawiera element najmniejszy.

Dowód. (1) Niech

będzie dobrym porządkiem typu . Dla każdego

niech

będzie typem

porządkowym zbioru

. Wówczas

i każda liczba porządkowa

jest typem

porządkowym jedynego odcinka początkowego zbioru

.

Dlatego po pierwsze istnieje zbiór

liczb porządkowych mniejszych od . Fakt ten jest konsekwencją

tak zwanego aksjomatu zastępowania (który omówimy w następnym rozdziale). Po drugie, funkcja

jest izomorfizmem porządkowym. Zatem zbiór

jest dobrze uporządkowany przez

.

(2) Niech

będzie pewnym niepustym zbiorem liczb porządkowych. Niech

. Jeśli nie jest

najmniejszy w

, to wszystkie elementy

mniejsze od leżą w zbiorze

, który jest

podzbiorem dobrego porządku

. Dlatego zawiera on element najmniejszy.

.

Kolejna uwaga przypomina antynomię Russella.

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

Dowód. Nie wprost. Przypuśćmy, że

jest zbiorem wszystkich liczb porządkowych. Wówczas

jest

dobrze uporządkowany przez relację

. Niech będzie typem porządkowym zbioru

. Wtedy

i

na mocy wniosku 14.9, zbiór

ma również typ . Zatem

, sprzeczność z lematem 14.8(3).

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

Definicja 14..11 Niech i będą liczbami porządkowymi.

(1) Sumą

nazywamy typ porządkowy zbioru

, gdzie

i

,

zaś zbiór

porządkujemy w ten sposób, że na częściach

i

zachowujemy ich uporządkowanie i

dodatkowo kładziemy

dla wszystkich

i

.

(2) Iloczynem

nazywamy typ porządkowy zbioru

, gdzie

, zaś

porządek

na zbiorze

określony jest w sposób leksykograficzny:

Przykłady.

Konstrukcja liczb porządkowych w teorii mnogości ma dodatkową własność, że

, to znaczy

liczba 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 , druga liczba porządkowa to

, czyli , i ogólniej -ta liczba porządkowa to zbiór

, czyli liczba naturalna .

Typ porządkowy zbioru liczb naturalnych

ze zwykłym porządkiem oznaczamy przez . Widzimy więc,

że w istocie

.

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 to typ porządkowy zbioru

powiększonego o dodatkowy największy

element. Zatem jest to liczba

. Zwróćmy uwagę na podobieństwo z definicją liczby

.

Typ porządkowy zbioru

z początku rozdziału to

. 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

, jeśli bowiem na

początku zbioru liczb naturalnych dopiszemy jeden element, to typ porządkowy zbioru się nie zmieni. Z
drugiej strony liczba

jest następnikiem . Zatem

.

Podobnie

. Istotnie, jest to typ porządkowy kopii porządku dwuelementowego, ułożonych

jedna za drugą. Z drugiej strony

jest typem porządkowym dwóch kopii zbioru ułożonych

jedna za drugą. Widzimy więc, że

.

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

,

zaś jej moc przez

. Zatem hipoteza continuum mówi, że

. Moce nieskończonych liczb

porządkowych nazywamy alefami. Dokładniej, alefy są to wręcz liczby porządkowe

takie, że

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 ,

to -ty alef.