Zasada indukcji

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

Definicja 3.1.

Niech \( \displaystyle (X,\leq) \) będzie liniowym porządkiem. W \( \displaystyle (X,\leq) \) obowiązuje zasada indukcji, jeśli dla dowolnego zbioru \( \displaystyle Z \) takiego, że:

\( \displaystyle Z \subset X \),
\( \displaystyle Z\neq \emptyset \),
dla dowolnego \( \displaystyle x\in X \), jeśli \( \displaystyle \{y\in X: y < x\} \subset Z \), to \( \displaystyle x\in Z \).

zachodzi \( \displaystyle Z=X \).

W wykładzie o liczbach naturalnych udowodniliśmy twierdzenie o indukcji (patrz wykład 7 "Konstrukcja von Neumanna liczb naturalnych, twierdzenie o indukcji, zasady minimum, maksimum, definiowanie przez indukcje", Twierdzenie 3.1), z którego wynika, że zasada indukcji obowiązuje w \( \displaystyle (\mathbb{N},\leq) \). W poniższym twierdzeniu dowodzimy analogiczne twierdzenie, dla wszystkich zbiorów dobrze uporządkowanych.

Twierdzenie 3.2.

W każdym zbiorze dobrze uporządkowanym obowiązuje zasada indukcji.

Dowód

Niech \( \displaystyle (X,\leq) \) będzie dobrym porządkiem. Niech \( \displaystyle Z \) będzie dowolnym zbiorem takim, że:

\( \displaystyle Z \subset X \),
element najmniejszy \( \displaystyle X \) należy do \( \displaystyle Z \),
dla dowolnego \( \displaystyle x\in X \) jeśli \( \displaystyle \{y\in X: y < x\} \subset Z \) to \( \displaystyle x\in Z \).

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

Twierdzenie 3.3.

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

Dowód

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

\( \displaystyle Z= \{z\in X: \forall_{a\in A} z < a\}. \)

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

Pokazaliśmy, że zbiór \( \displaystyle Z \) spełnia założenia zasady indukcji. Ponieważ zasada ta obowiązuje w \( \displaystyle (X,\leq) \), to otrzymujemy \( \displaystyle Z=X \). Wynika stąd, że zbiór \( \displaystyle A \) musi być pusty. Wobec tego każdy niepusty podzbiór \( \displaystyle X \) ma element najmniejszy, a więc \( \displaystyle (X,\leq) \) 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 \( \displaystyle (x,b) \) na podstawie wartości \( \displaystyle x,b \) oraz wartości tej funkcji dla wszystkich \( \displaystyle (y,b) \) takich, że \( \displaystyle y < x \), to wyznaczymy jednoznacznie funkcję \( \displaystyle h \) 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 \( \displaystyle (X,\leq) \) będzie dobrym porządkiem. Przez \( \displaystyle PF(P,Q) \) oznaczamy zbiór wszystkich funkcji częściowych ze zbioru \( \displaystyle P \) do \( \displaystyle Q \). Pokażemy, że dla każdej funkcji \( \displaystyle g:PF(X \times B,C)\times X \times B \rightarrow C \) istnieje dokładnie jedna funkcja \( \displaystyle h:X \times B \rightarrow C \), dla której:

\( \displaystyle h(x,b)= g( h \cap (O(x) \times B \times C) ,x,b). \quad \quad \quad (3.1) \)

Dowód

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

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

gdzie \( \displaystyle (1) \) i \( \displaystyle (2) \) oznaczają odpowiednio:

\( \displaystyle e:\overline{O(a)} \times B \rightarrow C \),
\( \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) \).

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

Pokażemy, że dla każdych dwóch funkcji częściowych \( \displaystyle h_1, h_2 \in H \) jedna z nich jest rozszerzeniem drugiej. Przypuśćmy, że tak nie jest. Weźmy funkcje \( \displaystyle h_1, h_2 \in H \) określone odpowiednio na zbiorach \( \displaystyle \overline{O(a_1)} \times B, \overline{O(a_2)} \times B \), 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 \( \displaystyle a_1\leq a_2 \). Rozważmy zbiór \( \displaystyle D=\{y\in \overline{O(a_1)}: \exists_{b\in B} h_1(y,b) \neq h_2(y,b) \). Zbiór \( \displaystyle D \) jest podzbiorem \( \displaystyle X \). Skoro funkcje się różnią na jakimś argumencie, to jest \( \displaystyle D \) niepusty, a więc zawiera element najmniejszy, oznaczmy go przez \( \displaystyle z \). Skoro \( \displaystyle z \) jest najmniejszy, to dla \( \displaystyle v < z \) dla wszystkich \( \displaystyle b\in B \) funkcje muszą być równe. Czyli:

\( \displaystyle h_1\cap (O(z) \times B \times C) = h_2\cap (O(z) \times B \times C), \)

wobec tego dla dowolnego \( \displaystyle b\in B \) mamy:

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

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

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

\( \displaystyle h_z= \bigcup H_z \cup \bigcup_{b\in B} \{((z,b),g(\bigcup H_z,z,b))\}. \)

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

1. Jeśli \( \displaystyle x=z \), to:

\( \displaystyle h_z(z,b)= g(\bigcup H_z,b,z) \)

i ponieważ \( \displaystyle h_z \cap (O(z) \times B \times C)= \bigcup H_z \), to:

\( \displaystyle h_z(z,b)= g(h_z \cap (O(z) \times B \times C),z,b). \)

2. W pozostałym przypadku \( \displaystyle x < z \). Wtedy \( \displaystyle (x,h_z(x)) \in \bigcup H_z \), a więc musi należeć do którejś z funkcji z \( \displaystyle H_z \), nazwijmy tę funkcję \( \displaystyle h_x \). Ponieważ \( \displaystyle h_x \in H \), to:

\( \displaystyle h_z(x,b)=h_x(x,b)= g(h_x \cap (O(x) \times B \times C),z,b). \)

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

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

Stąd otrzymujemy:

\( \displaystyle h_z(x,b)= g(h_z \cap (O(x) \times B \times C),z,b). \)

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

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

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

\( \displaystyle h\cap O(z) \times B \times C= h'\cap O(z) \times B \times C. \)

Ustalmy dowolne \( \displaystyle b\in B \). Wtedy:

\( \displaystyle g((h\cap O(z) \times B \times C),z,b)= g((h'\cap O(z) \times B \times C),z,b). \)

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

Ćwiczenie 3.5

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

Wskazówka

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

Rozwiązanie

Idea następującego rozwiązania jest bardzo prosta. Na początek uporządkujemy dobrze zbiór \( \displaystyle X \), a potem za pomocą definiowania przez indukcję określimy funkcję \( \displaystyle h \), przypisując na przemian 0 i 1 na "kolejnych" elementach \( \displaystyle X \). Elementom \( \displaystyle X \), 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 \( \displaystyle X \) będzie dowolnym zbiorem nieskończonym. Z twierdzenia Ernsta Zermelo (patrz Wykład 11 "Zbiory dobrze uporządkowane. Lemat Kuratowskiego Zorna i twierdzenie Zermelo, przykłady", Twierdzenie 3.4) wynika, że zbiór \( \displaystyle X \) można dobrze uporządkować. Niech więc \( \displaystyle (X,\leq) \) będzie dobrym porządkiem. Zaczniemy od zdefiniowania funkcji \( \displaystyle h:X \rightarrow \{0,1\} \) dla której relacja \( \displaystyle \sim_{h} \) wyznaczy szukany podział zbioru \( \displaystyle X \). Funkcje \( \displaystyle h \) zdefiniujemy przez indukcję pozaskończoną za pomocą funkcji \( \displaystyle g: PF(X,\{0,1\}) \times X \rightarrow \{0,1\} \) zdefiniowanej następująco (przez \( \displaystyle y' \) oznaczamy następnik elementu \( \displaystyle y \) w \( \displaystyle (X,\leq) \)):

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

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

Za pomocą definiowania przez indukcję zdefiniujemy teraz funkcję \( \displaystyle h \) jako funkcję spełniającą: \( \displaystyle h(x)= g( h \cap (O(x) \times \{0,1\}),x). \)

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

\( \displaystyle h(x)=1 \), gdy \( \displaystyle h(y)=0 \);
\( \displaystyle h(x)=0 \), gdy \( \displaystyle h(y)=1 \).

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

Zdefiniujmy funkcję częściową \( \displaystyle e \subset X^2 \) następująco:

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

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

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

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

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

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.

Twierdzenie 3.6.

Niech \( \displaystyle (X,\leq_X) \), \( \displaystyle (Y,\leq_Y) \) będą dobrymi porządkami. Wtedy przynajmniej jedno z poniższych zdań jest prawdziwe:

istnieje przedział początkowy \( \displaystyle P\subset X \) taki, że \( \displaystyle (P,\leq_X \cap P\times P) \) jest podobny do \( \displaystyle (Y,\leq_Y) \),
istnieje przedział początkowy \( \displaystyle S \subset Y \) taki, że \( \displaystyle (S,\leq_Y \cap S\times S) \) jest podobny do \( \displaystyle (X,\leq_X) \).

Dowód

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

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

\( \displaystyle g(r)= \min((Z\setminus \vec{r}(X)) \cup \{\top\}). \)

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

\( \displaystyle \begin{align*} \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). \end{align*} \)

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

\( \displaystyle h(x)= g( h \cap (O(x) \times Z) ). \)

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

\( \displaystyle \begin{align*} O(x) \subset O(y) \\ h \cap (O(x) \times Z) \subset h \cap (O(y) \times Z) \end{align*} \)

i z monotoniczności funkcji \( \displaystyle g \) otrzymujemy:

\( \displaystyle h(x) = g( h \cap (O(x) \times Z) ) \subset g( h \cap (O(y) \times Z) )= h(y). \)

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

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

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

Rozważymy teraz dwa przypadki.

1. Jeśli \( \displaystyle \top \notin \vec{h}(X) \), to \( \displaystyle h \) jest iniekcją. Zauważmy, że

\( \displaystyle X=\bigcup_{x\in X} \overline{O(x)} \). Ponieważ \( \displaystyle \vec{h}(\overline{O(x)}) =\overline{O(h(x))} \), to

\( \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} \ (h{x}). \)

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

2. Jeśli \( \displaystyle \top \in \vec{h}(X) \), to niech \( \displaystyle v\in X \) będzie takim elementem, że

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

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

Twierdzenie 3.7.

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

\( \displaystyle x \leq_m y \vee y \leq_m x. \)

Dowód

Z Twierdzenia 3.6 (patrz Twierdzenie 3.6.) wynika, że dowolne zbiory dobrze uporządkowane można porównywać na moc. Z twierdzenia Ernsta Zermelo (patrz Wykład 11 "Zbiory dobrze uporządkowane. Lemat Kuratowskiego Zorna i twierdzenie Zermelo, przykłady", Twierdzenie 3.4) wynika, że dowolne zbiory \( \displaystyle x,y \) można dobrze uporządkować. Wobec tego dowolne zbioru można porównywać na moc.

Twierdzenie 3.8.

Żaden zbiór dobrze uporządkowany nie jest podobny do swojego istotnego przedziału początkowego.

Dowód

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

\( \displaystyle f(f(c))=f(c) \), wtedy \( \displaystyle f \) nie jest iniekcją, a więc dostaliśmy sprzeczność.
\( \displaystyle f(f(c)) > f(c) \), a więc \( \displaystyle f \) nie jest monotoniczna i dostaliśmy sprzeczność.