Przypomnijmy:
Jeśli \(\displaystyle{ \left( X, \le _X\right) }\); \(\displaystyle{ \left( Y, \le _Y\right) }\) są zbiorami uporządkowanymi, to na iloczynie kartezjańskim \(\displaystyle{ X \times Y}\) definiujemy porządek antyleksykograficzny w następujący sposób:
\(\displaystyle{ \left( x_1, y_1\right) \le \left( x_2, y_2\right) \Longleftrightarrow \left( y_1<_Y y_2\right) \vee \left( y_1= y_2 \wedge x_1 \le_X x_2\right),}\)
tzn. jedna para z iloczynu kartezjańskiego \(\displaystyle{ X \times Y}\) jest mniejsza od drugiej tego typu pary, gdy druga współrzędna pary większej jest silnie większa od drugiej współrzędnej pary mniejszej, a gdy drugie współrzędne par są równe, to para o pierwszej współrzędnej mniejszej jest mniejsza od pary o pierwszej współrzędnej większej.
To jest tak jakbyśmy rozważali słowa dwuliterowe na alfabecie liter języka polskiego, i czytali je od tyłu- wtedy np. każde słowo kończące się na "A" jest mniejsze od każdego słowa kończąego się na "C", a jeśli słowa kończą się tą samą literą, dajmy na to na "A", to patrzymy na pierwszą literę, i słowo o wcześniejszej pierwszej literze jest mniejsze od słowa o późniejszej pierwszej literze. Tłumaczy to nazwę porządek " antyleksykograficzny", inaczej "antysłownikowy", gdyż tutaj te słowa dwuliterowe czytamy od tyłu.
Łatwo jest zauważyć, że jeśli zbiory \(\displaystyle{ X}\) i \(\displaystyle{ Y}\) są uporządkowane liniowo, to ich porządek antyleksykograficzny jest porządkiem liniowym na \(\displaystyle{ X \times Y}\), gdyż z dwóch różnych par (każda para jest mniejsza lub równa od jej samej, na mocy zwrotności porządku), i z dwóch różnych par o różnych drugich współrzędnych ta para jest wcześniejsza, których druga współrzędna jest wcześniejsza ( zbiór \(\displaystyle{ Y}\) z założenia jest liniowo uporządkowany, a więc istotnie jedna z tych współrzędnych jest wcześniejsza), a z dwóch par o tej samej drugiej współrzędnej (ponieważ te pary są różne, to muszą teraz pierwsze współrzędne takich par być różne ), i ta para jest wcześniejsza, których pierwsza współrzędna jest wcześniejsza.
Oto ilustracja takiego porządku antyleksykograficznego (dla dwóch skończonych zbiorów liniowo uporządkowanych), jest to porządek idący kolejno "po prostych poziomych": \(\displaystyle{ \\}\) \(\displaystyle{ \\}\) \(\displaystyle{ \\}\) Zauważmy, że jak mamy dwa zbiory liniowo uporządkowane \(\displaystyle{ \left( X, \le _X\right)}\) oraz \(\displaystyle{ \left( Y, \le _Y\right)}\), oraz mamy jeszcze dwa zbiory \(\displaystyle{ A \subset X, B \subset Y}\) mające elementy najmniejsze równe odpowiednio: \(\displaystyle{ a \in A}\) oraz element \(\displaystyle{ b \in B}\) najmniejszy w \(\displaystyle{ B}\), to para \(\displaystyle{ \left( a,b\right)}\) jest elementem najmniejszym w \(\displaystyle{ A \times B}\) z porządkiem antyleksykograficznym (możliwe, ze również z porządkiem leksykograficznym, bo podobny fakt jest, trzeba byłoby jeszcze sprawdzić czy wszystko tam się zgadza).
Oto:
Dowód tego faktu jest symetryczny do powyższego (nie jestem jeszcze gotowy aby rozważać porządek odwrotny do antyleksykograficznego, może w przyszłości, także tu nie kombinowałem, tylko w sposób symetryczny jak powyżej to udowodniłem).
Przejdźmy do naszych zadań:
Niech \(\displaystyle{ \left( X, \le _X\right) }\); \(\displaystyle{ \left( Y, \le _Y\right) }\) będą zbiorami dobrze uporządkowanymi.
Wykażemy, że iloczyn kartezjański \(\displaystyle{ X \times Y}\) z porządkiem antyleksykograficznym jest zbiorem dobrze uporządkowanym.
DOWÓD TEGO FAKTU:
Ponieważ zbiór \(\displaystyle{ X}\) jest uporządkowany dobrze, a więc i liniowo, ponieważ zbiór \(\displaystyle{ Y}\) jest uporządkowany liniowo, więc zbiór \(\displaystyle{ X \times Y}\) jest liniowo uporządkowany przez porządek antyleksykograficzny.
Niech \(\displaystyle{ \left\{ \right\} \neq A \neq X \times Y}\) będzie niepustym podzbiorem tego prostokąta kartezjańskiego. Wykażemy, że zbiór \(\displaystyle{ A}\) ma element najmniejszy.
Zauważmy, że tak akurat się składa, że wtedy zbiór \(\displaystyle{ A}\) jest relacją z \(\displaystyle{ X}\) do \(\displaystyle{ Y}\).
Rozważmy prawą dziedzinę tej relacji, tzn. rozważmy zbiór \(\displaystyle{ A_P \subset Y.}\)
Ponieważ \(\displaystyle{ A \neq \left\{ \right\},}\) więc istnieje para \(\displaystyle{ \left( x,y\right) \in A}\), a wtedy \(\displaystyle{ y \in A_P}\), a więc zbiór \(\displaystyle{ A_P}\) jest niepusty. Mamy \(\displaystyle{ A_P \subset Y}\), a \(\displaystyle{ Y}\) jest dobrze uporządkowany, a zatem zbiór \(\displaystyle{ A_P}\) ma element najmniejszy \(\displaystyle{ y \in A_P.}\)
Rozważmy zbiór \(\displaystyle{ \stackrel{ \leftarrow }{A} (y)}\), czyli zbiór poprzedników elementu \(\displaystyle{ y}\) poprzez relację \(\displaystyle{ A}\), tzn.:
\(\displaystyle{ \stackrel{ \leftarrow }{A} (y) = \left[ \left( X \times \left\{ y\right\} \right) \cap A \right] _L.}\)
Ponieważ \(\displaystyle{ y \in A_P,}\) więc \(\displaystyle{ \left( x,y\right) \in A}\), dla pewnego elementu \(\displaystyle{ x \in X}\). Wtedy \(\displaystyle{ x \in \stackrel{ \leftarrow }{A} (y)}\), a więc zbiór \(\displaystyle{ \stackrel{ \leftarrow }{A} (y)}\) jest niepusty. I jest podzbiorem zbioru \(\displaystyle{ X}\); ponieważ \(\displaystyle{ X}\) jest dobrze uporządkowany, więc zbiór \(\displaystyle{ \stackrel{ \leftarrow }{A} (y)}\) ma element najmniejszy \(\displaystyle{ x \in \stackrel{ \leftarrow }{A} (y).}\)
Wykażemy, że para \(\displaystyle{ \left( x,y\right) }\) jest elementem najmniejszym zbioru \(\displaystyle{ A}\) względem porządku antyleksykograficznego \(\displaystyle{ \le _{X \otimes' Y } .}\)
Mamy \(\displaystyle{ x \in \stackrel{ \leftarrow }{A} (y),}\) a więc \(\displaystyle{ \left( x,y\right) \in A}\), jak trzeba.
Niech \(\displaystyle{ \left( x' ,y'\right) \in A}\). Wtedy \(\displaystyle{ y' \in A_P}\), a ponieważ element \(\displaystyle{ y}\) jest najmniejszy w \(\displaystyle{ A_P}\), więc \(\displaystyle{ y \le y'. }\)
Jeśli \(\displaystyle{ y \neq y',}\) wtedy \(\displaystyle{ y<y'}\), a więc z definicji porządku antyleksykograficznego:
\(\displaystyle{ \left( x,y\right) \le \left( x',y'\right)}\), co należało pokazać.
Jeśli \(\displaystyle{ y= y'}\), to ponieważ \(\displaystyle{ \left( x',y'\right) = \left( x',y\right) \in A}\), a zatem \(\displaystyle{ x' \in \stackrel{ \leftarrow }{A} (y)}\). Ponieważ element \(\displaystyle{ x}\) jest najmniejszy w \(\displaystyle{ \stackrel{ \leftarrow }{A} (y)}\), więc \(\displaystyle{ x \le x'}\), a zatem: \(\displaystyle{ \left( x,y\right) \le \left( x', y\right) = \left( x',y'\right) ,}\)
a zatem para \(\displaystyle{ \left( x,y\right)}\) jest elementem najmniejszym zbioru \(\displaystyle{ A}\),
i zbiór \(\displaystyle{ \left( X \times Y, \le _{X\otimes ' Y}\right) }\) jest zbiorem dobrze uporządkowanym.\(\displaystyle{ \square }\)
Oto FASCYNUJĄCA ILUSTRACJA TEGO FAKTU: \(\displaystyle{ \\}\) \(\displaystyle{ \\}\)
Przejdźmy do drugiego z naszych faktów:
Rozważmy zbiór \(\displaystyle{ \left\{ 0,1\right\} ^{*}}\), czyli zbiór wszystkich skończonych ciągów zero-jedynkowych.
Aha, przypomnę może najpierw czym jest porządek prefiksowy.
Jeśli mamy alfabet, dajmy na to \(\displaystyle{ \left\{ a,b,c,\ldots, z\right\},}\) to porządkiem prefiksowym są np. relacje:
\(\displaystyle{ \hbox{tak} \prec \hbox{takt} \prec \hbox{taktyk}\prec \hbox {taktyka}.}\)
Czyli słowo krótsze jest prefiksem słowa dłuższego.
Niech teraz alfabetem będzie zbiór \(\displaystyle{ \left\{ 0,1\right\}}\).
W zbiorze \(\displaystyle{ \left\{ 0,1\right\} ^{*}}\) porządek antyleksykograficzny (silny) określamy jako:
\(\displaystyle{ x\prec y}\) , gdy \(\displaystyle{ y}\) jest prefiksem \(\displaystyle{ x}\) lub gdy na pierwszej, licząc od tyłu, współrzędnej na której te ciągi się różnią, w \(\displaystyle{ x}\) występuje \(\displaystyle{ 0}\), a w \(\displaystyle{ y}\) występuje \(\displaystyle{ 1.}\)
Pokażemy, że zbiór uporządkowany \(\displaystyle{ \left( \left\{ 0,1\right\} ^{*}, \preccurlyeq \right)}\) nie jest dobrze uporządkowany.
Idea dowodu:
\(\displaystyle{ \ldots\prec\left( 1, 0,0,0\right) \prec\left( 1,0,0\right) \prec \left( 1,0\right) .}\)
Niech:
\(\displaystyle{ A= \left\{ \left( 1,0 ^{n}\right) \Bigl| \ n \in \NN \right\} }\),
gdzie \(\displaystyle{ 0 ^{n}}\) oznacza ciąg zer długości \(\displaystyle{ n}\), tzn.:
\(\displaystyle{ 0 ^{n}= \left( \underbrace { 0,0,\ldots, 0}_{n \hbox{ zer}}.\right) }\)
Jest to zbiór ciągów postaci \(\displaystyle{ \left( 1, 0,\ldots, 0\right).}\)
Wtedy \(\displaystyle{ A \subset \left\{ 0,1\right\} ^{ *}}\) i \(\displaystyle{ \left( 1\right) \in A}\), a więc zbiór \(\displaystyle{ A}\) jest niepusty.
Pokażemy, że w \(\displaystyle{ A}\) nie ma elementu najmniejszego.
Przypuśćmy nie wprost, że w \(\displaystyle{ A}\) jest element najmniejszy \(\displaystyle{ a \in A}\). Ponieważ wtedy \(\displaystyle{ a \in A}\), to ciąg \(\displaystyle{ a}\) jest postaci \(\displaystyle{ \left( 1, 0 ^{n} \right)}\), gdzie \(\displaystyle{ n \in \NN}\). Czyli \(\displaystyle{ a= 1\underbrace {0,0, \ldots, 0}_{n \hbox{ zer}} .}\)
Rozważy ciąg: \(\displaystyle{ \left( 1, 0 ^{n+1} \right) }\).
Wtedy taki ciąg jest elementem zbioru \(\displaystyle{ A}\), i \(\displaystyle{ \left( 1, 0 ^{\left( n+1\right) } \right) = \left( 1,\underbrace{0,0,\ldots, 0} _{\ (n+1) \hbox{ zer}}\right)}\) jest mniejszy od ciągu \(\displaystyle{ \left( 1, 0 ^{n}\right) = \left( 1, \underbrace{0,0,\ldots, 0}_{n \hbox{ zer}}\right) }\), gdyż na pierwszej , licząc od tyłu, współrzędnej, na której te ciągi się różnią ( \(\displaystyle{ \left( n+1\right)}\)-ej ), w pierwszym występuje \(\displaystyle{ 0}\), a w drugim występuje \(\displaystyle{ 1}\). Otrzymujemy zatem sprzeczność.
Wobec czego w zbiorze \(\displaystyle{ A}\) nie ma elementu najmniejszego, i zbiór uporządkowany \(\displaystyle{ \left( \left\{ 0,1\right\} ^{*}, \preccurlyeq \right) }\) nie jest dobrze uporządkowany.\(\displaystyle{ \square}\)
Na koniec dodam, że można podać łańcuch podzbiorów danego zbioru, łańcuch pod względem inkluzji, mocy continuum.
Wystarczy rozważyć zbiór liczb zespolonych \(\displaystyle{ \CC}\), i rozważyć rodzinę jego wszystkich podzbiorów uporządkowaną inkluzją.
Wtedy \(\displaystyle{ \left( P\left( \CC\right), \subset\right) }\) jest zbiorem uporządkowanym. I dla dowolnej liczby rzeczywistej dodatniej \(\displaystyle{ x}\) rozważmy zbiór \(\displaystyle{ A_x}\) dany jako:
\(\displaystyle{ A_x= \left\{ z \in \CC: \ \ \left| z\right| <x \right\} .}\)
Jest to koło otwarte o środku w punkcie \(\displaystyle{ \left( 0,0\right)}\) i promieniu \(\displaystyle{ x>0}\).
Zbiory \(\displaystyle{ \left( A_x\right) _{x>0}}\) tworzą żądany łańcuch, co można łatwo sprawdzić.