Twierdzenia dla zbiorów dobrze uporządkowanych nie zachodzące dla zbiorów liniowo uporządkowanych

[Jakub Gurak]

W ostatnich dniach zbadałem kilka takich twierdzeń. Podałem wczoraj ciekawy przykład pokazujący, że zbiór liniowo uporządkowany może być podobny do swojego istotnego przedziału początkowego. Dzisiaj uzasadniłem w miarę dokładnie, ze twierdzenie mówiące, ze dla dwóch zbiorów dobrze uporządkowanych jeden z nich jest podobny do przedziału początkowego drugiego- uogólnienie na zbiory liniowo uporządkowane nie zachodzi. Łatwo też uzasadnić, że w zbiorze liniowo uporządkowanym \(\displaystyle{ \left( X, \le\right)}\) nie każdy przedział początkowy zbioru \(\displaystyle{ X}\) różny od \(\displaystyle{ X}\) jest postaci \(\displaystyle{ O(x)=\left\{ y\in X\Bigl| \ \ y<x\right\}}\), dla pewnego elementu \(\displaystyle{ x\in X}\). Przedstawię teraz dowody tych ciekawych faktów.

Aby uzasadnić pierwszy fakt rozważmy odcinek \(\displaystyle{ \left[ 0,2\right]}\) z naturalnym porządkiem \(\displaystyle{ \le _{\left[ 0,2\right] } }\). Jest to więc zbiór liniowo uporządkowany. Rozważmy jako przedział początkowy \(\displaystyle{ \left[ 0,1\right].}\) Jest to niewątpliwie przedział początkowy w \(\displaystyle{ [0,2]}\) różny od \(\displaystyle{ \left[ 0,2\right] }\). Pokażemy, że jest podony do \(\displaystyle{ \left[ 0,2\right]}\). Rozważmy funkcję \(\displaystyle{ f:\left[ 0,2\right] \rightarrow \left[ 0,1\right]}\) daną jako:

\(\displaystyle{ f(x)= \frac{x}{2}.}\)

jest to niewątpliwie bijekcja (co łatwo sprawdzić) , i jest monotoniczna, gdyż jeśli \(\displaystyle{ x \le y}\), to \(\displaystyle{ f(x)= \frac{x}{2} \le f(y) = \frac{y}{2}. }\)

A więc \(\displaystyle{ f}\) jest monotoniczna, \(\displaystyle{ f}\) jest bijekcją, zatem \(\displaystyle{ f}\) jest podobieństwem, i otrzymujemy, że zbiór \(\displaystyle{ [0,2]}\) jest podobny do \(\displaystyle{ [0,1]}\). Ponieważ \(\displaystyle{ [0,1]}\) jest przedziałem początkowym w \(\displaystyle{ [0,2]}\), więc zbiór \(\displaystyle{ [0,2]}\) jest podobny do swojego istotnego przedziału początkowego\(\displaystyle{ .\square}\)

Aby uzasadnić drugi fakt podajmy najpierw lemat:

Ukryta treść:    

że jeśli \(\displaystyle{ \left( X, \le \right)}\) jest zbiorem liniowo uporządkowanym, \(\displaystyle{ \left\{ \right\} \neq A\subset X}\) niepustym przedziałem początkowym, a \(\displaystyle{ a\in X}\) elementem, to mamy równoważność:

\(\displaystyle{ a}\) jest elementem najmniejszym w \(\displaystyle{ X}\), dokładnie wtedy, gdy \(\displaystyle{ a}\) jest najmniejszy w \(\displaystyle{ A}\)( w tym przedziale początkowym).

Dowód:

\(\displaystyle{ \Longrightarrow}\) Niech \(\displaystyle{ b\in A \neq \left\{ \right\}. }\) Wtedy \(\displaystyle{ b\in X.}\) Ponieważ \(\displaystyle{ a}\) jest najmniejszy w \(\displaystyle{ X}\), więc \(\displaystyle{ a \le b}\), ponieważ zbiór \(\displaystyle{ A}\) jest przedziałem początkowym, a \(\displaystyle{ a \le b \in A}\), więc wnioskujemy, że również \(\displaystyle{ a\in A.}\)
Pozostaje pokazać, że \(\displaystyle{ a}\) jest mniejsze od każdego elementu \(\displaystyle{ A}\). Niech zatem \(\displaystyle{ c\in A.}\) Wtedy \(\displaystyle{ c\in X}\). Ponieważ element \(\displaystyle{ a}\) jest najmniejszy w \(\displaystyle{ X}\), więc \(\displaystyle{ a \le c}\). A zatem (z dowolności \(\displaystyle{ c}\)) otrzymujemy, że \(\displaystyle{ a}\) jest elementem najmniejszym w \(\displaystyle{ A}\).

\(\displaystyle{ \Longleftarrow }\) Aby pokazać, że \(\displaystyle{ a}\) jest elementem najmniejszym w \(\displaystyle{ X}\), to weźmy \(\displaystyle{ b\in X}\), i pokażmy, że \(\displaystyle{ a \le b}\). Przypuśćmy, że tak nie jest. Wtedy ponieważ \(\displaystyle{ (X, \le )}\) jest zbiorem liniowo uporządkowanym, więc konieczne jest aby \(\displaystyle{ b<a}\), a ponieważ element \(\displaystyle{ a}\) najmniejszy w \(\displaystyle{ A}\) nalezy do \(\displaystyle{ A}\), a \(\displaystyle{ A}\) jest przedziałem początkowym, więc również \(\displaystyle{ b\in A}\). Ponieważ \(\displaystyle{ a}\) jest najmniejszy w \(\displaystyle{ A}\), więc \(\displaystyle{ a \le b}\), a mamy \(\displaystyle{ b<a}\)- sprzeczność. \(\displaystyle{ \square}\)

Przypomnę może pewien fakt o podobieństwie: Podobieństwo zachowuje elementy najmniejsze, tzn. jeśli \(\displaystyle{ \left( X, \le_X\right) ; \left( Y, \le _Y\right)}\) są zbiorami liniowo uporządkowanymi podobnymi, to jeśli w \(\displaystyle{ X}\) jest element najmniejszy, to w \(\displaystyle{ Y}\) jest element najmniejszy. Podobnie, jeśli w \(\displaystyle{ X}\) jest element największy, to w \(\displaystyle{ Y}\) jest element największy.

Łatwo teraz pokazać, że twierdzenie, ze dla dowolnych dwóch zbiorów liniowo uporządkowanych jeden z nich jest podobny do przedziału początkowego drugiego, dla liniowych porządków tak być nie musi.

Jako kontrprzykład rozważmy odcinek \(\displaystyle{ \left[ 0,2\right]}\) z naturalnym porządkiem \(\displaystyle{ \le _{\left[ 0,2\right] } }\) a jako drugi zbiór weżmy \(\displaystyle{ \left( 0,1\right]}\) ( \(\displaystyle{ 0}\) otwarte, to jest tu kluczowe) z naturalnym porządkiem \(\displaystyle{ \le _{ \left( 0,1\right] } .}\) Są to dwa zbiory liniowo uporządkowane.

Przypuśćmy, że \(\displaystyle{ \left[ 0,2\right]}\) jest podobny do pewnego przedziału początkowego \(\displaystyle{ A}\) w \(\displaystyle{ \left( 0,1\right].}\) Ponieważ \(\displaystyle{ 0}\) jest elementem najmniejszym w \(\displaystyle{ \left[ 0,2\right] }\), to w podobnym zbiorze liniowo uporządkowanym \(\displaystyle{ A \subset \left( 0,1\right]}\) jest element najmniejszy \(\displaystyle{ a\in A}\), w szczególności \(\displaystyle{ A}\) jest zbiorem niepustym, i \(\displaystyle{ A}\) jest przedziałem początkowym w \(\displaystyle{ \left( 0,1\right]}\), więc stosując nasz lemat otrzymujemy, że \(\displaystyle{ a}\) jest najmniejszy również w \(\displaystyle{ \left( 0,1\right]}\), wtedy prowadzi to do sprzeczności, gdyż \(\displaystyle{ a\in\left( 0,1\right]}\), a więc \(\displaystyle{ a>0}\), i otrzymujemy, że istnieje \(\displaystyle{ b\in\RR}\), takie, że \(\displaystyle{ 0<b<a<1}\), a zatem \(\displaystyle{ b\in \left( 0,1\right]}\) i \(\displaystyle{ b<a}\), a więc \(\displaystyle{ b}\) jest jeszcze mniejszym elementem \(\displaystyle{ \left( 0,1\right]}\)- sprzeczność. Wobec czego zbiór \(\displaystyle{ \left[ 0,2\right]}\) nie jest podobny do żadnego przedziału początkowego w \(\displaystyle{ \left( 0,1\right].}\)

Przypuśćmy teraz, że zbiór \(\displaystyle{ \left( 0,1\right]}\) jest podobny do przedziału początkowego \(\displaystyle{ A}\) w \(\displaystyle{ \left[ 0,2\right].}\) Istnieje zatem podobieństwo między tymi dwoma zbiorami. Niech \(\displaystyle{ f:\left( 0,1\right] \rightarrow A}\) będzie podobieństwem. Wtedy \(\displaystyle{ f}\) jest bijekcją, więc ponieważ \(\displaystyle{ \left(0,1 \right]}\) jest zbiorem niepustym, to \(\displaystyle{ A}\) również, wtedy \(\displaystyle{ 0}\) jest najmniejszą liczbą w \(\displaystyle{ \left[ 0,2\right] }\), więc również \(\displaystyle{ 0}\) jest najmniejsze w \(\displaystyle{ A}\). Ponieważ zbiór \(\displaystyle{ \left( 0,1\right]}\) jest podobny do \(\displaystyle{ A}\), więc również w \(\displaystyle{ \left( 0,1\right]}\) powinien być element najmniejszy, a w \(\displaystyle{ \left( 0,1\right]}\) nie ma liczby najmniejszej- sprzeczność. Wobec czego \(\displaystyle{ \left( 0,1\right]}\) nie jest podobny do żadnego przedziału początkowego w \(\displaystyle{ \left[ 0,2\right] .\square}\)

A więc twierdzenie, że dla dwóch zbiorów dobrze uporządkowanych jeden z nich jest podobny do przedziału początkowego drugiego, twierdzenie to nie ma odpowiednika dla liniowych porządków.

Wiemy, że w zborze dobrze uporządkowanym \(\displaystyle{ \left( X, \le \right) }\) każdy przedział pocżatkowy zbioru \(\displaystyle{ X}\) różny od \(\displaystyle{ X}\), jest postaci \(\displaystyle{ O(x)=\left\{ y\in X: \ y<x\right\}}\), dla pewnego \(\displaystyle{ x\in X}\). Uogólnienie na zbiory liniowo uporządkowane nie zachodzi. Wystarczy rozważyć zbiór liczb rzeczywistych z naturalnym porządkiem, a jako przedział początkowy wziąć, \(\displaystyle{ \overline{O\left( 0\right) } =\RR _{-} \cup \left\{ 0\right\}.}\) Niewątpliwie jest to przedział początkowy w \(\displaystyle{ \RR}\) (bo zbiory postaci \(\displaystyle{ \overline {O(x)}}\), gdzie \(\displaystyle{ x}\) jest elementem danego zbioru liniowo uporządkowanego, są zawsze przedziałami początkowymi, co łatwo sprawdzić jakby co). Niewątplwie \(\displaystyle{ \overline{O\left( 0\right) } \neq \RR}\), łatwo się przekonać, że nie może być on postaci \(\displaystyle{ O(x),}\) dla żadnej liczby rzeczywistej \(\displaystyle{ x\in\RR.}\)

Na koniec podam jeszcze jeden fakt właściwy zbiorom dobrze uporządkowanym.

Przypomnę może, że jeśli \(\displaystyle{ \left( X, \le\right)}\) jest zbiorem dobrze uporządkowanym, to rodzina jego wszystkich jego istotnych( różnych od \(\displaystyle{ X}\)) przedziałów początkowych uporządkowana inkluzją jest do niego podobna( a więc jest zbiorem dobrze uporządkowanym, gdyż własność bycia dobrym porządkiem jest przenoszona przez podobieństwo, można stosować więc ten chwyt dowolną skończoną ilość razy, więcej na ten temat można przeczytać TUTAJ). Jednak nie zachodzi to dla dowolnych zbiorów liniowo uporządkowanych, nie zachodzi np. dla porządków gęstych, nie zachodzi np. dla porządków ciągłych.( Przypominam można łatwo pokazać, że dla zbioru liniowo uporządkowanego rodzina jego wszystkich przedziałów początkowych jest uporządkowana liniowo przez inkluzję).

Aby pokazać kontrprzykład dla porządków gęstych rozważmy standardowo zbiór liczb wymiernych z naturalnym porządkiem- jest to zbiór liniowo uporządkowany gęsty. Rozważmy rodzinę jego wszystkich istotnych przedziałów początkowych uporządkowaną liniowo przez inkluzję. Ponieważ \(\displaystyle{ 0\in\QQ}\), to możemy rozważyć zbiory: \(\displaystyle{ O(0)=\left\{ x\in\QQ: x<0\right\},}\) i \(\displaystyle{ \overline{O\left( 0\right) }=\left\{ x\in\QQ: \ x \le 0\right\}.}\) Są to niewątpliwie przedziały początkowe w \(\displaystyle{ \QQ}\) różne od \(\displaystyle{ \QQ}\), i \(\displaystyle{ O(0)\subset \overline{O(0)}}\). Łatwo się można też przekonać, że nie da się pomiędzy nimi włożyć przedziału początkowego pośredniego względem inkluzji (gdyż różnią się tylko jednym elementem- zerem), więc nie ma pomiędzy nimi przedziału początkowego pośredniego względem inkluzji, a więc ten porządek nie jest gęsty. Ponieważ zbiór liczb wymiernych jest uporządkowany w sposób gęsty, a więc rodzina jego istotnych przedziałów początkowych uporządkowana inkluzją nie może być do niego podobna.

Podobnie dla porządków ciągłych, wystarczy rozważyć \(\displaystyle{ \RR}\) z naturalnym porządkiem, a jako przedziały początkowe wziąć: \(\displaystyle{ \RR_{-}=O(0)}\) i \(\displaystyle{ \overline{O(0)}=\RR_{-} \cup \left\{ 0\right\}}\), podobnie to można uzasadnić, ale muszę już iść spać.