Trzy porządki (nieliniowe) na liniowych porządkach, supremum łańcuchów

Projekty i prace naukowe i badawcze. Nowatorskie idee matematyczne. Literatura specjalistyczna.
Jakub Gurak
Użytkownik
Użytkownik
Posty: 749
Rejestracja: 20 lip 2012, o 21:19
Płeć: Mężczyzna
Lokalizacja: Rzeszów
Podziękował: 24 razy
Pomógł: 50 razy

Trzy porządki (nieliniowe) na liniowych porządkach, supremum łańcuchów

Post autor: Jakub Gurak » 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.
WERSJA PROSTSZA- DWA LINIOWE PORZĄDKI:    
Przypomnę teraz fakt, że
FAKT 0:    
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}\),
RODZINA WSZYSTKICH RELACJI Z X DO Y:    
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}.}\)
Ukryta treść:    
Ł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ć :lol: 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ść:    
Wykażemy teraz, że \(\displaystyle{ \sqsubseteq}\) jest relacją porządku na \(\displaystyle{ \mathbb{B}.}\)
Ukryta treść:    
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.
Lemat 1:    
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 }\) :lol:


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):    
Aby wykazać, że relacja \(\displaystyle{ \succcurlyeq}\) jest relacją porządku będziemy potrzebowali pewnego ogólnego lematu.
Lemat 2:    
Ł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},}\)
Ukryta treść:    
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}\) :D :D :lol:

To może podsumujmy ilustracją tej zależności, gdyż to było motywem tych rozważań. ILUSTRACJA 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.
Rekrutacja Instytut Matematyczny, Uniwersytet Wrocławski (gif)

Jakub Gurak
Użytkownik
Użytkownik
Posty: 749
Rejestracja: 20 lip 2012, o 21:19
Płeć: Mężczyzna
Lokalizacja: Rzeszów
Podziękował: 24 razy
Pomógł: 50 razy

Re: Trzy porządki (nieliniowe) na liniowych porządkach, supremum łańcuchów

Post autor: Jakub Gurak » 29 lip 2020, o 18:58

Udowodniłem wczoraj, że jeśli mamy łańcuch \(\displaystyle{ \mathbb {B}}\) (łańcuch względem rozszerzenia) złożony z liniowych porządków na podzbiorach zbioru \(\displaystyle{ X}\), to relacja \(\displaystyle{ \bigcap\mathbb {B}}\) jest liniowym porządkiem na przekroju wszystkich zbiorów na których są określone liniowe porządki tej rodziny. Przedstawię teraz dowód:

Dowód:

Przypomnę może, ż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}\).


Uzasadniamy najpierw, że \(\displaystyle{ \bigcap\mathbb{B}}\) jest relacją w \(\displaystyle{ \bigcap_{R \in\mathbb{B}} X _{R}. }\) Zakładamy oczywiście, że rodzina \(\displaystyle{ \mathbb{B}}\) jest niepusta (choć w pustej rodzinie wygląda na to, że też to zachodzi).

Niech \(\displaystyle{ x \in \bigcap_{R \in \mathbb{B}} R_L.}\) Wtedy \(\displaystyle{ x \in R_L}\), dla każdej relacji \(\displaystyle{ R \in\mathbb{B} .}\) Relacje takie jako relacje liniowego porządku są zwrotne w \(\displaystyle{ X_R}\), a zatem \(\displaystyle{ R_L=X_R,}\) a zatem \(\displaystyle{ x \in X_R}\) dla każdej relacji \(\displaystyle{ R \in\mathbb{B}}\), i ponieważ rodzina \(\displaystyle{ \mathbb{B}}\) jest niepusta, to \(\displaystyle{ x \in\bigcap_{R \in\mathbb{B}} X_R}\). A zatem \(\displaystyle{ \bigcap_{R \in\mathbb{B} } R_L \subset \bigcap_{R \in\mathbb{B}} X_R.}\)
Ponieważ \(\displaystyle{ \left( \bigcap\mathbb{B}\right)_L \subset \bigcap_{R \in\mathbb{B}}R_L}\) (łatwo taką ogólną inkluzje udowodnić ) , więc \(\displaystyle{ \left( \bigcap\mathbb{B}\right) _{L} \subset \bigcap_{R \in\mathbb{B}} X_R. }\) Analogicznie można pokazać, że \(\displaystyle{ \bigcap _{R\in\mathbb{B}} R_P \subset \bigcap_{R \in \mathbb{B}} X_R.}\) Łatwo pokazać ogólną inkluzję, dzięki której \(\displaystyle{ \left( \bigcap \mathbb{B}\right) _{P} \subset \bigcap_{R\in\mathbb{B}} R_P. }\) Wobec czego \(\displaystyle{ \left( \bigcap \mathbb{B}\right)_P \subset \bigcap_{R \in \mathbb{B}} X_R}\). Ponieważ mamy prawo relacji między dwoma zbiorami, że \(\displaystyle{ R \subset R_L \times R_P}\), więc również \(\displaystyle{ \bigcap \mathbb{B} \subset \left( \bigcap \mathbb{B}\right)_L \times \left( \bigcap \mathbb{B}\right)_P \subset \bigcap_{R \in \mathbb{B}} X_R \times \bigcap_{R \in \mathbb{B}} X_R}\), a zatem \(\displaystyle{ \bigcap \mathbb{B}}\) jest relacją w \(\displaystyle{ \bigcap_{R \in \mathbb{B}} X_R. }\)

Pozostaje wykazać, że taka relacja jest zwrotna, antysymetryczna, przechodnia i spójna.

Zwrotność. Niech \(\displaystyle{ x\in\bigcap_{R \in \mathbb{B}} X_R. }\) Wtedy \(\displaystyle{ x\in X_R}\), dla każdej relacji \(\displaystyle{ R\in\mathbb{B}}\), każda taka relacja \(\displaystyle{ R}\) jest zwrotna w \(\displaystyle{ X_R}\), więc \(\displaystyle{ (x,x)\in R}\), dla każdej relacji \(\displaystyle{ R\in\mathbb{B}}\), i ponieważ rodzina \(\displaystyle{ \mathbb{B}}\) jest niepusta, więc \(\displaystyle{ (x,x)\in \bigcap\mathbb{B}.}\) A więc \(\displaystyle{ \bigcap \mathbb{B}}\) jest relacją zwrotną w \(\displaystyle{ \bigcap_{R \in \mathbb{B}} X_R. }\)

Antysymetria. Łatwo jest pokazać ogólną własność, że każdy podzbiór relacji antysymetrycznej w danym zbiorze jest relacją antysymetryczną. Niech zatem \(\displaystyle{ R\in\mathbb {B}\neq \left\{ \right\}.}\) Wtedy \(\displaystyle{ R}\) jest antysymetryczną, oraz z własności przekroju mnogościowego \(\displaystyle{ \bigcap\mathbb {B} \subset R}\). Zatem wspomniany fakt daje, że \(\displaystyle{ \bigcap\mathbb{B}}\) jest relacją antysymetryczną.

Przechodniość. \(\displaystyle{ \bigcap\mathbb{B}}\) jest relacją przechodnią, gdyż iloczyn niepustej rodziny relacji przechodnich w danym zbiorze jest relacją przechodnią, co udowodniłem tutaj.

Pozostaje do udowodnienia spójność, niestety będzie to najtrudniejsze.

Niech \(\displaystyle{ x,y\in\bigcap_{R \in \mathbb{B}} X_R. }\) Wtedy \(\displaystyle{ x\in X_R, }\) dla każdej relacji \(\displaystyle{ R\in\mathbb{B}}\), oraz \(\displaystyle{ y\in X_R,}\) dla każdej relacji \(\displaystyle{ R\in\mathbb{B}}\). Chcemy pokazać, że \(\displaystyle{ (x,y)\in \bigcap \mathbb{B}}\) lub \(\displaystyle{ (y,x)\in\bigcap \mathbb{B}.}\) Aby to pokazać przypuśćmy, że \(\displaystyle{ (y,x)\not\in \bigcap\mathbb{B}}\) i pokażmy, że \(\displaystyle{ (x,y)\in \bigcap\mathbb{B}}\). Niech zatem \(\displaystyle{ R\in\mathbb{B}.}\) Wtedy \(\displaystyle{ x\in X_R, y\in X_R}\). Wtedy \(\displaystyle{ R}\) jest relacją spójną w \(\displaystyle{ X_R}\), a zatem \(\displaystyle{ (x,y)\in R}\) lub \(\displaystyle{ (y,x)\in R}\). Ponieważ \(\displaystyle{ (y,x)\not\in \bigcap\mathbb{B}}\) i ponieważ \(\displaystyle{ \mathbb{B} \neq \left\{ \right\}}\), więc \(\displaystyle{ (y,x)\not\in S}\), dla pewnej relacji \(\displaystyle{ S\in\mathbb{B}.}\) Wtedy \(\displaystyle{ x,y\in X_S}\), i relacja \(\displaystyle{ S\in\mathbb{B}}\) jest relacją spójną w \(\displaystyle{ X_S}\), zatem \(\displaystyle{ (x,y)\in S}\).

Przypuśćmy teraz , że \(\displaystyle{ (y,x)\in R}\). Ponieważ \(\displaystyle{ \mathbb{B}}\) jest łańcuchem, to relacja \(\displaystyle{ R}\) rozszerza relację \(\displaystyle{ S}\) lub \(\displaystyle{ S}\) rozszerza \(\displaystyle{ R}\). Nie może jednak \(\displaystyle{ S}\) rozszerzać \(\displaystyle{ R}\), gdyż wtedy \(\displaystyle{ (y,x)\in S}\)- sprzeczność; wobec czego musi \(\displaystyle{ R}\) rozszerzać \(\displaystyle{ S}\), więc ponieważ \(\displaystyle{ (x,y)\in S}\), to również \(\displaystyle{ (x,y)\in R}\). Ponieważ \(\displaystyle{ (x,y)\in R}\), \(\displaystyle{ (y,x)\in R}\), więc z antysymetrii \(\displaystyle{ R}\) otrzymujemy \(\displaystyle{ x=y}\). Możemy zatem wnioskować stąd, że \(\displaystyle{ (x,x)\not\in S}\), co jest sprzeczne ze zwrotnością \(\displaystyle{ S.}\)

Wobec czego \(\displaystyle{ (y,x)\not\in R}\), więc pozostaje możliwość \(\displaystyle{ (x,y)\in R}\).
Otrzymujemy zatem, że para \(\displaystyle{ (x,y)\in R,}\) dla każdej relacji \(\displaystyle{ R\in\mathbb{B}}\), i ponieważ rodzina \(\displaystyle{ \mathbb{B}}\) jest niepusta, więc \(\displaystyle{ (x,y)\in \bigcap\mathbb{B}.\square }\) :D

A zatem przekrój dowolnego łańcucha złożonego z liniowych porządków jest liniowym porządkiem. Wynika stąd, że w rodzinie \(\displaystyle{ \left( \mathbb{B}, \subset \right) }\) wszystkich liniowych porządków na podzbiorach zbioru \(\displaystyle{ X}\), każdy niepusty łańcuch posiada infimum ( którym to infimum, dla łańcucha \(\displaystyle{ \left\{ \right\} \neq \mathbb{D}\subset\mathbb{B}}\), jest \(\displaystyle{ \bigcap\mathbb{D}}\)- \(\displaystyle{ \bigcap\mathbb{D}}\) jest liniowym porządkiem, i jest to infimum rodziny liniowych porządków \(\displaystyle{ \mathbb{D}}\)). :lol:

ODPOWIEDZ