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.

Przykład 2.1.

Przykładem zbioru dobrze uporządkowanego jest zbiór \( \displaystyle \mathbb{N} \) uporządkowany, przez \( \displaystyle \subset \). Zasada minimum, wykład 7 "Konstrukcja von Neumanna liczb naturalnych, twierdzenie o indukcji, zasady minimum, maksimum, definiowanie przez indukcje", Twierdzenie 5.2 mówi, że w każdym podzbiorze \( \displaystyle \mathbb{N} \) istnieje element najmniejszy, a więc, że ten porządek jest dobry.

Ćwiczenie 2.2

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

Wskazówka

Rozważ podzbiory dwuelementowe.

Rozwiązanie

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

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 \( \displaystyle (X,\leq) \) element \( \displaystyle y \) nazywamy następnikiem elementu \( \displaystyle x \), jeśli \( \displaystyle x \leq y \), \( \displaystyle x\neq y \) oraz każdy element silnie większy od \( \displaystyle x \) jest nie mniejszy od \( \displaystyle y \) (czyli \( \displaystyle (x \leq z \wedge x \neq z) \Rightarrow y\leq z \)).

Ćwiczenie 2.4

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

Rozwiązanie

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

\( \displaystyle x < \frac{x+y}{2} < y. \)

Ponieważ \( \displaystyle \frac{x+y}{2} \) jest liczbą wymierną to otrzymujemy sprzeczność z definicją następnika.

Twierdzenie 2.5.

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

Dowód

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

\( \displaystyle A= \{y\in X: x < y\}. \)

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

Definicja 2.6.

Element zbioru dobrze uporządkowanego nazywamy elementem granicznym, jeśli nie jest następnikiem, żadnego elementu.

Ćwiczenie 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?

Rozwiązanie

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

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

\( \displaystyle (x,0) \leq_A (y,0) \Leftrightarrow x \leq_{\mathbb{N}} y, \)

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

\( \displaystyle (x,1) \leq_B (y,1) \Leftrightarrow x \leq_{\mathbb{Z}} y, \)

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

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

Definicja 2.8.

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

\( \displaystyle \forall_{x\in A} \forall_{y\in X} ( y\leq x \Rightarrow y\in A ). \)

Czyli \( \displaystyle A \) jest przedziałem początkowym, jeśli wraz z każdym swoim elementem zawiera także wszystkie elementy zbioru \( \displaystyle X \), które są od niego mniejsze. Będziemy używać następujących oznaczeń, dla \( \displaystyle x_0\in X \) niech:

\( \displaystyle O(x_0)=\{x\in X: x < x_0\} \)

oraz:

\( \displaystyle \overline{O(x_0)}=\{x\in X: x \leq x_0\}. \)

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

Twierdzenie 2.9.

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

Dowód

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

Ćwiczenie 2.10

Podaj przykład zbioru dobrze uporządkowanego \( \displaystyle X \), w którym istnieje przedział początkowy różny od \( \displaystyle X \), który nie jest postaci \( \displaystyle \{x\in X: x \leq x_0\} \) (uwaga! nierówność jest słaba).

Wskazówka

Dodaj jeden element do zbioru liczb naturalnych.

Rozwiązanie

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

Ćwiczenie 2.11

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

Rozwiązanie

Zdefiniujemy zbiór \( \displaystyle \min \) następująco: \( \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 ] \}. \) Istnienie zbioru \( \displaystyle \min \) wynika z aksjomatu wyróżniania. Jest to funkcja częściowa, ponieważ istnieje co najwyżej jeden element najmniejszy w każdym podzbiorze \( \displaystyle A \). \( \displaystyle \min \) jest funkcją totalną, ponieważ \( \displaystyle A \) jest dobrze uporządkowany, a więc w każdym podzbiorze istnieje element najmniejszy.

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

Twierdzenie 2.12

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

Dowód

Zdefiniujmy funkcję \( \displaystyle f:X \rightarrow \mathcal{R} \), tak aby \( \displaystyle f(x)=O(x) \). Pokażemy, że ta funkcja ustala podobieństwo. Pokażemy po kolei, że jest suriekcją , iniekcją oraz że jest monotoniczna:

Suriektywność funkcji \( \displaystyle f \) wynika z Twierdzenia 2.9 (patrz Twierdzenie 2.9).
Weźmy dowolne \( \displaystyle x,y \in X \) takie, że \( \displaystyle x < y \). Wtedy z definicji \( \displaystyle x \in O(y) \) oraz \( \displaystyle x\notin O(x) \), a więc \( \displaystyle f(x)\neq f(y) \).
Weźmy dowolne \( \displaystyle x,y \in X \) takie, że \( \displaystyle x < y \). Weźmy dowolny \( \displaystyle z\in f(x) \).

Oznacza to, że \( \displaystyle z\in O(x) \), a więc \( \displaystyle z < x \). Wtedy również \( \displaystyle z < y \), a więc \( \displaystyle z\in O(y)=f(y) \). Wobec dowolności wyboru \( \displaystyle z \) otrzymujemy \( \displaystyle f(x) \subset f(z) \), a więc funkcja \( \displaystyle f \) jest monotoniczna.

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

Ćwiczenie 2.13

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

Rozwiązanie

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

\( \displaystyle \min(\vec{f}^{-1}(A)) \leq_X c, \)

wobec tego z monotoniczności \( \displaystyle f \) otrzymujemy:

\( \displaystyle a=f( \min(\vec{f}^{-1}(A))) \leq_Y f(c)=b, \)

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

Ćwiczenie 2.14

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

\( \displaystyle (a,b) \prec (c,d) \Leftrightarrow (a\leq_X c) \vee (a=c \wedge b\leq_Y c), \)

Dla zbiorów \( \displaystyle \{0,1\},\mathbb{N}, \mathbb{Z}, \mathbb{R} \) uporządkowanych w naturalny sposób, sprawdź, czy następujące ich produkty są dobrze uporządkowane:

\( \displaystyle \{0,1\} \times \mathbb{N} \),
\( \displaystyle \mathbb{N} \times \mathbb{N} \),
\( \displaystyle \mathbb{Z} \times \mathbb{N} \),
\( \displaystyle \mathbb{N} \times \mathbb{Z} \).

Rozwiązanie

1. Tak, porządek leksykograficzny na zbiorze \( \displaystyle \{0,1\} \times \mathbb{N} \) jest dobrym porządkiem. Rozważmy dowolny niepusty podzbiór \( \displaystyle A \subset (\{0,1\} \times \mathbb{N}) \), pokażemy, że istnieje w nim element najmniejszy. Zbiór \( \displaystyle A \) możemy podzielić na dwa podzbiory \( \displaystyle A_0,A_1 \) tak, że \( \displaystyle A_0= A \cap (\{0\}\times \mathbb{N}) \) oraz \( \displaystyle A_1= A \cap (\{1\} \times \mathbb{N}) \). Wtedy zbiory \( \displaystyle A_0,A_1 \) są rozłączne oraz \( \displaystyle A_0 \cup A_1= A \). Ponadto każdy element ze zbioru \( \displaystyle A_0 \) jest mniejszy od każdego elementu ze zbioru \( \displaystyle A_1 \).

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

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

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

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

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

Ćwiczenie 2.15

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

\( \displaystyle (a,b)\prec(c,d) \Leftrightarrow (a < c) \vee (a=c \wedge b\leq d) \)
\( \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))). \)

Czy porządki te są podobne?

Wskazówka

Tylko jeden z nich jest dobry?

Rozwiązanie

W poprzednim ćwiczeniu pokazaliśmy, że porządek \( \displaystyle \prec \) jest dobry. Pokażemy teraz, że \( \displaystyle \ll \) 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 \( \displaystyle \{1\} \times \mathbb{N} \). Przypuśćmy, że istnieje w nim element minimalny \( \displaystyle (1,a) \). Z definicji porządku \( \displaystyle \ll \) wynika, że \( \displaystyle (1,a+1)\ll (1,a) \). Ponieważ \( \displaystyle (1,a+1)\in \{1\} \times \mathbb{N} \), to \( \displaystyle (1,a) \) nie może być elementem minimalnym w tym zbiorze. Wobec tego porządek \( \displaystyle \ll \) nie jest dobry.

Ćwiczenie 2.16

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

Wskazówka

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

Rozwiązanie

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