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:
\(\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}\)
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:
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}\)
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}\)
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:
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}\)