Przekrój łańcucha liniowych porządków

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

Przekrój łańcucha liniowych porządków

Post autor: Jakub Gurak »

Udowodniłem w czwartek, że jeśli mamy łańcuch liniowych porządków względem rozszerzenia przez dodanie elementów mniejszych, to jego przekrój jest liniowym porządkiem, i jest to infimum tego łańcucha liniowych porządków. Przedwczoraj udowodniłem- w sumie już na dwa sposoby, podobny fakt dla rozszerzenia przez dodanie elementów większych. Dla tych dowodów, sam wprowadziłem nowe pojęcie- nazwałem je uzupełnieniem liniowego porządku do porządku rozszerzającego, to się tu przydało. Przedstawię teraz dowody tych ciekawych faktów.

Wprowadźmy najpierw to pojęcie uzupełnienia liniowego porządku.

Niech \(\displaystyle{ (X,R);( Y,S)}\) będą zbiorami liniowo uporządkowanymi, takimi, że zbiór liniowo uporządkowany \(\displaystyle{ (X,R)}\) rozszerza zbiór \(\displaystyle{ (Y,S).}\) Przez uzupełnienie porządku \(\displaystyle{ S}\) do zbioru liniowo uporządkowanego (\(\displaystyle{ X,R)}\) rozumiemy porządek rozszerzający \(\displaystyle{ R}\) zawężony do dopełnienia \(\displaystyle{ Y}\), tzn. \(\displaystyle{ S':= R_{|(Y'=X \setminus Y)}=R \cap \left[ \left( X \setminus Y\right) \times \left( X \setminus Y\right) \right]}\) i oznaczamy jako \(\displaystyle{ S^{'}.}\) Oznaczenie to nie prowadzi do nieporozumień, gdyż dla liniowych porządków nie będziemy w ogóle rozważać dopełnień jako relacji, nie będzie takiej najmniejszej potrzeby, więc takie oznaczenie jest bezpieczne. A, ponieważ tutaj \(\displaystyle{ (X,R)}\) jest zbiorem liniowo uporzadkowanym, to uzupelnienie \(\displaystyle{ S'}\) jako podzbiór zbioru liniowo uporządkowanego jest liniowo uporządkowany na \(\displaystyle{ Y'.}\) Zauważmy, że zawsze porządek \(\displaystyle{ R}\) rozszerza uzupełnienie \(\displaystyle{ S'.}\)

Zauważmy, że jeśli \(\displaystyle{ (X,R);(Y,S)}\) są zbiorami liniowo uporządkowanymi, takimi, że \(\displaystyle{ X}\) rozszerza \(\displaystyle{ Y}\), to \(\displaystyle{ (S')'=S}\)- uzupełnienie uzupełnienia porządku \(\displaystyle{ S}\) jest porządkiem \(\displaystyle{ S.}\)

Aby to udowodnić przypomnijmy prosty fakt, że jeśli \(\displaystyle{ (X, \le _X); (Y, \le _Y)}\) są zbiorami liniowo uporządkowanymi, takimi, że porządek \(\displaystyle{ \le _Y}\) rozszerza porządek \(\displaystyle{ \le _{X}}\) , to porządek rozszerzający \(\displaystyle{ \le _{Y}}\) zawężony do zbioru \(\displaystyle{ X}\) jest równy temu porządkowi \(\displaystyle{ \le _X}\) na zbiorze \(\displaystyle{ X}\). Jest to prosty fakt.

W takim razie łatwo możemy teraz udowodnić, że jeśli \(\displaystyle{ (X,R);(Y,S)}\) są zbiorami liniowo uporządkowanymi, takimi, że zbiór \(\displaystyle{ (X,R)}\) rozszerza zbiór \(\displaystyle{ (Y,S)}\), to \(\displaystyle{ (S')'=S}\)- uzupełnienie uzupełnienia porządku \(\displaystyle{ S}\) jest porządkiem \(\displaystyle{ S}\).

Dowód:

\(\displaystyle{ (S')'=R_{|\left( Y'=X \setminus Y=X_{S^{'}}\right) ' } = R_{|Y}=S,}\)

gdzie ostania równość wynika z faktu wspomnianego powyżej. Dowód jest zakończony.

Przypomnijmy jeszcze, że jeśli \(\displaystyle{ \mathbb{B}}\) jest łańcuchem (względem relacji rozszerzania) liniowych porządków na podzbiorach zbioru \(\displaystyle{ X}\), to \(\displaystyle{ \bigcap\mathbb{B}}\) jest liniowym porządkiem w przekroju zbiorów na których są określone te liniowe porządki, co udowodniłem TUTAJ, W DRUGIM POŚCIE.

Przejdźmy do pierwszego z głównych problemów.

Niech \(\displaystyle{ X}\) będzie zbiorem.

Rozważmy rodzinę liniowych porządków \(\displaystyle{ \mathbb{A}:}\)

\(\displaystyle{ \mathbb{A}=\left\{ R: R \hbox { jest liniowym porządkiem na pewnym zbiorze } Y\subset X\right\},}\)

wraz z porządkiem \(\displaystyle{ \succcurlyeq }\),( tzn. dla dowolnego \(\displaystyle{ R\in\mathbb{A}}\), przez \(\displaystyle{ X_R}\) oznaczamy zbiór na którym jest określony liniowy porządek \(\displaystyle{ R}\)) :

\(\displaystyle{ R\succcurlyeq S \Longleftrightarrow S\hbox { rozszerza } R \hbox{ i } \left( x\in X_R, y\in X_S \setminus X_R \rightarrow y(S)x \right). }\)

tzn. liniowy porządek jest większy od danego, gdy jest jego rozszerzeniem, i to przez dodanie elementów mniejszych od wszystkich zastanych.

Jak wykazałem, dowód można znaleźć w pierwszym poście z tego linku jest to relacja porządku, a więc \(\displaystyle{ (\mathbb{A},\succcurlyeq )}\) jest zbiorem uporządkowanym. Niech zatem \(\displaystyle{ \left\{ \right\} \neq \mathbb{B}}\) bedzie niepustym łańcuchem liniowych porządków względem \(\displaystyle{ \succcurlyeq}\). Wykażemy, że przekrój \(\displaystyle{ \bigcap\mathbb{B}}\) jest liniowym porządkiem, i \(\displaystyle{ \bigcap\mathbb{B}= \bigwedge\limits_{ \succcurlyeq}\ B}\)- jest to infimum rodziny tych liniowych porządków.

Podajmy najpierw dwa lematy.

Lemat 1.

Jeśli mamy trzy zbiory liniowo uporządkowane- równoważnie zbiór \(\displaystyle{ X}\), i trzy podzbiory liniowo uporządkowane \(\displaystyle{ (X_0,R_0);(X_1,R_1);(X_2,R_2) }\) (jest to podejście równoważne, bo nawet gdy zbiór \(\displaystyle{ X}\) nie jest ustalony, to mając trzy zbiory liniowo uporządkowane \(\displaystyle{ X_1,X_2, X_3}\), wtedy zbiór \(\displaystyle{ X=X_1 \cup X_2 \cup X_3}\) jest wyznaczony jednoznacznie, i te trzy zbiory liniowo uporządkowane są oczywiście podzbiorami zbioru \(\displaystyle{ X}\), co uzasadnia implikacje w prawo, a implikacja w drugą stronę jest oczywista, wobec czego jest to sformułowanie równoważne), i jeśli \(\displaystyle{ R_2 \succcurlyeq R_1 \succcurlyeq R}\) ( wtedy \(\displaystyle{ R}\) rozszerza \(\displaystyle{ R_1}\) i \(\displaystyle{ R_1}\) rozszerza \(\displaystyle{ R_2}\), więc również \(\displaystyle{ R}\) rozszerza \(\displaystyle{ R_2}\), i \(\displaystyle{ X_0\supset X_2}\) oraz \(\displaystyle{ X_0\supset X_1}\), możemy zatem rozważać uzupełnienia \(\displaystyle{ R'_1}\) i \(\displaystyle{ R'_2}\) w zbiorze liniowo uporządkowanym \(\displaystyle{ (X_0,R)}\) ) i pokażemy, że dla tych uzupełnień, mamy: \(\displaystyle{ R'_1\sqsubseteq R'_2}\), gdzie \(\displaystyle{ \sqsubseteq}\) oznacza relację rozszerzenia przez dodanie elementów większych, tzn. liniowy porządek \(\displaystyle{ R}\) jest mniejszy od liniowego porządku \(\displaystyle{ S}\), gdy \(\displaystyle{ S}\) jest rozszerzeniem \(\displaystyle{ R}\), i to przez dodanie elementów większych od wszystkich zastanych. I pokażemy, że \(\displaystyle{ R'_1\sqsubseteq R'_2.}\)

Dowód lematu:

Ponieważ \(\displaystyle{ R_2\succcurlyeq R_1}\), więc z definicji porządku \(\displaystyle{ \succcurlyeq}\)- rozszerzenia przez dodanie elementów mniejszych wnioskujemy natychmiast, że \(\displaystyle{ R_1}\) rozszerza \(\displaystyle{ R_2}\), czyli \(\displaystyle{ R_1\supset R_2}\). Ponieważ porządek rozszerzający musi być określony na nadzbiorze zbioru na którym jest określony porządek dany (prosty fakt), więc \(\displaystyle{ X_1\supset X_2}\), zatem dla dopełnień (do zbioru \(\displaystyle{ X_0}\)) otrzymujemy: \(\displaystyle{ X'_1\subset X'_2}\), a zatem \(\displaystyle{ X'_1 \times X'_1 \subset X'_2 \times X'_2}\), więc:

\(\displaystyle{ R' _{1}=R _{|X' _{1} } = R \cap \left( X' _{1} \times X' _{1} \right) \subset R \cap \left( X' _{2} \times X' _{2} \right)=R _{|X' _{2} } = R' _{2},}\)

A zatem ponieważ \(\displaystyle{ R'_2}\) jest nadzbiorem \(\displaystyle{ R'_1}\), więc porządek \(\displaystyle{ R'_2}\) rozszerza porządek \(\displaystyle{ R'_1.}\)

Pozostaje pokazać punkt drugi- że to jest rozszerzenie przez dodanie elementów większych od wszystkich zastanych.

W tym celu weźmy \(\displaystyle{ x\in X _{R'_1}=X_0 \setminus X_1=X '_{1}}\), i weźmy \(\displaystyle{ y\in X _{R'_2}=X_0 \setminus X_2=X '_{2}}\), takie, że \(\displaystyle{ y\not\in X _{R'_1}=X '_{1}}\), i pokażmy, że \(\displaystyle{ x\left( R'_2 \right)y.}\)

Mamy \(\displaystyle{ y\not\in X'_1}\), więc \(\displaystyle{ y\in X_1.}\) Mamy \(\displaystyle{ x\in X_0, x\not\in X_1, y\in X_1.}\) Ponieważ \(\displaystyle{ R_1\succcurlyeq R}\), więc z definicji \(\displaystyle{ \succcurlyeq}\) możemy wnioskować, że \(\displaystyle{ x(R)y.}\) Wiemy, że porządek \(\displaystyle{ R_1}\) rozszerza porządek \(\displaystyle{ R_2}\), więc ponieważ porządek rozszerzający musi być określony na nadzbiorze zbioru na którym jest określony porządek dany, więc: \(\displaystyle{ X_1\supset X_2}\), więc dla dopełnień \(\displaystyle{ X'_1 \subset X'_2.}\) Ponieważ \(\displaystyle{ x\in X'_1}\), więc \(\displaystyle{ x\in X'_2.}\) Mamy również \(\displaystyle{ y\in X'_2}\), i nierówność \(\displaystyle{ x(R)y}\), więc \(\displaystyle{ x \left( R _{|X'_{2} }\right) y}\), a ponieważ uzupełnienie \(\displaystyle{ R'_2}\) jest zdefiniowane jako \(\displaystyle{ R}\) zawężone do \(\displaystyle{ X'_
2}\)
, więc \(\displaystyle{ x( R'_2)y.}\) Spełniony zatem jest punkt drugi w definicji \(\displaystyle{ \sqsubseteq}\), a więc \(\displaystyle{ R'_1\sqsubseteq R'_2.\square}\)

Podajmy jeszcze drugi symetryczny lemat.

Lemat 2.

Jeśli mamy trzy zbiory liniowo uporządkowane \(\displaystyle{ (X_0,R_0); (X_1,R_1);(X_2,R_2)}\) (równoważnie- gdy mamy zbiór i trzy podzbiory liniowo uporządkowane), i jeśli \(\displaystyle{ R_2 \sqsubseteq R_1\sqsubseteq R_0}\), (wtedy \(\displaystyle{ R_0}\) rozszerza zarówno \(\displaystyle{ R_1}\), jak i \(\displaystyle{ R_2}\), możemy zatem rozważać uzupełnienia \(\displaystyle{ R'_1}\) oraz \(\displaystyle{ R'_2}\) ) i wtedy \(\displaystyle{ R'_1\succcurlyeq R'_2.}\)

Nim to udowodnimy, udowodnijmy, że jeśli \(\displaystyle{ (X,R); (Y,S)}\) są zbiorami liniowo uporządkowanymi, tak, że \(\displaystyle{ X}\) rozszerza \(\displaystyle{ Y}\), to \(\displaystyle{ \left( S' \right) ^{-1} =\left( S^{-1}\right)' _{R^{-1}}}\)- porządek odwrotny do uzupełnienia porządku jest uzupełnieniem porządku odwrotnego do porządku odwrotnego \(\displaystyle{ R^{-1}}\) w całym nadzbiorze \(\displaystyle{ X.}\)
PROSTY DOWÓD:    
Przypomnijmy, że mamy prawo dla \(\displaystyle{ R, S\in\mathbb{A}}\), mamy:

\(\displaystyle{ R \succcurlyeq S \Longleftrightarrow R^{-1}\sqsubseteq S^{-1}}\),

co oznacza, że jeśli pomiędzy liniowymi porządkami mamy rozszerzenie przez dodanie elementów mniejszych to na odpowiadających porządkach odwrotnych mamy rozszerzenie przez dodanie elementów większych ( i na odwrót). Dowód tej intuicyjnie oczywistej zależności przedstawiłem TUTAJ, i my z tej zależności będziemy korzystać.

Dowód drugiego lematu:

Mamy \(\displaystyle{ R_2\sqsubseteq R_1\sqsubseteq R_0}\), więc na mocy faktu powyżej, dla porządków odwrotnych, otrzymujemy:

\(\displaystyle{ R_2 ^{-1} \succcurlyeq R_1 ^{-1} \succcurlyeq R_0 ^{-1}. }\)

Wiemy, że \(\displaystyle{ R_0}\) rozszerza \(\displaystyle{ R_1}\), jak i \(\displaystyle{ R_2}\), innymi słowy \(\displaystyle{ R_0\supset R_1,R_2}\), więc również \(\displaystyle{ R_1^{-1}, R_2^{-1}\subset R_0^{-1}}\), a zatem zbiór liniowo uporządkowany \(\displaystyle{ ( X_0, R_0^{-1})}\) rozszerza zarówno \(\displaystyle{ R_1^{-1} }\)jak i \(\displaystyle{ R_2^{-1}}\). Możemy zatem rozważyć uzupełnienia tych porządków do \(\displaystyle{ \left( X_0, R_0^{-1}\right) .}\) Stosując lemat 1 do nich otrzymujemy: \(\displaystyle{ \left( R_1 ^{-1} \right)' \sqsubseteq \left( R_2 ^{-1} \right)'}\) , ponieważ uzupełnienie porządku odwrotnego jest porządkiem odwrotnym do uzupełnienia porządku danego, więc \(\displaystyle{ \left( R'_1\right)^{-1} \sqsubseteq \left( R'_2\right) ^{-1}}\), więc zgodnie tym prawem wyrażającym związek rozszerzenia przez dodanie elementów większych a rozszerzeniem przez dodanie elementów mniejszych na odpowiadających porżadkach odwrotnych, więc otrzymujemy: \(\displaystyle{ (R'_1)\succcurlyeq R'_2. \square}\) :lol:


Przejdźmy do głównego problemu. Wykażemy, że:

Jeśli \(\displaystyle{ X}\) jest zbiorem, a \(\displaystyle{ \mathbb{A}}\) rodziną wszystkich liniowych porządków na pewnych podzbiorach zbioru \(\displaystyle{ X}\) wraz z porządkiem \(\displaystyle{ \succcurlyeq}\) ( czyli jest to rozszerzenie przez dodanie elementów mniejszych), i jeśli \(\displaystyle{ \mathbb{B}}\) jest niepustym łańcuchem liniowych porządków względem \(\displaystyle{ \succcurlyeq}\), to wykażemy, że przekrój \(\displaystyle{ \bigcap\mathbb{B}}\) jest liniowym porządkiem, i \(\displaystyle{ \bigcap\mathbb{B}=\bigwedge \limits_{\succcurlyeq}\mathbb{B}}\)- jest to infimum tej rodziny liniowych porządków.

Dowód:

Wykażmy, że \(\displaystyle{ \mathbb{B}}\) jest łańcuchem względem relacji rozszerzania. To jednak jest proste. Jeśli \(\displaystyle{ R_1,R_2\in\mathbb{B}}\), ponieważ \(\displaystyle{ \mathbb{B}}\) jest łańcuchem względem \(\displaystyle{ \succcurlyeq}\), więc \(\displaystyle{ R_1\succcurlyeq R_2}\) lub \(\displaystyle{ R_2\succcurlyeq R_1}\). A stąd możemy wnioskować, że porżądek \(\displaystyle{ R_2}\) rozszerza porządek \(\displaystyle{ R_1}\) lub porządek \(\displaystyle{ R_1}\) rozszerza \(\displaystyle{ R_2.}\) A zatem rodzina \(\displaystyle{ \mathbb{B}}\) jest łańcuchem również względem relacji rozszerzania.

Ponieważ \(\displaystyle{ \mathbb{B}}\) jest łańcuchem liniowych porządków względem relacji rozszerzania, to przekrój \(\displaystyle{ \bigcap\mathbb{B}}\) jest liniowym porządkiem w \(\displaystyle{ X_0:= \bigcap_{R\in\mathbb{B}} X_R}\), czyli w przekroju zbiorów na których są określone te liniowe porządki. A zatem \(\displaystyle{ \bigcap\mathbb{B}\in\mathbb{A}.}\)

Zauważmy, że \(\displaystyle{ \bigcup\mathbb{B}}\) jest liniowym porządkiem i jest to supremum tej rodziny liniowych porządków, na mocy dowodu z
pierwszego linku (w pierwszym poście). A zatem dla dowolnego liniowego porządku \(\displaystyle{ R\in \mathbb{B}}\) mamy, że \(\displaystyle{ \bigcup\mathbb{B}}\) rozszerza \(\displaystyle{ R}\). Możemy zatem rozważać uzupełnienia liniowych porządków \(\displaystyle{ R\in\mathbb{B}}\) do porządku liniowego \(\displaystyle{ \bigcup\mathbb{B}. }\) Rozważmy zatem rodzinę uzupełnień porządków z łańcucha \(\displaystyle{ \mathbb{B}.}\)

\(\displaystyle{ \mathbb{B}_2=\left\{ R' | \ R\in\mathbb{B} \right\}.}\)

Rozważamy uzupełnienia do zbioru liniowo uporządkowanego \(\displaystyle{ (X _{ \bigcup\mathbb{B}}, \bigcup\mathbb{B}).}\) Mamy \(\displaystyle{ \mathbb{B}_2\subset \mathbb{A}. }\) Wykażemy, że rodzina \(\displaystyle{ \mathbb{B}_2}\) jest łańcuchem względem \(\displaystyle{ \sqsubseteq.}\)

Niech \(\displaystyle{ S_1,S_2\in\mathbb{B}_2.}\) Wtedy \(\displaystyle{ S_1=R'_1}\), gdzie \(\displaystyle{ R_1\in\mathbb{B};}\) i \(\displaystyle{ S_2=R'_2}\), gdzie \(\displaystyle{ R_2\in\mathbb{B}}\). Ponieważ \(\displaystyle{ R_1, R_2\in\mathbb{B}}\), a \(\displaystyle{ \mathbb{B}}\) jest łańcuchem względem \(\displaystyle{ \succcurlyeq}\), więc \(\displaystyle{ R_1\succcurlyeq R_2}\) lub \(\displaystyle{ R_2\succcurlyeq R_1}\).

Jeśli \(\displaystyle{ R_1\succcurlyeq R_2}\), to na mocy lematu 1, otrzymujemy:

\(\displaystyle{ S_2=R'_2\sqsubseteq R'_1=S_1}\), czyli \(\displaystyle{ S_2\sqsubseteq S_1.}\)

Jeśli \(\displaystyle{ R_2\succcurlyeq R_1}\), to symetrycznie ten przypadek prowadzi do relacji: \(\displaystyle{ S_1\sqsubseteq S_2.}\)

A zatem rodzina \(\displaystyle{ \mathbb{B}_2}\) jest łańcuchem względem \(\displaystyle{ \sqsubseteq.}\)

Ponieważ łańcuch \(\displaystyle{ \mathbb{B}}\) jest niepusty, to \(\displaystyle{ \mathbb{B}_2}\) również. Ponieważ rodzina \(\displaystyle{ \mathbb{B}_2}\) jest niepustym łańcuchem względem \(\displaystyle{ \sqsubseteq}\), to \(\displaystyle{ S:=\bigcup \mathbb{B}_2}\) jest liniowym porządkiem, i \(\displaystyle{ \bigcup\mathbb{B}_2 = \bigvee\limits_{\sqsubseteq}\mathbb{B}_2}\)- jest to supremum tej rodziny liniowych porządków, na mocy faktu w pierwszym podanym linku, w pierwszym poście.

Wykażemy teraz, że \(\displaystyle{ S'=(\bigcup\mathbb{B} ) _{|X_0}= S= \bigcap\mathbb{B}}\), czyli uzupełnienie \(\displaystyle{ S}\), jak i przekrój \(\displaystyle{ \bigcap\mathbb{B}}\) są równe sumie \(\displaystyle{ \bigcup\mathbb{B}}\) zawężonej do \(\displaystyle{ X_0= \bigcap_{R\in\mathbb{B}} X_R}\) , czyli do tego przekroju zbiorów na których są określone te liniowe porządki z \(\displaystyle{ \mathbb{B}}\).

Ponieważ \(\displaystyle{ \bigcup\mathbb{B}\supset \bigcap\mathbb{B}}\), to porządek \(\displaystyle{ \bigcup\mathbb{B}}\) rozszerza porządek \(\displaystyle{ \bigcap\mathbb{B}}\), a ponieważ \(\displaystyle{ \bigcap\mathbb{B}}\) jest liniowym porżądkiem w \(\displaystyle{ X_0}\), to suma \(\displaystyle{ \bigcup\mathbb{B}}\) zawężona do \(\displaystyle{ X_0}\), a tam jest określony porządek \(\displaystyle{ \bigcap\mathbb{B}}\), który jest rozszerzany przez \(\displaystyle{ \bigcup\mathbb{B}}\) , więc ta suma zawężona do \(\displaystyle{ X_0}\) jest równa temu porządkowi danemu, czyli \(\displaystyle{ \bigcap\mathbb{B}.}\) Czyli \(\displaystyle{ \left( \bigcup\mathbb{B}\right) _{|X_0}= \bigcap\mathbb{B}.}\).

Wykażemy teraz, że \(\displaystyle{ \left( \bigcup\mathbb{B}\right) _{|X_0}=S'}\). W tym celu, zauważmy, że jeśli \(\displaystyle{ R\in\mathbb{B}_2}\), to \(\displaystyle{ \bigcup\mathbb{B}}\) rozszerza \(\displaystyle{ R}\) (bo uzupełniamy do \(\displaystyle{ \bigcup\mathbb{B}}\), więc suma \(\displaystyle{ \bigcup\mathbb{B}}\) musi rozszerzać uzupełnienie), czyli \(\displaystyle{ \bigcup\mathbb{B} \supset R}\), zatem dla dowolnego \(\displaystyle{ R\in\mathbb{B}_2}\), mamy: \(\displaystyle{ R\subset \bigcup\mathbb{B}}\), więc również \(\displaystyle{ \bigcup \mathbb{B}_2 =\bigcup_{R\in\mathbb{B}_2} R \subset \bigcup\mathbb{B}}\) , czyli \(\displaystyle{ \bigcup\mathbb{B}_2\subset \bigcup \mathbb{B},}\) i ponieważ zarówno \(\displaystyle{ \bigcup \mathbb{B},}\) jak i \(\displaystyle{ \bigcup \mathbb{B}_2=S}\) są liniowymi porządkami, więc \(\displaystyle{ \bigcup \mathbb{B}}\) rozszerza \(\displaystyle{ \bigcup\mathbb{B}_2=S}\), więc \(\displaystyle{ \bigcup \mathbb{B}}\) rozszerza również uzupełnienie \(\displaystyle{ S'.}\)

Zauważmy, że jeśli \(\displaystyle{ R_2\in \mathbb{B}_2}\), to \(\displaystyle{ R_2=R'}\), gdzie \(\displaystyle{ R\in\mathbb{B}}\), wtedy \(\displaystyle{ X _{R_{2}}= (X_R)'= \left( X_ {\bigcup \mathbb{B}} \right) \setminus X_R }\), i \(\displaystyle{ S= \bigcup\mathbb{B}_2}\) jest liniowym porządkiem w \(\displaystyle{ X_2:= \bigcup_{R_2\in\mathbb{B}_2} X _{R_{2}}= \bigcup_{R\in\mathbb{B}} (X_R)'= \left( \bigcap_{R\in\mathbb{B}} X_R\right) '= X'_0.}\)

Ponieważ \(\displaystyle{ S}\) jest liniowym porządkiem w \(\displaystyle{ X'_0}\), to jego uzupełnienie \(\displaystyle{ S'}\) jest liniowym porządkiem w \(\displaystyle{ \left( X'_0\right)'=X_0.}\) Ponieważ \(\displaystyle{ \bigcup\mathbb{B}}\) rozszerza \(\displaystyle{ S'}\), więc \(\displaystyle{ \bigcup \mathbb{B}}\) zawężona do \(\displaystyle{ X_0}\) jest równa uzupełnieniu \(\displaystyle{ S'.}\) Czyli \(\displaystyle{ \left( \bigcup\mathbb{B}\right) _{|X_0}=S'.}\)

Mamy zatem \(\displaystyle{ S'= \bigcap\mathbb{B}}\), i \(\displaystyle{ S}\) jest supremum rodziny \(\displaystyle{ \mathbb{B}_2}\) względem \(\displaystyle{ \sqsubseteq}\). Mamy natomiast pokazać, że \(\displaystyle{ S' = \bigcap\mathbb{B}}\) jest infimum rodziny \(\displaystyle{ \mathbb{B}}\) względem \(\displaystyle{ \succcurlyeq.}\)

Nim to udowodnimy wykażemy teraz lemat 3.

Lemat 3:

Jeśli \(\displaystyle{ R\in\mathbb{A}}\), to \(\displaystyle{ R}\) jest ograniczeniem dolnym \(\displaystyle{ \mathbb{B}}\) względem \(\displaystyle{ \succcurlyeq}\), dokładnie wtedy, gdy uzupełnienie \(\displaystyle{ R'}\) jest ograniczeniem górnym \(\displaystyle{ \mathbb{B}_2}\) względem \(\displaystyle{ \sqsubseteq}\).
Dowód:    
Wykażemy teraz, że \(\displaystyle{ S'= \bigcap\mathbb{B}}\) jest infimum rodziny \(\displaystyle{ \mathbb{B}}\) względem \(\displaystyle{ \succcurlyeq.}\)

Mamy, że przekrój \(\displaystyle{ \bigcap\mathbb{B}}\) jest liniowym porządkiem w \(\displaystyle{ X_0}\), a zatem \(\displaystyle{ S'= \bigcap\mathbb{B}\in\mathbb{A}.}\)

Wykażemy, że \(\displaystyle{ \bigcap\mathbb{B}}\) jest ograniczeniem dolnym dla rodziny \(\displaystyle{ \mathbb{B}.}\) Niech \(\displaystyle{ R\in\mathbb{B}.}\) Wtedy \(\displaystyle{ R'\in\mathbb{B}_2}\), ponieważ \(\displaystyle{ S}\) jest supremum \(\displaystyle{ \mathbb{B}_2}\) względem \(\displaystyle{ \sqsubseteq}\), więc \(\displaystyle{ S}\) jest ograniczeniem górnym \(\displaystyle{ \mathbb{B}_2}\), więc jest większe lub równe od każdego elementu \(\displaystyle{ \mathbb{B}_2}\), więc \(\displaystyle{ R' \sqsubseteq S\sqsubseteq \bigcup\mathbb{B}}\), więc na mocy lematu 2, otrzymujemy: \(\displaystyle{ \bigcap\mathbb{B} =S'\succcurlyeq (R')'=R}\), czyli \(\displaystyle{ \bigcap \mathbb{B}\succcurlyeq R}\), i przekrój \(\displaystyle{ \bigcap \mathbb{B}}\) jest ograniczeniem dolnym \(\displaystyle{ \mathbb{B}.}\)

Pozostaje pokazać, że jest to największe ograniczenie dolne dla \(\displaystyle{ \mathbb{B}. }\)

Niech \(\displaystyle{ R}\) będzie ograniczeniem dolnym \(\displaystyle{ \mathbb{B}}\) względem \(\displaystyle{ \succcurlyeq}\). Wtedy, na mocy lematu 3 powyżej, uzupełnienie \(\displaystyle{ R'}\) jest ograniczeniem górnym \(\displaystyle{ \mathbb{B}_2}\) względem \(\displaystyle{ \sqsubseteq}\). Ponieważ porządek \(\displaystyle{ S}\) jest supremum \(\displaystyle{ \mathbb{B}_2}\), względem \(\displaystyle{ \sqsubseteq}\), czyli \(\displaystyle{ S}\) jest najmniejszym ograniczeniem górnym \(\displaystyle{ \mathbb{B}_2}\) względem \(\displaystyle{ \sqsubseteq}\), więc \(\displaystyle{ S\sqsubseteq R'\sqsubseteq \bigcup\mathbb{B}}\), stosując zatem lemat 2, otrzymujemy:

\(\displaystyle{ R=(R')' \succcurlyeq S'= \bigcap\mathbb{B}}\),

otrzymujemy zatem, że \(\displaystyle{ S'= \bigcap\mathbb{B}}\) jest największym ograniczeniem dolnym \(\displaystyle{ \mathbb{B}}\) względem \(\displaystyle{ \succcurlyeq}\), a więc \(\displaystyle{ \bigcap\mathbb{B}= \bigwedge\limits_{\succcurlyeq} \mathbb{B}}\)- jest to infimum dla \(\displaystyle{ \mathbb{B}}\), względem \(\displaystyle{ \succcurlyeq. \square}\) :D :lol:


Można też rozważać symetryczny problem dla łańcucha liniowych porządków względem rozszerzenia przez dodanie elementów większych, tzn.:

Jeśli \(\displaystyle{ X}\) jest zbiorem, a \(\displaystyle{ \mathbb{A}}\) rodziną wszystkich liniowych porządków na pewnych podzbiorach zbioru \(\displaystyle{ X}\), a \(\displaystyle{ \mathbb{B}}\) niepustym łańcuchem liniowych porządków względem \(\displaystyle{ \sqsubseteq}\), czyli względem tego rozszerzenia przez dodanie elementów większych, to \(\displaystyle{ \bigcap\mathbb{B}}\) jest liniowym porządkiem, i \(\displaystyle{ \bigcap \mathbb{B}= \bigwedge \limits_{\sqsubseteq}\mathbb{B}}\)- i jest to infimum tej rodziny liniowych porządków.

Szkic pierwszego dowodu:

Analogicznie:

Ponieważ \(\displaystyle{ \mathbb{B}}\) jest łańcuchem liniowych porządków względem \(\displaystyle{ \sqsubseteq}\), więc łatwo pokazać, że \(\displaystyle{ \mathbb{B}}\) jest łańcuchem również względem relacji rozszerzania (łańcuchem liniowych porządków), więc jego przekrój jest liniowym porządkiem w przekroju zbiorów na których są określone te liniowe porządki.

Aby wykazać, że to jest infimum \(\displaystyle{ \mathbb{B}}\) względem \(\displaystyle{ \sqsubseteq}\), znowu rozważamy rodzinę \(\displaystyle{ \mathbb{B}_2}\) uzupełnień liniowych porządków z \(\displaystyle{ \mathbb{B}}\). Łatwo jest pokazać, (mając lemat 1 i lemat 2), że rodzina \(\displaystyle{ \mathbb{B}_2}\) jest łańcuchem niepustym względem \(\displaystyle{ \succcurlyeq}\). Zatem \(\displaystyle{ S:= \bigcup \mathbb{B}_2= \bigvee\limits_{\succcurlyeq} \mathbb{B}_2}\), na mocy jednego z faktów udowodnionych w pierwszym podanym linku w pierwszym poście. Pokazujemy analogicznie jak poprzednio \(\displaystyle{ S'=\bigcup\mathbb{B}_{|X_0}= \bigcap \mathbb{B}.}\) Ponieważ \(\displaystyle{ S= \bigcup \mathbb{B}_2= \bigvee\limits_{\succcurlyeq} \mathbb{B}_2}\), zatem \(\displaystyle{ S'= \bigcap\mathbb{B}= \bigwedge\limits_{\sqsubseteq} \mathbb{B}. }\)

Należy to wykazać. Należy wykazać, że dla \(\displaystyle{ R\in\mathbb{A}}\), mamy, że \(\displaystyle{ R}\) jest ograniczeniem górnym \(\displaystyle{ \mathbb{B}_2}\) względem \(\displaystyle{ \succcurlyeq,}\) dokładnie wtedy, gdy uzupełnienie \(\displaystyle{ R'}\) jest ograniczeniem dolnym \(\displaystyle{ \mathbb{B}}\) względem \(\displaystyle{ \sqsubseteq}\). Mając lemat 1 i lemat 2, raczej nie jest trudno to udowodnić, a potem należy to wykorzystać by pokazać, że \(\displaystyle{ S'= \bigcap\mathbb{B}}\) jest infimum dla \(\displaystyle{ \mathbb{B}}\) względem \(\displaystyle{ \sqsubseteq.}\)

Szkic drugiego dowodu (a dokładniej jedynie faktu z infimum):

Rozważamy rodzinę \(\displaystyle{ \mathbb{B}_2}\) złożoną z porządków odwrotnych do porządków z \(\displaystyle{ \mathbb{B}}\). Wykazujemy, że ona jest łańcuchem względem \(\displaystyle{ \succcurlyeq}\). Łatwo to pokazać, gdyż rodzina \(\displaystyle{ \mathbb{B}}\) jest łańcuchem względem \(\displaystyle{ \sqsubseteq}\)( i na mocy drugiego linkowanego faktu o związku tych dwóch rozszerzeń i porządków odwrotnych). Na mocy naszego twierdzenia udowodnionego powyżej \(\displaystyle{ \bigcap \mathbb{B}_2}\) jest infimum dla \(\displaystyle{ \mathbb{B}_2}\) względem \(\displaystyle{ \succcurlyeq.}\)
Chcemy uzasdnić, że \(\displaystyle{ \bigcap\mathbb{B}}\) jest infimum \(\displaystyle{ \mathbb{B}}\) względem \(\displaystyle{ \sqsubseteq.}\) W tym celu należy pokazać, że \(\displaystyle{ R}\) jest ograniczeniem dolnym \(\displaystyle{ \mathbb{B}_2}\) względem \(\displaystyle{ \succcurlyeq}\), dokładnie wtedy, gdy \(\displaystyle{ R^{-1}}\) jest ograniczeniem dolnym \(\displaystyle{ \mathbb{B}}\) względem \(\displaystyle{ \sqsubseteq}\). Na mocy linkowanego prawa nie jest to trudno pokazać. A potem należy zauważyć, że \(\displaystyle{ \left( \bigcap\mathbb{B}_2 \right) ^{-1} = \bigcap\mathbb{B}}\), (gdyż mamy prawo, dla rodziny relacji między dwoma zbiorami, że relacja odwrotna do przekroju rodziny relacji jest przekrojem relacji odwrotnych, jest to prosty fakt), i dzięki temu\(\displaystyle{ \left( \bigcap\mathbb{B}\right)^{-1}= \bigcap\mathbb{B}_2}\), a więc \(\displaystyle{ \left( \bigcap\mathbb{B}_2\right) ^{-1} = \bigcap \mathbb{B}}\) , i to należy wykorzystać do dowodu infimum. \(\displaystyle{ \square}\) :lol:

Na koniec podam takie dwa proste dowodziki odnośnie przedziałów początkowych i reszt.

Mamy bowiem taki prosty fakt, że jeśli \(\displaystyle{ \left( X, \le\right) }\) jest zbiorem liniowo upor\(\displaystyle{ }\)ządkowanym, a zbiór \(\displaystyle{ A\subset X}\) jest przedziałem początkowym, i mamy zbiór \(\displaystyle{ Y\subset X}\) z porządkiem \(\displaystyle{ \le}\) z danego zbioru \(\displaystyle{ X}\) zawężonym do zbioru \(\displaystyle{ Y}\), to przekrój \(\displaystyle{ A \cap Y}\) jest przedziałem początkowym w \(\displaystyle{ Y}\).
PROSTY DOWODZIK:    
Podobny fakt można udowodnić dla reszty i dla przedziału. Ale można też inaczej to udowodnić dla reszty.

Przypomnę może najpierw, że w zbiorze liniowo uporżadkowanym \(\displaystyle{ \left( X, \le\right) }\) zbiór \(\displaystyle{ A\subset X}\) nazywamy resztą, gdy z każdym swoim elementem \(\displaystyle{ a\in A,}\) każdy element zbioru \(\displaystyle{ X}\) większy od \(\displaystyle{ a}\) jest elementem \(\displaystyle{ A.}\)

Czyli jest to zbiór od pewnego momentu do końca zbioru liniowo uporządkowanego. Mamy proste fakty, że dla dowolnego \(\displaystyle{ x\in X}\) zbiór postaci \(\displaystyle{ \left(x, \rightarrow \right)=\left\{ y\in X: \ y>x \right\} }\) jest zawsze resztą, jak i zbiór postaci \(\displaystyle{ \left[ x, \rightarrow \right)=\left\{ y\in X: \ y \ge x \right\}}\) jest zawsze resztą, cały zbiór tez jest resztą (nieistotną).

Mamy prosty fakt, że jeśli \(\displaystyle{ \left( X, \le\right)}\) jest zbiorem liniowo uporządkowanym, a zbiór \(\displaystyle{ A\subset X}\) jest resztą i \(\displaystyle{ Y\subset X}\) jest podzbiorem z porządkiem danym \(\displaystyle{ \le}\) zawężonym do zbioru \(\displaystyle{ Y}\), to zbiór \(\displaystyle{ A \cap Y}\) jest resztą w \(\displaystyle{ Y. }\)

Łatwo to można sprawdzić, wprost z definicji reszty. Ale można tez inaczej- skorzystać z faktu, że jeśli w zbiorze liniowo uporządkowanym \(\displaystyle{ \left( X, \le\right) }\) zbiór \(\displaystyle{ A\subset X}\) jest resztą, to w porządku odwrotnym zbiór \(\displaystyle{ A}\) jest przedziałem początkowym, a jeśli zbiór \(\displaystyle{ A\subset X}\) jest przedziałem początkowym w \(\displaystyle{ \left( X, \le\right), }\) to w porządku odwrotnym zbiór \(\displaystyle{ A}\) jest resztą, są to proste fakty. Mamy też prosty fakt, że jeśli \(\displaystyle{ \left( X, \le\right) }\) jest zbiorem liniowo uporządkowanym, a \(\displaystyle{ A\subset X}\) podzbiorem, to porządek odwrotny do zawężenia porządku \(\displaystyle{ \le}\) do zbioru \(\displaystyle{ A}\) jest zawężeniem porządku odwrotnego \(\displaystyle{ \le ^{-1}}\) na \(\displaystyle{ X}\) do zbioru \(\displaystyle{ A}\)- jest to prosty fakt. Przedstawmy teraz ten dowód z zawężeniem reszty do podzbioru.

Ciekawszy dowód:

Zbiór \(\displaystyle{ A}\) jest resztą w \(\displaystyle{ (X, \le)}\), więc w \(\displaystyle{ \left( X, \le ^{-1}\right) }\) zbiór \(\displaystyle{ A}\) jest przedziałem początkowym. Stosując fakt, udowodniony w ukrytej treści, otrzymujemy, że \(\displaystyle{ A \cap Y}\) jest przedziałem początkowym w \(\displaystyle{ Y}\) względem \(\displaystyle{ \left( \le ^{-1}_X \right) _{|Y}.}\) Ale ponieważ zawężenie porządku odwrotnego jest porządkiem odwrotnym do zawężenia, więc \(\displaystyle{ A \cap Y}\) jest przedziałem pocżątkowym względem \(\displaystyle{ \left( \le _{|Y}\right) ^{-1}}\), więc \(\displaystyle{ A \cap Y}\) jest resztą względem \(\displaystyle{ \left( \left( \le _{|Y} \right) ^{-1}\right) ^{-1}= \le _{|Y|}. \square}\)
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: Przekrój łańcucha liniowych porządków

Post autor: Jakub Gurak »

W sobotę przed snem zakończyłem pracę nad czterema pokrewnymi zadaniami związanymi z tym wątkiem. Udowodniłem na przykład, że jeśli mamy łańcuch, względem rozszerzenia przez dodanie elementów większych, łańcuch porządków gęstych, to jego przekrój jest porządkiem gęstym, i jest to infimum tego łańcucha porządków gęstych. Udowodniłem także podobny fakt, że jeśli mamy łańcuch porządków ciągłych, względem rozszerzenia przez dodanie elementów większych, to jego przekrój jest porządkiem ciągłym, i jest to infimum tego łańcucha porządków ciągłych. Podobne dwa fakty udowodniłem dla rozszerzeń przez dodanie elementów mniejszych. Również dla dobrych porządków takie dwa fakty udowodniłem. Przedstawię teraz dowody tych ciekawych faktów.

Zacznijmy od spostrzeżenia, że przekrój łańcucha (zwykłego- względem relacji rozszerzania ) łańcucha porządków gęstych, wtedy przekrój nie musi być porządkiem gęstym.

Aby to uzasadnić, rozważmy poniższy ciąg porządków gęstych, na podzbiorach przedziału \(\displaystyle{ [-1,2]}\):

\(\displaystyle{ \left( X_0:=\left[ -1,2\right] , \ \ \le _0:=\le _{|X_0}\right) ;}\)
\(\displaystyle{ \left( X_1:=\left[ -1, \frac{1}{2} \right) \cup \left[ 1,2\right], \ \ \le_1:=\le _{|X_1} \right); }\)
\(\displaystyle{ \vdots}\)
\(\displaystyle{ \left( X_n:=\left[ -1, \frac{1}{n+1} \right) \cup \left[ 1,2\right], \ \ \le _n:= \le _{|X_n}\right) ;}\)
\(\displaystyle{ \vdots}\)

Jest to ciąg zbiorów liniowo uporządkowanych , jako podzbiorów zbioru \(\displaystyle{ \RR}\), i gęstych, gdyż żaden przekrój Dedekinda nie daje skoku (polecam zrobić sobie prosty rysunek), a nawet ciągłych, gdyż żaden przekrój nie daje luki. I ten ciąg porządków ciągłych tworzy łańcuch. Niewątpliwie, rozważane zbiory \(\displaystyle{ X_n}\) tworzą łańcuch względem inkluzji, ale te zbiory liniowo uporządkowane tworzą również łańcuch względem relacji rozszerzania, gdyż: jeśli dla \(\displaystyle{ n}\) naturalnego, mamy: \(\displaystyle{ X_n \subset X_{n+1}}\), to porządek \(\displaystyle{ \le _{n+1} }\) rozszerza porządek \(\displaystyle{ \le _{n}}\), gdyż jeśli \(\displaystyle{ x \le _n y}\), to \(\displaystyle{ x,y\in X_n}\) i \(\displaystyle{ x \le y}\), wtedy \(\displaystyle{ x,y \in X_{n+1}}\) i \(\displaystyle{ x \le y}\), a więc \(\displaystyle{ x \le _{n+1} y}\), i porządek \(\displaystyle{ \le _{n+1}}\) rozszerza porządek \(\displaystyle{ \le _{n}}\) , więc jest to również łańcuch względem relacji rozszerzania. Tymczasem \(\displaystyle{ \bigcap_{n\in\NN} \le _{n}=\left( \left[ -1,0\right] \cup \left[ 1,2\right] =:Y, \le _{|Y}\right) }\) , a więc pomiędzy \(\displaystyle{ 0}\) a \(\displaystyle{ 1}\) nie ma tu elementu pośredniego, i porządek ten nie jest gęsty\(\displaystyle{ .\square}\)

Wynika stąd, że również przekrój łańcucha porządków ciągłych nie musi być porządkiem ciągłym.

Jednak mamy twierdzenie, że przekrój łańcucha porządków dobrych jest porządkiem dobrym, co udowodniłem TUTAJ.


Przejdźmy do naszych zadań.

Niech \(\displaystyle{ X}\) będzie zbiorem, \(\displaystyle{ \mathbb{B}}\) rodziną wszystkich porządków liniowych na pewnych zbiorach \(\displaystyle{ Y\subset X}\), a \(\displaystyle{ \mathbb{A}}\) rodziną wszystkich porządków gęstych na podzbiorach zbioru \(\displaystyle{ X.}\) Wiemy, że rodzina \(\displaystyle{ \mathbb{B}}\) jest zbiorem uporządkowanym przez \(\displaystyle{ \succcurlyeq}\), czyli przez relację rozszerzenia przez dodanie elementów mniejszych, mamy \(\displaystyle{ \mathbb{A}\subset \mathbb{B}}\) (porządek gęsty jest liniowy), zatem również \(\displaystyle{ \left( \mathbb{A},\succcurlyeq\right) }\) jako podzbiór zbioru uporządkowanego jest zbiorem uporządkowanym. Skoro \(\displaystyle{ \left( \mathbb{A},\succcurlyeq\right) }\) jest zbiorem uporządkowanym, to możemy rozważać łańcuchy w tym zbiorze uporządkowanym. Niech \(\displaystyle{ \left\{ \right\} \neq \mathbb{D}\subset \mathbb{A}}\) będzie łańcuchem niepustym. Pokażemy, że \(\displaystyle{ \bigcap\mathbb{D}}\) jest porządkiem gęstym, oraz, że \(\displaystyle{ \bigcap\mathbb{D} = \bigwedge\limits_{\left( \mathbb{A},\succcurlyeq\right) }\mathbb{D}}\)- jest to infimum tego łańcucha porządków gęstych.

Dowód:

Zacznijmy od wykazania, że łańcuch \(\displaystyle{ \mathbb{D}}\) jest również łańcuchem względem relacji rozszerzania. Niech \(\displaystyle{ R_1,R_2\in\mathbb{D}}\). Ponieważ \(\displaystyle{ \mathbb{D}}\) jest łańcuchem względem \(\displaystyle{ \succcurlyeq}\), więc \(\displaystyle{ R_1\succcurlyeq R_2}\) lub \(\displaystyle{ R_2\succcurlyeq R_1.}\) W pierwszym przypadku porządek \(\displaystyle{ R_2}\) rozszerza porządek \(\displaystyle{ R_1}\), a w drugim porządek \(\displaystyle{ R_1}\) rozszerza porządek \(\displaystyle{ R_2}\). A więc \(\displaystyle{ \mathbb{D}}\) jest łańcuchem względem relacji rozszerzania.

Ponieważ \(\displaystyle{ \mathbb{D}}\) jest łańcuchem porządków liniowych względem relacji rozszerzania, więc \(\displaystyle{ \bigcap\mathbb{D}}\) jest porządkiem liniowym w \(\displaystyle{ \bigcap_{R\in\mathbb{D}} X_R}\), czyli w przekroju zbiorów gdzie są określone te liniowe porządki.

Aby wykazać, że ten porządek jest gęsty, to weźmy \(\displaystyle{ x,y\in \bigcap_{R \in \mathbb{D}}X_R}\) , takie, że \(\displaystyle{ x\left( \bigcap\mathbb{D}\right) y}\). Ponieważ element \(\displaystyle{ x}\) jest mniejszy od \(\displaystyle{ y}\) względem \(\displaystyle{ \bigcap\mathbb{D}}\), więc \(\displaystyle{ x(R)y}\), dla każdego liniowego porządku \(\displaystyle{ R\in\mathbb{D}}\). Niech \(\displaystyle{ R\in\mathbb{D} \neq \left\{ \right\}}\) . Wtedy \(\displaystyle{ R}\) jest porządkiem gęstym, i mamy nierówność: \(\displaystyle{ x(R)y}\). Ponieważ porządek \(\displaystyle{ R}\) jest gęsty, wiec otrzymujemy element pośredni \(\displaystyle{ z\in X_R}\), tzn. taki, że: \(\displaystyle{ x<_R z<_R y}\). Wtedy \(\displaystyle{ x \neq z \neq y}\). Wykażemy, że wtedy również \(\displaystyle{ x<_S z<_S y}\), dla każdego porządku \(\displaystyle{ S\in\mathbb{D}.}\)

Niech \(\displaystyle{ S\in\mathbb{D}}\). Wtedy porządek \(\displaystyle{ S}\) jest gesty. Jeśli \(\displaystyle{ S}\) rozszerza \(\displaystyle{ R}\), to \(\displaystyle{ x \le_S z \le _S y}\) (i mamy \(\displaystyle{ x \neq z \neq y}\)), więc \(\displaystyle{ x<_S z<_S y}\), co chciałem wykazać.
Załóżmy więc dalej, że porządek \(\displaystyle{ S}\) nie rozszerza porządku \(\displaystyle{ R}\). Mamy \(\displaystyle{ R,S\in\mathbb{D}}\), a \(\displaystyle{ \mathbb{D}}\) jest łańcuchem względem \(\displaystyle{ \succcurlyeq}\), więc \(\displaystyle{ R \succcurlyeq S}\) lub \(\displaystyle{ S \succcurlyeq R}\). Nie może być \(\displaystyle{ R\succcurlyeq S}\), gdyż z tego by wynikało, że porządek \(\displaystyle{ S}\) rozszerzałby porządek \(\displaystyle{ R}\)-sprzeczność. Wobec czego musi być \(\displaystyle{ S\succcurlyeq R}\). Wtedy, ja stwierdzam, że \(\displaystyle{ z\in X_S.}\)
Przypuśćmy nie wprost, że tak nie jest, że \(\displaystyle{ z\not\in X_S}\). Mamy\(\displaystyle{ z\in X_R}\), zatem \(\displaystyle{ z\in X_R \setminus X_S}\). Ponieważ \(\displaystyle{ S\in\mathbb{D}}\), to \(\displaystyle{ x(S)y}\), (bo taka nierówność, pomiędzy \(\displaystyle{ x}\) a \(\displaystyle{ y}\), zachodzi dla każdego liniowego porządku \(\displaystyle{ T\in\mathbb{D}}\)), a więc \(\displaystyle{ x\in X_S}\). Mamy więc \(\displaystyle{ z\in X_R \setminus X_S}\),\(\displaystyle{ x\in X_S}\) i \(\displaystyle{ S \succcurlyeq R}\), stosując zatem definicję tego rozszerzenia przez dodanie elementów mniejszych, wnioskujemy, że \(\displaystyle{ z(R)x}\), a mamy \(\displaystyle{ x<_R z}\)- sprzeczność.
Wobec czego \(\displaystyle{ z\in X_S}\). Mamy relację \(\displaystyle{ x(S) y}\), więc \(\displaystyle{ x,y\in X_S.}\) Wtedy \(\displaystyle{ x<_S z<_S y}\).
Przypuśćmy nie wprost, że pierwsza nierówność nie zachodzi. Wtedy, ponieważ \(\displaystyle{ S}\) jest porządkiem liniowym, więc konieczne jest aby \(\displaystyle{ z \le_S x}\), a ponieważ mamy relację: \(\displaystyle{ S \succcurlyeq R}\), więc porządek \(\displaystyle{ R}\) rozszerza porządek \(\displaystyle{ S}\), więc \(\displaystyle{ z \le _R x}\), a mamy \(\displaystyle{ x<_R z-}\) sprzeczność. A zatem \(\displaystyle{ x<_S y.}\) Drugą nierówność udowadniamy analogicznie (dowodem nie wprost).
Wobec czego \(\displaystyle{ x<_S z<_S y}\), i (z dowolności \(\displaystyle{ S}\)) otrzymujemy, że dla każdego porządku \(\displaystyle{ S\in \mathbb{D}}\), zachodzą takie nierówności, więc ( i ponieważ rodzina \(\displaystyle{ \mathbb{D}}\) jest niepusta), więc: \(\displaystyle{ x< _{ \bigcap\mathbb{D}} z< _{ \bigcap\mathbb{D}} y}\). A więc element \(\displaystyle{ z}\) jest elementem pośrednim, względem \(\displaystyle{ \bigcap\mathbb{D}}\), i porządek \(\displaystyle{ \bigcap \mathbb{D}}\) jest gęsty.\(\displaystyle{ \square }\)

Nim przejdziemy dalej, przypomnijmy, że można dość prosto wykazać, że jeśli \(\displaystyle{ (A, \le)}\) jest zbiorem uporządkowanym, a zbiór \(\displaystyle{ B\subset A}\) podzbiorem uporządkowanym, przez porządek \(\displaystyle{ \le}\) zawężony do elementów zbioru \(\displaystyle{ B}\) , i jeśli mamy zbiór \(\displaystyle{ C\subset B,}\) i ten zbiór ma infimum \(\displaystyle{ S:=\bigwedge\limits_{A} C}\) względem porządku na \(\displaystyle{ A}\), to jeśli \(\displaystyle{ S\in B}\), to \(\displaystyle{ S= \bigwedge\limits_{B} C}\)- czyli, o ile, infimum \(\displaystyle{ S}\), zbioru \(\displaystyle{ C,}\) jest elementem podzbioru uporządkowanego, to infimum \(\displaystyle{ S}\) jest również infimum liczonego zbioru \(\displaystyle{ C}\) względem porządku na podzbiorze- to można dość prosto udowodnić.


Zakończmy więc nasze pierwsze zadanie.

Mamy, że porządek \(\displaystyle{ \bigcap\mathbb{D}}\) jest gęsty, a więc \(\displaystyle{ \bigcap\mathbb{D} \in \mathbb{A}}\), i mamy \(\displaystyle{ \bigcap\mathbb{D} = \bigwedge\limits_{\left( \mathbb{B},\succcurlyeq\right) }\mathbb{D}}\), na podstawie jednego z faktów w poście powyżej, gdyż \(\displaystyle{ \mathbb{D}}\) jest to łańcuch porządków liniowych względem rozszerzenia przez dodanie elementów mniejszych, więc jest to infimum dla \(\displaystyle{ \mathbb{D}}\), ale infimum to jest elementem \(\displaystyle{ \mathbb{A}}\)- podzbioru uporządkowanego, zatem \(\displaystyle{ \bigcap\mathbb{D}= \bigwedge\limits_{\left( \mathbb{B},\succcurlyeq\right) }\mathbb{D} = \bigwedge\limits_{\left( \mathbb{A},\succcurlyeq\right) } \mathbb{D}. \square }\):D


Rozważymy teraz łańcuchy porządków gęstych względem rozszerzenia przez dodanie elementów większych.

Niech \(\displaystyle{ X}\) będzie zbiorem. Niech \(\displaystyle{ \mathbb{B}}\) będzie rodziną wszystkich porządków liniowych na pewnych podzbiorach zbioru \(\displaystyle{ X}\). Niech \(\displaystyle{ \mathbb{A}}\) będzie rodziną wszystkich porządków gęstych na pewnych podzbiorach zbioru \(\displaystyle{ X}\). Wiemy, że rodzina \(\displaystyle{ \mathbb{B}}\) jest zbiorem uporządkowanym przez \(\displaystyle{ \sqsubseteq}\), czyli przez relację rozszerzenia przez dodanie elementów większych, mamy \(\displaystyle{ \mathbb{A}\subset \mathbb{B}}\) (porządek gęsty jest liniowy), a więc \(\displaystyle{ \left( \mathbb{A}, \sqsubseteq\right) }\) jako podzbiór zbioru uporządkowanego jest zbiorem uporządkowanym. Możemy zatem rozważać łańcuchy w tym zbiorze uporządkowanym. Niech \(\displaystyle{ \left\{ \right\} \neq \mathbb{D}\subset\mathbb{A}}\) będzie niepustym łańcuchem. Wykażemy, że \(\displaystyle{ \bigcap\mathbb{D}}\) jest porządkiem gęstym, oraz, że \(\displaystyle{ \bigcap\mathbb{D} = \bigwedge\limits_{\left( \mathbb{A},\sqsubseteq\right) }\mathbb{D}}\)- jest to infimum tego łańcucha porządków gęstych.

Dowód:

Rozważmy nową rodzinę zbiorów:

\(\displaystyle{ \mathbb{D'}=\left\{ R ^{-1}\Bigl| \ \ R\in\mathbb{D} \right\},}\)

złożoną z porządków odwrotnych do porządków z \(\displaystyle{ \mathbb{D}}\). I zauważmy, że jeśli \(\displaystyle{ R\in\mathbb{D}}\), to \(\displaystyle{ R}\) jest porządkiem gęstym, wtedy \(\displaystyle{ R^{-1}}\) jest również porządkiem gęstym (gdyż porządek odwrotny do gęstego jest zawsze gęsty- jest to prosty fakt), a więc rodzina \(\displaystyle{ \mathbb{D'}}\) jest rodziną porządków gęstych, i \(\displaystyle{ \mathbb{D'}\subset A}\). Wykażemy, że rodzina \(\displaystyle{ \mathbb{D'}}\) jest łańcuchem względem \(\displaystyle{ \succcurlyeq}\). Niech \(\displaystyle{ S_1,S_2\in \mathbb{D'}}\)'. Wtedy \(\displaystyle{ S_1=R_1 ^{-1}}\), gdzie \(\displaystyle{ R_1\in\mathbb{D}}\), \(\displaystyle{ S_2=R_2 ^{-1}}\), gdzie \(\displaystyle{ R_2\in\mathbb{D}}\). Ponieważ \(\displaystyle{ R_1, R_2\in\mathbb{D}}\), a \(\displaystyle{ \mathbb{D}}\) jest łańcuchem względem \(\displaystyle{ \sqsubseteq}\), więc \(\displaystyle{ R_1\sqsubseteq R_2}\) lub \(\displaystyle{ R_2\sqsubseteq R_1}\). Ponieważ mamy prawo, że jeśli pomiędzy dwoma liniowymi porządkami mamy relację rozszerzenia przez dodanie elementów większych, to na odpowiadających porządkach odwrotnych mamy rozszerzenie przez dodanie elementów mniejszych. W związku z czym, jeśli \(\displaystyle{ R_1 \sqsubseteq R_2}\), to :

\(\displaystyle{ S_1=R_1 ^{-1} \succcurlyeq R_2 ^{-1}=S_2}\), czyli \(\displaystyle{ S_1 \succcurlyeq S_2}\).

A jeśli \(\displaystyle{ R_2 \sqsubseteq R_1 }\), to \(\displaystyle{ S_2=R_2 ^{-1} \succcurlyeq R_1 ^{-1}=S_1}\), czyli \(\displaystyle{ S_2 \succcurlyeq S_1.
}\)


Wobec czego zbiór \(\displaystyle{ \mathbb{D'}}\) jest łańcuchem względem \(\displaystyle{ \succcurlyeq}\). Ponieważ jest to łańcuch porządków gęstych względem rozszrzenia przez dodanie elementów mniejszych, więc na mocy dowodu powyżej, otrzymujemy, że: przekrój \(\displaystyle{ \bigcap\mathbb{D'}}\) jest porządkiem gęstym. Ale \(\displaystyle{ \bigcap\mathbb{D'}= \bigcap_{R\in\mathbb{D}} R ^{-1} =\left( \bigcap\mathbb{D}\right) ^{-1}}\), gdyż mamy prawo, że dla dowolnej rodziny relacji między dwoma zbiorami, relacja odwrotna do przekroju rodziny relacji jest przekrojem relacji odwrotnych (to można łatwo udowodnić) , wobec czego u nas również zachodzi ta równość, i również \(\displaystyle{ \left( \bigcap \mathbb{D} \right) ^{-1} }\) jest porządkiem gęstym, jako ten sam porządek co \(\displaystyle{ \bigcap\mathbb{D'}}\), i ponieważ porządek odwrotny do gęstego jest gesty, więc \(\displaystyle{ \bigcap\mathbb{D} =\left( \left( \bigcap\mathbb{D} \right) ^{-1} \right) ^{-1}}\) jest gęsty.

Pozostał nam fakt z infimum do wykazania.

Wiemy, ponieważ \(\displaystyle{ \mathbb{D}}\) jest łańcuchem porządków liniowych, więc na mocy (drugiego) twierdzenia z postu powyżej: \(\displaystyle{ \bigcap\mathbb{D} = \bigwedge\limits_{\left( \mathbb{B},\sqsubseteq\right) }\mathbb{D}}\)- jest to infimum tego łańcucha porządków liniowych. Ale \(\displaystyle{ \bigcap\mathbb{D} }\) jest gęsty, zatem \(\displaystyle{ \bigcap \mathbb{D} \in\mathbb{A}}\), a zatem \(\displaystyle{ \bigcap\mathbb{D} = \bigwedge\limits_{\left( \mathbb{B},\sqsubseteq\right) }\mathbb{D}= \bigwedge\limits_{\left( \mathbb{A},\sqsubseteq\right) }\mathbb{D}. \square}\)


Przeprowadzimy podobne rozważania dla porządków ciągłych. Nim to zrobimy będziemy potrzebować dwóch lematów:

Lemat 1. Jeśli mamy zbiór \(\displaystyle{ X,}\) oraz dwa podzbiory liniowo uporządkowane \(\displaystyle{ (X_1,R_1);(X_2,R_2)}\) (równoważnie- gdy mamy po prostu dwa zbiory liniowo uporządkowane \(\displaystyle{ (X_1,R_1);(X_2,R_2)}\) - jest to sformułowanie równoważne, bo nawet gdy zbiór \(\displaystyle{ X}\) nie jest ustalony, to możemy rozważyć \(\displaystyle{ X=X_1 \cup X_2,}\) i wtedy te dwa zbiory \(\displaystyle{ X_1,X_2}\) są oczywiście podzbiorami zbioru \(\displaystyle{ X,}\) podzbiorami liniowo uporządkowanymi, co uzasadnia implikację w lewo, druga implikacja jest oczywista, wobec czego jest to sformułowanie równoważne ), i jeśli pomiędzy porządkami \(\displaystyle{ R_1}\) a \(\displaystyle{ R_2}\) mamy rozszerzenie przez dodanie elementów mniejszych, tzn. jeśli zachodzi relacja \(\displaystyle{ R_1\succcurlyeq R_2,}\) to zbiór \(\displaystyle{ X_1}\) jest resztą w zbiorze liniowo uporządkowanym \(\displaystyle{ (X_2,R_2)}\) (definicję reszty można znaleźć pod koniec postu powyżej, jest to podzbiór zbioru liniowo uporządkowanego, który jest zbiorem od pewnego momentu do końca zbioru liniowo uporządkowanego).

Dowód:

Ponieważ \(\displaystyle{ R_1\succcurlyeq R_2}\), to porządek \(\displaystyle{ R_2}\) rozszerza porządek \(\displaystyle{ R_1}\). Ponieważ porządek rozszerzający musi być określony na nadzbiorze zbioru na którym jest określony porządek dany (elementarny fakt), więc \(\displaystyle{ X_2\supset X_1}\). Chcemy pokazać, że zbiór \(\displaystyle{ X_1}\) jest resztą w \(\displaystyle{ X_2}\), więc zbiór \(\displaystyle{ X_1}\) powinien być podzbiorem \(\displaystyle{ X_2}\), i właśnie uzasadniliśmy, że jest. Aby wykazać, że zbiór \(\displaystyle{ X_1}\) jest resztą, weźmy element \(\displaystyle{ x\in X_1,}\) i weźmy element \(\displaystyle{ y\in X_2}\), taki, że: \(\displaystyle{ x(R_2)y}\) i pokażmy, że \(\displaystyle{ y\in X_1}\). Przypuśćmy nie wprost, że tak nie jest. Wtedy \(\displaystyle{ y\in X_2 \setminus X_1, x\in X_1, R_1\succcurlyeq R_2}\), zatem stosując definicję rozszerzenia przez dodanie elementów mniejszych wnioskujemy, że \(\displaystyle{ y(R_2)x}\). Mamy \(\displaystyle{ x(R_2)y}\), więc z antysymetrii porządku: \(\displaystyle{ x=y}\). A więc \(\displaystyle{ y=x\in X_1}\), a z założenia nie wprost \(\displaystyle{ y\not\in X_1}\)-sprzeczność, co kończy dowód.

Czas na drugi lemat.

Lemat 2.: Jeśli mamy zbiór \(\displaystyle{ X}\) i dwa podzbiory liniowo uporządkowane \(\displaystyle{ (X_1,R_1);(X_2,R_2)}\) (równoważnie, gdy mamy po prostu dwa zbiory liniowo uporządkowane \(\displaystyle{ (X_1,R_1);(X_2,R_2)}\)), i jeśli pomiędzy porządkami \(\displaystyle{ R_1}\) a \(\displaystyle{ R_2}\) mamy rozszerzenie przez dodanie elementów większych, tzn. gdy zachodzi relacja \(\displaystyle{ R_1 \sqsubseteq R_2}\), to zbiór \(\displaystyle{ X_1}\) jest przedziałem początkowym w zbiorze liniowo uporządkowanym \(\displaystyle{ (X_2,R_2).}\)

Nim przeprowadzimy dowód, przypomnijmy (raczej prosty) fakt, że jeśli w zbiorze liniowo uporządkowanym \(\displaystyle{ (Y, \le)}\) zbiór \(\displaystyle{ A\subset Y }\) jest resztą, to w porządku odwrotnym zbiór \(\displaystyle{ A}\) jest przedziałem początkowym, a jeśli zbiór \(\displaystyle{ A}\) jest przedziałem początkowym w \(\displaystyle{ \left( Y, \le\right) }\) , to w porządku odwrotnym zbiór \(\displaystyle{ A}\) jest resztą- są to proste fakty.

Dowód drugiego lematu:

Mamy \(\displaystyle{ R_1\sqsubseteq R_2}\), więc na odpowiadających porządkach odwrotnych będziemy mieć pomiędzy nimi rozszerzenie przez dodanie elementów mniejszych, tzn. \(\displaystyle{ R_1 ^{-1}\succcurlyeq R_2^{-1} }\). Zauważmy, że pary \(\displaystyle{ (X_1, R_1 ^{-1} ) ; (X_2, R_2 ^{-1} )}\) są zbiorami liniowo uporządkowanymi, i mamy relację \(\displaystyle{ R_1 ^{-1}\succcurlyeq R_2^{-1}}\), stosując zatem pierwszy lemat otrzymujemy, że zbiór \(\displaystyle{ X_1}\) jest resztą w \(\displaystyle{ (X_2,R_2 ^{-1} )}\). A zatem zbiór \(\displaystyle{ X_1}\) jest przedziałem początkowym w \(\displaystyle{ (X_2, \left( (R_2) ^{-1}\right) ^{-1} =R_2 ).\square}\)


Przeprowadzimy podobne rozważania dla porządków ciągłych.

Przypomnijmy jeszcze, to będzie bardzo ważne tutaj, że jeśli mamy łańcuch \(\displaystyle{ \mathbb{D}}\) porządków ciągłych względem rozszerzenia przez dodanie elementów większych, to jego suma jest porządkiem ciągłym, i \(\displaystyle{ \bigcup\mathbb{D}= \bigvee \mathbb{D}}\)- jest to supremum tego łańcucha porządków ciągłych.

Podobnie, jeśli mamy łańcuch \(\displaystyle{ \mathbb{D}}\) porządków ciągłych względem rozszerzenia przez dodanie elementów mniejszych, to jego suma jest porządkiem ciągłym, i \(\displaystyle{ \bigcup\mathbb{D}= \bigvee\mathbb{D}}\)- jest to supremum tego łańcucha porządków ciągłych, które to te cztery fakty udowodniłem TUTAJ.

Przejdźmy do problemu:

Niech \(\displaystyle{ X}\) będzie zbiorem, \(\displaystyle{ \mathbb{B}}\) rodziną wszystkich porządków liniowych na pewnych podzbiorach zbioru \(\displaystyle{ X}\), a \(\displaystyle{ \mathbb{A}}\) rodziną wszystkich porządków ciągłych na podzbiorach zbioru \(\displaystyle{ X}\). Wtedy para \(\displaystyle{ (\mathbb{B}, \succcurlyeq)}\) tworzy zbiór uporządkowany, mamy \(\displaystyle{ \mathbb{A}\subset \mathbb{B}}\) (porządek ciągły jest liniowy) , zatem również \(\displaystyle{ \left(\mathbb{A}, \succcurlyeq\right) }\) jest zbiorem uporządkowanym. Możemy zatem rozważać łańcuchy w tym zbiorze uporządkowanym. Niech \(\displaystyle{ \left\{ \right\} \neq \mathbb{D}\subset\mathbb{A}}\) będzie niepustym łańcuchem. Wykażemy, że przekrój \(\displaystyle{ \bigcap\mathbb{D}}\) jest porządkiem ciągłym, i \(\displaystyle{ \bigcap\mathbb{D} = \bigwedge\limits_{\left( \mathbb{A},\succcurlyeq\right) }\mathbb{D}}\)- jest to infimum tego łańcucha porządków ciągłych.

Dowód:

\(\displaystyle{ \mathbb{D}}\) jest niepustym łańcuchem porządków ciągłych, (a więc i gęstych) , więc na mocy pierwszego dowodu z tego postu: \(\displaystyle{ \bigcap \mathbb{D}}\) jest porządkiem gęstym w \(\displaystyle{ X_0:= \bigcap_{R\in\mathbb{D}} X_R}\) , czyli w przekroju zbiorów gdzie są określone te porządki ciągle.

Nim przejdziemy dalej, przypomnijmy (prosty fakt), że jeśli mamy dwa zbiory liniowo uporządkowane \(\displaystyle{ (A, \le _A); (B, \le _B)}\) takie, że porządek \(\displaystyle{ \le _B}\) rozszerza porządek \(\displaystyle{ \le _A}\), to \(\displaystyle{ \left( \le _{B} \right) _{|A}= \le _A}\)- porządek rozszerzający zawężony do zbioru, gdzie jest określony porządek dany, jest porządkiem danym (te dwa porządki są równe). Jest to prosty fakt.

Wykażmy, że suma \(\displaystyle{ \bigcup\mathbb{D}}\) zawężona do \(\displaystyle{ X_0,}\) do tego przekroju zbiorów, jest równa przekrojowi \(\displaystyle{ \bigcap\mathbb{D}}\), tzn. \(\displaystyle{ \left( \bigcup \mathbb{D}\right) _{|X_0}= \bigcap \mathbb{D}.}\) Mamy \(\displaystyle{ \bigcup \mathbb{D}\supset \bigcap \mathbb{D}}\), ponieważ zarówno zbiór \(\displaystyle{ \bigcup \mathbb{D},}\) jak i \(\displaystyle{ \bigcap \mathbb{D},}\) są tutaj liniowymi porządkami, więc porządek \(\displaystyle{ \bigcup \mathbb{D}}\) rozszerza porządek \(\displaystyle{ \bigcap \mathbb{D}}\), ponieważ przekrój \(\displaystyle{ \bigcap \mathbb{D}}\) jest porządkiem gęstym określonym dokładnie w zbiorze \(\displaystyle{ X_0}\), więc stosując powyżej wspomniany fakt otrzymujemy, że: \(\displaystyle{ (\bigcup \mathbb{D}) _{|X_0}= \bigcap \mathbb{D}.}\)

Wykażemy teraz, że dla dowolnego porządku \(\displaystyle{ R\in \mathbb{D}}\), zbiór \(\displaystyle{ X_R}\), czyli zbiór na którym jest określony ten porządek \(\displaystyle{ R}\), zbiór \(\displaystyle{ X_R}\) jest resztą w zbiorze liniowo uporządkowanym \(\displaystyle{ \left( X _{ \bigcup \mathbb{D}} , \bigcup \mathbb{D}\right).}\)

Niech \(\displaystyle{ R\in \mathbb{D}}\). Wiemy, na podstawie dowodu z ostatniego linku, że \(\displaystyle{ \bigcup \mathbb{D}}\) jest supremum dla \(\displaystyle{ \mathbb{D}}\). Zatem \(\displaystyle{ \bigcup \mathbb{D}}\) jest ograniczeniem górnym dla \(\displaystyle{ \mathbb{D}}\), a więc \(\displaystyle{ R\succcurlyeq \bigcup \mathbb{D}}\), a więc na mocy lematu 1, otrzymujemy, że zbiór \(\displaystyle{ X_R}\) jest resztą w zbiorze liniowo uporządkowanym \(\displaystyle{ (X _{ \bigcup \mathbb{D} }, \bigcup \mathbb{D}).}\) A zatem (z dowolności \(\displaystyle{ R\in \mathbb{D}}\)) otrzymujemy, że dla dowolnego porządku \(\displaystyle{ R\in \mathbb{D}:}\) zbiór \(\displaystyle{ X_R}\) jest resztą w zbiorze liniowo uporządkowanym \(\displaystyle{ \left( X _{ \bigcup \mathbb{D}}, \bigcup \mathbb{D} \right) }\).

Zatem zbiór \(\displaystyle{ X_0= \bigcap_{R\in \mathbb{D}} X_R,}\) jako przekrój rodziny reszt jest resztą ( jest to, formalnie rzecz biorąc, raczej nietrudny fakt), a więc zbiór \(\displaystyle{ X_0}\) jest resztą, a więc przedziałem w \(\displaystyle{ \left( X _{ \bigcup \mathbb{D}} , \bigcup \mathbb{D}\right).}\) Ponieważ zbiór liniowo uporządkowany \(\displaystyle{ \left( X _{ \bigcup \mathbb{D}}, \bigcup \mathbb{D}\right) }\) jest ciągły, a zbiór \(\displaystyle{ X_0}\) jest przedziałem w nim, więc zbiór liniowo uporządkowany \(\displaystyle{ \left( X_0,(\bigcup \mathbb{D}) _{|X_0}\right) }\) jest ciągły, gdyż przedziały w zbiorze liniowo uporządkowanym ciągłym są uporządkowane w sposób ciągły. Ponieważ wykazaliśmy wcześniej, że \(\displaystyle{ \bigcap \mathbb{D}=(\bigcup \mathbb{D}) _{|X_0}}\), więc zbiór liniowo uporządkowany \(\displaystyle{ (X_0, \bigcap \mathbb{D}),}\) jako ten sam zbiór liniowo uporządkowany, jest ciągły\(\displaystyle{ .\square}\) :lol: :D \(\displaystyle{ }\)


Pozostał nam fakt z infimum do wykazania.

Ponieważ \(\displaystyle{ \mathbb{D}\subset \mathbb{B}}\) jest łańcuchem porządków liniowych, względem rozszerzenia przez dodanie elementów mniejszych, więc na mocy dowodu z postu powyżej: \(\displaystyle{ \bigcap \mathbb{D}= \bigwedge\limits_{\left( \mathbb{B}, \succcurlyeq\right) } \mathbb{D}. }\) Ale porządek \(\displaystyle{ \bigcap \mathbb{D}}\) jest ciągły, więc \(\displaystyle{ \bigcap \mathbb{D}\in \mathbb{A}}\), a zatem \(\displaystyle{ \bigcap \mathbb{D}= \bigwedge\limits_{\left( \mathbb{B}, \succcurlyeq\right) } \mathbb{D}= \bigwedge\limits_{\left( \mathbb{A}, \succcurlyeq\right) } \mathbb{D}.}\)


I ostatni problem:

Niech \(\displaystyle{ X}\) będzie zbiorem, \(\displaystyle{ \mathbb{B}}\) tą samą rodziną liniowych porzadków na podzbiorach, a \(\displaystyle{ \mathbb{A}}\) rodziną wszystkich porządków ciągłych na podzbiorach. Wtedy \(\displaystyle{ \left( \mathbb{B},\sqsubseteq\right) }\), jest zbiorem uporżadkowanym przez to rozszerzenie \(\displaystyle{ \sqsubseteq}\) przez dodanie elementów większych, i \(\displaystyle{ \mathbb{A} \subset \mathbb{B}}\) (porządek ciągły jest liniowy ) zatem \(\displaystyle{ \left( \mathbb{A},\sqsubseteq\right) }\) jest zbiorem uporządkowanym. Niech \(\displaystyle{ \left\{ \right\} \neq \mathbb{D}\subset \mathbb{A}}\) będzie niepustym łańcuchem. Wykażemy, że przekrój \(\displaystyle{ \bigcap\mathbb{D}}\) jest porządkiem ciągłym, i \(\displaystyle{ \bigcap\mathbb{D}= \bigwedge\limits_{\left( \mathbb{A}, \sqsubseteq\right) } \mathbb{D}}\). W ukrytej treści poniżej przedstawiam dowód tego faktu, nawet dwa dowody na to, że przekrój jest ciągły.
DWA PODOBNE DOWODY:    
Na koniec podamy dwa takie proste dowody, tzn.

Jeśli \(\displaystyle{ X}\) jest zbiorem, a \(\displaystyle{ \mathbb{B}}\) ustaloną rodziną dobrych porządków (niektórych) na podzbiorach zbioru \(\displaystyle{ X}\), będącą łańcuchem względem \(\displaystyle{ \sqsubseteq}\), to przekrój \(\displaystyle{ \bigcap\mathbb{B}}\) jest dobrym porządkiem.

Prosty dowód:

Wykażmy, że \(\displaystyle{ \mathbb{B}}\) jest łańcuchem również względem inkluzji. Niech \(\displaystyle{ R_1,R_2\in\mathbb{B}.}\) Ponieważ \(\displaystyle{ \mathbb{B}}\) jest łańcuchem względem \(\displaystyle{ \sqsubseteq}\), więc \(\displaystyle{ R_1\sqsubseteq R_2}\) lub \(\displaystyle{ R_2\sqsubseteq R_1}\). Skąd możemy wnioskować, że porządek \(\displaystyle{ R_2}\) rozszerza porządek \(\displaystyle{ R_1}\) lub porządek \(\displaystyle{ R_1}\) rozszerza porządek \(\displaystyle{ R_2}\), czyli \(\displaystyle{ R_2\supset R_1}\) lub \(\displaystyle{ R_1\supset R_2}\). A więc \(\displaystyle{ \mathbb{B}}\) jest łancuchem względem inkluzji( czyli względem relacji rozszerzania). Ponieważ jest to łancuch dobrych porządków, to \(\displaystyle{ \bigcap\mathbb{B}}\) jest dobrym porządkiem, na mocy dowodu z pierwszego linku\(\displaystyle{ .\square}\)

Również, jeśli \(\displaystyle{ X}\) jest zbiorem, a \(\displaystyle{ \mathbb{B}}\) jest ustaloną rodziną dobrych porządków (niektórych) na podzbiorach zbioru \(\displaystyle{ X}\), będąca łańcuchem względem \(\displaystyle{ \succcurlyeq}\), to przekrój \(\displaystyle{ \bigcap\mathbb{B}}\) jest dobrym porządkiem .

Dla dowodu:

Łatwo wykazać, że \(\displaystyle{ \mathbb{B}}\) jest łańcuchem względem relacji rozszerzania, łańcuchem dobrych porządków, zatem, podobnie jak wcześniej, przekrój \(\displaystyle{ \bigcap\mathbb{B}}\) jest dobrym porządkiem\(\displaystyle{ .\square }\)

Dodajmy, że suma łańcucha porządków dobrych względem rozszerzenia przez dodanie elementów większych, taka suma jest dobrym porządkiem- dowód jest w pierwszym podanym linku. Również suma łańcucha (zwykłego- względem relacji rozszerzania) porządków gęstych jest porządkiem gęstym.

:lol:
ODPOWIEDZ