Zbiory liniowo uporządkowane skończone i nieskończone

Algebra zbiorów. Relacje, funkcje, iloczyny kartezjańskie... Nieskończoność, liczby kardynalne... Aksjomatyka.
Jakub Gurak
Użytkownik
Użytkownik
Posty: 1392
Rejestracja: 20 lip 2012, o 21:19
Płeć: Mężczyzna
Lokalizacja: Rzeszów
Podziękował: 60 razy
Pomógł: 83 razy

Zbiory liniowo uporządkowane skończone i nieskończone

Post autor: Jakub Gurak »

Udowodniłem przedwczoraj, że zbiór liniowo uporządkowany jest skończony, dokładnie wtedy, gdy są spełnione poniższe dwa warunki: 1) niepuste podzbiory mają elementy najmniejsze; i po drugie 2) niepuste podzbiory mają elementy największe. Oznacza to, że w zbiorze liniowo uporządkowanym nieskończonym albo istnieje niepusty podzbiór bez elementu najmniejszego (on chyba będzie musiał być nieskończony), albo istnieje niepusty podzbiór bez elementu największego (on chyba również będzie musiał być nieskończony). Myślę, że to ciekawe. Udowodniłem też, że jeśli rozważać będziemy zbiory liniowo uporządkowane podobne do podzbiorów zbioru liczb naturalnych z naturalnym porządkiem, to albo takie zbiory muszą być skończone, albo podobne do zbioru liczb naturalnych z naturalnym porządkiem. Proszę zobaczyć, mimo że podzbiorów nieskończonych zbioru liczb naturalnych jest mnóstwo, to pod względem typu porządkowego jest dokładnie jeden- typ zbioru liczb naturalnych ze zwykłym porządkiem. Zadziwiające. Przedstawię teraz dowody tych ciekawych faktów.

Przypomnijmy prosty fakt, że w zbiorze liniowo uporządkowanym skończone niepuste podzbiory mają zawsze element najmniejszy i największy. W szczególności dla podzbiorów jednoelementowych ich jedyny element jest ich elementem najmniejszym i największym. Łato to przez indukcję można udowodnić.

Przypomnijmy, że zbiór liniowo uporządkowany \(\displaystyle{ \left( X, \le\right) }\) nazywamy zbiorem dobrze uporządkowanym, gdy każdy niepusty podzbiór \(\displaystyle{ X}\) ma element najmniejszy.

Przypomnijmy, że jeśli \(\displaystyle{ \left( X, \le\right) }\) jest zbiorem liniowo uporządkowanym, to porządek odwrotny \(\displaystyle{ \le ^{-1}}\) jest porządkiem liniowym na tym samym zbiorze \(\displaystyle{ X}\) .

Udowodnijmy teraz lemat:

Lemat: jeśli \(\displaystyle{ \left( X, \le\right) }\) jest zbiorem dobrze uporządkowanym, to zbiór uporządkowany \(\displaystyle{ \left( X, \le ^{-1}\right) }\) jest dobrze uporządkowany, dokładnie wtedy, gdy zbiór \(\displaystyle{ X}\) jest skończony,

Dowód:

Zauważmy najpierw, że ponieważ \(\displaystyle{ X}\) jest dobrze uporządkowany, a więc i liniowo przez \(\displaystyle{ \le}\), to \(\displaystyle{ \le ^{-1}}\) jest liniowym porządkiem na \(\displaystyle{ X.}\)

Implikacja w jedną stronę jest prosta: jeśli \(\displaystyle{ X}\) jest skończony, to \(\displaystyle{ \left( X, \le ^{-1}\right) }\) jest dobrze uporządkowany. Aby to wykazać, należy wykazać, że każdy niepusty podzbiór \(\displaystyle{ X}\) ma element najmniejszy, względem \(\displaystyle{ \le ^{-1}.}\) Niech zatem \(\displaystyle{ A\subset X}\) będzie niepustym podzbiorem zbioru \(\displaystyle{ X}\). Pokażemy, że zbiór \(\displaystyle{ A}\) ma element najmniejszy względem \(\displaystyle{ \le ^{-1}}\). Ponieważ zbiór \(\displaystyle{ \left( X, \le\right) }\) jest dobrze uporządkowany, (a więc i liniowo),i zbiór \(\displaystyle{ X}\) jest skończony (więc zbiór \(\displaystyle{ A}\) również), więc skończony niepusty zbiór \(\displaystyle{ A}\) ma element najmniejszy i największy względem \(\displaystyle{ \le}\) , więc w szczególności zbiór \(\displaystyle{ A}\) ma element największy \(\displaystyle{ a}\) względem \(\displaystyle{ \le}\), który to element \(\displaystyle{ a}\) jest elementem najmniejszym \(\displaystyle{ A}\) względem \(\displaystyle{ \le ^{-1} .\square}\)

W drugą stronę, jeśli \(\displaystyle{ X}\) jest nieskończony, to \(\displaystyle{ \left( X, \le ^{-1}\right) }\) nie jest dobrze uporządkowany.

Aby to udowodnić wykorzystamy twierdzenie, że dla dwóch zbiorów dobrze uporządkowanych jeden z nich jest podobny do przedziału początkowego drugiego.

Rozważmy \(\displaystyle{ \left( \NN=\omega, \le _{\omega}\right) }\) ze zwykłym porządkiem, zbiór dobrze uporządkowany, oraz nasz zbiór dobrze uporządkowany \(\displaystyle{ \left( X, \le\right) }\) . Przypuśćmy, że \(\displaystyle{ X}\) jest podobny do pewnego istotnego (a więc gdy \(\displaystyle{ \omega \neq A}\)) przedziału początkowego \(\displaystyle{ A\subset \omega}\) zbioru \(\displaystyle{ \omega.}\) Ponieważ \(\displaystyle{ \left(\omega, \le _\omega\right) }\) jest zbiorem dobrze uporządkowanym, a \(\displaystyle{ A}\) istotnym przedziałem początkowym, to \(\displaystyle{ A}\) jest postaci \(\displaystyle{ A=O(x)=\left\{ y\in\omega: \ y< _{\omega} x \right\}}\) , gdzie \(\displaystyle{ x\in\omega=\NN.}\) Ponieważ w konstrukcji von Neumanna liczb naturalnych liczba naturalna jest zbiorem liczb naturalnych od niej mniejszych, to \(\displaystyle{ A=O(x)= x\in\NN}\). Oczywiście liczba naturalna von Neumanna \(\displaystyle{ x}\) jest zbiorem skończonym, więc \(\displaystyle{ A}\) jest zbiorem skończonym. Ponieważ \(\displaystyle{ X}\) jest podobny do \(\displaystyle{ A}\), to istnieje podobieństwo \(\displaystyle{ f:X \rightarrow A}\). Wtedy \(\displaystyle{ f}\) jest bijekcją, a zatem zbiór \(\displaystyle{ X}\) jest równoliczny ze zbiorem \(\displaystyle{ A}\)- zbiorem skończonym, więc zbiór \(\displaystyle{ X}\) jest skończony-sprzeczność. Wobec czego \(\displaystyle{ X}\) nie jest podobny do żadnego istotnego przedziału początkowego zbioru \(\displaystyle{ \omega.}\)

Wobec czego zbiór \(\displaystyle{ \omega}\) musi być podobny do pewnego przedziału początkowego \(\displaystyle{ A}\) zbioru \(\displaystyle{ \left( X, \le\right) }\). Ponieważ podobieństwo jest bijekcją, to \(\displaystyle{ \omega\sim A}\)- zbiór \(\displaystyle{ \omega}\) jest równoliczny z \(\displaystyle{ A}\). Wtedy \(\displaystyle{ A}\) jest zbiorem niepustym, i jest podzbiorem zbioru \(\displaystyle{ X}\), i wtedy w \(\displaystyle{ A}\) nie ma elementu najmniejszego względem \(\displaystyle{ \le ^{-1}. }\) (Gdyby bowiem element \(\displaystyle{ x}\) byłby elementem najmniejszym \(\displaystyle{ A}\) względem \(\displaystyle{ \le ^{-1}}\), to \(\displaystyle{ x}\) byłby elementem największym \(\displaystyle{ A}\) względem \(\displaystyle{ \le}\) , wtedy zbiór liniowo uporządkowany \(\displaystyle{ \left( A, \le_A\right) }\) miałby element największy , więc ponieważ zbiór \(\displaystyle{ \omega}\) jest podobny do \(\displaystyle{ A}\), to również w \(\displaystyle{ \left( \omega, \le _{\omega}\right) }\) byłby element największy, a w \(\displaystyle{ \omega=\NN}\) nie ma liczby największej-sprzeczność).
Wobec czego w \(\displaystyle{ A}\) nie ma elementu najmniejszego względem \(\displaystyle{ \le ^{-1}}\), a więc \(\displaystyle{ \left( X, \le ^{-1}\right) }\) nie jest dobrze uporządkowany.\(\displaystyle{ \square }\) :lol:


Udowodnimy teraz zapowiedzianą charakteryzację:

Jeśli \(\displaystyle{ \left( X, \le\right)}\) jest zbiorem liniowo uporządkowanym, to:

\(\displaystyle{ X}\) jest skończony, wtedy i tylko wtedy, gdy: [ 1) każdy niepusty zbiór \(\displaystyle{ \left\{ \right\} \neq A\subset X}\) ma element najmniejszy; i 2) każdy zbiór \(\displaystyle{ \left\{ \right\} \neq A\subset X}\) ma element największy ].

Dowód:

Implikacja w jedną stronę jest prosta, tzn. jeśli \(\displaystyle{ X}\) jest skończony, to teza łatwo wynika z podanego faktu o skończonych podzbiorach zbioru liniowo uporządkowanego.

Jeśli \(\displaystyle{ X}\) jest nieskończony, to :

Rozważmy dwa przypadki:

1)\(\displaystyle{ X}\) nie jest dobrze uporządkowany. Wtedy \(\displaystyle{ X}\) jako nieskończony, jest oczywiście niepusty, zatem ma niepusty podzbiór (np. \(\displaystyle{ X}\)), więc ponieważ nie jest dobrze uporządkowany, więc również istnieje niepusty podzbiór \(\displaystyle{ \left\{ \right\} \neq A\subset X}\) bez elementu najmniejszego, a wiec równoważność nasza zachodzi, (zgodnie ze schematem \(\displaystyle{ 0 \Leftrightarrow 0 \wedge P =0}\), gdzie \(\displaystyle{ P}\) oznacza dowolne zdanie), a więc równoważność nasza zachodzi.

2) Jeśli \(\displaystyle{ X}\) jest dobrze uporządkowany, to ponieważ \(\displaystyle{ X}\) jest nieskończony, to na mocy lematu powyżej \(\displaystyle{ \left( X, \le ^{-1}\right) }\) nie jest dobrze uporządkowany, a zatem (i ponieważ istnieją niepuste podzbiory zbioru \(\displaystyle{ X}\), np. cały \(\displaystyle{ X}\)), więc również istnieje niepusty zbiór \(\displaystyle{ \left\{ \right\} \neq A\subset X}\) bez elementu najmniejszego względem \(\displaystyle{ \le ^{-1}.}\) Wtedy w \(\displaystyle{ A}\) nie ma elementu największego względem \(\displaystyle{ \le.}\) (Gdyż gdyby \(\displaystyle{ A}\) miał element największy \(\displaystyle{ a\in A}\), względem \(\displaystyle{ \le}\), to \(\displaystyle{ a}\) byłby elementem najmniejszym \(\displaystyle{ A}\) względem \(\displaystyle{ \le ^{-1}}\)). A zatem zbiór \(\displaystyle{ \left\{ \right\} \neq A\subset X}\) nie ma elementu największego względem \(\displaystyle{ \le}\), równoważność więc zachodzi (zgodnie ze schematem zdaniowym \(\displaystyle{ 0 \Leftrightarrow P \wedge 0=0}\), gdzie \(\displaystyle{ P}\) oznacza dowolne zdanie), więc równoważność nasza zachodzi, co kończy dowód.\(\displaystyle{ \square}\) :lol:

Oznacza to zatem, że jeśli zbiór liniowo uporządkowany \(\displaystyle{ X}\) jest nieskończony, to albo istnieje nieskończony podzbiór bez elementu najmniejszego, albo istnieje nieskończony podzbiór bez elementu największego. Myślę, ze to ciekawe.

Udowodnijmy jeszcze, ze jeśli \(\displaystyle{ \left( X, \le\right) }\) jest zbiorem liniowo uporządkowanym, i \(\displaystyle{ X}\) jest podobny do pewnego podzbioru \(\displaystyle{ A}\) zbioru liczb naturalnych z naturalnym porządkiem, to \(\displaystyle{ X}\) jest skończony lub \(\displaystyle{ X}\) jest podobny do \(\displaystyle{ \NN}\) ze zwykłym porządkiem.

Dowód:

Załóżmy, że \(\displaystyle{ X}\) jest nieskończony, i pokażmy, że \(\displaystyle{ X}\) jest podobny do \(\displaystyle{ \NN.}\)

Ponieważ \(\displaystyle{ X}\) jest podobny do \(\displaystyle{ A}\), więc istnieje podobieństwo \(\displaystyle{ f:X \rightarrow A.}\) Wtedy \(\displaystyle{ f}\) jest bijekcją, a zatem zbiór \(\displaystyle{ X}\) jest równoliczny ze zbiorem \(\displaystyle{ A}\), ponieważ \(\displaystyle{ X}\) jest nieskończony, to również \(\displaystyle{ A}\) jest nieskończony. Mamy \(\displaystyle{ A\subset \NN.}\) Ponieważ \(\displaystyle{ A}\) jest nieskończonym podzbiorem zbioru liczb naturalnych, to pewne twierdzenie mocy zbiorów daje, że zbiór \(\displaystyle{ A}\) musi być równoliczny ze zbiorem liczb naturalnych \(\displaystyle{ \NN}\). Można zatem zbiór \(\displaystyle{ A}\) ustawić w ciąg \(\displaystyle{ A=\left\{ a_0.a_1, a_2,\ldots\right\}.}\) Wtedy \(\displaystyle{ A}\) jest podobny do \(\displaystyle{ \NN}\)- wystarczy przyporządkować \(\displaystyle{ a_n\in A \rightarrow n\in \NN.}\) A zatem \(\displaystyle{ A \approx \NN}\)- zbiór \(\displaystyle{ A}\) jest podobny do \(\displaystyle{ \NN}\), ponieważ \(\displaystyle{ X \approx A}\), więc \(\displaystyle{ X \approx \NN. \square}\) :lol: :D
Jakub Gurak
Użytkownik
Użytkownik
Posty: 1392
Rejestracja: 20 lip 2012, o 21:19
Płeć: Mężczyzna
Lokalizacja: Rzeszów
Podziękował: 60 razy
Pomógł: 83 razy

Re: Zbiory liniowo uporządkowane skończone i nieskończone

Post autor: Jakub Gurak »

Udowodniłem przedwczoraj w końcu, nie było to łatwe- zajęło mi to co najmniej \(\displaystyle{ 6}\) wieczorów, ale się udało, udowodniłem, że jeśli \(\displaystyle{ \left( X, \le\right) }\) jest zbiorem liniowo uporządkowanym podobnym do pewnego podzbioru \(\displaystyle{ A\subset \ZZ}\) zbioru liczb całkowitych z naturalnym porządkiem, to są jedynie cztery możliwości:

1) zbiór \(\displaystyle{ X}\) jest skończony;
2) zbiór \(\displaystyle{ X}\) jest podobny do \(\displaystyle{ \NN}\)( z naturalnym porządkiem);
3) \(\displaystyle{ X}\) jest podobny do \(\displaystyle{ \ZZ_- \cup \left\{ 0\right\}}\);
4) \(\displaystyle{ X}\) jest podobny do \(\displaystyle{ \ZZ.}\)

Tzn. zachodzi dokładnie jedna z tych czterech możliwości. Oznacza to, że jeśli zbiór \(\displaystyle{ X}\) jest nieskończony, to są możliwe tylko trzy typy porządkowe: typ zbioru \(\displaystyle{ \NN}\), typ zbioru \(\displaystyle{ \ZZ_- \cup \left\{ 0\right\}}\) liczb całkowitych ujemnych wraz z zerem i typ zbioru \(\displaystyle{ \ZZ}\) - mimo, że podzbiorów nieskończonych zbioru liczb całkowitych jest mnóstwo, to pod względem typu porządkowego są tylko trzy możliwości- myślę, że to ciekawe. Przedstawię teraz dowód tego ciekawego faktu.

Podajmy najpierw dwa lematy.

Lemat 1. Jeśli zbiór liniowo uporządkowany \(\displaystyle{ (Y, \le)}\) jest podobny do pewnego podzbioru \(\displaystyle{ B}\) zbioru liczb całkowitych ujemnych wraz z zerem \(\displaystyle{ \ZZ_- \cup \left\{ 0\right\}}\), to zbiór \(\displaystyle{ Y}\) jest skończony lub \(\displaystyle{ Y}\) jest podobny do \(\displaystyle{ \ZZ _{-} \cup \left\{ 0\right\}}\), czyli \(\displaystyle{ Y \approx \ZZ_- \cup \left\{ 0\right\}.}\)

Tzn. jeśli zbiór \(\displaystyle{ Y}\) jest nieskończony, to musi być typu \(\displaystyle{ \ZZ_- \cup \left\{ 0\right\}.}\)

Dowód:

Załóżmy, że \(\displaystyle{ Y}\) jest nieskończony, i pokażmy, że \(\displaystyle{ Y}\) jest podobny do \(\displaystyle{ \ZZ _{-} \cup \left\{ 0\right\}.}\)

Ponieważ \(\displaystyle{ Y}\) jest podobny do \(\displaystyle{ B\subset \ZZ_- \cup \left\{ 0\right\}}\), więc istnieje podobieństwo \(\displaystyle{ f:Y \rightarrow B}\). Wtedy \(\displaystyle{ f}\) jest bijekcją, zatem zbiór \(\displaystyle{ Y}\) jest równoliczny ze zbiorem \(\displaystyle{ B}\), ponieważ \(\displaystyle{ Y}\) jest nieskończony, to również zbiór \(\displaystyle{ B}\) jest nieskończony.

Rozważmy teraz zbiór \(\displaystyle{ -B:=\left\{ -x| \ x\in B\right\}\subset \NN.}\)

Łatwo pokazać, że funkcja \(\displaystyle{ g:B \rightarrow \left( -B\right) }\), dana jako:

\(\displaystyle{ g(x)=-x, }\)

jest bijekcją.

A zatem zbiór \(\displaystyle{ B}\) jest równoliczny ze zbiorem \(\displaystyle{ (-B).}\) Ponieważ zbiór \(\displaystyle{ B}\) jest nieskończony, to również zbiór \(\displaystyle{ (-B)}\) jest nieskończony.

Ale zbiór \(\displaystyle{ (-B)\subset \NN}\) i zbiór \(\displaystyle{ (-B)}\) jest nieskończony, i \(\displaystyle{ \left(-B, \le _{\NN}\right)}\) jest zbiorem liniowo uporządkowanym, oraz \(\displaystyle{ \left( -B\right) \approx \left( -B\right) \subset \NN}\), a zatem (ponieważ \(\displaystyle{ -B}\) jest nieskończony ) ,więc na mocy ostatniego dowodu z postu powyżej, musi zbiór \(\displaystyle{ -B}\) być podobny do \(\displaystyle{ \NN.}\)

Wykażemy teraz, że \(\displaystyle{ (-B, \ge _\NN) \approx (B, \le_\ZZ).}\)

Wystarczy rozważyć poprzednią bijekcję \(\displaystyle{ g:B \rightarrow -B}\), daną jako \(\displaystyle{ g(x)=-x.}\) I mamy (dla dowolnych \(\displaystyle{ x_1, x_2\in B}\)) mamy:

\(\displaystyle{ x_1 \le_\ZZ x_2 \Leftrightarrow -x_1 \ge _\NN -x_2 \Leftrightarrow g(x_1) \ge_\NN g(x_2) \Leftrightarrow g(x_1) \le _\NN ^{-1} g(x_2).}\)

Wobec czego \(\displaystyle{ g}\) jest podobieństwem, i zbiory liniowo uporządkowane \(\displaystyle{ (B, \le _Z)}\) oraz \(\displaystyle{ (-B, \ge _\NN)}\) są podobne.

Wiemy, że \(\displaystyle{ \NN}\) jest podobny do \(\displaystyle{ \left( -B, \le _\NN\right)}\), ponieważ \(\displaystyle{ \left(B, \le _\ZZ\right)}\) jest podobny do \(\displaystyle{ (-B, \ge _\NN)=\left( -B, \le _\NN ^{-1} \right)}\) (i \(\displaystyle{ \NN}\) jest podobny do \(\displaystyle{ (-B, \le _\NN)}\), więc również dla porządków odwrotnych otrzymujemy, że \(\displaystyle{ (-B, \le _\NN ^{-1} ) \approx (\NN, \le ^{-1} ) \approx \ZZ_- \cup \left\{ 0\right\}.}\)

A zatem \(\displaystyle{ B}\) jest podobny do \(\displaystyle{ \ZZ _{-} \cup \left\{ 0\right\}}\), czyli \(\displaystyle{ B \approx \ZZ_- \cup \left\{ 0\right\}. }\) Ponieważ \(\displaystyle{ Y \approx B}\), więc \(\displaystyle{ Y \approx \ZZ_- \cup \left\{ 0\right\}. \square}\)

Wykażemy teraz jeszcze jeden lemat:

Lemat 2. Jeśli mamy cztery zbiory liniowo uporządkowane \(\displaystyle{ \left( X, \le _X\right); \left( Y, \le_Y\right)}\), gdzie zbiory \(\displaystyle{ X, Y}\) są rozłączne, oraz zbiory liniowo uporządkowane \(\displaystyle{ \left( X', \le _{X'}\right) ; \left( Y', \le _{Y'}\right)}\) , gdzie zbiory \(\displaystyle{ X', Y'}\) są rozłączne, oraz odpowiednie zbiory są podobne (tzn. \(\displaystyle{ X \approx X'}\) oraz \(\displaystyle{ Y \approx Y'}\)), to suma porządkowa \(\displaystyle{ X\oplus Y}\) jest podobna do sumy porządkowej \(\displaystyle{ X'\oplus Y'.}\)

Dowód:

Ponieważ \(\displaystyle{ X}\) jest podobny do \(\displaystyle{ X'}\), więc istnieje podobieństwo \(\displaystyle{ f:X \rightarrow X'}\), wtedy \(\displaystyle{ f}\) jest bijekcją. Ponieważ \(\displaystyle{ Y}\) jest podobny do \(\displaystyle{ Y'}\), więc istnieje podobieństwo \(\displaystyle{ g:Y \rightarrow Y'}\), wtedy \(\displaystyle{ g}\) jest bijekcją. Rozważmy relację \(\displaystyle{ (f \cup g)}\), ponieważ zbiory \(\displaystyle{ X,Y}\) są rozłączne, i zbiory \(\displaystyle{ X', Y'}\) są rozłączne, to suma takich dwóch bijekcji o rozłącznych dziedzinach i rozłącznych przeciwdziedzinach będzie bijekcją ze sumy dziedzin \(\displaystyle{ X \cup Y}\) w sumę przeciwdziedzin \(\displaystyle{ X' \cup Y'}\) ( jest to w miarę prosty fakt).

Pozostaje pokazać, że funkcja \(\displaystyle{ \left( f \cup g\right)}\) jest monotoniczna.

W tym celu ustalmy dowolne \(\displaystyle{ a,b\in X \cup Y}\), i załóżmy, że \(\displaystyle{ a \le _{X\oplus Y} b}\) i pokażmy, że również \(\displaystyle{ \left( f \cup g\right)(a) \le _{X'\oplus Y'} \left( f \cup g\right) (b).}\)

Jeśli \(\displaystyle{ a,b\in X}\), to z definicji sumy porządkowej dostajemy \(\displaystyle{ a \le _X b}\). Ponieważ \(\displaystyle{ f:X \rightarrow X'}\) jest podobieństwem, więc również \(\displaystyle{ f(a) \le _{X'} f(b)}\), ponieważ funkcja \(\displaystyle{ \left( f \cup g\right) }\) jest rozszerzeniem funkcji \(\displaystyle{ f}\), to \(\displaystyle{ (f \cup g)\left( a\right)=f(a) \le _{X'} f(b)=\left( f \cup g\right) (b)}\), i ponieważ liniowy porządek \(\displaystyle{ \le _{X'\oplus Y'}}\) rozszerza liniowy porządek \(\displaystyle{ \le _{X'}}\), więc tym bardziej otrzymujemy nierówność \(\displaystyle{ \left( f \cup g\right) (a) \le _{X'\oplus Y'} \left( f \cup g\right) (b).}\)

Jeśli \(\displaystyle{ a,b\in Y}\), to rozumujemy analogicznie.

Jeśli \(\displaystyle{ a\in X, b\in Y}\), to \(\displaystyle{ f(a)\in X', g(b)\in Y'}\), więc ponieważ, z definicji sumy porządkowej, każdy element \(\displaystyle{ X'}\) jest mniejszy od każdego elementu \(\displaystyle{ Y'}\), więc \(\displaystyle{ f(a) \le _{X'\oplus Y'} g(b)}\), a ponieważ funkcja \(\displaystyle{ \left( f \cup g\right)}\) jest rozszerzeniem funkcji \(\displaystyle{ f}\) i \(\displaystyle{ g}\), więc: \(\displaystyle{ \left( f \cup g\right)\left( a\right)=f(a) \le _{X'\oplus Y'} g(b)=\left( f \cup g\right) (b).}\)

Przypadek \(\displaystyle{ a \in Y, b\in X}\) jest niemożliwy, gdyż wtedy, ponieważ z definicji sumy porządkowej, każdy element \(\displaystyle{ X}\) jest mniejszy od każdego elementu \(\displaystyle{ Y}\), więc \(\displaystyle{ b \le _{X\oplus Y} a}\), a mamy \(\displaystyle{ a \le _{X\oplus Y} b}\), tak więc \(\displaystyle{ a=b}\), a więc \(\displaystyle{ a\in X \cap Y}\), a zbiory \(\displaystyle{ X,Y}\) są rozłączne- sprzeczność.

Zatem funkcja \(\displaystyle{ \left( f \cup g\right)}\) jest monotoniczna. Ponieważ ta funkcja jest bijekcją z \(\displaystyle{ X \cup Y}\) do \(\displaystyle{ X' \cup Y'}\)- bijekcją monotoniczną pomiędzy dwoma zbiorami liniowo uporządkowanymi, wiec \(\displaystyle{ (f \cup g )}\) jest podobieństwem, i \(\displaystyle{ X \oplus Y \approx X'\oplus Y'. \square}\)


Przejdźmy do naszego dowodu.

Wykażemy, że zachodzi co najmniej jeden z tych czterech przypadków. W tym celu załóżmy, że zbiór \(\displaystyle{ X}\) jest nieskończony, i że \(\displaystyle{ X}\) nie jest podobny do \(\displaystyle{ \NN}\), oraz że \(\displaystyle{ X}\) nie jest podobny do \(\displaystyle{ \ZZ _{-} \cup\left\{ 0\right\}}\), i pokażmy, że \(\displaystyle{ X}\) jest podobny do \(\displaystyle{ \ZZ.}\)

Ponieważ \(\displaystyle{ X \approx A\subset \ZZ}\), więc istnieje podobieństwo \(\displaystyle{ f:A \rightarrow X}\), wtedy \(\displaystyle{ f}\) jest bijekcją, a zatem zbiór \(\displaystyle{ A}\) jest równoliczny ze zbiorem \(\displaystyle{ X}\). Ponieważ zbiór \(\displaystyle{ X}\) jest nieskończony, to \(\displaystyle{ A}\) również jest nieskończony.

Pokażemy teraz, że zbiór \(\displaystyle{ A_-:=\left\{ x\in A: x<0\right\}}\) jest nieskończony. Przypuśćmy nie wprost, że jest skończony. Pokażemy, że wtedy \(\displaystyle{ X}\) jest podobny do \(\displaystyle{ \NN.}\)

Skończony zbiór \(\displaystyle{ A_-}\) oznaczmy ( i uporządkujmy porządkiem naturalnym) jako: \(\displaystyle{ A_-=\left\{ a_1, a_2,\ldots, a_n\right\}.}\) Wtedy zbiór \(\displaystyle{ A_+:=A \cap \NN}\) jest nieskończony, gdyż:

\(\displaystyle{ A_- \cup A_+=\left( A \cap \RR_-\right) \cup (A \cap \NN )= \stackrel {A\subset \ZZ}=(A \cap \ZZ_-) \cup \left( A \cap \NN\right)=A \cap \ZZ=A,}\)

Więc, w przeciwnym razie, zbiór \(\displaystyle{ A}\), jako suma dwóch zbiorów skończonych, byłby skończony- sprzeczność.

Zauważmy, że \(\displaystyle{ (A_+, \le _\NN)}\) jest zbiorem liniowo uporządkowanym, i \(\displaystyle{ A_+ \approx A_+\subset \NN}\), ponieważ \(\displaystyle{ A_+}\) jest nieskończony, to na mocy faktu udowodnionego w poście powyżej na samym końcu, otrzymujemy, że musi zbiór \(\displaystyle{ A_+}\) być podobnym do \(\displaystyle{ \NN}\). A zatem istnieje podobieństwo \(\displaystyle{ g:\NN \rightarrow A_+.}\) Wtedy \(\displaystyle{ g}\) jest bijekcją. A zatem zbiór \(\displaystyle{ A_+}\) można ustawić w ciąg \(\displaystyle{ A_+=\left\{ g_0,g_1,g_2,\ldots \right\} }\). Teraz tworzymy podobieństwo \(\displaystyle{ h}\) z \(\displaystyle{ \NN}\) do \(\displaystyle{ A}\). Jego działanie jest następujące:

\(\displaystyle{ 0 \rightarrow a_1, \\
1 \rightarrow a_2, \\
2 \rightarrow a_3, \\
\vdots \\
n-1 \rightarrow a_n, \\
n \rightarrow g_0, \\
\left( n+1\right) \rightarrow g_1, \\
\left( n+2\right) \rightarrow g_2, \\
\vdots}\)


Formalnie funkcję \(\displaystyle{ h:\NN \rightarrow A}\) określamy jako:

\(\displaystyle{ h(m)= \begin{cases} a_{\left( m+1\right) }, \hbox { dla m<n,} \\ g_{\left( m-n\right) }, \hbox {dla }m \ge n. \end{cases} }\)

I pokazujemy, że ona jest podobieństwem.
Dowód:    
A zatem zbiór \(\displaystyle{ \NN}\) jest podobny do \(\displaystyle{ A}\), ponieważ \(\displaystyle{ X}\) jest podobny do \(\displaystyle{ A}\), więc możemy wnioskować, że \(\displaystyle{ X}\) jest podobny do \(\displaystyle{ \NN}\)-sprzeczność.

Wobec czego zbiór \(\displaystyle{ A_-}\) jest nieskończony.


Wykażemy analogicznie, że zbiór \(\displaystyle{ A_+}\) jest nieskończony. Może w skrócie, jest to podobne rozumowanie.

Przypuśćmy nie wprost, że \(\displaystyle{ A_+=\left\{ x\in A: \ x \ge 0\right\}}\), przypuśćmy, że ten zbiór jest skończony, wtedy \(\displaystyle{ A_-}\) nieskończony (gdyby \(\displaystyle{ A_-}\) był skończony, to \(\displaystyle{ A,}\) jako suma dwóch zbiorów skończonych, byłby skończony, a \(\displaystyle{ A}\) jest nieskończony- sprzeczność). Ponieważ \(\displaystyle{ \left( A_-, \le _\ZZ\right) }\) jest zbiorem liniowo uporządkowanym, i \(\displaystyle{ A_- \approx A_-\subset \ZZ _{-} \cup \left\{ 0\right\} }\)(i \(\displaystyle{ A_-}\) jest nieskończony), więc na mocy lematu 1 zbiór \(\displaystyle{ A_-}\) musi być podobnym do \(\displaystyle{ \ZZ _{-} \cup \left\{ 0\right\} .}\) A zatem istnieje podobieństwo \(\displaystyle{ g:\ZZ _{-} \cup \left\{ 0 \right\} \rightarrow A_-}\) . Wtedy \(\displaystyle{ g}\) jest bijekcją. Ponieważ \(\displaystyle{ A_+}\) jest skończony, to oznaczmy \(\displaystyle{ A_+=\left\{ a_1,a_2,\ldots,a_n\right\}}\) (z porządkiem naturalnym) , i rozważmy poniższe podobieństwo, działające następująco:

\(\displaystyle{ 0 \rightarrow a_n, \\
-1 \rightarrow a_{n-1}; \\
-2 \rightarrow a_{n-2}, \\
\vdots \\
-n+1 \rightarrow a_1, \\
-n \rightarrow g_0, \\
-n-1 \rightarrow g\left( -1\right), \\
-n-2 \rightarrow g\left( -2\right), \\
\vdots}\)


Formalnie, definiujemy funkcję \(\displaystyle{ h:\ZZ_- \cup \left\{ 0\right\} \rightarrow A}\) określoną jako:

\(\displaystyle{ h(m)= \begin{cases} a _{(m+n)}, \hbox{ dla m>-n}, \\ g(m+n),\hbox { dla } m \le -n. \end{cases} }\)

I pokazujemy, że ona jest podobieństwem.

A zatem \(\displaystyle{ \ZZ_- \cup \left\{ 0\right\}}\) jest podobny do \(\displaystyle{ A}\). Ponieważ \(\displaystyle{ X}\) jest podobny do \(\displaystyle{ A}\), więc \(\displaystyle{ X}\) jest podobny do \(\displaystyle{ \ZZ_- \cup \left\{ 0\right\}}\) - sprzeczność.

Wobec czego zbiór \(\displaystyle{ A_+}\) jest nieskończony. Wiemy również już, że \(\displaystyle{ A_-}\) jest nieskończony. Ponieważ \(\displaystyle{ (A_+, \le _\ZZ)}\) jest zbiorem liniowo uporządkowanym, i \(\displaystyle{ A_+ \approx A_+\subset\NN}\), więc ( i ponieważ \(\displaystyle{ A_+}\) jest nieskończony), to musi \(\displaystyle{ A_+}\) być podobny do \(\displaystyle{ \NN.}\)

Podobnie, ponieważ \(\displaystyle{ (A_-, \le _\ZZ )}\) jest zbiorem liniowo uporządkowanym, i \(\displaystyle{ A_- \approx A_-\subset \ZZ_- \cup \left\{ 0\right\}}\) , (i ponieważ zbiór \(\displaystyle{ A_-}\) jest nieskończony), więc na mocy lematu 1: \(\displaystyle{ A_- \approx \ZZ_- \cup \left\{ 0\right\}.}\) Ponieważ oczywiście \(\displaystyle{ \ZZ_- \cup \left\{ 0\right\} \approx \ZZ_-}\) , więc \(\displaystyle{ A_- \approx \ZZ_- .}\) Zauważmy, że \(\displaystyle{ A=A_- \oplus A_+}\) - zbiór \(\displaystyle{ A}\) jest sumą porządkową zbioru \(\displaystyle{ A_-}\) i zbioru \(\displaystyle{ A_+}\), ponieważ \(\displaystyle{ A_-}\) jest podobny do \(\displaystyle{ \ZZ_-}\) i \(\displaystyle{ A_+}\) jest podobny do \(\displaystyle{ \NN}\), to ta suma porządkowa jest podobna, na mocy lematu 2, do sumy porządkowej \(\displaystyle{ \ZZ_-\oplus \NN=\ZZ.}\) Tak więc \(\displaystyle{ A \approx \ZZ}\), ponieważ \(\displaystyle{ X \approx A}\), więc \(\displaystyle{ X \approx \ZZ. \square}\) :D

Pozostaje wykazać, że nie może zachodzić żadne dwa z tych czterech przypadków na raz.

To jednak jest proste, jeśli zbiór \(\displaystyle{ X}\) jest skończony i niepusty to ma element najmniejszy i największy, podczas gdy w zbiorze podobnym do \(\displaystyle{ \NN}\) nie ma elementu największego (tak jak w \(\displaystyle{ \NN}\)), w zbiorze podobnym do \(\displaystyle{ \ZZ_- \cup \left\{ 0\right\}}\) nie ma elementu najmniejszego, a w zbiorze podobnym do \(\displaystyle{ \ZZ}\) nie ma elementu najmniejszego ani największego. Zbiór skończony może być pusty, ale zbiór podobny do \(\displaystyle{ \NN}\) musi być niepusty, podobnie zbiór podobny do \(\displaystyle{ \ZZ_- \cup \left\{ 0\right\}}\) musi być niepusty i zbiór podobny do \(\displaystyle{ \ZZ}\) musi być niepusty. W ten sposób wykluczyliśmy pierwszy przypadek z pozostałymi. Teraz wykluczymy przypadek drugi z trzecim i czwartym. Ponieważ \(\displaystyle{ 0}\) jest najmniejszą liczbą naturalną, to w zbiorze podobnym do \(\displaystyle{ \NN}\) jest element najmniejszy, podczas gdy w zbiorze podobnym do \(\displaystyle{ \ZZ_- \cup \left\{ 0\right\}}\) nie ma elementu najmniejszego, podobnie, w zbiorze podobnym do \(\displaystyle{ \ZZ}\) nie ma elementu najmniejszego. Pozostaje wykluczyć przypadek trzeci z czwartym. Ponieważ \(\displaystyle{ 0}\) jest elementem największym w \(\displaystyle{ \ZZ_- \cup \left\{ 0\right\}}\) , to w zbiorze do niego podobnym jest element największy, podczas gdy w zbiorze podobnym do \(\displaystyle{ \ZZ}\) nie ma elementu największego.

W ten oto prosty sposób pokazaliśmy, że nie może zachodzić jednocześnie dwa z tych przypadków, wobec czego zachodzi zawsze co najwyżej jeden z tych czterech przypadków. Ale cały dowód powyżej pokazał, że zachodzi co najmniej jeden z tych czterech przypadków, wobec czego zachodzi zawsze dokładnie jeden z tych czterech przypadków.\(\displaystyle{ \square}\) :D :lol: 8-)
Jakub Gurak
Użytkownik
Użytkownik
Posty: 1392
Rejestracja: 20 lip 2012, o 21:19
Płeć: Mężczyzna
Lokalizacja: Rzeszów
Podziękował: 60 razy
Pomógł: 83 razy

Re: Zbiory liniowo uporządkowane skończone i nieskończone

Post autor: Jakub Gurak »

Udowodniłem w ostatnią środę wieczorem, że w zbiorze liniowo uporządkowanym podobnym do zbioru liczb całkowitych ujemnych wraz z zerem z naturalnym porządkiem , w dowolnym zbiorze liniowo uporządkowanym podobnym do niego, wtedy każdy przekrój Dedekinda daje skok. Przedstawię teraz dowód tego ciekawego faktu.

Przypomnę może najpierw, że:

W zbiorze liniowo uporządkowanym \(\displaystyle{ \left( X, \le\right) }\) przekrój Dedekinda, to para jego podzbiorów, która tworzy 'rozcięcie' zbioru \(\displaystyle{ X}\), dowolne 'rozcięcie' zbioru \(\displaystyle{ X}\). Wtedy pierwszy zbiór pary zbiorów nazywamy klasą dolną przekroju, drugi zbiór nazywamy klasą górną przekroju. Jest to dowolne 'rozcięcie' zbioru \(\displaystyle{ X}\). Formalnie, to taka para \(\displaystyle{ (A,B)}\) podzbiorów zbioru \(\displaystyle{ X}\), że: ich suma daje cały zbiór \(\displaystyle{ X}\), i każdy element zbioru \(\displaystyle{ A}\) jest ( :!: silnie) mniejszy od każdego elementu zbioru \(\displaystyle{ B}\), i zbiory \(\displaystyle{ A, B}\) są niepuste.

W zbiorze liniowo uporządkowanym \(\displaystyle{ (X, \le)}\) jeśli mamy przekrój Dedekinda \(\displaystyle{ (A,B)}\), to przekrój ten daje skok, gdy: (zbiór \(\displaystyle{ A}\) ma element największy i zbiór \(\displaystyle{ B}\) ma element najmniejszy). Na 'rozcięciu' tych dwóch zbiorów jest więc 'skok', zobacz ilustrację 8-)

Np. w zbiorze liczb całkowitych każdy przekrój daje skok, teraz jestem w stanie udowodnić znacznie więcej, co może jeszcze zaznaczę.


Przejdźmy do naszego dowodu.

Niech \(\displaystyle{ \left( X, \le\right) }\) będzie zbiorem liniowo uporządkowanym podobnym do \(\displaystyle{ \ZZ _{-} \cup \left\{ 0\right\}}\) do zbioru liczb całkowitych ujemnych wraz z zerem, a para zbiorów \(\displaystyle{ (A,B)}\) niech będzie przekrojem Dedekinda w \(\displaystyle{ \left( X, \le\right). }\) Wykażemy, że ten przekrój daje skok.

Dowód:

Ponieważ zbiór liniowo uporządkowany \(\displaystyle{ \left( X, \le\right) }\) jest podobny do \(\displaystyle{ \ZZ_- \cup \left\{ 0\right\}}\), więc również dla porządków odwrotnych mamy: \(\displaystyle{ \left( X, \le ^{-1}\right) \approx \left( \ZZ_- \cup \left\{ 0\right\} , \le _{\ZZ_-} ^{-1}\right) }\), a ten zbiór jest podobny do \(\displaystyle{ \NN}\).

Wystarczy bowiem określić podobieństwo \(\displaystyle{ f:\ZZ_- \cup \left\{0 \right\} \rightarrow \NN}\), jako:

\(\displaystyle{ f(x)=-x.}\)

Funkcja \(\displaystyle{ f}\) jest dobrze określona, gdyż jeśli \(\displaystyle{ x\in\ZZ_- \cup \left\{ 0\right\}}\), to \(\displaystyle{ x=-n}\), gdzie \(\displaystyle{ n\in\NN}\), i wtedy \(\displaystyle{ f(x)=-x=-\left( -n\right) =n\in\NN}\), a więc jest to liczba naturalna, i (z dowolności \(\displaystyle{ x}\)) otrzymujemy poprawność określenia funkcji \(\displaystyle{ f.}\)

Łatwo sprawdzić, że funkcja \(\displaystyle{ f}\) jest bijekcją. Pokażemy, że ta funkcja jest monotoniczna.

Niech \(\displaystyle{ x_1,x_2\in\ZZ_- \cup \left\{ 0\right\}}\), będą takie, że \(\displaystyle{ x_1 \le ^{-1} _{\ZZ_-} x_2}\) , wtedy \(\displaystyle{ x_1 \ge x_2}\), a zatem \(\displaystyle{ f(x_1)=-x_1 \le _{\NN} -x_2= f(x_2)}\). Wobec czego \(\displaystyle{ f}\) jest monotoniczna.

Ponieważ \(\displaystyle{ f}\) jest bijekcją monotoniczną pomiędzy dwoma zbiorami liniowo uporządkowanymi, to \(\displaystyle{ f}\) jest podobieństwem. Wobec czego zbiór \(\displaystyle{ \left( \ZZ_- \cup \left\{ 0\right\}, \le _{\ZZ-} ^{-1}\right) }\) jest podobny do zbioru \(\displaystyle{ \left( \NN, \le _{\NN}\right)}\). Mamy, że \(\displaystyle{ \left( X, \le ^{-1}\right) }\) jest podobny do \(\displaystyle{ \left( \ZZ_- \cup \left\{ 0\right\} , \le _{\ZZ_-} ^{-1}\right) }\) , wiec \(\displaystyle{ \left( X, \le ^{-1}\right) }\) jest podobny do \(\displaystyle{ (\NN, \le_{\NN}).}\) Istnieje więc podobieństwo między tymi dwoma zbiorami liniowo uporządkowanymi. Niech \(\displaystyle{ f:X \rightarrow \NN}\) będzie tym podobieństwem.

Ponieważ para zbiorów \(\displaystyle{ (A,B)}\) jest przekrojem w \(\displaystyle{ X}\), to \(\displaystyle{ A}\) jest niepustym podzbiorem zbioru \(\displaystyle{ X}\). Rozważmy obraz tego zbioru \(\displaystyle{ \stackrel {\rightarrow }{f}(A)\subset \NN.}\) Ponieważ \(\displaystyle{ A}\) jest zbiorem niepustym, to obraz \(\displaystyle{ \stackrel { \rightarrow }{f}(A)}\) również jest niepusty, Ponieważ ten obraz jest niepustym podzbiorem \(\displaystyle{ \NN}\), więc z zasady minimum ma liczbę najmniejszą \(\displaystyle{ n\in \stackrel { \rightarrow }{f}(A).}\) Ponieważ \(\displaystyle{ f}\) jako podobieństwo jest bijekcją, to niech \(\displaystyle{ x\in X}\) będzie takim elementem, że: \(\displaystyle{ f(x)=n}\). Pokażemy, że element \(\displaystyle{ x}\) jest najmniejszy w \(\displaystyle{ A}\), względem \(\displaystyle{ \le ^{-1}.}\) Mamy \(\displaystyle{ f(x)=n\in \stackrel { \rightarrow }{f} (A)}\), więc \(\displaystyle{ x\in\stackrel { \rightarrow }{f ^{-1} }\left( \stackrel { \rightarrow }{f} (A)\right)}\), a ponieważ \(\displaystyle{ f}\) jako podobieństwo jest bijekcją, więc przeciwobraz z obrazem się znosi, więc ten zbiór, którego tu \(\displaystyle{ x}\) jest elementem, jest równy \(\displaystyle{ A}\), więc \(\displaystyle{ x\in A}\).

Weźmy teraz \(\displaystyle{ a\in A}\), i pokażmy, że \(\displaystyle{ x \le ^{-1} a.}\) Mamy \(\displaystyle{ a\in A}\), więc \(\displaystyle{ m:=f(a)\in \stackrel{ \rightarrow }{f} (A)}\), ponieważ liczba naturalna \(\displaystyle{ n}\) jest najmniejsza w \(\displaystyle{ \stackrel { \rightarrow }{f} (A)}\), więc: \(\displaystyle{ f(x)=n \le m=f(a)}\), więc z własności podobieństwa otrzymujemy, ze \(\displaystyle{ x \le ^{-1} a}\), i \(\displaystyle{ x}\) jest najmniejszy w \(\displaystyle{ A}\) względem \(\displaystyle{ \le ^{-1}.}\)

A zatem, na podstawie charakteryzacji porządków odwrotnych, otrzymujemy, że \(\displaystyle{ x}\) jest największy w \(\displaystyle{ A}\) względem \(\displaystyle{ \le.}\)


Wykażemy podobnie, że zbiór \(\displaystyle{ B}\) ma element najmniejszy.

Wykażmy najpierw, ze zbiór \(\displaystyle{ B}\) jest ograniczony z dołu.

Niech \(\displaystyle{ a\in A \neq \left\{ \right\}.}\) Jeśli \(\displaystyle{ b\in B}\), mamy \(\displaystyle{ a\in A}\), ponieważ para zbiorów \(\displaystyle{ (A,B)}\) jest przekrojem Dedekinda, wiec każdy element \(\displaystyle{ A}\) jest mniejszy od każdego elementu \(\displaystyle{ B}\), więc \(\displaystyle{ a \le b}\), i (z dowolności \(\displaystyle{ b\in B}\) ) otrzymujemy, że \(\displaystyle{ a}\) jest ograniczeniem dolnym \(\displaystyle{ B}\), i zbiór \(\displaystyle{ B}\) jest ograniczony z dołu.

Wtedy \(\displaystyle{ a}\) jest ograniczeniem górnym \(\displaystyle{ B}\) względem porządku odwrotnego \(\displaystyle{ \le ^{-1} .}\) Pokażemy, że obraz \(\displaystyle{ \stackrel { \rightarrow }{f}(B)}\) jest również ograniczony z góry względem \(\displaystyle{ \le _{\NN}.}\) Mamy \(\displaystyle{ a\in X}\). Pokażemy, że element \(\displaystyle{ f(a)}\) jest ograniczeniem górnym obrazu \(\displaystyle{ \stackrel{ \rightarrow }{f}(B)}\).

Niech \(\displaystyle{ y\in\stackrel{ \rightarrow }{f} (B).}\) Wtedy \(\displaystyle{ y=f(b)}\), gdzie \(\displaystyle{ b\in B}\). Ponieważ \(\displaystyle{ a}\) jest ograniczeniem górnym \(\displaystyle{ B}\) względem \(\displaystyle{ \le ^{-1}}\), więc \(\displaystyle{ b \le ^{-1} a.}\) Wtedy, z monotoniczności podobieństwa \(\displaystyle{ f}\), dostajemy \(\displaystyle{ f(b)=y \le _\NN f(a)}\), a więc element \(\displaystyle{ f(a)}\) jest większy od \(\displaystyle{ y}\). Wobec dowolności \(\displaystyle{ y}\), wnioskujemy, że element \(\displaystyle{ f(a)}\) jest ograniczeniem górnym obrazu \(\displaystyle{ \stackrel{ \rightarrow }{f}(B)}\).

A więc ten obraz \(\displaystyle{ \stackrel { \rightarrow }{f}(B)}\) jest ograniczony z góry. Ale ten zbiór, ze swej natury, jest podzbiorem \(\displaystyle{ \NN}\)( ograniczonym od góry, i ponieważ zbiór \(\displaystyle{ B}\) jest niepusty, to jego obraz przez funkcję \(\displaystyle{ f}\) również jest niepusty), zatem, z zasady maksimum w zbiorze liczb naturalnych, otrzymujemy, że ten obraz \(\displaystyle{ \stackrel{ \rightarrow }{f}(B)}\) ma liczbę największą \(\displaystyle{ y\in\stackrel{ \rightarrow }{f}(B)}\). Ponieważ \(\displaystyle{ y\in\stackrel{ \rightarrow }{f}(B)}\), więc \(\displaystyle{ y=f(b)}\), gdzie \(\displaystyle{ b\in B}\). Pokażemy, że \(\displaystyle{ b}\) jest największy w \(\displaystyle{ B}\) względem \(\displaystyle{ \le ^{-1}}\).

Niech \(\displaystyle{ a\in B}\). Wtedy \(\displaystyle{ f(a)\in \stackrel{ \rightarrow }{f} (B).}\) Ponieważ \(\displaystyle{ y}\) jest największy w \(\displaystyle{ \stackrel { \rightarrow }{f} (B)}\), więc \(\displaystyle{ f(a) \le y=f(b)}\), więc z własności podobieństwa: \(\displaystyle{ a \le ^{-1} b}\), i otrzymujemy, że element \(\displaystyle{ b}\) jest największy w \(\displaystyle{ B}\) względem \(\displaystyle{ \le ^{-1}}\).

A zatem, na podstawie charakteryzacji porządków odwrotnych, otrzymujemy, że \(\displaystyle{ b}\) jest najmniejszy w \(\displaystyle{ B}\) względem \(\displaystyle{ \le .}\)

Ponieważ \(\displaystyle{ x}\) jest największy w \(\displaystyle{ A}\), względem \(\displaystyle{ \le }\), i \(\displaystyle{ b}\) jest elementem najmniejszym \(\displaystyle{ B}\) względem \(\displaystyle{ \le}\), więc przekrój \(\displaystyle{ (A,B)}\) daje skok.\(\displaystyle{ \square }\)


Możemy zatem podsumować twierdzeniem, że:

Jeśli \(\displaystyle{ \left( X, \le\right) }\) jest zbiorem liniowo uporządkowanym podobnym do pewnego zbioru \(\displaystyle{ C\subset \ZZ}\), to w dowolnym takim zbiorze podobnym, wtedy każdy przekrój daje skok.

Dowód:

Niech \(\displaystyle{ (A,B)}\) będzie przekrojem Dedekinda w \(\displaystyle{ \left( X, \le\right) }\). Wykażemy, że ten przekrój daje skok.

Jeśli \(\displaystyle{ \left( X, \le\right) }\) jest skończony, to przekrój \(\displaystyle{ (A,B)}\) daje skok, gdyż w zbiorze liniowo uporządkowanym skończonym każdy przekrój daje skok, jest to prosty fakt. A wiec przekrój \(\displaystyle{ (A,B)}\) daje skok.

jeśli \(\displaystyle{ X}\) jest nieskończony, a \(\displaystyle{ X}\) jest podobny do pewnego zbioru \(\displaystyle{ C\subset \ZZ}\), więc na mocy twierdzenia udowodnionego w poście powyżej możliwe są tylko trzy przypadki.

1. \(\displaystyle{ X \approx \NN}\)( rozumiemy \(\displaystyle{ \NN}\) z naturalnym porządkiem).
2. \(\displaystyle{ X \approx \ZZ_- \cup \left\{ 0\right\}.}\)
3. \(\displaystyle{ X \approx \ZZ.}\)

1.W pierwszym przypadku, ponieważ TUTAJ, W DRUGIM POŚC IE udowodniłem, że w zbiorze liniowo uporządkowanym podobnym do \(\displaystyle{ \NN}\) każdy przekrój daje skok, więc nasz przekrój \(\displaystyle{ (A,B)}\) daje skok.

2. Jeśli \(\displaystyle{ X}\) jest podobnym do zbioru liczb całkowitych ujemnych wraz z zerem, to na mocy przed chwilą udowodnionego faktu: przekrój \(\displaystyle{ (A,B)}\) daje skok.

3. Jeśli \(\displaystyle{ X}\) jest podobny do \(\displaystyle{ \ZZ}\), ponieważ w zbiorze podobnym do \(\displaystyle{ \ZZ}\) każdy przekrój daje skok, co nie jest bardzo trudnym faktem( mógłbym dać odnośnik do dowodu, ale trzeciego linku chyba nie da rady dać, ale to nie jest bardzo trudny fakt), więc przekrój \(\displaystyle{ (A,B)}\) daje skok. \(\displaystyle{ \square}\) 8-) :D
Jakub Gurak
Użytkownik
Użytkownik
Posty: 1392
Rejestracja: 20 lip 2012, o 21:19
Płeć: Mężczyzna
Lokalizacja: Rzeszów
Podziękował: 60 razy
Pomógł: 83 razy

Re: Zbiory liniowo uporządkowane skończone i nieskończone

Post autor: Jakub Gurak »

Wczoraj na dobranoc, udowodniłem sobie, że jeśli \(\displaystyle{ \left( X, \le\right) }\) jest skończonym zbiorem liniowo uporządkowanym, a podzbiór \(\displaystyle{ A}\) jest różną od całego zbioru \(\displaystyle{ X}\) resztą, to ta reszta jest w postaci: \(\displaystyle{ A=\left( x, \rightarrow \right) =\left\{ y\in X: \ y>x\right\} }\), gdzie \(\displaystyle{ x\in X}\), i gdzie mamy silną nierówność. Jest to prawo skończonych zbiorów liniowo uporządkowanych, gdyż wczoraj również łatwo wykazałem, że w (nieskończonym) zbiorze liniowo uporządkowanym \(\displaystyle{ \left( X, \le\right) }\) (a nawet w zbiorze dobrze uporządkowanym) może istnieć różna od całego zbioru \(\displaystyle{ X}\) reszta, która nie jest postaci \(\displaystyle{ \left( x, \rightarrow \right)}\), dla żadnego \(\displaystyle{ x\in X}\). Przedstawię teraz dowody tych ciekawych faktów.

Może najpierw przypomnę , że w zbiorze liniowo uporządkowanym \(\displaystyle{ \left( X, \le\right) }\) podzbiór \(\displaystyle{ A\subset X}\) nazywamy resztą, gdy dla każdego \(\displaystyle{ a\in A}\), dla każdego \(\displaystyle{ x\in X}\), takiego, że \(\displaystyle{ a<x}\), zachodzi: \(\displaystyle{ x\in A}\).

Czyli zbiór \(\displaystyle{ A}\) jest resztą, gdy z każdym swoim elementem zawiera również każdy element zbioru liniowo uporządkowanego \(\displaystyle{ X}\), który jest od niego większy. Jest to pojęcie symetryczne do pojęcia przedziału początkowego- jak przedział początkowy jest zbiorem 'od początku' do pewnego momentu zbioru liniowo uporządkowanego, tak reszta jest zbiorem od pewnego momentu 'do końca'.

Przejdźmy do naszych zadań.


Niech \(\displaystyle{ \left( X, \le\right) }\) będzie skończonym zbiorem liniowo uporządkowanym, a podzbiór \(\displaystyle{ A\subset X}\) niech będzie różną od całego zbioru \(\displaystyle{ X}\) resztą. Wykażemy, że \(\displaystyle{ A=\left( x, \rightarrow \right)= \left\{ y\in X: \ y>x\right\} }\), gdzie \(\displaystyle{ x\in X}\).

DOWÓD TEGO FAKTU:

Mamy \(\displaystyle{ A \neq X}\), więc zbiór \(\displaystyle{ X \setminus A =:A'}\) jest niepusty. Zauważmy, że również zbiór \(\displaystyle{ A'\subset X}\) jest zbiorem skończonym. A zatem taki podzbiór \(\displaystyle{ A'}\) zbioru liniowo uporządkowanego ma element największy \(\displaystyle{ a\in A'.}\) Wtedy \(\displaystyle{ a\in X}\), i wykażemy, że \(\displaystyle{ A=\left( a, \rightarrow \right).}\)
\(\displaystyle{ }\)
Niech \(\displaystyle{ b\in \left( a, \rightarrow \right).}\) Wtedy \(\displaystyle{ b\in X}\) i \(\displaystyle{ b>a}\). Przypuśćmy nie wprost, że \(\displaystyle{ b\not\in A}\), wtedy \(\displaystyle{ b\in X \setminus A=A'}\), a ponieważ element \(\displaystyle{ a}\) jest największy w \(\displaystyle{ A'}\), więc \(\displaystyle{ b\le a}\), a mamy \(\displaystyle{ a<b}\)-sprzeczność. Wobec czego musi być: \(\displaystyle{ b\in A}\), i \(\displaystyle{ \left( a, \rightarrow \right)\subset A.}\)

Aby pokazać inkluzję w drugą stronę, to niech \(\displaystyle{ b\in A}\). Wtedy \(\displaystyle{ b\in X}\). Przypuśćmy nie wprost, że \(\displaystyle{ b\not>a}\). Wtedy \(\displaystyle{ A\ni b \le a}\), a zbiór \(\displaystyle{ A}\) jest resztą, więc wnioskujemy, że \(\displaystyle{ a\in A}\), a mamy: \(\displaystyle{ a\in A'}\)-sprzeczność. Wobec czego musi być \(\displaystyle{ b>a}\), i i \(\displaystyle{ b\in \left( a, \rightarrow \right).}\)

A zatem \(\displaystyle{ \left( a, \rightarrow \right) =A}\), gdzie \(\displaystyle{ a\in X.\square}\) :D


Jednak w zbiorze liniowo uporządkowanym \(\displaystyle{ \left( X, \le\right) }\) (a nawet dobrze uporządkowanym) może istnieć różna od całego zbioru \(\displaystyle{ X}\) reszta, która nie jest postaci \(\displaystyle{ \left( x, \rightarrow \right)}\), dla żadnego \(\displaystyle{ x\in X.}\)

Aby to wykazać, rozważmy zbiór \(\displaystyle{ X=\NN \cup \left\{ T\right\}}\) , gdzie \(\displaystyle{ T\not\in \NN}\), zbiór liczb naturalnych z dodanym jednym elementem \(\displaystyle{ T}\) jako największym- jest to zbiór liniowo uporządkowany( a nawet dobrze uporządkowany, gdyż zbiór \(\displaystyle{ \NN}\) jest dobrze uporządkowany przez zwykły porządek).

Rozważmy zbiór jednoelementowy \(\displaystyle{ \left\{ T\right\}.}\) Jest on resztą, gdyż jest postaci \(\displaystyle{ \left\{ T\right\} =\left[ T, \rightarrow \right) =\left\{ y\in X: \ y \ge T\right\}}\), gdzie \(\displaystyle{ T\in X}\), gdyż \(\displaystyle{ T}\) jest największy w \(\displaystyle{ X}\), a więc zbiór \(\displaystyle{ \left\{ T\right\}}\) jest resztą. i oczywiście \(\displaystyle{ \left\{ T\right\} \neq X}\).

Nie jest on jednak postaci \(\displaystyle{ \left( x, \rightarrow \right)}\), dla żadnego \(\displaystyle{ x\in X}\). Jeśli bowiem \(\displaystyle{ x\in\NN}\), to:

\(\displaystyle{ \left( x, \rightarrow \right) =\left\{ x+1, x+2,\ldots \right\} \cup \left\{ T\right\} \neq \left\{ T\right\}.}\)

A jeśli \(\displaystyle{ x\not\in\NN}\), to pozostaje jedynie możliwość \(\displaystyle{ x=T.}\) A wtedy:

\(\displaystyle{ \left( T, \rightarrow \right)=\emptyset \neq \left\{ T\right\}. }\)

Wobec czego reszta \(\displaystyle{ \left\{ T\right\}}\) nie jest tej postaci\(\displaystyle{ .\square}\)


Na koniec odpowiemy na pytanie: Czy można podać przykład zbioru liniowo uporządkowanego takiego ( i oczywiście takiego, że istnieją przekroje Dedekinda w tym zbiorze liniowo uporządkowanym), i tak, aby każdy z tych przekrojów dawałby lukę?? :o

Przypomnę może, że w zbiorze liniowo uporządkowanym \(\displaystyle{ \left( X, \le \right)}\) przekrój \(\displaystyle{ \left( A,B\right)}\) daje lukę, gdy w \(\displaystyle{ A}\) nie ma elementu największego i w \(\displaystyle{ B}\) nie ma elementu najmniejszego . Na 'rozcięciu' tych dwóch zbiorów jest więc luka.

W zbiorze liniowo uporządkowanym ciągłym żaden przekrój nie daje luki, chyba również podobnie w zbiorze dobrze uporządkowanym, jak i w porządku odwrotnym do dobrego. Jednak, np. w zbiorze liczb wymiernych istnieją przekroje dające luki- liczby niewymierne. Zachodzi zatem pytanie: Czy można podać przykład zbioru liniowo uporządkowanego takiego, że( i takiego, że istnieją w nim przekroje Dedekinda), i tak, aby każdy z tych przekrojów Dedekinda dawałby lukę?? Okazuje się, że to jest niemożliwe, bo zawsze można skonstruować przekrój Dedekinda nie dający luki. Tzn. wykażemy, że:

Jeśli \(\displaystyle{ \left( X, \le\right) }\) jest zbiorem liniowo uporządkowanym, co najmniej dwuelementowym (w jednoelementowym zbiorze nie sposób utworzyć przekroju Dedekinda, podobnie w zbiorze pustym), to istnieje również przekrój Dedekinda nie dający luki.

Może jeszcze przypomnę pewną charakteryzacje przekrojów Dedekinda, gdyż z niej skorzystamy:

W zbiorze liniowo uporządkowanym \(\displaystyle{ \left( X, \le\right), }\) para podzbiorów \(\displaystyle{ \left( A,B\right)}\) jest przekrojem Dedekinda, dokładnie wtedy, gdy pierwszy zbiór pary \(\displaystyle{ A}\) jest niepustym i różnym od całego zbioru \(\displaystyle{ X}\) przedziałem początkowym, a drugi zbiór pary \(\displaystyle{ B}\) jest jego dopełnieniem do zbioru \(\displaystyle{ X}\).

Przejdźmy do naszego zadania.

Ponieważ zbiór \(\displaystyle{ X}\) ma co najmniej dwa elementy, wiec istnieją dwa różne elementy \(\displaystyle{ x,y\in X}\). Ponieważ zbiór \(\displaystyle{ X}\) jest uporządkowany liniowo, więc \(\displaystyle{ x<y}\) lub \(\displaystyle{ y<x.}\)

Jeśli \(\displaystyle{ x<y}\). To zbiór \(\displaystyle{ \overline{O(x)} =\left\{ z\in X: \ z \le x \right\}}\) jest przedziałem początkowym, bo zbiory w takiej postaci są zawsze przedziałami początkowymi, niepustym (bo \(\displaystyle{ x\in \overline{O(x)}}\)), i różnym od całego zbioru \(\displaystyle{ X}\) (bo \(\displaystyle{ y\in X}\) , a \(\displaystyle{ y\not\in \overline{O(x)}}\), bo \(\displaystyle{ y>x}\)), biorąc zatem parę zbiorów: \(\displaystyle{ \left( \overline{O(x)}, X \setminus \overline{ O(x)} \right)}\), w myśl przytoczonej charakteryzacji przekrojów Dedekinda otrzymujemy, że ta para zbiorów jest przekrojem Dedekinda.

I wtedy, łatwo się przekonać, że element \(\displaystyle{ x}\) jest największy w \(\displaystyle{ \overline {O(x)}}\), a więc ten przekrój nie daje luki.

Jeśli \(\displaystyle{ y<x}\), to rozumujemy w sposób symetryczny\(\displaystyle{ .\square}\) :D 8-)
ODPOWIEDZ