Zbiory liniowo uporządkowane gęste

[Jakub Gurak]

Zbór liniowo uporządkowany \(\displaystyle{ \left( X, \le \right) }\) nazywamy gęstym, gdy dla dowolnych elementów \(\displaystyle{ x,y\in X}\) takich, że \(\displaystyle{ x<y}\)( i \(\displaystyle{ x \neq y}\)) istnieje element \(\displaystyle{ z\in X}\), taki, że \(\displaystyle{ x<z<y.}\)

Czyli gdy pomiędzy dwoma dowolnymi elementami jest trzeci element pomiędzy nimi.

Najbardziej typowym przykładem zbioru liniowo uporządkowanego gęstego jest zbiór liczb wymiernych \(\displaystyle{ \QQ}\) z naturalnym porządkiem. Pokażemy, że jest on gęsty. Niech \(\displaystyle{ x,y\in\QQ}\) będą takie, ze \(\displaystyle{ x<y.}\) Rozważmy \(\displaystyle{ z= \frac{x+y}{2} }\), ponieważ suma dwóch liczb wymiernych jest liczbą wymierną, stąd \(\displaystyle{ z\in\QQ.}\) Ponieważ \(\displaystyle{ x<y}\), więc \(\displaystyle{ x<\frac{x+y}{2}<y}\). Wskazaliśmy zatem element \(\displaystyle{ z\in\QQ}\) taki, że \(\displaystyle{ x<z<y}\). Wobec dowolności wyboru \(\displaystyle{ x,y}\) dowiedliśmy, że \(\displaystyle{ \left( \QQ, \le \right) }\) jest gęsty.

Kolejny przykład: W zbiorze funkcji \(\displaystyle{ \NN^\NN}\) rozważmy relację porządku:

\(\displaystyle{ f_1\sqsubseteq f_2 \Longleftrightarrow \hbox{ dla każdego } n\in\NN: f_1(n) \le f_2(n). }\)

Porządek ten nie jest gęsty. Aby się o tym przekonać, to niech \(\displaystyle{ f_1:\NN \rightarrow \NN}\) będzie funkcją stałą, stale równą \(\displaystyle{ 0}\), a \(\displaystyle{ f_2:\NN \rightarrow \NN}\) będzie określona jako
\(\displaystyle{ f_2(x)= \begin{cases} 1, \hbox{ dla } x=0, \\ 0, \hbox{ dla }x>0. \end{cases} }\)

Z definicji funkcji oraz porządku \(\displaystyle{ \sqsubseteq}\) wynika, że \(\displaystyle{ f_1\sqsubseteq f_2.}\)

(Intuicyjnie funkcja \(\displaystyle{ f_2}\) różni się od \(\displaystyle{ f_1}\) tylko tym, że na zerze przyjmuje wartość \(\displaystyle{ 1}\), a więc jest to minimalny wzrost, stąd nie da się pomiędzy nimi włożyć funkcji pośredniej, ale to tylko intuicje, które nie zastępują dowodu).

Niech \(\displaystyle{ g\in\NN^\NN}\) będzie dowolną funkcją taką, że \(\displaystyle{ f_1\sqsubseteq g\sqsubseteq f_2}\) ( nierówność jest słaba- wtedy takie funkcje \(\displaystyle{ g}\) na pewno istnieją, np.\(\displaystyle{ g=f_1}\) ). Wtedy, z definicji porządku \(\displaystyle{ \sqsubseteq}\) dla każdego \(\displaystyle{ x\in\NN \setminus \left\{ 0\right\}}\) mamy:

\(\displaystyle{ 0=f_1(x) \le g(x) \le f_2(x)=0,}\)

a więc \(\displaystyle{ g(x)=0}\), dla \(\displaystyle{ x \neq 0.}\) Dla \(\displaystyle{ x=0}\), mamy:

\(\displaystyle{ 0=f_1(0) \le g(0) \le f_2(0)=1.}\)

Ponieważ \(\displaystyle{ g:\NN \rightarrow \NN}\), więc \(\displaystyle{ g(0)\in\NN}\), więc są tylko dwie możliwości \(\displaystyle{ g(0)=0}\) lub \(\displaystyle{ g(0)=1.}\) Jeśli \(\displaystyle{ g(0)=0}\), to wtedy \(\displaystyle{ g}\) jest stale równa \(\displaystyle{ 0}\), skąd \(\displaystyle{ g=f_1.}\) Jeśli \(\displaystyle{ g(0)=1}\), wtedy łato sprawdzić, że podobnie funkcje \(\displaystyle{ g}\) i \(\displaystyle{ f_2}\) na każdym argumencie przyjmują te same wartości, skąd \(\displaystyle{ g=f_2.}\) Wynika stąd, że nie istnieje funkcja \(\displaystyle{ g}\) różna od \(\displaystyle{ f_1,f_2}\), taka, że \(\displaystyle{ f_1\sqsubseteq g\sqsubseteq f_2}\) (czyli pomiędzy \(\displaystyle{ f_1,f_2}\) nie można włożyć funkcji pośredniej), a więc ten porządek nie jest gęsty. \(\displaystyle{ \square}\)

Mamy twierdzenie, które mówi, że gęstość jest przenoszona przez podobieństwo, tzn.

Jeśli \(\displaystyle{ \left( X, \le _{X}\right) ,\left( Y ,\le _{Y} \right) }\) są zbiorami liniowo uporządkowanymi podobnymi, porządek na \(\displaystyle{ X}\) jest gęsty, to również \(\displaystyle{ \left( Y, \le _{Y} \right) }\) jest gęsty.

Dowód:

Niech \(\displaystyle{ f:X \rightarrow Y}\) będzie podobieństwem. Aby pokazać, że \(\displaystyle{ \left( Y, \le _{Y} \right) }\) jest gęsty, weźmy dowolne elementy \(\displaystyle{ y_1,y_2\in Y}\) dla których \(\displaystyle{ y_1<y_2}\). Skoro \(\displaystyle{ f}\) jest podobieństwem, więc jest bijekcją, wiec jest 'na', więc \(\displaystyle{ y_1=f(x_1)}\) dla pewnego \(\displaystyle{ x_1\in X}\), oraz \(\displaystyle{ y_2=f(x_2)}\) dla pewnego \(\displaystyle{ x_2\in X.}\) Skoro \(\displaystyle{ f(x _{1} )<f(x_{2} )}\), to \(\displaystyle{ x _{1} \le x _{2}}\), oczywiście \(\displaystyle{ x_1 \neq x_2}\)( w przeciwnym razie otrzymalibyśmy \(\displaystyle{ y_1=y_2}\)), więc \(\displaystyle{ x_1<x_2}\). Ponieważ \(\displaystyle{ \left( X, \le\right)}\) jest gęsty, więc istnieje element \(\displaystyle{ x_3 \in X}\) spełniający \(\displaystyle{ x _{1}<x_3<x_2.}\) Ustalmy go. Wtedy \(\displaystyle{ y_1=f(x_1) \le f (x_{3}) \le f(x _{2} )=y_2.}\) Ponieważ \(\displaystyle{ f}\) jest też różnowartościowa, a \(\displaystyle{ x_1 \neq x _{3} \neq x _{2}}\), więc \(\displaystyle{ f\left( x_1\right) \neq f\left( x_3\right)=:y_3 \neq y_2.}\) Wynika stąd, że \(\displaystyle{ y_1<y_3<y_2}\), a więc element \(\displaystyle{ y_3}\) leży pomiędzy \(\displaystyle{ y_1}\) a \(\displaystyle{ y_2}\). Wobec dowolności wyboru takich elementów, wnioskujemy, że \(\displaystyle{ \left( Y, \le _{Y} \right) }\) jest gęsty. \(\displaystyle{ \square}\)

Zdefiniujemy teraz przekroje Dedekinda w zbiorze liniowo uporządkowanym.

Niech \(\displaystyle{ \left( X, \le \right) }\) będzie zbiorem liniowo uporządkowanym. Przekrojem Dedekinda w \(\displaystyle{ \left( X, \le \right) }\) nazywamy każdą parę \(\displaystyle{ (A,B)}\) podzbiorów zbioru \(\displaystyle{ X}\), taką, że:

1. \(\displaystyle{ A \cup B=X.}\)
2. dla kążdego \(\displaystyle{ a\in A}\), i każdego \(\displaystyle{ b\in B}\) mamy \(\displaystyle{ a<b.}\)
3. \(\displaystyle{ A \neq \emptyset, B \neq \emptyset.}\)

Intuicyjnie jest to dowolne rozcięcie zbioru liniowo uporządkowanego \(\displaystyle{ X}\) na dwie części. Zbiór \(\displaystyle{ A}\) nazywamy klasą dolną przekroju, zbiór \(\displaystyle{ B}\) nazywamy klasą górną przekroju.

W zbiorze liniowo uporządkowanym mówimy, że przekrój Dedekinda \(\displaystyle{ (A,B)}\) daje skok, gdy \(\displaystyle{ A}\) ma element największy i \(\displaystyle{ B}\) ma element najmniejszy.

Na rozcięciu tych dwóch zbiorów jest więc "skok"- zobacz ilustrację .

Twierdzenie:

Zbiór liniowo uporządkowany jest gęsty, wtedy i tylko wtedy, gdy żaden przekrój nie daje skoku.

Dowód:

Niech \(\displaystyle{ \left( X, \le \right) }\) będzie zbiorem liniowo uporządkowanym.

Przypuśćmy, że w \(\displaystyle{ \left( X, \le \right) }\) istnieje przekrój Dedekinda \(\displaystyle{ (A,B)}\) który daje skok. Zatem zbiór \(\displaystyle{ A}\) ma element największy \(\displaystyle{ a\in A}\), \(\displaystyle{ B}\) ma element najmniejszy \(\displaystyle{ b\in B}\). Ponieważ \(\displaystyle{ a\in A,b\in B}\) więc z definicji przekroju Dedekinda mamy \(\displaystyle{ a<b.}\) Weżmy dowolny element \(\displaystyle{ x\in X}\), taki, że \(\displaystyle{ a \le x \le b.}\) Element \(\displaystyle{ x}\) należy do \(\displaystyle{ X=A \cup B}\), więc musi należeć do któregoś zbioru przekroju. Jeśli \(\displaystyle{ x\in A}\), a element \(\displaystyle{ a}\) jest największy w \(\displaystyle{ A}\), skąd \(\displaystyle{ x\le a}\), mamy też \(\displaystyle{ a \le x}\), skąd \(\displaystyle{ x=a}\). W przeciwnym przypadku \(\displaystyle{ x\in B}\), ponieważ \(\displaystyle{ b}\) jest najmniejszy w \(\displaystyle{ B}\), więc \(\displaystyle{ b \le x}\), mamy \(\displaystyle{ x \le b}\), skąd \(\displaystyle{ x=b}\). Pokazaliśmy zatem, że jeżeli element \(\displaystyle{ x}\) leży pomiędzy \(\displaystyle{ a}\) a \(\displaystyle{ b}\), to \(\displaystyle{ x=a }\) lub \(\displaystyle{ x=b.}\) Wynika stąd, że nie istnieje element różny od \(\displaystyle{ a,b}\) leżący pomiędzy \(\displaystyle{ a,b}\), a więc ten porządek nie jest gęsty.

Przypuśćmy, że w \(\displaystyle{ \left( X, \le \right) }\) żaden przekrój nie daje skoku. Pokażemy, ze ten porządek jest gęsty. Weźmy dowolne elementy \(\displaystyle{ a,b\in X}\), takie, że \(\displaystyle{ a<b.}\) Rozważmy zbiór \(\displaystyle{ A=\left\{ x\in X\Bigl| \ \ x \le a\right\}}\) oraz zbiór \(\displaystyle{ B=X\setminus A.}\) Pokażemy teraz, że para zbiorów \(\displaystyle{ (A,B)}\) tworzy przekrój Dedekinda w \(\displaystyle{ X}\). Łatwo sprawdzić, że \(\displaystyle{ A\cup B=X}\). Aby sprawdzić punkt drugi, to niech \(\displaystyle{ x\in A, y\in B}\). Ponieważ zbiory \(\displaystyle{ A,B}\) są rozłączne, to \(\displaystyle{ x \neq y. }\) Wtedy \(\displaystyle{ x \le a}\), i \(\displaystyle{ y \in X\setminus A}\), a więc \(\displaystyle{ y\not\le a}\), a ponieważ \(\displaystyle{ \le}\) jest porządkiem liniowym, więc \(\displaystyle{ a\le y}\). Mamy \(\displaystyle{ x \le a}\), skąd \(\displaystyle{ x \le y}\), więc \(\displaystyle{ x<y}\). A więc spełniony jest też punkt drugi. Mamy również oczywiście \(\displaystyle{ A \neq \left\{ \right\}}\), i \(\displaystyle{ B \neq \left\{ \right\}}\), gdyż \(\displaystyle{ b\in B}\), gdyż \(\displaystyle{ b\not\in A}\), gdyż \(\displaystyle{ b \not\le a}\), gdyż \(\displaystyle{ a<b}\). Zatem spełniony jest też punkt trzeci, wobec czego para \(\displaystyle{ (A,B)}\) tworzy przekrój Dedekinda w \(\displaystyle{ X}\). Mamy też \(\displaystyle{ b\in B}\)(bo \(\displaystyle{ a<b}\)), oraz \(\displaystyle{ a}\) jest elementem największym \(\displaystyle{ A}\). Ponieważ ten przekrój \(\displaystyle{ (A,B)}\) nie może dawać skoku, to w zbiorze \(\displaystyle{ B}\) nie może istnieć element najmniejszy. Zatem w szczególności \(\displaystyle{ b}\) nie jest elementem najmniejszym \(\displaystyle{ B}\), a więc istnieje element \(\displaystyle{ c\in B}\), taki że \(\displaystyle{ b\not\le c}\), i ponieważ jesteśmy na zbiorze liniowo uporządkowanym, więc \(\displaystyle{ c<b}\). Ponieważ \(\displaystyle{ c\in B,a\in A}\), więc z drugiej własności przekroju Dedekinda otrzymujemy, że \(\displaystyle{ a<c.}\) Wskazaliśmy zatem element \(\displaystyle{ c\in X}\), dla którego \(\displaystyle{ a<c<b.}\) Wobec dowolności wyboru \(\displaystyle{ a,b}\) dowiedliśmy, że zbiór liniowo uporządkowany \(\displaystyle{ \left( X, \le\right)}\) jest gęsty. \(\displaystyle{ \square}\)

[Dasio11]

Kolejny przykład: W zbiorze funkcji \(\displaystyle{ \NN^\NN}\) rozważmy relację porządku:

\(\displaystyle{ f_1\sqsubseteq f_2 \Longleftrightarrow \hbox{ dla każdego } n\in\NN: f_1(n) \le f_2(n). }\)

Porządek ten nie jest gęsty.

Ten porządek nie może być gęsty z definicji, bo nie jest liniowy.

[Jakub Gurak]

Wczoraj udowodniłem, że na iloczynie kartezjańskim dwóch zbiorów liniowo uporządkowanych gęstych porządek leksykograficzny jest gęsty. Zauważyłem też że suma porządkowa dwóch zbiorów liniowo uporządkowanych gęstych nie musi być gęsta.

Oto dowód:

Kontrprzykład dla sumy porządkowej: \(\displaystyle{ A=[0,1]\cap \QQ}\) z naturalnym porządkiem, oraz \(\displaystyle{ B=[2,3]\cap \QQ}\) z naturalnym porządkiem
Są to zbiory liniowo uporządkowane gęste. Są gęste, gdyż są złożone z liczb wymiernych, a pomiędzy dwoma liczbami wymiernymi jest trzecia liczba wymierna. Są to zbiory rozłączne, zatem suma porządkowa jest liniowym porządkiem. Nie jest jednak gęsta- pomiędzy \(\displaystyle{ 1}\) a \(\displaystyle{ 2}\) nie ma wartości pośredniej. A więc suma porządkowa nie jest gęsta. \(\displaystyle{ \square}\)

Wykażemy teraz, zgodnie z zapowiedzią, że na iloczynie kartezjańskim dwóch zbiorów liniowo uporządkowanych gęstych porządek leksykograficzny jest gęsty.

Niech \(\displaystyle{ \left( X, \le _{X}\right) ; \left( Y, \le _{Y} \right) }\) będą zbiorami liniowo uporządkowanymi gęstymi. Wtedy \(\displaystyle{ X\times Y}\), z porządkiem leksykograficznym (oznaczmy go jako \(\displaystyle{ \le _{l} }\)) jest zbiorem liniowo uporządkowanym. Aby wykazać, że jest gęsty, niech \(\displaystyle{ \left( x _{1},y _{1} \right); \left( x _{2},y _{2} \right) \in X\times Y}\), będą takie, że \(\displaystyle{ \left( x _{1},y _{1} \right)< _{l} \left( x _{2},y _{2} \right).}\) Rozważmy teraz dwa przypadki:

1.\(\displaystyle{ x_1 \neq x_2}\). Wtedy z definicji porządku leksykograficznego dostajemy\(\displaystyle{ x_1 <_X x_2}\). Ponieważ \(\displaystyle{ \le _X}\) jest porządkiem gęstym na \(\displaystyle{ X}\), więc istnieje element \(\displaystyle{ x_3\in X}\), spełniający \(\displaystyle{ x_1<x_3<x_2}\). A zatem również \(\displaystyle{ (x_1,y_1)<_l (x_3,y_1)<_l (x_2,y_2)}\). A zatem pomiędzy parami \(\displaystyle{ (x_1,y_1);(x_2,y_2)}\) jest para pośrednia.

2. W pozostałym przypadku \(\displaystyle{ x_1=x_2,}\) oznaczmy tą wartość jako \(\displaystyle{ x}\). Wtedy \(\displaystyle{ y_1 <_Y y_2}\). Ponieważ porządek liniowy \(\displaystyle{ \le _{Y}}\) jest gęsty, więc istnieje element \(\displaystyle{ y_3\in Y}\), taki, że \(\displaystyle{ y_1<y_3<y_2}\). Wtedy również \(\displaystyle{ (x=x_1,y_1)< _{l} (x,y_3)<_l (x=x_2,y_2)}\), a więc również pomiędzy parami \(\displaystyle{ (x_1,y_1);(x_2,y_2)}\) jest para pośrednia. Zatem \(\displaystyle{ \left( X\times Y, \le _{l}\right)}\) jest gęsty. \(\displaystyle{ \square}\)

Również porządek odwrotny do gęstego jest gesty.

Szkic dowodu: Niech \(\displaystyle{ \left( X, \le \right)}\) będzie zbiorem liniowo uporządkowanym gęstym. Porządek odwrotny na \(\displaystyle{ X}\) oznaczmy jako \(\displaystyle{ \ge}\). Jest on oczywiście liniowy. Aby wykazać, że jest gesty, to niech \(\displaystyle{ a,b\in X}\) będą takie, że \(\displaystyle{ a \ge b}\). Wtedy \(\displaystyle{ b \le a}\) ( uwaga, w tym momencie nie możemy odwracać nierówności danego porządku, formalnie rozważamy inny porządek- odwrotny), ponieważ porządek \(\displaystyle{ \le}\) jest gęsty, więc otrzymujemy element \(\displaystyle{ c\in X}\), taki, że \(\displaystyle{ b \le c \le a.}\) Wtedy \(\displaystyle{ a \ge c \ge b}\), a więc pomiędzy \(\displaystyle{ a,b}\) jest element pośredni między nimi względem \(\displaystyle{ \ge }\). \(\displaystyle{ \square}\)

[Jakub Gurak]

Wczoraj udowodniłem ( z pomocą literatury wpadłem na ten problem), że jeśli \(\displaystyle{ \left( X, \le \right) }\) jest zbiorem liniowo uporządkowanym, to poniższe warunki są równoważne:

(1)\(\displaystyle{ (X, \le )}\) jest zbiorem liniowo uporządkowanym gęstym,
(2) w \(\displaystyle{ X}\) żaden element nie ma następnika,
(3) w \(\displaystyle{ X}\) żaden element nie ma poprzednika.

Przypomnę, że jeśli \(\displaystyle{ \left( X, \le\right) }\) jest zbiorem liniowo uporządkowanym, to element \(\displaystyle{ y\in X}\) jest następnikiem elementu \(\displaystyle{ x\in X}\), jeśli \(\displaystyle{ x<y}\), i gdy każdy element silnie większy od \(\displaystyle{ x}\) jest większy lub równy od \(\displaystyle{ y}\) (od tego następnika), czyli \(\displaystyle{ y}\) jest elementem najmniejszym zbioru wszystkich elementów zbioru \(\displaystyle{ X}\) silnie większych od \(\displaystyle{ x}\). Podobnie element \(\displaystyle{ y}\) jest poprzednikiem elementu \(\displaystyle{ x}\), gdy \(\displaystyle{ y}\) jest elementem największym w zbiorze wszystkich elementów zbioru \(\displaystyle{ X}\) silnie mniejszych od \(\displaystyle{ x}\). Przedstawię teraz dowód:

Niech \(\displaystyle{ \left( X, \le\right)}\) będzie zbiorem liniowo uporządkowanym.

Zauważmy, że jeśli \(\displaystyle{ X=\emptyset}\), to równoważność zachodzi:
\(\displaystyle{ X=\emptyset}\), jest gęsty (co łatwo sprawdzić),dla każdego \(\displaystyle{ x\in\emptyset}\): \(\displaystyle{ x}\) nie ma następnika (2), i dla każdego \(\displaystyle{ x\in\emptyset}\): \(\displaystyle{ x}\) nie ma poprzednika (3).
Wszystkie te trzy zdania są prawdziwe, a więc są równoważne. Załóżmy dalej, że \(\displaystyle{ X}\) jest zbiorem niepustym.

Jeśli w \(\displaystyle{ X}\) pewien element \(\displaystyle{ x\in X}\) ma następnik \(\displaystyle{ y\in X}\), to \(\displaystyle{ y>x}\), i rozważmy dwa zbiory:

\(\displaystyle{ X_1=\left\{ z\in X: \ z \le x\right\} ; X_2=\left\{ z\in X: z \ge y \right\} .}\)

Pokażemy, że para zbiorów \(\displaystyle{ (X_1,X_2)}\) tworzy przekrój Dedekinda. Oczywiście \(\displaystyle{ X_1 \neq \left\{ \right\} , X_2 \neq \left\{ \right\}}\) (\(\displaystyle{ x\in X_1, y\in X_2}\)), jeśli \(\displaystyle{ a\in X_1, b\in X_2}\), to \(\displaystyle{ a \le x<y \le b}\), a więc \(\displaystyle{ a<b}\)

Nie całkiem oczywisty dowód rzeczy oczywistej:    

jeśli w zbiorze uporządkowanym, \(\displaystyle{ a \le b<c}\), to \(\displaystyle{ a<c}\). Oczywiście z przechodniości porządku \(\displaystyle{ a \le c}\), ale chodzi o to żeby wykluczyć równość \(\displaystyle{ a=c.}\) Gdyby \(\displaystyle{ a=c}\), to \(\displaystyle{ c \le a}\)( ze zwrotności), a więc \(\displaystyle{ c \le a \le b}\), więc \(\displaystyle{ c \le b }\) i \(\displaystyle{ b<c}\), a zatem \(\displaystyle{ c \le b}\) i \(\displaystyle{ b \le c}\), a zatem z antysymetrii \(\displaystyle{ c=b}\), ale \(\displaystyle{ b<c}\), więc \(\displaystyle{ b \neq c}\)- sprzeczność. A zatem \(\displaystyle{ a \neq c}\), i \(\displaystyle{ a \le c}\), więc \(\displaystyle{ a<c.}\)

Również, w zbiorze uporządkowanym, jeśli \(\displaystyle{ a<b \le c}\), to \(\displaystyle{ a<c}\). Oczywiście \(\displaystyle{ a \le c}\) z przechodniości porządku. Wykluczmy równość \(\displaystyle{ a=c}\). Gdyby byłoby \(\displaystyle{ a=c}\), to \(\displaystyle{ c=a<b}\), czyli \(\displaystyle{ c<b}\), a \(\displaystyle{ c \ge b}\)- sprzeczność. Zatem \(\displaystyle{ a \neq c}\) i \(\displaystyle{ a \le c}\), więc \(\displaystyle{ a<c.}\)

A zatem z tych udowodnionych 'oczywistości' wynika, że \(\displaystyle{ a<b}\) ( czyli otrzymujemy, że każdy element \(\displaystyle{ X_1}\) jest mniejszy od każdego elementu \(\displaystyle{ X_2}\)). Pozostaje pokazać, że \(\displaystyle{ X_1 \cup X_2=X}\). W tym celu pokażmy, że \(\displaystyle{ X \setminus X_1\subset X_2.}\) Niech \(\displaystyle{ z\in X \setminus X_1.}\) Wtedy \(\displaystyle{ z\not\in X_1}\), \(\displaystyle{ z\in X}\), a zatem z definicji zbioru \(\displaystyle{ X_1}\): \(\displaystyle{ z\not \le x}\), ponieważ \(\displaystyle{ (X, \le )}\) jest zbiorem uporządkowanym liniowo, więc konieczne jest aby \(\displaystyle{ x<z}\), ponieważ \(\displaystyle{ y}\) jest następnikiem \(\displaystyle{ x}\), więc \(\displaystyle{ y \le z}\), a stąd \(\displaystyle{ z\in X_2}\). A zatem (z dowolności z) otrzymujemy: \(\displaystyle{ X \setminus X_1 \subset X_2}\), czyli dopełnienie \(\displaystyle{ X'_1=X \setminus X_1 \subset X_2}\), a zatem \(\displaystyle{ X_1 \cup X_2=X}\)( gdyż \(\displaystyle{ X_2\supset X'_1}\)). A zatem para zbiorów \(\displaystyle{ (X_1,X_2)}\) tworzy przekrój Dedekinda w \(\displaystyle{ X}\), i w \(\displaystyle{ X_1}\) element \(\displaystyle{ x}\) jest największy, w \(\displaystyle{ X_2}\) element \(\displaystyle{ y}\) jest najmniejszy, a zatem przekrój Dedekinda \(\displaystyle{ (X_1,X_2)}\) daje skok, a więc zbiór liniowo uporządkowany \(\displaystyle{ \left( X, \le\right)}\) nie jest gęsty.

Załóżmy teraz, że w zbiorze liniowo uporządkowanym \(\displaystyle{ \left( X, \le \right) }\) żaden element nie ma następnika, i pokażmy, że ten zbiór liniowo uporządkowany \(\displaystyle{ \left( X, \le\right)}\) jest gęsty. Niech para zbiorów \(\displaystyle{ (A,B)}\) będzie przekrojem Dedekinda w \(\displaystyle{ X}\). Przypuśćmy nie wprost, że ten przekrój daje skok. Wtedy w \(\displaystyle{ A}\) jest element największy \(\displaystyle{ a\in A}\), w \(\displaystyle{ B}\) jest element najmniejszy \(\displaystyle{ b\in B}\). Pokażemy teraz, że element \(\displaystyle{ b}\) jest następnikiem elementu \(\displaystyle{ a}\).

Ponieważ para zbiorów \(\displaystyle{ (A,B)}\) jest przekrojem Dedekinda, więc każdy element \(\displaystyle{ A}\) jest mniejszy od każdego elementu \(\displaystyle{ B}\), mamy \(\displaystyle{ a\in A, b\in B}\), więc \(\displaystyle{ a<b}\). Weźmy teraz \(\displaystyle{ c\in X}\), taki, że \(\displaystyle{ c>a}\), i pokażmy, że \(\displaystyle{ c \ge b}\). Mamy \(\displaystyle{ c\not\in A}\) (gdyby \(\displaystyle{ c\in A}\), a \(\displaystyle{ a}\) jest największy w \(\displaystyle{ A}\), więc \(\displaystyle{ a \ge c}\), a \(\displaystyle{ a<c}\)- sprzeczność). Ponieważ para zbiorów \(\displaystyle{ (A,B)}\) jest przekrojem Dedekinda, to \(\displaystyle{ A \cup B=X}\), mamy \(\displaystyle{ c\in X=A \cup B, c\not\in A}\), więc pozostaje możliwość \(\displaystyle{ c\in B}\), ponieważ \(\displaystyle{ b}\) jest najmniejszy w \(\displaystyle{ B}\), więc \(\displaystyle{ b \le c}\). A zatem, z definicji następnika, otrzymujemy, że element \(\displaystyle{ b}\) jest następnikiem elementu \(\displaystyle{ a}\). Mamy \(\displaystyle{ a,b\in X}\), a w \(\displaystyle{ X}\) żaden element nie ma następnika- sprzeczność. A zatem w \(\displaystyle{ \left( X, \le \right) }\) żaden przekrój nie daje skoku, i zbiór liniowo uporządkowany \(\displaystyle{ \left( X, \le \right) }\) jest gęsty\(\displaystyle{ . \square}\)

A zatem (1) \(\displaystyle{ \Leftrightarrow}\) (2).

Jeśli w \(\displaystyle{ X}\) pewien element \(\displaystyle{ x}\) ma poprzednik \(\displaystyle{ y}\), to rozważmy zbiory: \(\displaystyle{ X_1=\left\{ z\in X: z \le y\right\} , X_2=\left\{ z\in X: z \ge x \right\} .}\) Oczywiście zbiory \(\displaystyle{ X_1,X_2}\) są niepuste, oraz każdy element \(\displaystyle{ X_1}\) jest mniejszy od każdego elementu \(\displaystyle{ X_2}\). Pozostaje pokazać, aby pokazać, że para zbiorów \(\displaystyle{ (X_1,X_2)}\) tworzy przekrój Dedekinda, więc pozostaje pokazać, że \(\displaystyle{ X_1 \cup X_2=X.}\) W tym celu pokażmy, że \(\displaystyle{ X \setminus X_2\subset X_1.}\) Niech \(\displaystyle{ z\in X \setminus X_2}\). Wtedy \(\displaystyle{ z\in X, z\not\in X_2}\). Z ostatniego, i definicji zbioru \(\displaystyle{ X_2}\) otrzymujemy \(\displaystyle{ z\not \ge x.}\) Ponieważ \(\displaystyle{ \left( X, \le\right)}\) jest zbiorem liniowo uporządkowanym, więc musi być \(\displaystyle{ z<x}\), ponieważ \(\displaystyle{ y}\) jest poprzednikiem \(\displaystyle{ x}\), więc \(\displaystyle{ z \le y}\), a zatem \(\displaystyle{ z\in X_1}\). A zatem \(\displaystyle{ X'_2=X \setminus X_2\subset X_1}\). A zatem \(\displaystyle{ X_1 \cup X_2=X}\), gdyż \(\displaystyle{ X_1\supset X'_2}\), tak więc \(\displaystyle{ X_1 \cup X_2=X}\). A zatem para zbiorów \(\displaystyle{ (X_1,X_2)}\) jest przekrojem Dedekinda w \(\displaystyle{ X}\), oraz zbiór \(\displaystyle{ X_1}\) ma element największy (\(\displaystyle{ y}\)), i zbiór \(\displaystyle{ X_2}\) ma element najmniejszy (\(\displaystyle{ x}\)). A więc przekrój \(\displaystyle{ (X_1,X_2)}\) daje skok. A więc zbiór liniowo uporządkowany \(\displaystyle{ \left( X, \le\right) }\) nie jest gęsty.

Jeśli w \(\displaystyle{ \left( X, \le \right) }\) żaden element nie ma poprzednika, to \(\displaystyle{ \left( X, \le \right)}\) jest gęsty. Aby to pokazać, to niech para zbiorów \(\displaystyle{ (A,B)}\) będzie przekrojem Dedekinda w \(\displaystyle{ X}\). Przypuśćmy, nie wprost, że ten przekrój daje skok. Wtedy w \(\displaystyle{ A}\) jest element największy \(\displaystyle{ a\in A}\), w \(\displaystyle{ B}\) jest element najmniejszy \(\displaystyle{ b\in B}\). Pokażemy teraz, że \(\displaystyle{ a}\) jest poprzednikiem elementu \(\displaystyle{ b}\). Mamy \(\displaystyle{ a,b\in X}\). Ponieważ para zbiorów \(\displaystyle{ (A,B)}\) jest przekrojem Dedekinda w \(\displaystyle{ X}\), więc każdy element \(\displaystyle{ A}\) jest mniejszy od każdego elementu \(\displaystyle{ B}\), a mamy \(\displaystyle{ a\in A, b\in B}\), więc \(\displaystyle{ a<b}\). Weźmy teraz \(\displaystyle{ c\in X}\), taki, że \(\displaystyle{ c<b}\), i pokażmy, że \(\displaystyle{ c \le a}\). Mamy \(\displaystyle{ c\not\in B}\)( gdyby \(\displaystyle{ c\in B}\), ponieważ \(\displaystyle{ b}\) jest najmniejszy w \(\displaystyle{ B}\), więc \(\displaystyle{ b \le c}\), a \(\displaystyle{ c<b}\)- sprzeczność), zatem \(\displaystyle{ c\not\in B}\), ale \(\displaystyle{ c\in X=A \cup B}\)( para zbiorów \(\displaystyle{ (A,B)}\) jest przekrojem Dedekinda w \(\displaystyle{ X}\)), zatem \(\displaystyle{ c\in A \cup B}\) , \(\displaystyle{ c\not\in B}\), więc \(\displaystyle{ c\in A}\). A ponieważ \(\displaystyle{ a}\) jest największy w \(\displaystyle{ A}\), więc \(\displaystyle{ a \ge c}\). A zatem ( z definicji poprzednika) otrzymujemy, że \(\displaystyle{ a}\) jest poprzednikiem \(\displaystyle{ b}\). A \(\displaystyle{ a,b\in X}\), i w \(\displaystyle{ X}\) żaden element nie ma poprzednika- sprzeczność. A więc w \(\displaystyle{ \left( X, \le\right)}\) żaden przekrój nie daje skoku, więc \(\displaystyle{ \left( X, \le \right) }\) jest gęsty. \(\displaystyle{ \square}\)

A zatem (3) \(\displaystyle{ \Leftrightarrow}\) (1). \(\displaystyle{ \square}\)

Jeszcze jeden dowód ostatniej zależności, na podstawię literatury:    

Załóżmy, że w \(\displaystyle{ X}\) żaden element nie ma poprzednika. I pokażmy, że \(\displaystyle{ \left( X, \le\right) }\) jest gęsty. W tym celu weźmy \(\displaystyle{ x,y\in X,}\) takie, że \(\displaystyle{ x<y.}\) Rozważmy zbiór: \(\displaystyle{ A=\left\{ z\in X: z<y\right\}}\). Taki zbiór \(\displaystyle{ A}\) nie ma elementu największego, gdyż gdyby miał to byłby poprzednikiem \(\displaystyle{ y}\), a \(\displaystyle{ y\in X}\), i w \(\displaystyle{ X}\) żaden element nie ma poprzednika- sprzeczność. Mamy \(\displaystyle{ x\in A}\); w szczególności \(\displaystyle{ x}\) nie jest największy w \(\displaystyle{ A}\), (i \(\displaystyle{ x\in A}\)) ,więc wnioskujemy, że dla pewnego \(\displaystyle{ z\in A}\) (\(\displaystyle{ A \neq \left\{ \right\}}\) ): \(\displaystyle{ x\not \ge z}\) ( w przeciwnym razie \(\displaystyle{ x}\) byłby największy w \(\displaystyle{ A}\) ). Mamy \(\displaystyle{ x,z\in X}\), ponieważ \(\displaystyle{ X}\) jest liniowo uporządkowany, więc konieczne jest aby \(\displaystyle{ x<z}\). Ponieważ \(\displaystyle{ z\in A}\), więc z definicji tego zbioru \(\displaystyle{ z<y}\). A więc \(\displaystyle{ x<z<y.}\) Wskazaliśmy zatem element \(\displaystyle{ z}\) leżący pomiędzy \(\displaystyle{ x}\) i \(\displaystyle{ y}\). Wobec dowolności wyboru \(\displaystyle{ x,y}\) udowodniliśmy, że zbiór liniowo uporządkowany \(\displaystyle{ \left( X, \le\right) }\)jest gęsty.

Lubię ścisłą matematykę, ścisłe rozumowania.