Trzy porządki (nieliniowe) na liniowych porządkach, supremum łańcuchów
: 26 cze 2020, o 03:25
Udało mi się udowodnić, że w rodzinie wszystkich liniowych porządków na podzbiorach zbioru \(\displaystyle{ X}\), relacja taka, że liniowy porządek jest większy od danego gdy jest jego rozszerzeniem przez dodanie elementów mniejszych, taka relacja jest relacją porządku, i w tym zbiorze uporządkowanym \(\displaystyle{ \mathbb{B}}\) jeśli wezmę łańcuch \(\displaystyle{ \mathbb{A}\subset \mathbb{B}}\) to \(\displaystyle{ \bigcup\mathbb{A}}\) jest jego supremum. Myślę, że to ciekawe. Jednak dowód przeprowadziłem w oparciu o fakt, że na tej samej rodzinie \(\displaystyle{ \mathbb{B}}\) relacja taka, że liniowy porządek jest większy od danego gdy jest jego rozszerzeniem przez dodanie elementów większych, taka relacja jest relacją porządku, i na podstawie tego, że w takim zbiorze uporządkowanym każdy niepusty łańcuch posiada supremum. Udowodniłem to chyba w ostatnie wakacje, ale za mało dokładnie, skąd zrodziły mi się wątpliwości.. Trzeba będzie się poprawić i zrobić to lepiej w sposób pewny i ścisły.
Niech \(\displaystyle{ \left( X, \le _{X} \right),\left( Y, \le _{Y} \right) }\) będą zbiorami liniowo uporządkowanymi. Wtedy porządek \(\displaystyle{ \le _{Y}}\) jest rozszerzeniem porządku \(\displaystyle{ \le _{X},}\) gdy dla dowolnych \(\displaystyle{ a,b \in X}\) zachodzi warunek:
\(\displaystyle{ a\le _{X}b \Longrightarrow a\le _{Y}b.}\)
Tzn., jeśli \(\displaystyle{ a}\) jest mniejszy (lub równy) od \(\displaystyle{ b}\) względem danego porządku (na \(\displaystyle{ X}\)), to tym bardziej \(\displaystyle{ a}\) musi być mniejsze od \(\displaystyle{ b}\) względem porządku rozszerzającego.
Inaczej mówiąc \(\displaystyle{ \left( \le _{X}\right) \subseteq \left( \le _{Y} \right)}\), czyli po prostu porządek rozszerzający \(\displaystyle{ \le _{Y}}\) jest nadzbiorem danego porządku \(\displaystyle{ \le _{X}}\). Dla liniowych porządków ma to wymowną ilustrację- porządek rozszerzający jest szerszy, zobacz ilustrację:
Przypomnę powszechny fakt: jeśli \(\displaystyle{ X}\) jest zbiorem, a \(\displaystyle{ S}\) rodziną liniowych porządków( samych relacji) określonych na pewnych podzbiorach zbioru \(\displaystyle{ X}\), taką, że dla dowolnych dwóch liniowych porządków w \(\displaystyle{ S}\) jeden jest rozszerzeniem drugiego, to wtedy dla relacji \(\displaystyle{ \bigcup S}\), zachodzi \(\displaystyle{ \left( \bigcup S\right) _{L}=\left( \bigcup S\right) _{P}}\) i \(\displaystyle{ \bigcup S}\) jest liniowym porządkiem na tym zbiorze.''
Tzn. suma rodziny liniowych porządków na podzbiorach \(\displaystyle{ X}\), i jeśli wiemy, że dla dowolnych dwóch takich liniowych porządków jeden jest rozszerzeniem drugiego, to wtedy suma rodziny takich liniowych porządków jest liniowym porządkiem na swoim polu.
Przypomnę teraz fakt, że
Niech \(\displaystyle{ X}\) będzie zbiorem. Niech \(\displaystyle{ \mathbb{B}}\) będzie rodziną wszystkich liniowych porządków na podzbiorach zbioru \(\displaystyle{ X}\). Możemy taką rodzinę utworzyć gdyż możemy utworzyć rodzinę wszystkich relacji z \(\displaystyle{ X}\) do \(\displaystyle{ X}\),
Zatem w szczególności możemy mówić o rodzinie wszystkich relacji z \(\displaystyle{ X}\) do \(\displaystyle{ X}\), i wybrać z niej te relacje które są relacjami liniowego porządku na pewnych zbiorach \(\displaystyle{ Y\subset X}\). Oznaczmy ta rodzinę liniowych porządków jako \(\displaystyle{ \mathbb{B}.}\)
Łatwo więc będzie pokazać, że w \(\displaystyle{ \left( \mathbb{B}, \subset\right)}\) każdy łańcuch posiada supremum.
Niech \(\displaystyle{ \mathbb{D}\subset\mathbb{B}}\) będzie łańcuchem. Wtedy \(\displaystyle{ \mathbb{D}}\) jest zbiorem złożonym z liniowych porządków, i jeśli mamy dwa elementy \(\displaystyle{ \mathbb{D}}\) to są one liniowymi porządkami na podzbiorach zbioru \(\displaystyle{ X}\), i ponieważ \(\displaystyle{ \mathbb{D}}\) jest łańcuchem to są porównywalne( jeden mniejszy drugi większy), wtedy większy jest rozszerzeniem mniejszego. Otrzymujemy zatem, że dla dowolnych dwóch liniowych porządków w \(\displaystyle{ \mathbb{D}}\) jeden jest rozszerzeniem drugiego, a zatem ten fakt o sumie liniowych porządków daje, że \(\displaystyle{ \bigcup \mathbb{D}}\) jest liniowym porządkiem na swoim polu, czyli na podzbiorze zbioru \(\displaystyle{ X}\). A zatem \(\displaystyle{ \bigcup\mathbb{D}\in\mathbb{B}}\), a zatem na mocy faktu 0: \(\displaystyle{ \bigcup\mathbb{D}= \bigvee \mathbb{D}.\square }\)
Warunek ten mówi, że jeśli weźmiemy dowolny łańcuch \(\displaystyle{ \mathbb{D}\subset\mathbb{B}}\), to \(\displaystyle{ \bigcup\mathbb{D} }\) jest jego supremum. Warunek ten da się narysować Oto ilustracja:
Jednak jest też oczywiste, że ten porządek na liniowych porządkach nie musi być liniowy. Wystarczy rozważyć np. \(\displaystyle{ X=\RR}\), na zbiorze \(\displaystyle{ \left[ 0,1\right]}\) naturalny porządek (liniowy) oznaczmy go jako \(\displaystyle{ R}\), a na zbiorze \(\displaystyle{ \left[ \frac{1}{2},2 \right]}\) naturalny porządek (liniowy) \(\displaystyle{ S}\), wtedy \(\displaystyle{ R}\) nie rozszerza \(\displaystyle{ S}\), ani \(\displaystyle{ S}\) nie rozszerza \(\displaystyle{ R}\). Zatem tutaj \(\displaystyle{ \subset}\) nie jest porządkiem liniowym.
Rozważmy teraz znowu tą samą rodzinę liniowych porządków \(\displaystyle{ \mathbb{B}}\). Przyjmijmy oznaczenia, że jeśli \(\displaystyle{ R\in\mathbb{B}}\), to przez \(\displaystyle{ X _{R}}\) będziemy oznaczać zbiór na którym jest określony liniowy porządek \(\displaystyle{ R}\). Zauważmy, że jeśli \(\displaystyle{ R\in\mathbb{B}}\), to \(\displaystyle{ R}\) jest relacją zwrotną w \(\displaystyle{ X_R}\), zatem \(\displaystyle{ R _{L}=X_R=R_P. }\) W efekcie \(\displaystyle{ R_L \cup R_P=X_R}\), zatem polem relacji \(\displaystyle{ R}\) jest cały zbiór \(\displaystyle{ X_R.}\)
Rozważmy relację \(\displaystyle{ \sqsubseteq}\) na elementach \(\displaystyle{ \mathbb{B}:}\)
\(\displaystyle{ \left( \le_{1}\right) \sqsubseteq \left( \le_{2}\right) \Longleftrightarrow\left( \le_{2} \hbox{ rozszerza } \le_{1}\right) \wedge \Bigl ( x \in X _{ \le _{1} },y \in X _{ \le _{2} } \setminus X _{ \le _{1} } \Longrightarrow x \le _{2}y\Bigr) .}\)
Czyli jeden liniowy porządek \(\displaystyle{ \le _{1}}\) na podzbiorze \(\displaystyle{ X}\) jest mniejszy od drugiego liniowego porządku \(\displaystyle{ \le _{2}}\), gdy \(\displaystyle{ \le _{2}}\) jest rozszerzeniem \(\displaystyle{ \le _{1}}\), i to przez dodanie elementów większych od wszystkich zastanych, co przedstawia ilustracja:
Wykażemy teraz jeszcze raz, że jest to relacja porządku, a potem, że jeśli weźmiemy dowolny niepusty łańcuch \(\displaystyle{ \mathbb{D} \subset \mathbb{B}}\) to zbiór \(\displaystyle{ \bigcup \mathbb {D}}\) jest liniowym porządkiem na podzbiorze \(\displaystyle{ X}\), i jest to supremum dla rodziny \(\displaystyle{ \mathbb{D}}\) takich liniowych porządków. Warunek ten da się narysować. Oto ilustracja.
Niemniej musimy ten ciekawy fakt udowodnić, a najpierw wykazać, że jest to relacja porządku.
Jeśli chcemy być dokładni to udowodnijmy krótko, że porządek rozszerzający względem porządku danego jest określony na nadzbiorze zbioru na którym określony jest dany porządek.
Wykażemy teraz, że \(\displaystyle{ \sqsubseteq}\) jest relacją porządku na \(\displaystyle{ \mathbb{B}.}\)
Jednak ten porządek nie jest liniowy. Wystarczy rozważyć ten sam kontrprzykład co poprzedni kontrprzykład na liniowość w \(\displaystyle{ \left( \mathbb{B},\subset\right) }\). Ponieważ porządek \(\displaystyle{ \subset}\) na \(\displaystyle{ \mathbb{B}}\)- rozszerzenie- nie jest liniowy, więc porządek \(\displaystyle{ \sqsubseteq}\) na \(\displaystyle{ \mathbb{B}}\)- rozszerzenie przez dodanie elementów większych- tym bardziej nie jest liniowy.
Spróbuję wykazać, że w zbiorze uporządkowanym \(\displaystyle{ \left( \mathbb{B},\sqsubseteq\right)}\) każdy niepusty łańcuch posiada supremum, a bardziej wymownie chodzi o to, że jeśli weźmiemy dowolny łańcuch \(\displaystyle{ \mathbb{D} \subset \mathbb{B}}\) złożony z liniowych porządków, to chodzi o pokazanie, że relacja \(\displaystyle{ \bigcup \mathbb {D}}\) jest liniowym porządkiem na podzbiorze \(\displaystyle{ X}\), i jest supremum dla rodziny \(\displaystyle{ \mathbb{D}}\) takich liniowych porządków. Udało się mi to pokazać.
Dowód:
Niech \(\displaystyle{ \mathbb {D} \subset \mathbb {B}}\) będzie dowolnym niepustym łańcuchem. Wtedy jeśli \(\displaystyle{ S _{1},S _{2}}\) są elementami \(\displaystyle{ \mathbb {D}}\), to \(\displaystyle{ S _{1},S _{2}}\) są liniowymi porządkami, i ponieważ \(\displaystyle{ \mathbb {D}}\) jest łańcuchem, więc \(\displaystyle{ S_1, S_2}\) są porównywalne względem \(\displaystyle{ \sqsubseteq}\) , więc \(\displaystyle{ S _{1}\sqsubseteq S_2}\) lub \(\displaystyle{ S _{2}\sqsubseteq S_1}\), więc z definicji \(\displaystyle{ \sqsubseteq}\) wnioskujemy, że \(\displaystyle{ S_2}\) jest rozszerzeniem \(\displaystyle{ S _{1}}\) lub \(\displaystyle{ S _{1}}\) jest rozszerzeniem \(\displaystyle{ S _{2}}\), otrzymujemy zatem, że dla dowolnych dwóch liniowych porządków w \(\displaystyle{ \mathbb {D}}\) jeden jest rozszerzeniem drugiego, a zatem ten powszechny fakt gwarantuje, że relacja \(\displaystyle{ \bigcup \mathbb {D}}\) jest liniowym porządkiem na swoim polu, czyli na pewnym podzbiorze zbioru \(\displaystyle{ X.}\) Zatem \(\displaystyle{ \bigcup\mathbb{D} \in \mathbb{B}}\). Wykażemy teraz, że jest to supremum rodziny takich liniowych porządków.
Należy najpierw pokazać, że zbiór \(\displaystyle{ \bigcup\mathbb {D}}\) jest ograniczeniem górnym dla \(\displaystyle{ \mathbb {D}}\). W tym celu: Niech \(\displaystyle{ S \in\mathbb {D}.}\) Pokażemy najpierw, że \(\displaystyle{ S\sqsubseteq \bigcup \mathbb {D}.}\) Z własności sumy \(\displaystyle{ S\subset \bigcup \mathbb {D},}\) zatem liniowy porządek \(\displaystyle{ \bigcup \mathbb {D}}\) rozszerza liniowy porządek \(\displaystyle{ S}\). Wykażemy teraz punkt drugi odnośnie warunku, że \(\displaystyle{ S \sqsubseteq\bigcup\mathbb{D}.}\) Wykażemy najpierw lemat, że \(\displaystyle{ X _{ \bigcup D} = \bigcup_{C \in\mathbb {D}}X _{C}, }\) czyli, że zbiór na którym jest określony liniowy porządek, którym jest \(\displaystyle{ \bigcup\mathbb {D}}\) jest sumą zbiorów na których są określone te liniowe porządki z \(\displaystyle{ \mathbb {D}.}\) Będzie on nam potrzebny nie raz, więc warto go wpierw udowodnić, niż wprowadzać niezręczności. Niech teraz \(\displaystyle{ x\in X _{S},y \in X_{ \bigcup D} \setminus X_{S}.}\) Pokażemy, że \(\displaystyle{ x\left( \bigcup\mathbb {D}\right) y,}\) czyli, że \(\displaystyle{ (x,y)\in \bigcup \mathbb{D}}\). Mamy \(\displaystyle{ x \in X _{S},y \in X _{ \bigcup D}, y \not\in X _{S}.}\) mamy \(\displaystyle{ y \in X_{ \bigcup D},}\) więc \(\displaystyle{ y \in X _{S _{0} },}\) dla pewnego \(\displaystyle{ S _{0} \in\mathbb {D}.}\) (gdyby (a wiemy, że rodzina \(\displaystyle{ \mathbb{D}}\) jest niepusta, więc istotnie działają prawa zaprzeczania kwantyfikatorom, w rodzinie pustej nie działają), gdyby \(\displaystyle{ y \not\in X _{C}}\) dla żadnego \(\displaystyle{ C \in \mathbb {D}}\), to również \(\displaystyle{ y\not\in \bigcup_{C \in \mathbb {D} }X _{C},}\) a \(\displaystyle{ y \in X_{ \bigcup D} = \bigcup_{C \in \mathbb {D}} X _{C}.}\) na mocy udowodnionego lematu. Zasada równości zbiorów daje więc sprzeczność.) Zatem ponieważ \(\displaystyle{ \mathbb{D} \neq \left\{ \right\}}\), to (stosując prawo zaprzeczania kwantyfikatorowi ogólnemu) otrzymujemy, że \(\displaystyle{ y\in X_{S_0}}\) dla pewnego \(\displaystyle{ S_0\in\mathbb{D}}\). Ponieważ \(\displaystyle{ S_0,S\in\mathbb{D}}\), a \(\displaystyle{ \mathbb{D} }\)jest łańcuchem, to \(\displaystyle{ S_0\sqsubseteq S}\) lub \(\displaystyle{ S\sqsubseteq S_0.}\) Jeśli byłoby \(\displaystyle{ S_0\sqsubseteq S}\), to porządek \(\displaystyle{ S}\) rozszerzałby porządek \(\displaystyle{ S_0}\), a zatem również \(\displaystyle{ X_S\supset X_{S_0}}\), ponieważ \(\displaystyle{ y\in X_{S_0}}\), to \(\displaystyle{ y\in X_S}\)-sprzeczność. Zatem pozostaje możliwość \(\displaystyle{ S\sqsubseteq S_0}\), więc ponieważ \(\displaystyle{ x\in X_S,y\in X_{S_0} \setminus X_S}\), więc stosując definicję \(\displaystyle{ \sqsubseteq}\) wnioskujemy, że \(\displaystyle{ x(S_0)y}\), innymi słowy \(\displaystyle{ (x,y)\in S_0}\), ponieważ \(\displaystyle{ S_0\in\mathbb{D}}\), to tym bardziej \(\displaystyle{ (x,y)\in \bigcup\mathbb{D}}\). Zatem jest spełniony rownież punkt drugi, a zatem \(\displaystyle{ S\sqsubseteq \bigcup\mathbb{D}}\), i z dowolności \(\displaystyle{ S\in\mathbb{D}}\) otrzymujemy, że \(\displaystyle{ \bigcup\mathbb{D}}\) jest ograniczeniem górnym dla \(\displaystyle{ \mathbb{D}. }\)
Pozostaje pokazać, że jest to najmniejsze ograniczenie górne dla \(\displaystyle{ \mathbb{D}}\). Niech \(\displaystyle{ S\in\mathbb{B}}\) będzie ograniczeniem górnym dla \(\displaystyle{ \mathbb{D}}\). Pokażemy, że \(\displaystyle{ \bigcup\mathbb{D}\sqsubseteq S.}\) Ponieważ \(\displaystyle{ S}\) jest ograniczeniem górnym dla \(\displaystyle{ \mathbb{D}}\), więc \(\displaystyle{ A\sqsubseteq S}\), dla każdego zbioru \(\displaystyle{ A\in\mathbb{D}}\). Jeśli więc \(\displaystyle{ A\in\mathbb{D}}\), to oczywiście \(\displaystyle{ A\sqsubseteq S}\), a zatem z definicji porządku \(\displaystyle{ \sqsubseteq}\) wnioskujemy, że \(\displaystyle{ S}\) jest rozszerzeniem \(\displaystyle{ A}\), czyli \(\displaystyle{ S\supset A}\), czyli \(\displaystyle{ A\subset S}\). Pokażaliśmy, w ten oto prosty sposób, że jeśli \(\displaystyle{ A\in \mathbb{D} }\) to \(\displaystyle{ A\subset S}\). Zatem każdy zbiór z rodziny \(\displaystyle{ \mathbb{D}}\) jest podzbiorem \(\displaystyle{ S}\), więc również ich unia ( suma ) jest podzbiorem \(\displaystyle{ S}\)- \(\displaystyle{ \bigcup\mathbb{D}\subset S.}\) A zatem liniowy porządek \(\displaystyle{ S}\) rozszerza liniowy porządek, którym jest \(\displaystyle{ \bigcup \mathbb{D}}\). Pozostaje pokazać punkt drugi, że to jest rozszerzenie przez dodanie elementów większych od wszystkich zastanych. Aby to pokazać, to niech \(\displaystyle{ x\in X_{ \bigcup D} , y\in X_ S\setminus X_{\bigcup \mathbb{D} }. }\) Pokażemy, że \(\displaystyle{ x(S)y.}\) Ponieważ \(\displaystyle{ x\in X_{\bigcup D}}\), to \(\displaystyle{ x\in X_A}\) dla pewnego \(\displaystyle{ A\in \mathbb{D}.}\) Uzasadnienie takie jak wcześniej, mamy \(\displaystyle{ \mathbb{D} \neq \left\{ \right\}}\) (więc działa prawo zaprzeczania kwantyfikatorowi ogólnemu), więc gdyby byłoby \(\displaystyle{ x\not\in X_A}\), dla żadnego zbioru \(\displaystyle{ A\in\mathbb{D}}\) to również \(\displaystyle{ x\not\in \bigcup_{A\in\mathbb{D}} X_A}\), natomiast \(\displaystyle{ x\in X_{ \bigcup D}= \bigcup_{A\in \mathbb{D}} X_A}\), zasada równości zbiorów daje więc sprzeczność. Więc ponieważ również \(\displaystyle{ \mathbb{D} \neq \left\{ \right\}}\), więc \(\displaystyle{ x\in X_A}\), dla pewnego zbioru \(\displaystyle{ A\in\mathbb{D}}\). Ponieważ \(\displaystyle{ y\not\in X _{ \bigcup D}}\), to \(\displaystyle{ y\not\in X_C}\) dla żadnego \(\displaystyle{ C \in \mathbb{D}}\) (tzn. \(\displaystyle{ y}\) do żadnego z tych zbiorów nie nalezy), znowu, nie jest to wbrew pozorom oczywiste, tylko uzasadniamy to naszym lematem: gdyby było \(\displaystyle{ y\not\in X_C}\), gdzie \(\displaystyle{ C\in \mathbb{D},}\) to tym bardziej byłoby \(\displaystyle{ y\in \bigcup_{C\in\mathbb{D}} X_C= X _{ \bigcup D}}\), na mocy naszego lematu, a zatem \(\displaystyle{ y\in X _{ \bigcup D}}\)- sprzeczność. A zatem rzeczywiście \(\displaystyle{ y}\) nie należy do żadnego ze zbiorów \(\displaystyle{ X_C}\), gdzie \(\displaystyle{ C\in\mathbb{D}}\), więc w szczególności \(\displaystyle{ y\not\in X_A}\). Ponieważ \(\displaystyle{ A\in \mathbb{D}}\), to \(\displaystyle{ A\sqsubseteq S}\) (gdyż \(\displaystyle{ S}\) jako ograniczenie górne dla \(\displaystyle{ \mathbb{D}}\) jest większe od każdego zbioru z \(\displaystyle{ \mathbb{D}}\)), mamy \(\displaystyle{ y\in X_S, y\not\in X_A , x\in X_A}\), to stosując definicję \(\displaystyle{ \sqsubseteq}\) do relacji \(\displaystyle{ A\sqsubseteq S}\), i do tych elementów wnioskujemy, że \(\displaystyle{ x(S)y}\), co należało pokazać. A zatem jest spelniony również punkt drugi w definicji \(\displaystyle{ \sqsubseteq}\), a zatem \(\displaystyle{ \bigcup\mathbb{D}\sqsubseteq S}\), gdzie \(\displaystyle{ S}\) było dowolnym ograniczenie górnym dla \(\displaystyle{ \mathbb{D}.}\)
Otrzymujemy zatem, że \(\displaystyle{ \bigcup\mathbb{D}}\) jest najmniejszym ograniczeniem górnym dla \(\displaystyle{ \mathbb{D}}\) względem \(\displaystyle{ \sqsubseteq}\), a więc \(\displaystyle{ \bigcup\mathbb{D}= \bigvee\mathbb{D}. \square }\)
Rozważmy ostatni trzeci porządek na rodzinie \(\displaystyle{ \mathbb{B}}\), tzn. taki porządek, że liniowy porządek jest większy od danego, gdy jest jego rozszerzeniem przez dodanie elementów mniejszych tym razem od wszystkich zastanych, formalnie definiujemy porzadek \(\displaystyle{ \succcurlyeq}\) na rodzinie \(\displaystyle{ \mathbb{B}:}\)
\(\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). }\)
Wykażemy, że ta relacja jest relacją porządku, a następnie, że jeśli weźmiemy niepusty łańcuch \(\displaystyle{ \mathbb{A}\subset \mathbb{B}}\) to zbiór \(\displaystyle{ \bigcup \mathbb{A}}\) jest liniowym porządkiem, i jest to supremum tej rodziny liniowych porządków.
Aby to zrobić to:
Przede wszystkim rozważmy nową rodzinę zbiorów \(\displaystyle{ \mathbb{D}}\)( łatwo potem pokażemy, że to ta sama rodzina tylko inaczej zapisana):
\(\displaystyle{ \mathbb{D}=\left\{ R ^{-1}\Bigl| \ \ R\in\mathbb{B} \right\}}\), złożoną z porządków odwrotnych do porządków liniowych z \(\displaystyle{ \mathbb{B}.}\)
I proszę teraz zauważyć, że ( dla \(\displaystyle{ R,S \in \mathbb{B}}\)) jeśli między \(\displaystyle{ R}\) a \(\displaystyle{ S }\) mamy rozszerzenie przez dodanie elementów mniejszych, to na odpowiadających porządkach odwrotnych mamy rozszerzenie przez dodanie elementów większych. Intuicyjnie jest to zupełnie oczywiste, ale formalnie chyba nie, formalnie, należy pokazać równoważność (dla \(\displaystyle{ R,S\in\mathbb{B}}\)):
\(\displaystyle{ R\succcurlyeq S\Longleftrightarrow R ^{-1} \sqsubseteq S ^{-1}.}\)
Dowód tej oczywistej zależności przedstawiłem tutaj I my wielokrotnie z tej równoważności będziemy korzystać.
Aby wykazać, że relacja \(\displaystyle{ \succcurlyeq}\) jest relacją porządku będziemy potrzebowali pewnego ogólnego lematu.
Łatwo zauważyć, że funkcja \(\displaystyle{ f:\mathbb{B} \rightarrow \mathbb{B}}\) określona \(\displaystyle{ f(R)=R ^{-1}}\) Jest bijekcją. Jest różnowartościowa, gdyż jeśli \(\displaystyle{ f(R)=f(S)}\), to \(\displaystyle{ R^{-1}=S^{-1}}\), zatem \(\displaystyle{ R= \left( R^{-1} \right) ^{-1}= \left( S ^{-1}\right) ^{-1}=S}\), więc \(\displaystyle{ R=S}\). Więc jest różnowartościowa, i oczywiście jest 'na'. Zatem jest bijekcją.
Ponieważ \(\displaystyle{ \left( \mathbb{B},\sqsubseteq\right) }\) jest zbiorem uporządkowanym, a \(\displaystyle{ f:\mathbb{B} \rightarrow \mathbb{B}}\) jest bijekcją, to na mocy lematu 2 relacja \(\displaystyle{ \le _{\mathbb{B} }}\) na rodzinie \(\displaystyle{ \mathbb{B}}\):
\(\displaystyle{ R \le _{\mathbb{B} } S \Longleftrightarrow R ^{-1}=f( R) \sqsubseteq f \left( S \right)=S ^{-1} }\) jest relacją porządku.
Ponieważ jednak mamy prawo \(\displaystyle{ R^{-1}\sqsubseteq S ^{-1}\Longleftrightarrow R\succcurlyeq S
}\), więc to oznacza, że również \(\displaystyle{ \succcurlyeq}\) jest (jako ta sama relacja co \(\displaystyle{ \le _{\mathbb{B} }}\) ) jest relacją porządku na \(\displaystyle{ \mathbb{B}}\), a więc \(\displaystyle{ \left( \mathbb{B},\succcurlyeq\right) }\) jest zbiorem uporządkowanym.
Oh, czystej logiki to chyba nie lubię. Ten porządek również nie jest liniowy. Ponieważ \(\displaystyle{ \subset}\) na \(\displaystyle{ \mathbb{B}}\), rozszerzenie, nie jest porządkiem liniowym, więc porzadek \(\displaystyle{ \succcurlyeq}\)- rozszerzenie przez dodanie elementów mniejszych, tym bardziej nie jest liniowy.
Możemy zatem sprawdzić czy w tym zbiorze uporządkowanym każdy niepusty łańcuch posiada supremum (czyli jeśli weźmiemy łańcuch \(\displaystyle{ \mathbb{A} \subset \left( \mathbb{B}, \succcurlyeq\right) }\) to \(\displaystyle{ \bigcup\mathbb{A}}\) jest jego supremum). Aby wykazać ten ciekawy fakt to: niech \(\displaystyle{ \left\{ \right\} \neq \mathbb{A}\subset \mathbb{B}}\), będzie niepustym łańcuchem (względem \(\displaystyle{ \succcurlyeq}\)). Za supremum kładziemy jak zwykle \(\displaystyle{ \bigcup \mathbb{A}}\). Wpierw jednak musimy zapewnić, że \(\displaystyle{ \bigcup \mathbb{A}\in\mathbb{B}.}\) Ponieważ \(\displaystyle{ \mathbb{A}}\) jest łańcuchem względem \(\displaystyle{ \succcurlyeq}\) zatem fakt o sumie liniowych porządków daje, że \(\displaystyle{ \bigcup\mathbb{A}}\) jest liniowym porządkiem na podzbiorze zbioru \(\displaystyle{ X}\), a zatem \(\displaystyle{ \bigcup\mathbb{A} \in \mathbb{B}.}\)
Rozważmy nową rodzinę zbiorów: \(\displaystyle{ \mathbb{A} ^{'}=\left\{ R ^{-1}\Bigl| \ \ R\in\mathbb{A} \right\} }\) złożoną z porządków odwrotnych do porządków z łańcucha \(\displaystyle{ \mathbb{A}}\). Niewątpliwie \(\displaystyle{ \mathbb{A}'\subset\mathbb{B}}\), i ponieważ łańcuch \(\displaystyle{ \mathbb{A}}\) jest niepusty, to zbiór \(\displaystyle{ \mathbb{A}'}\) również. Należy pokazać, że zbiór \(\displaystyle{ \mathbb{A}'}\) jest łańcuchem względem \(\displaystyle{ \sqsubseteq}\). Wynika to łatwo stąd, że \(\displaystyle{ \mathbb{A}}\) jest łańcuchem względem \(\displaystyle{ \succcurlyeq}\) (i naszej równoważności między tymi porządkami).
Ponieważ zbiór \(\displaystyle{ \mathbb{A}'}\) jest łańcuchem względem \(\displaystyle{ \sqsubseteq}\), oraz \(\displaystyle{ \mathbb{A}' \neq \left\{ \right\}}\) a wiemy, że w \(\displaystyle{ \left( \mathbb{B},\sqsubseteq\right)}\) , każdy niepusty łańcuch posiada supremum (którym dla łańcucha \(\displaystyle{ \mathbb{S}\subset\mathbb{B}}\) jest \(\displaystyle{ \bigcup\mathbb{S}}\)), więc \(\displaystyle{ \bigcup\mathbb{A}'}\) jest supremum dla \(\displaystyle{ \mathbb{A}'.}\) Musimy natomiast wykazać, że zbiór \(\displaystyle{ \bigcup\mathbb{A}}\) jest supremum dla \(\displaystyle{ \mathbb{A}}\) względem \(\displaystyle{ \succcurlyeq}\). Zauważmy, że \(\displaystyle{ \bigcup\mathbb{A}'= \bigcup_{R\in\mathbb{A}} R ^{-1}= \left( \bigcup\mathbb{A}\right) ^{-1},}\) A zatem \(\displaystyle{ \bigcup\mathbb{A}'= \left( \bigcup\mathbb{A}\right) ^{-1}.}\)
Aby pokazać, że \(\displaystyle{ \bigcup\mathbb{A}}\) jest ograniczeniem górnym dla \(\displaystyle{ \mathbb{A}}\), względem \(\displaystyle{ \succcurlyeq}\), to niech \(\displaystyle{ R\in \mathbb{A}}\). Pokażemy że \(\displaystyle{ R \succcurlyeq \bigcup\mathbb{A}.}\) Ponieważ \(\displaystyle{ R\in \mathbb{A}}\), to \(\displaystyle{ R^{-1}\in \mathbb{A}'}\), ponieważ \(\displaystyle{ \bigcup \mathbb{A}'}\) jest supremum \(\displaystyle{ \mathbb{A}'}\) względem \(\displaystyle{ \sqsubseteq}\), to jest jego ograniczeniem gornym, skąd \(\displaystyle{ R^{-1}\sqsubseteq\bigcup \mathbb{A}'= \left( \bigcup\mathbb{A}\right) ^{-1}}\), co oznacza, na mocy naszej równoważności, że \(\displaystyle{ R \succcurlyeq \bigcup\mathbb{\mathbb{A} }}\), co należało pokazać. Zatem \(\displaystyle{ \bigcup\mathbb{A}}\) jest ograniczeniem górnym dla \(\displaystyle{ \mathbb{A}.}\)
Pozostaje pokazać, że jest to najmniejsze ograniczenie górne dla \(\displaystyle{ \mathbb{A}}\). Nim to zrobimy będziemy potrzebowali prostego faktu, że jeśli \(\displaystyle{ S}\) jest ograniczeniem górnym dla \(\displaystyle{ \mathbb{A}}\) względem \(\displaystyle{ \succcurlyeq}\) , to \(\displaystyle{ S^{-1}}\) jest ograniczeniem górnym dla \(\displaystyle{ \mathbb{A}'}\) względem \(\displaystyle{ \sqsubseteq}\). Łatwo ten fakt udowodnić, na mocy naszej równoważności między tymi porządkami. W takim razie jesteśmy gotowi udowodnić, że \(\displaystyle{ \bigcup\mathbb{A}}\) jest najmniejszym ograniczeniem górnym dla \(\displaystyle{ \mathbb{A}}\) względem \(\displaystyle{ \succcurlyeq.}\)
Niech \(\displaystyle{ S}\) będzie ograniczeniem górnym \(\displaystyle{ \mathbb{A}}\) względem \(\displaystyle{ \succcurlyeq.}\) Pokażemy, że \(\displaystyle{ \bigcup \mathbb{A}\succcurlyeq S.}\) Relacja ta zachodzi, wtedy i tylko wtedy, (na mocy naszej równoważności) gdy \(\displaystyle{ \left( \bigcup \mathbb{A}\right) ^{-1}\sqsubseteq S ^{-1},}\) lewa strona tej nierówności jest równa \(\displaystyle{ \bigcup \mathbb{A}'}\), więc to znaczy to samo co \(\displaystyle{ \bigcup \mathbb{A}'\sqsubseteq S ^{-1}, }\) ponieważ \(\displaystyle{ S}\) jest ograniczeniem górnym dla \(\displaystyle{ \mathbb{A}}\) względem \(\displaystyle{ \succcurlyeq}\), więc \(\displaystyle{ S^{-1}}\) jest ograniczeniem górnym dla \(\displaystyle{ \mathbb{A}'}\) względem \(\displaystyle{ \sqsubseteq}\). Poniewaz \(\displaystyle{ \bigcup \mathbb{A}'}\) jest supremum \(\displaystyle{ \mathbb{A}'}\) względem \(\displaystyle{ \sqsubseteq}\). czyli najmniejszym ograniczeniem górnym dla \(\displaystyle{ \mathbb{A}'}\), więc \(\displaystyle{ \bigcup \mathbb{A}'\sqsubseteq S ^{-1}}\), co należało stwierdzić.
Otrzymujemy zatem, że \(\displaystyle{ \bigcup\mathbb{A}}\) jest najmniejszym ograniczeniem górnym dla \(\displaystyle{ \mathbb{A}}\) względem \(\displaystyle{ \succcurlyeq}\), a więc suma \(\displaystyle{ \bigcup\mathbb{A}}\) jest supremum rodziny \(\displaystyle{ \mathbb{A}}\)- \(\displaystyle{ \bigcup \mathbb{A}= \bigvee \mathbb{A}. \square}\)
To może podsumujmy ilustracją tej zależności, gdyż to było motywem tych rozważań. Chętnie bym zrobił więcej potrzebnych ilustracji, ale miniaturki nie da rady zamieścić (mówi że nie można określić rozmiaru obrazka, nie wiem, a odnośników można dać tylko dwa). To może dodam jeszcze, że w podanym linku z forum, tak się właśnie składa, że jest więcej wniosków z tego faktu o sumie liniowych porządków, w szczególności polecam ostatni post z tego wątku, gdzie (właśnie kilka dni temu) udowodniłem, że suma łańcucha porządków gęstych jest liniowym porządkiem gęstym, oraz suma łańcucha porządków ciągłych jest liniowym porządkiem ciągłym, polecam.
Niech \(\displaystyle{ \left( X, \le _{X} \right),\left( Y, \le _{Y} \right) }\) będą zbiorami liniowo uporządkowanymi. Wtedy porządek \(\displaystyle{ \le _{Y}}\) jest rozszerzeniem porządku \(\displaystyle{ \le _{X},}\) gdy dla dowolnych \(\displaystyle{ a,b \in X}\) zachodzi warunek:
\(\displaystyle{ a\le _{X}b \Longrightarrow a\le _{Y}b.}\)
Tzn., jeśli \(\displaystyle{ a}\) jest mniejszy (lub równy) od \(\displaystyle{ b}\) względem danego porządku (na \(\displaystyle{ X}\)), to tym bardziej \(\displaystyle{ a}\) musi być mniejsze od \(\displaystyle{ b}\) względem porządku rozszerzającego.
Inaczej mówiąc \(\displaystyle{ \left( \le _{X}\right) \subseteq \left( \le _{Y} \right)}\), czyli po prostu porządek rozszerzający \(\displaystyle{ \le _{Y}}\) jest nadzbiorem danego porządku \(\displaystyle{ \le _{X}}\). Dla liniowych porządków ma to wymowną ilustrację- porządek rozszerzający jest szerszy, zobacz ilustrację:
Przypomnę powszechny fakt: jeśli \(\displaystyle{ X}\) jest zbiorem, a \(\displaystyle{ S}\) rodziną liniowych porządków( samych relacji) określonych na pewnych podzbiorach zbioru \(\displaystyle{ X}\), taką, że dla dowolnych dwóch liniowych porządków w \(\displaystyle{ S}\) jeden jest rozszerzeniem drugiego, to wtedy dla relacji \(\displaystyle{ \bigcup S}\), zachodzi \(\displaystyle{ \left( \bigcup S\right) _{L}=\left( \bigcup S\right) _{P}}\) i \(\displaystyle{ \bigcup S}\) jest liniowym porządkiem na tym zbiorze.''
Tzn. suma rodziny liniowych porządków na podzbiorach \(\displaystyle{ X}\), i jeśli wiemy, że dla dowolnych dwóch takich liniowych porządków jeden jest rozszerzeniem drugiego, to wtedy suma rodziny takich liniowych porządków jest liniowym porządkiem na swoim polu.
WERSJA PROSTSZA- DWA LINIOWE PORZĄDKI:
FAKT 0:
RODZINA WSZYSTKICH RELACJI Z X DO Y:
Ukryta treść:
Niech \(\displaystyle{ \mathbb{D}\subset\mathbb{B}}\) będzie łańcuchem. Wtedy \(\displaystyle{ \mathbb{D}}\) jest zbiorem złożonym z liniowych porządków, i jeśli mamy dwa elementy \(\displaystyle{ \mathbb{D}}\) to są one liniowymi porządkami na podzbiorach zbioru \(\displaystyle{ X}\), i ponieważ \(\displaystyle{ \mathbb{D}}\) jest łańcuchem to są porównywalne( jeden mniejszy drugi większy), wtedy większy jest rozszerzeniem mniejszego. Otrzymujemy zatem, że dla dowolnych dwóch liniowych porządków w \(\displaystyle{ \mathbb{D}}\) jeden jest rozszerzeniem drugiego, a zatem ten fakt o sumie liniowych porządków daje, że \(\displaystyle{ \bigcup \mathbb{D}}\) jest liniowym porządkiem na swoim polu, czyli na podzbiorze zbioru \(\displaystyle{ X}\). A zatem \(\displaystyle{ \bigcup\mathbb{D}\in\mathbb{B}}\), a zatem na mocy faktu 0: \(\displaystyle{ \bigcup\mathbb{D}= \bigvee \mathbb{D}.\square }\)
Warunek ten mówi, że jeśli weźmiemy dowolny łańcuch \(\displaystyle{ \mathbb{D}\subset\mathbb{B}}\), to \(\displaystyle{ \bigcup\mathbb{D} }\) jest jego supremum. Warunek ten da się narysować Oto ilustracja:
Jednak jest też oczywiste, że ten porządek na liniowych porządkach nie musi być liniowy. Wystarczy rozważyć np. \(\displaystyle{ X=\RR}\), na zbiorze \(\displaystyle{ \left[ 0,1\right]}\) naturalny porządek (liniowy) oznaczmy go jako \(\displaystyle{ R}\), a na zbiorze \(\displaystyle{ \left[ \frac{1}{2},2 \right]}\) naturalny porządek (liniowy) \(\displaystyle{ S}\), wtedy \(\displaystyle{ R}\) nie rozszerza \(\displaystyle{ S}\), ani \(\displaystyle{ S}\) nie rozszerza \(\displaystyle{ R}\). Zatem tutaj \(\displaystyle{ \subset}\) nie jest porządkiem liniowym.
Rozważmy teraz znowu tą samą rodzinę liniowych porządków \(\displaystyle{ \mathbb{B}}\). Przyjmijmy oznaczenia, że jeśli \(\displaystyle{ R\in\mathbb{B}}\), to przez \(\displaystyle{ X _{R}}\) będziemy oznaczać zbiór na którym jest określony liniowy porządek \(\displaystyle{ R}\). Zauważmy, że jeśli \(\displaystyle{ R\in\mathbb{B}}\), to \(\displaystyle{ R}\) jest relacją zwrotną w \(\displaystyle{ X_R}\), zatem \(\displaystyle{ R _{L}=X_R=R_P. }\) W efekcie \(\displaystyle{ R_L \cup R_P=X_R}\), zatem polem relacji \(\displaystyle{ R}\) jest cały zbiór \(\displaystyle{ X_R.}\)
Rozważmy relację \(\displaystyle{ \sqsubseteq}\) na elementach \(\displaystyle{ \mathbb{B}:}\)
\(\displaystyle{ \left( \le_{1}\right) \sqsubseteq \left( \le_{2}\right) \Longleftrightarrow\left( \le_{2} \hbox{ rozszerza } \le_{1}\right) \wedge \Bigl ( x \in X _{ \le _{1} },y \in X _{ \le _{2} } \setminus X _{ \le _{1} } \Longrightarrow x \le _{2}y\Bigr) .}\)
Czyli jeden liniowy porządek \(\displaystyle{ \le _{1}}\) na podzbiorze \(\displaystyle{ X}\) jest mniejszy od drugiego liniowego porządku \(\displaystyle{ \le _{2}}\), gdy \(\displaystyle{ \le _{2}}\) jest rozszerzeniem \(\displaystyle{ \le _{1}}\), i to przez dodanie elementów większych od wszystkich zastanych, co przedstawia ilustracja:
Wykażemy teraz jeszcze raz, że jest to relacja porządku, a potem, że jeśli weźmiemy dowolny niepusty łańcuch \(\displaystyle{ \mathbb{D} \subset \mathbb{B}}\) to zbiór \(\displaystyle{ \bigcup \mathbb {D}}\) jest liniowym porządkiem na podzbiorze \(\displaystyle{ X}\), i jest to supremum dla rodziny \(\displaystyle{ \mathbb{D}}\) takich liniowych porządków. Warunek ten da się narysować. Oto ilustracja.
Niemniej musimy ten ciekawy fakt udowodnić, a najpierw wykazać, że jest to relacja porządku.
Jeśli chcemy być dokładni to udowodnijmy krótko, że porządek rozszerzający względem porządku danego jest określony na nadzbiorze zbioru na którym określony jest dany porządek.
Ukryta treść:
Ukryta treść:
Spróbuję wykazać, że w zbiorze uporządkowanym \(\displaystyle{ \left( \mathbb{B},\sqsubseteq\right)}\) każdy niepusty łańcuch posiada supremum, a bardziej wymownie chodzi o to, że jeśli weźmiemy dowolny łańcuch \(\displaystyle{ \mathbb{D} \subset \mathbb{B}}\) złożony z liniowych porządków, to chodzi o pokazanie, że relacja \(\displaystyle{ \bigcup \mathbb {D}}\) jest liniowym porządkiem na podzbiorze \(\displaystyle{ X}\), i jest supremum dla rodziny \(\displaystyle{ \mathbb{D}}\) takich liniowych porządków. Udało się mi to pokazać.
Dowód:
Niech \(\displaystyle{ \mathbb {D} \subset \mathbb {B}}\) będzie dowolnym niepustym łańcuchem. Wtedy jeśli \(\displaystyle{ S _{1},S _{2}}\) są elementami \(\displaystyle{ \mathbb {D}}\), to \(\displaystyle{ S _{1},S _{2}}\) są liniowymi porządkami, i ponieważ \(\displaystyle{ \mathbb {D}}\) jest łańcuchem, więc \(\displaystyle{ S_1, S_2}\) są porównywalne względem \(\displaystyle{ \sqsubseteq}\) , więc \(\displaystyle{ S _{1}\sqsubseteq S_2}\) lub \(\displaystyle{ S _{2}\sqsubseteq S_1}\), więc z definicji \(\displaystyle{ \sqsubseteq}\) wnioskujemy, że \(\displaystyle{ S_2}\) jest rozszerzeniem \(\displaystyle{ S _{1}}\) lub \(\displaystyle{ S _{1}}\) jest rozszerzeniem \(\displaystyle{ S _{2}}\), otrzymujemy zatem, że dla dowolnych dwóch liniowych porządków w \(\displaystyle{ \mathbb {D}}\) jeden jest rozszerzeniem drugiego, a zatem ten powszechny fakt gwarantuje, że relacja \(\displaystyle{ \bigcup \mathbb {D}}\) jest liniowym porządkiem na swoim polu, czyli na pewnym podzbiorze zbioru \(\displaystyle{ X.}\) Zatem \(\displaystyle{ \bigcup\mathbb{D} \in \mathbb{B}}\). Wykażemy teraz, że jest to supremum rodziny takich liniowych porządków.
Należy najpierw pokazać, że zbiór \(\displaystyle{ \bigcup\mathbb {D}}\) jest ograniczeniem górnym dla \(\displaystyle{ \mathbb {D}}\). W tym celu: Niech \(\displaystyle{ S \in\mathbb {D}.}\) Pokażemy najpierw, że \(\displaystyle{ S\sqsubseteq \bigcup \mathbb {D}.}\) Z własności sumy \(\displaystyle{ S\subset \bigcup \mathbb {D},}\) zatem liniowy porządek \(\displaystyle{ \bigcup \mathbb {D}}\) rozszerza liniowy porządek \(\displaystyle{ S}\). Wykażemy teraz punkt drugi odnośnie warunku, że \(\displaystyle{ S \sqsubseteq\bigcup\mathbb{D}.}\) Wykażemy najpierw lemat, że \(\displaystyle{ X _{ \bigcup D} = \bigcup_{C \in\mathbb {D}}X _{C}, }\) czyli, że zbiór na którym jest określony liniowy porządek, którym jest \(\displaystyle{ \bigcup\mathbb {D}}\) jest sumą zbiorów na których są określone te liniowe porządki z \(\displaystyle{ \mathbb {D}.}\) Będzie on nam potrzebny nie raz, więc warto go wpierw udowodnić, niż wprowadzać niezręczności.
Lemat 1:
Pozostaje pokazać, że jest to najmniejsze ograniczenie górne dla \(\displaystyle{ \mathbb{D}}\). Niech \(\displaystyle{ S\in\mathbb{B}}\) będzie ograniczeniem górnym dla \(\displaystyle{ \mathbb{D}}\). Pokażemy, że \(\displaystyle{ \bigcup\mathbb{D}\sqsubseteq S.}\) Ponieważ \(\displaystyle{ S}\) jest ograniczeniem górnym dla \(\displaystyle{ \mathbb{D}}\), więc \(\displaystyle{ A\sqsubseteq S}\), dla każdego zbioru \(\displaystyle{ A\in\mathbb{D}}\). Jeśli więc \(\displaystyle{ A\in\mathbb{D}}\), to oczywiście \(\displaystyle{ A\sqsubseteq S}\), a zatem z definicji porządku \(\displaystyle{ \sqsubseteq}\) wnioskujemy, że \(\displaystyle{ S}\) jest rozszerzeniem \(\displaystyle{ A}\), czyli \(\displaystyle{ S\supset A}\), czyli \(\displaystyle{ A\subset S}\). Pokażaliśmy, w ten oto prosty sposób, że jeśli \(\displaystyle{ A\in \mathbb{D} }\) to \(\displaystyle{ A\subset S}\). Zatem każdy zbiór z rodziny \(\displaystyle{ \mathbb{D}}\) jest podzbiorem \(\displaystyle{ S}\), więc również ich unia ( suma ) jest podzbiorem \(\displaystyle{ S}\)- \(\displaystyle{ \bigcup\mathbb{D}\subset S.}\) A zatem liniowy porządek \(\displaystyle{ S}\) rozszerza liniowy porządek, którym jest \(\displaystyle{ \bigcup \mathbb{D}}\). Pozostaje pokazać punkt drugi, że to jest rozszerzenie przez dodanie elementów większych od wszystkich zastanych. Aby to pokazać, to niech \(\displaystyle{ x\in X_{ \bigcup D} , y\in X_ S\setminus X_{\bigcup \mathbb{D} }. }\) Pokażemy, że \(\displaystyle{ x(S)y.}\) Ponieważ \(\displaystyle{ x\in X_{\bigcup D}}\), to \(\displaystyle{ x\in X_A}\) dla pewnego \(\displaystyle{ A\in \mathbb{D}.}\) Uzasadnienie takie jak wcześniej, mamy \(\displaystyle{ \mathbb{D} \neq \left\{ \right\}}\) (więc działa prawo zaprzeczania kwantyfikatorowi ogólnemu), więc gdyby byłoby \(\displaystyle{ x\not\in X_A}\), dla żadnego zbioru \(\displaystyle{ A\in\mathbb{D}}\) to również \(\displaystyle{ x\not\in \bigcup_{A\in\mathbb{D}} X_A}\), natomiast \(\displaystyle{ x\in X_{ \bigcup D}= \bigcup_{A\in \mathbb{D}} X_A}\), zasada równości zbiorów daje więc sprzeczność. Więc ponieważ również \(\displaystyle{ \mathbb{D} \neq \left\{ \right\}}\), więc \(\displaystyle{ x\in X_A}\), dla pewnego zbioru \(\displaystyle{ A\in\mathbb{D}}\). Ponieważ \(\displaystyle{ y\not\in X _{ \bigcup D}}\), to \(\displaystyle{ y\not\in X_C}\) dla żadnego \(\displaystyle{ C \in \mathbb{D}}\) (tzn. \(\displaystyle{ y}\) do żadnego z tych zbiorów nie nalezy), znowu, nie jest to wbrew pozorom oczywiste, tylko uzasadniamy to naszym lematem: gdyby było \(\displaystyle{ y\not\in X_C}\), gdzie \(\displaystyle{ C\in \mathbb{D},}\) to tym bardziej byłoby \(\displaystyle{ y\in \bigcup_{C\in\mathbb{D}} X_C= X _{ \bigcup D}}\), na mocy naszego lematu, a zatem \(\displaystyle{ y\in X _{ \bigcup D}}\)- sprzeczność. A zatem rzeczywiście \(\displaystyle{ y}\) nie należy do żadnego ze zbiorów \(\displaystyle{ X_C}\), gdzie \(\displaystyle{ C\in\mathbb{D}}\), więc w szczególności \(\displaystyle{ y\not\in X_A}\). Ponieważ \(\displaystyle{ A\in \mathbb{D}}\), to \(\displaystyle{ A\sqsubseteq S}\) (gdyż \(\displaystyle{ S}\) jako ograniczenie górne dla \(\displaystyle{ \mathbb{D}}\) jest większe od każdego zbioru z \(\displaystyle{ \mathbb{D}}\)), mamy \(\displaystyle{ y\in X_S, y\not\in X_A , x\in X_A}\), to stosując definicję \(\displaystyle{ \sqsubseteq}\) do relacji \(\displaystyle{ A\sqsubseteq S}\), i do tych elementów wnioskujemy, że \(\displaystyle{ x(S)y}\), co należało pokazać. A zatem jest spelniony również punkt drugi w definicji \(\displaystyle{ \sqsubseteq}\), a zatem \(\displaystyle{ \bigcup\mathbb{D}\sqsubseteq S}\), gdzie \(\displaystyle{ S}\) było dowolnym ograniczenie górnym dla \(\displaystyle{ \mathbb{D}.}\)
Otrzymujemy zatem, że \(\displaystyle{ \bigcup\mathbb{D}}\) jest najmniejszym ograniczeniem górnym dla \(\displaystyle{ \mathbb{D}}\) względem \(\displaystyle{ \sqsubseteq}\), a więc \(\displaystyle{ \bigcup\mathbb{D}= \bigvee\mathbb{D}. \square }\)
Rozważmy ostatni trzeci porządek na rodzinie \(\displaystyle{ \mathbb{B}}\), tzn. taki porządek, że liniowy porządek jest większy od danego, gdy jest jego rozszerzeniem przez dodanie elementów mniejszych tym razem od wszystkich zastanych, formalnie definiujemy porzadek \(\displaystyle{ \succcurlyeq}\) na rodzinie \(\displaystyle{ \mathbb{B}:}\)
\(\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). }\)
Wykażemy, że ta relacja jest relacją porządku, a następnie, że jeśli weźmiemy niepusty łańcuch \(\displaystyle{ \mathbb{A}\subset \mathbb{B}}\) to zbiór \(\displaystyle{ \bigcup \mathbb{A}}\) jest liniowym porządkiem, i jest to supremum tej rodziny liniowych porządków.
Aby to zrobić to:
Przede wszystkim rozważmy nową rodzinę zbiorów \(\displaystyle{ \mathbb{D}}\)( łatwo potem pokażemy, że to ta sama rodzina tylko inaczej zapisana):
\(\displaystyle{ \mathbb{D}=\left\{ R ^{-1}\Bigl| \ \ R\in\mathbb{B} \right\}}\), złożoną z porządków odwrotnych do porządków liniowych z \(\displaystyle{ \mathbb{B}.}\)
I proszę teraz zauważyć, że ( dla \(\displaystyle{ R,S \in \mathbb{B}}\)) jeśli między \(\displaystyle{ R}\) a \(\displaystyle{ S }\) mamy rozszerzenie przez dodanie elementów mniejszych, to na odpowiadających porządkach odwrotnych mamy rozszerzenie przez dodanie elementów większych. Intuicyjnie jest to zupełnie oczywiste, ale formalnie chyba nie, formalnie, należy pokazać równoważność (dla \(\displaystyle{ R,S\in\mathbb{B}}\)):
\(\displaystyle{ R\succcurlyeq S\Longleftrightarrow R ^{-1} \sqsubseteq S ^{-1}.}\)
Dowód tej oczywistej zależności przedstawiłem tutaj I my wielokrotnie z tej równoważności będziemy korzystać.
(D=B):
Lemat 2:
Ponieważ \(\displaystyle{ \left( \mathbb{B},\sqsubseteq\right) }\) jest zbiorem uporządkowanym, a \(\displaystyle{ f:\mathbb{B} \rightarrow \mathbb{B}}\) jest bijekcją, to na mocy lematu 2 relacja \(\displaystyle{ \le _{\mathbb{B} }}\) na rodzinie \(\displaystyle{ \mathbb{B}}\):
\(\displaystyle{ R \le _{\mathbb{B} } S \Longleftrightarrow R ^{-1}=f( R) \sqsubseteq f \left( S \right)=S ^{-1} }\) jest relacją porządku.
Ponieważ jednak mamy prawo \(\displaystyle{ R^{-1}\sqsubseteq S ^{-1}\Longleftrightarrow R\succcurlyeq S
}\), więc to oznacza, że również \(\displaystyle{ \succcurlyeq}\) jest (jako ta sama relacja co \(\displaystyle{ \le _{\mathbb{B} }}\) ) jest relacją porządku na \(\displaystyle{ \mathbb{B}}\), a więc \(\displaystyle{ \left( \mathbb{B},\succcurlyeq\right) }\) jest zbiorem uporządkowanym.
Oh, czystej logiki to chyba nie lubię. Ten porządek również nie jest liniowy. Ponieważ \(\displaystyle{ \subset}\) na \(\displaystyle{ \mathbb{B}}\), rozszerzenie, nie jest porządkiem liniowym, więc porzadek \(\displaystyle{ \succcurlyeq}\)- rozszerzenie przez dodanie elementów mniejszych, tym bardziej nie jest liniowy.
Możemy zatem sprawdzić czy w tym zbiorze uporządkowanym każdy niepusty łańcuch posiada supremum (czyli jeśli weźmiemy łańcuch \(\displaystyle{ \mathbb{A} \subset \left( \mathbb{B}, \succcurlyeq\right) }\) to \(\displaystyle{ \bigcup\mathbb{A}}\) jest jego supremum). Aby wykazać ten ciekawy fakt to: niech \(\displaystyle{ \left\{ \right\} \neq \mathbb{A}\subset \mathbb{B}}\), będzie niepustym łańcuchem (względem \(\displaystyle{ \succcurlyeq}\)). Za supremum kładziemy jak zwykle \(\displaystyle{ \bigcup \mathbb{A}}\). Wpierw jednak musimy zapewnić, że \(\displaystyle{ \bigcup \mathbb{A}\in\mathbb{B}.}\) Ponieważ \(\displaystyle{ \mathbb{A}}\) jest łańcuchem względem \(\displaystyle{ \succcurlyeq}\) zatem fakt o sumie liniowych porządków daje, że \(\displaystyle{ \bigcup\mathbb{A}}\) jest liniowym porządkiem na podzbiorze zbioru \(\displaystyle{ X}\), a zatem \(\displaystyle{ \bigcup\mathbb{A} \in \mathbb{B}.}\)
Rozważmy nową rodzinę zbiorów: \(\displaystyle{ \mathbb{A} ^{'}=\left\{ R ^{-1}\Bigl| \ \ R\in\mathbb{A} \right\} }\) złożoną z porządków odwrotnych do porządków z łańcucha \(\displaystyle{ \mathbb{A}}\). Niewątpliwie \(\displaystyle{ \mathbb{A}'\subset\mathbb{B}}\), i ponieważ łańcuch \(\displaystyle{ \mathbb{A}}\) jest niepusty, to zbiór \(\displaystyle{ \mathbb{A}'}\) również. Należy pokazać, że zbiór \(\displaystyle{ \mathbb{A}'}\) jest łańcuchem względem \(\displaystyle{ \sqsubseteq}\). Wynika to łatwo stąd, że \(\displaystyle{ \mathbb{A}}\) jest łańcuchem względem \(\displaystyle{ \succcurlyeq}\) (i naszej równoważności między tymi porządkami).
Ponieważ zbiór \(\displaystyle{ \mathbb{A}'}\) jest łańcuchem względem \(\displaystyle{ \sqsubseteq}\), oraz \(\displaystyle{ \mathbb{A}' \neq \left\{ \right\}}\) a wiemy, że w \(\displaystyle{ \left( \mathbb{B},\sqsubseteq\right)}\) , każdy niepusty łańcuch posiada supremum (którym dla łańcucha \(\displaystyle{ \mathbb{S}\subset\mathbb{B}}\) jest \(\displaystyle{ \bigcup\mathbb{S}}\)), więc \(\displaystyle{ \bigcup\mathbb{A}'}\) jest supremum dla \(\displaystyle{ \mathbb{A}'.}\) Musimy natomiast wykazać, że zbiór \(\displaystyle{ \bigcup\mathbb{A}}\) jest supremum dla \(\displaystyle{ \mathbb{A}}\) względem \(\displaystyle{ \succcurlyeq}\). Zauważmy, że \(\displaystyle{ \bigcup\mathbb{A}'= \bigcup_{R\in\mathbb{A}} R ^{-1}= \left( \bigcup\mathbb{A}\right) ^{-1},}\)
Ukryta treść:
Aby pokazać, że \(\displaystyle{ \bigcup\mathbb{A}}\) jest ograniczeniem górnym dla \(\displaystyle{ \mathbb{A}}\), względem \(\displaystyle{ \succcurlyeq}\), to niech \(\displaystyle{ R\in \mathbb{A}}\). Pokażemy że \(\displaystyle{ R \succcurlyeq \bigcup\mathbb{A}.}\) Ponieważ \(\displaystyle{ R\in \mathbb{A}}\), to \(\displaystyle{ R^{-1}\in \mathbb{A}'}\), ponieważ \(\displaystyle{ \bigcup \mathbb{A}'}\) jest supremum \(\displaystyle{ \mathbb{A}'}\) względem \(\displaystyle{ \sqsubseteq}\), to jest jego ograniczeniem gornym, skąd \(\displaystyle{ R^{-1}\sqsubseteq\bigcup \mathbb{A}'= \left( \bigcup\mathbb{A}\right) ^{-1}}\), co oznacza, na mocy naszej równoważności, że \(\displaystyle{ R \succcurlyeq \bigcup\mathbb{\mathbb{A} }}\), co należało pokazać. Zatem \(\displaystyle{ \bigcup\mathbb{A}}\) jest ograniczeniem górnym dla \(\displaystyle{ \mathbb{A}.}\)
Pozostaje pokazać, że jest to najmniejsze ograniczenie górne dla \(\displaystyle{ \mathbb{A}}\). Nim to zrobimy będziemy potrzebowali prostego faktu, że jeśli \(\displaystyle{ S}\) jest ograniczeniem górnym dla \(\displaystyle{ \mathbb{A}}\) względem \(\displaystyle{ \succcurlyeq}\) , to \(\displaystyle{ S^{-1}}\) jest ograniczeniem górnym dla \(\displaystyle{ \mathbb{A}'}\) względem \(\displaystyle{ \sqsubseteq}\). Łatwo ten fakt udowodnić, na mocy naszej równoważności między tymi porządkami. W takim razie jesteśmy gotowi udowodnić, że \(\displaystyle{ \bigcup\mathbb{A}}\) jest najmniejszym ograniczeniem górnym dla \(\displaystyle{ \mathbb{A}}\) względem \(\displaystyle{ \succcurlyeq.}\)
Niech \(\displaystyle{ S}\) będzie ograniczeniem górnym \(\displaystyle{ \mathbb{A}}\) względem \(\displaystyle{ \succcurlyeq.}\) Pokażemy, że \(\displaystyle{ \bigcup \mathbb{A}\succcurlyeq S.}\) Relacja ta zachodzi, wtedy i tylko wtedy, (na mocy naszej równoważności) gdy \(\displaystyle{ \left( \bigcup \mathbb{A}\right) ^{-1}\sqsubseteq S ^{-1},}\) lewa strona tej nierówności jest równa \(\displaystyle{ \bigcup \mathbb{A}'}\), więc to znaczy to samo co \(\displaystyle{ \bigcup \mathbb{A}'\sqsubseteq S ^{-1}, }\) ponieważ \(\displaystyle{ S}\) jest ograniczeniem górnym dla \(\displaystyle{ \mathbb{A}}\) względem \(\displaystyle{ \succcurlyeq}\), więc \(\displaystyle{ S^{-1}}\) jest ograniczeniem górnym dla \(\displaystyle{ \mathbb{A}'}\) względem \(\displaystyle{ \sqsubseteq}\). Poniewaz \(\displaystyle{ \bigcup \mathbb{A}'}\) jest supremum \(\displaystyle{ \mathbb{A}'}\) względem \(\displaystyle{ \sqsubseteq}\). czyli najmniejszym ograniczeniem górnym dla \(\displaystyle{ \mathbb{A}'}\), więc \(\displaystyle{ \bigcup \mathbb{A}'\sqsubseteq S ^{-1}}\), co należało stwierdzić.
Otrzymujemy zatem, że \(\displaystyle{ \bigcup\mathbb{A}}\) jest najmniejszym ograniczeniem górnym dla \(\displaystyle{ \mathbb{A}}\) względem \(\displaystyle{ \succcurlyeq}\), a więc suma \(\displaystyle{ \bigcup\mathbb{A}}\) jest supremum rodziny \(\displaystyle{ \mathbb{A}}\)- \(\displaystyle{ \bigcup \mathbb{A}= \bigvee \mathbb{A}. \square}\)
To może podsumujmy ilustracją tej zależności, gdyż to było motywem tych rozważań. Chętnie bym zrobił więcej potrzebnych ilustracji, ale miniaturki nie da rady zamieścić (mówi że nie można określić rozmiaru obrazka, nie wiem, a odnośników można dać tylko dwa). To może dodam jeszcze, że w podanym linku z forum, tak się właśnie składa, że jest więcej wniosków z tego faktu o sumie liniowych porządków, w szczególności polecam ostatni post z tego wątku, gdzie (właśnie kilka dni temu) udowodniłem, że suma łańcucha porządków gęstych jest liniowym porządkiem gęstym, oraz suma łańcucha porządków ciągłych jest liniowym porządkiem ciągłym, polecam.