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 \( \displaystyle A \) i \( \displaystyle B \) są tego samego typu, jeśli \( \displaystyle A \) jest podobny do \( \displaystyle B \).

Łatwo wykazać, że każdy dobry porządek jest tego samego typu co on sam, jeśli \( \displaystyle A \) jest tego samego typu co \( \displaystyle B \), to \( \displaystyle B \) jest tego samego typu co \( \displaystyle A \) oraz że, jeśli \( \displaystyle A \) jest tego samego typu co \( \displaystyle B \) i \( \displaystyle B \) jest tego samego typu co \( \displaystyle C \), to \( \displaystyle A \) jest tego samego typu co \( \displaystyle C \). 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 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 \( \displaystyle X \) nazwiemy liczbą porządkową, jeśli ma następujące własności:

\( \displaystyle \forall_{x,y\in X} \;x \in y \vee y\in x \vee x=y \).
\( \displaystyle \forall_{x\in X} \;x\subset X \).

Najprostszym przykładem liczby porządkowej jest zbiór pusty. W poniższym ćwiczeniu pokazujemy, jak można konstruować kolejne liczby porządkowe.

Ćwiczenie 4.2

Udowodnij, że jeśli \( \displaystyle X \) jest liczbą porządkową, to \( \displaystyle X \cup \{X\} \) jest liczbą porządkową.

Rozwiązanie

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

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

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

Wobec tego każdy \( \displaystyle x \) ze zbioru \( \displaystyle X \cup \{X\} \) jest jego podzbiorem.

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

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 \( \displaystyle \mathbb{N} \) też jest liczbą porządkową (patrz Wykład 7 "Konstrukcja von Neumanna liczb naturalnych, twierdzenie o indukcji, zasady minimum, maksimum, definiowanie przez indukcje", Twierdzenie 4.1), a więc także \( \displaystyle \mathbb{N} \cup \{\mathbb{N}\} \) oraz \( \displaystyle \mathbb{N} \cup \{\mathbb{N}\} \cup \{\mathbb{N} \cup \{\mathbb{N}\}\} \), itd.

Twierdzenie 4.3.

Każdy element liczby porządkowej jest liczbą porządkową.

Dowód

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

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

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

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 \( \displaystyle X \) oraz elementów \( \displaystyle x,y\in X \), jeśli \( \displaystyle x\in y \), to \( \displaystyle x \subset y \).

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.

Twierdzenie 4.4.

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

Dowód

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

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

Twierdzenie 4.5.

Każdy przedział początkowy liczby porządkowej jest liczbą porządkową.

Dowód

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ą \( \displaystyle X \). Niech \( \displaystyle A \) będzie jej niepustym przedziałem początkowym. Pokażemy, że \( \displaystyle A \) jest liczbą porządkową.

Własność pierwsza wynika natychmiast z faktu, że \( \displaystyle A \subset X \).
Weźmy dowolną liczbę \( \displaystyle x\in A \). Skoro \( \displaystyle X \) jest liczbą porządkową, to \( \displaystyle x\subset X \). Weźmy dowolny element \( \displaystyle z\in x \), wynika stąd, że \( \displaystyle z\subset x \), a więc skoro \( \displaystyle A \)

jest przedziałem początkowym to \( \displaystyle z \in A \).

Ćwiczenie 4.6

Niech \( \displaystyle X \) będzie liczbą porządkową. Udowodnij, że dla dowolnych elementów \( \displaystyle x,y \in X \), jeśli \( \displaystyle x ⊊ y \), to \( \displaystyle x\in y \).

Wskazówka

Spróbuj nie wprost.

Rozwiązanie

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

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

Fakt 4.2.

Każdy element liczby porządkowej jest liczbą porządkową.

Ćwiczenie 4.7

Udowodnij, że \( \displaystyle \emptyset \) jest elementem każdej niepustej liczby porządkowej.

Rozwiązanie

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

Twierdzenie 4.8.

Dla każdych dwóch liczb porządkowych jedna jest podzbiorem drugiej.

Dowód

Dowiedliśmy już, że liczby porządkowe są dobrze uporządkowane przez inkluzję. Wobec tego z Twierdzenia 3.6 (patrz 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 \( \displaystyle X,Y \) i przypuśćmy, że funkcja \( \displaystyle f:X arrow Y \) jest podobieństwem pomiędzy porządkami \( \displaystyle (X,\subset) \) i \( \displaystyle (Y,\subset) \). Pokażemy, że \( \displaystyle f \) jest identycznością.

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

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

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

Pokazaliśmy, że założenie o niepustości zbioru \( \displaystyle A \) prowadzi do sprzeczności. Zbiór ten musi więc być pusty co oznacza, że funkcja \( \displaystyle f \) 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 \( \displaystyle x \leq y \), zamiast \( \displaystyle x\subset y \).

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

Ćwiczenie 4.9

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

Rozwiązanie

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

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

Twierdzenie 4.10. [Antynomia Burali-Forti]

Nie istnieje zbiór liczb porządkowych.

Dowód

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

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

Wobec powyższych faktów zbiór \( \displaystyle X \) 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ą.

Twierdzenie 4.11.

Każdy zbiór dobrze uporządkowany jest podobny do pewnej liczby porządkowej.

Dowód

Dla dowodu nie wprost załóżmy, że istnieje dobry porządek \( \displaystyle (X,\leq) \), który nie jest podobny do żadnej liczby porządkowej. Z Twierdzenia 3.6 wynika, że każda liczba porządkowa jest podobna do jakiegoś przedziału początkowego \( \displaystyle X \). Używając aksjomatu zastępowania z (patrz Wykład 4, Aksjomat Zastępowania) pokażemy, że istnieje wtedy zbiór liczb porządkowych.

Niech \( \displaystyle \phi(o,p) \) będzie formułą o zmiennych wolnych \( \displaystyle o,p \), która będzie spełniona wtedy i tylko wtedy, gdy \( \displaystyle o \) jest dobrym porządkiem, \( \displaystyle p \) jest liczbą porządkową i \( \displaystyle o \) jest podobne do \( \displaystyle p \). 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 \( \displaystyle o \) jest podobny do co najwyżej jednej liczby porządkowej. Wobec tego dla dowolnego \( \displaystyle o \) można dobrać co nawyżej jedno \( \displaystyle p \) takie, aby formuła \( \displaystyle \phi(o,p) \) była prawdziwa. To znaczy że dla formuły \( \displaystyle \phi(o,p) \) przesłanka aksjomatu zastępowania jest spełniona. Wobec tego prawdą jest również:

\( \displaystyle \forall_x \exists_y \forall_p (p\in y \Leftrightarrow (\exists_o o\in x \wedge \phi(o,p)) \)

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

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

Ćwiczenie 4.12

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

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

\( \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). \)

Rozwiązanie

1. Weźmy dowolny niepusty podzbiór \( \displaystyle X\subset A \cup B \). Pokażemy, że istnieje w nim element najmniejszy. Rozważmy dwa przypadki:

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

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

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

Powyższe konstrukcje łatwo zaadaptować do operowania na zbiorach, które nie są rozłączne. W miejsce \( \displaystyle A \) wystarczy wziąć zbiór \( \displaystyle \{0\} \times A \), a w miejsce \( \displaystyle B \) zbiór \( \displaystyle \{1\} \times B \). 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 \( \displaystyle [(0,a_1) \leq_{\{0\} \times A }(0,a_2)] \Leftrightarrow a_1\leq_A a_2 \)). 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 \( \displaystyle a,b \) będą liczbami porządkowymi. Wtedy:

Liczbę porządkową podobną do \( \displaystyle (a,\subset) \oplus (b,\subset) \) będziemy oznaczać przez \( \displaystyle a+b \).
Liczbę porządkową podobną do \( \displaystyle (a,\subset) \otimes (b,\subset) \) będziemy oznaczać przez \( \displaystyle a \cdot b \).

Ćwiczenie 4.14

Sprawdź, czy prawdziwe są następujące własności liczb porządkowych:

\( \displaystyle 1+\omega= \omega \).
\( \displaystyle \omega +1 \neq \omega \).
\( \displaystyle \omega + \omega = 2 \cdot \omega \).
\( \displaystyle a < b \Rightarrow a+c < b+c \).
\( \displaystyle b+a= c+a \Rightarrow b=c \).
\( \displaystyle a+b= a+c \Rightarrow b=c \).
\( \displaystyle a \cdot b= a \cdot c \Rightarrow b=c \).
\( \displaystyle x \cdot y = y \cdot x \).

Rozwiązanie

1. Równość jest prawdziwa. Zgodnie z definicją dodawania \( \displaystyle 1+\omega \) to liczba porządkowa odpowiadająca zbiorowi liczb naturalnych z dodanym jednym elementem jako

najmniejszym, oznaczymy go przez \( \displaystyle \bot \). Łatwo zauważyć, że funkcja \( \displaystyle f:\mathbb{N}\cup\{\bot\} arrow \mathbb{N} \) określona w następujący sposób:

\( \displaystyle \begin{align*} f(\bot) = 0 \\ F(n) & = n+1, \quad dla \quad \displaystyle n\in \mathbb{N} \end{align*} \)

jest monotoniczną bijekcją. Wobec tego częściowe porządki są podobne, a więc odpowiadają jednej liczbie porządkowej \( \displaystyle \omega \).

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

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

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

5. Implikacja nie jest prawdziwa. Sytuacja jest analogiczna do poprzedniego punktu. Mamy \( \displaystyle 0+\omega=1+\omega \), ale nieprawda, że \( \displaystyle 0=1 \).

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

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

\( \displaystyle f(n,x)= 2 \cdot n+x. \)

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

a) Jeśli \( \displaystyle n < m \), to:

\( \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). \)

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

\( \displaystyle f(n,x)=2\cdot n = 2\cdot m \leq 2\cdot m+1 =f(m,b). \)

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

Ćwiczenie 4.15

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

Rozwiązanie

Na początek zauważmy, że każda skończona liczba porządkowa ma powyższą własność. Niech \( \displaystyle n \) będzie skończoną liczbą porządkową. Wiemy, że \( \displaystyle n \) 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 \( \displaystyle n \) ma element największy. Ta własność wynika jednak z udowodnionej w Wykładzie 7 Zasady Maksimum (patrz Wykład 7 "Konstrukcja von Neumanna liczb naturalnych, twierdzenie o indukcji, zasady minimum, maksimum, definiowanie przez indukcje", Zasada Maksimum). Rozważmy teraz nieskończoną liczbę porządkową \( \displaystyle x \). Skoro \( \displaystyle x \) jest nieskończona to \( \displaystyle \omega \) musi być podobna do przedziału początkowego \( \displaystyle x \). Ponieważ w \( \displaystyle \omega \) nie ma elementu największego, to zbiór \( \displaystyle x \) nie może być dobrze uporządkowany przez odwrotną inkluzję.