Niech \(\displaystyle{ (X,R)}\) będzie zbiorem liniowo uporządkowanym, \(\displaystyle{ (Y,S)}\) podzbiorem liniowo uporządkowanym tak, że zbiór liniowo uporządkowany \(\displaystyle{ (X,R)}\) rozszerza zbiór \(\displaystyle{ (Y,S)}\). Przez uzupełnienie liniowego 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. do zbioru \(\displaystyle{ X \setminus Y}\), i oznaczamy jako \(\displaystyle{ S'}\), tzn.:
\(\displaystyle{ S':=R_{|\left( Y'=X \setminus Y\right) }=R \cap \left[\left( X \setminus Y\right) \times \left( X \setminus Y\right) \right] . }\)
Wtedy \(\displaystyle{ S'}\) jest liniowym porządkiem na \(\displaystyle{ Y'}\) ( gdyż podzbiór zbioru liniowo uporządkowanego jest liniowo uporządkowany). Zauważmy, że porządek rozszerzający \(\displaystyle{ R}\) musi rozszerzać również uzupełnienie \(\displaystyle{ S'.}\)
Udowodniłem przedwczoraj, że jeśli \(\displaystyle{ (A, \le _A ); \left( B, \le _{B}\right) }\) są zbiorami liniowo uporządkowanymi, na zbiorach rozłącznych \(\displaystyle{ A,B}\) (wtedy można rozważać sumę porządkową tych dwóch liniowych porządków), i jeśli mamy dwa zbiory \(\displaystyle{ A_2\subset A}\) oraz \(\displaystyle{ B_2\subset B}\), to uzupełnienie zbioru \(\displaystyle{ A_2 \cup B_2}\) (do \(\displaystyle{ A \cup B}\) ze sumą porządkową \(\displaystyle{ A\oplus B}\)) jest sumą porządkową uzupełnień, tzn. uzupełnienia zbioru \(\displaystyle{ A_2}\) do zbioru \(\displaystyle{ \left( A, \le_ A\right) }\) i uzupełnienia zbioru \(\displaystyle{ B_2}\) do zbioru \(\displaystyle{ \left( B, \le_ B\right) }\), czyli: \(\displaystyle{ \left( A_2 \cup B_2\right) '_{A\oplus B} =A'_2 \oplus B'_2.}\) Myślę, że to bardzo ciekawe.
Udowodniłem też wczoraj, tuż przed tym jak zacząłem pisać ten post, że jeśli \(\displaystyle{ (X,R)}\) jest zbiorem liniowo uporządkowanym, a \(\displaystyle{ X_1, X_ 2 \subset X}\) jego podzbiorami z porządkami odpowiednio: \(\displaystyle{ R}\) zawężonym do zbioru \(\displaystyle{ X_1,}\) oznaczmy go jako \(\displaystyle{ R_1}\), i drugi porządek to: \(\displaystyle{ R}\) zawężone do zbioru \(\displaystyle{ X_2}\), oznaczmy go jako \(\displaystyle{ R_2}\) (wtedy \(\displaystyle{ R}\) rozszerza \(\displaystyle{ R_1,R_2}\), możemy zatem rozważać uzupełnienia \(\displaystyle{ R'_1}\) i \(\displaystyle{ R'_2}\) do zbioru liniowo uporządkowanego \(\displaystyle{ (X,R)}\) ), i udowodniłem, że jeśli dla porządków \(\displaystyle{ R_1,R_2,}\) mamy, że jeden jest rozszerzeniem drugiego, to dla uzupełnień \(\displaystyle{ R'_1,R'_2}\), również jeden jest rozszerzeniem drugiego (ale ten związek nie jest odpowiedni, ma charakter zamienny, naprzemienny, nie jest odpowiedni- choć formalnie można udawać, że jest taki sam warunek
). Udowodniłem to wczoraj, zanim zacząłem pisać ten post. Przedstawię teraz dowody tych ciekawych faktów.Udowodnijmy najpierw pierwszy fakt ze sumą porządkową.
Dowód(zachowując oznaczenia):
Sprawdźmy najpierw, czy wszystko tu jest poprawnie określone:
Mamy, że \(\displaystyle{ \left( A_2, \le _A\right) ; (B_2, \le _B)}\) są zbiorami liniowo uporządkowanymi (gdyż podzbiór zbioru liniowo uporządkowanego jest liniowo uporządkowany). I zbiór \(\displaystyle{ A}\) rozszerza \(\displaystyle{ A_2}\), zbiór \(\displaystyle{ B}\) rozszerza zbiór \(\displaystyle{ B_2.}\) Możemy zatem rozważać ich uzupelnienia, które są liniowymi porządkami, a żeby wziąć sumę porządkową musi wykazać, że zbiory, w których określone są te uzupełnienia, że są rozłączne. Czyli musimy wykazać, że zbiory \(\displaystyle{ A \setminus A_2}\) i \(\displaystyle{ B \setminus B_2}\) są rozłączne. To jednak jest proste, gdyż:
\(\displaystyle{ (A \setminus A_2) \cap \left( B \setminus B_2\right) \subset A \cap B=\emptyset}\), gdyż zbiory \(\displaystyle{ A,B}\) są rozłączne. W takim razie ( gdyż jedynym podzbiorem zbioru pustego jest on sam), więc: \(\displaystyle{ \left( A \setminus A_2\right) \cap \left( B \setminus B_2\right)=\emptyset }\) , czyli zbiory \(\displaystyle{ A \setminus A_2}\) i \(\displaystyle{ B \setminus B_2 }\) nie mają wspólnych elementów, a więc są rozłączne.
Możemy zatem rozważać sumę porządkową tych uzupełnień \(\displaystyle{ A'_2\oplus B'_2.}\)
A dla zbioru po lewej stronie równości, to mamy: \(\displaystyle{ A_2 \cup B_2 \subset A \cup B,}\) i suma porządkowa na \(\displaystyle{ A \cup B}\) rozszerza zbiór \(\displaystyle{ A_2 \cup B_2}\), możemy zatem rozważać jego uzupełnienie, czyli wszystko jest tu poprawnie określone.
Musimy najpierw wykazać, że te dwa liniowe porządki są określone w tym samym zbiorze, czyli, że: \(\displaystyle{ (A \cup B) \setminus \left( A_2 \cup B_2\right)= (A \setminus A_2 ) \cup (B \setminus B_2).}\)
Niewątpliwie, mamy:
\(\displaystyle{ (A \cup B) \setminus \left( A_2 \cup B_2\right) =\left[ A \setminus \left( A_2 \cup B_2\right) \right] \cup \left[ B \setminus \left( A_2 \cup B_2\right) \right]=}\) Zajmijmy się teraz pierwszym składnikiem tej sumy. Korzystając z prawa, że dla zbiorów \(\displaystyle{ X,Y,Z}\), mamy: \(\displaystyle{ X \setminus \left( Y \cup Z\right)=\left( X \setminus Y\right) \cap \left( X \setminus Z \right),}\) więc u nas:
\(\displaystyle{ A \setminus \left( A_2 \cup B_2\right)=\left( A \setminus A_2 \right) \cap \left( A \setminus B_2\right)}\) , ponieważ \(\displaystyle{ B_2\subset B}\), to \(\displaystyle{ A \setminus B_2\supset A \setminus B=}\) , i ponieważ zbiory \(\displaystyle{ A,B}\) są rozłączne, to ten zbiór jest równy \(\displaystyle{ A,}\) tak więc \(\displaystyle{ A \setminus B_2=A.}\) A zatem:
\(\displaystyle{ A \setminus \left( A_2 \cup B_2\right) = \left( A \setminus A_2 \right) \cap \left( A \setminus B_2\right) =\left( A \setminus A_2 \right) \cap A=A \setminus A_2. }\)
Analogicznie, bardzo prosto można udowodnić, że: \(\displaystyle{ B \setminus \left( A_2 \cup B_2\right)=B \setminus B_2. }\)
Wobec czego \(\displaystyle{ (A \cup B) \setminus \left( A_2 \cup B_2\right)= (A \setminus A_2) \cup \left( B \setminus B_2\right).}\)
Wobec czego te dwa liniowe porządki są określone w tym samym zbiorze. Pozostaje pokazać, że te dwa liniowe porządki są równe.
W tym celu weźmy \(\displaystyle{ x,y \in (A \cup B) \setminus \left( A_2 \cup B_2\right)= (A \setminus A_2) \cup \left( B \setminus B_2\right)}\). A następnie załóżmy, że \(\displaystyle{ x \le _{A'_2\oplus B'_2} y}\), i pokażmy, że \(\displaystyle{ x\left( \le _{\left( A_2 \cup B_2\right)' _{A\oplus B} } \right) y}\), czyli, że \(\displaystyle{ x}\) jest mniejszy lub równy od \(\displaystyle{ y}\) również względem drugiego liniowego porządku.
Ze względu na definicję sumy porządkowej rozważmy teraz kilka przypadków:
1. \(\displaystyle{ x,y \in A \setminus A_2}\). Wtedy \(\displaystyle{ x \le _{A'_2} y.}\) Mamy, że porządek \(\displaystyle{ \le _A}\) rozszerza uzupełnienie \(\displaystyle{ \le _{A'_2}}\), wobec czego \(\displaystyle{ x \le_A y}\), a więc tym bardziej \(\displaystyle{ x\left( \le _{A\oplus B} \right) y}\). Mamy \(\displaystyle{ x,y\not\in A_2. }\) Pokażmy teraz, że \(\displaystyle{ x,y\not\in B_2.}\) Gdyby byloby \(\displaystyle{ x\in B_2}\), to \(\displaystyle{ x\in B}\), mamy \(\displaystyle{ x\in A}\), wobec czego \(\displaystyle{ x\in A \cap B}\), a zbiory \(\displaystyle{ A,B}\) są rozłączne- sprzeczność. Wobec czego \(\displaystyle{ x\not\in B_2}\). Podobnie prosto \(\displaystyle{ y\not\in B_2}\). Wobec czego \(\displaystyle{ x,y\not\in A_2 \cup B_2}\), i mamy \(\displaystyle{ x \le _{A\oplus B} y}\), zatem \(\displaystyle{ x\left( \le _{\left(A_2 \cup B_2 \right)' _{A\oplus B} } \right) y}\), co należało pokazać.
2. \(\displaystyle{ x,y \in B \setminus B_2}\). Wtedy, z definicji sumy porządkowej musi być: \(\displaystyle{ x \le _{B'_2} y.}\) Mamy, że porządek \(\displaystyle{ \le _B}\) rozszerza porządek \(\displaystyle{ \le _{B'_2}}\), wobec czego \(\displaystyle{ x \le _B y}\), więc tym bardziej \(\displaystyle{ x \le _{A\oplus B} y}\). Mamy \(\displaystyle{ x,y\not\in B_2}\). Również \(\displaystyle{ x,y\not\in A_2}\)( gdyby byłoby \(\displaystyle{ x\in A_2\subset A}\), to \(\displaystyle{ x\in A}\), mamy \(\displaystyle{ x\in B}\), a zbiory \(\displaystyle{ A,B}\) są rozłączne- sprzeczność). Zatem \(\displaystyle{ x\not\in A_2}\), podobnie prosto \(\displaystyle{ y\not\in A_2}\). Wobec czego \(\displaystyle{ x,y\not\in A_2 \cup B_2}\). Mamy \(\displaystyle{ x \le _{A\oplus B} y}\), w związku z czym \(\displaystyle{ x\left( \le _{\left( A_2 \cup B_2\right)' _{A\oplus B} } \right) y}\), co należało pokazać.
3. \(\displaystyle{ x\in A \setminus A_2, y\in B \setminus B_2.}\) Wtedy \(\displaystyle{ x\in A, y\in B.}\) Ponieważ, z definicji sumy porządkowej \(\displaystyle{ \le _{A\oplus B}}\) mamy, że każdy element zbioru \(\displaystyle{ A}\) jest mniejszy od każdego elementu zbioru \(\displaystyle{ B}\), wiec wnioskujemy, że \(\displaystyle{ x \le _{A\oplus B} y.}\) Mamy \(\displaystyle{ x\not\in A_2}\). Również \(\displaystyle{ x\not\in B_2}\)(gdyby \(\displaystyle{ x\in B_2\subset B}\), to \(\displaystyle{ x\in B}\). Mamy \(\displaystyle{ x\in A}\), a zbiory \(\displaystyle{ A,B}\) są rozłączne- sprzeczność). Wobec czego \(\displaystyle{ x\not\in B_2}\). Mamy \(\displaystyle{ y\not\in B_2.}\) Również \(\displaystyle{ y\not\in A_2}\) (łatwo to nie wprost udowodnić), wobec czego \(\displaystyle{ x\not\in A_2 \cup B_2}\), \(\displaystyle{ y\not\in A_2 \cup B_2}\). Mamy \(\displaystyle{ x \le _{A\oplus B} y}\), a zatem \(\displaystyle{ x \left( \le _{\left( A_2 \cup B_2\right)' _{A\oplus B} } \right) y}\), co należało pokazać.
4. \(\displaystyle{ x\in B \setminus B_2, y\in A \setminus A_2}\). Ten przypadek jest niemożliwy, gdyż ponieważ, z definicji sumy porządkowej, każdy element \(\displaystyle{ A \setminus A_2}\) jest mniejszy od każdego elementu \(\displaystyle{ B \setminus B_2}\), więc możemy wnioskować, że \(\displaystyle{ y \le _{A'_2\oplus B'_2} x}\), a mamy \(\displaystyle{ x \le _{A'_2\oplus B'_2} y}\)- sprzeczność.
Kończy to połowę dowodu tej ostatniej części.
Załóżmy teraz, że \(\displaystyle{ x\left( \le _{\left( A_2 \cup B_2\right)' _{A\oplus B} }\right) y.}\) Wtedy \(\displaystyle{ x,y\not\in A_2 \cup B_2}\). Rozważmy najpierw trzy proste przypadki.
1. \(\displaystyle{ x \le _A y}\). Ponieważ \(\displaystyle{ x,y\not\in A_2}\), to \(\displaystyle{ x \le _{A'_2} y}\), więc tym bardziej \(\displaystyle{ x \le _{A'_2\oplus B'_2} y}\), co należało pokazać.
2. \(\displaystyle{ x \le _B y.}\) Ponieważ \(\displaystyle{ x,y\not\in B_2}\), więc \(\displaystyle{ x \le _{B'_2} y}\), a więc tym bardziej \(\displaystyle{ x \le _{A'_2\oplus B'_2} y}\), co należało pokazać.
3. \(\displaystyle{ x\in A}\), \(\displaystyle{ y\in B.}\) Mamy \(\displaystyle{ x\not\in A_2}\), \(\displaystyle{ y\not\in B_2.}\) Zatem \(\displaystyle{ x\in A \setminus A_2; y\in B \setminus B_2}\). Ponieważ uzupełnienie \(\displaystyle{ A'_2}\) jest liniowym porządkiem na \(\displaystyle{ A \setminus A_2}\), a uzupełnienie \(\displaystyle{ B'_2}\) jest liniowym porządkiem na \(\displaystyle{ B \setminus B_2}\), więc, z definicji sumy porządkowej \(\displaystyle{ \le _{A'_2\oplus B'_2}}\), ponieważ każdy element \(\displaystyle{ A \setminus A_2}\) jest mniejszy od każdego elementu \(\displaystyle{ B \setminus B_2}\), więc wnioskujemy, że \(\displaystyle{ x \le _{A'_2\oplus B'_{2}} y}\), co należało pokazać.
Pozostaje pokazać, że nie ma innych przypadków. Zauważmy najpierw, że ponieważ \(\displaystyle{ \le _{ A\oplus B}}\) rozszerza uzupełnienie \(\displaystyle{ (A_2 \cup B_2)' _{A\oplus B}}\), więc \(\displaystyle{ x \le_{A\oplus B} y.}\)
W tym celu pokażemy, że jeśli nie zachodzi przypadek trzeci (z powyższych) , to musi zajść przypadek pierwszy lub drugi.
Jeśli nie zachodzi przypadek trzeci, to \(\displaystyle{ x\notin A}\) lub \(\displaystyle{ y\not\in B}\). Wtedy nie może być jednocześnie \(\displaystyle{ y\in A, x\in B}\), gdyż wtedy, ponieważ względem sumy porządkowej \(\displaystyle{ A\oplus B}\), mamy, że każdy element zbioru \(\displaystyle{ A}\) jest mniejszy od każdego elementu \(\displaystyle{ B}\), więc moglibyśmy wnioskować, że \(\displaystyle{ y \le _{A\oplus B} x}\), a mamy \(\displaystyle{ x \le _{A\oplus B} y}\), wobec czego \(\displaystyle{ x=y}\), \(\displaystyle{ x\in B, y=x\in A}\), a zbiory \(\displaystyle{ A,B}\) są rozłączne- sprzeczność.
Wobec czego są tylko dwa przypadki: \(\displaystyle{ x,y\in A}\) lub \(\displaystyle{ x,y\in B.}\)
Jeśli \(\displaystyle{ x,y\in A}\), ponieważ \(\displaystyle{ x \le _{A\oplus B} y}\), więc \(\displaystyle{ x \le _A y}\), co daje przypadek pierwszy (z trzech przypadków wcześniej rozważanych).
Jeśli \(\displaystyle{ x,y\in B}\), to ponieważ \(\displaystyle{ x \le _{A\oplus B} y}\), więc \(\displaystyle{ x \le _B y}\), co daje przypadek drugi. (Wystarczy dowód pozbierać aby go zakończyć)\(\displaystyle{ . \square}\)
Wykażemy teraz drugi fakt, tzn.:
Jeśli \(\displaystyle{ (X,R)}\) jest zbiorem liniowo uporządkowanym, a zbiory \(\displaystyle{ X_1,X_2\subset X}\) są jego podzbiorami, uporządkowanymi liniowo przez odpowiednio: \(\displaystyle{ R}\) zawężone do zbioru \(\displaystyle{ X_1,}\) oznaczmy ten porządek jako \(\displaystyle{ R_1}\), i drugi zbiór jest uporządkowany przez \(\displaystyle{ R}\) zawężone do zbioru \(\displaystyle{ X_2,}\) oznaczmy podobnie ten porządek jako \(\displaystyle{ R_2}\) (wtedy porządek \(\displaystyle{ R}\) rozszerza porządki \(\displaystyle{ R_1, R_2}\) , możemy zatem rozważać uzupełnienia \(\displaystyle{ R'_1}\) , \(\displaystyle{ R'_2}\) do zbioru liniowo uporządkowanego \(\displaystyle{ (X,R)}\) ), i wtedy, jeśli dla \(\displaystyle{ R_1, R_2,}\) jeśli jeden z tych dwóch liniowych porządków jest rozszerzeniem drugiego, tzn. jeśli \(\displaystyle{ R_1}\) rozszerza \(\displaystyle{ R_2}\) lub \(\displaystyle{ R_2}\) rozszerza \(\displaystyle{ R_1}\), to dla uzupełnień \(\displaystyle{ R'_1 ,R'_2,}\) również jeden z tych dwóch liniowych porządków jest rozszerzeniem drugiego.
Dowód:
Jeśli \(\displaystyle{ R_1}\) rozszerza \(\displaystyle{ R_2}\), to \(\displaystyle{ X_1\supset X_2}\) (porządek rozszerzający musi być określony na nadzbiorze zbioru, na którym jest określony porządek dany- jest to elementarny fakt), zatem dla dopełnień: \(\displaystyle{ X'_1=X \setminus X_1\subset X'_2=X \setminus X_2. }\)Wtedy \(\displaystyle{ X'_1 \times X'_1\subset X'_2 \times X'_2 }\), i dalej \(\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 }\), czyli \(\displaystyle{ R'_2\supset R'_1.}\) Ponieważ porządek \(\displaystyle{ R'_2}\) jest nadzbiorem porządku \(\displaystyle{ R'_1}\), to porządek \(\displaystyle{ R'_2}\) rozszerza porządek \(\displaystyle{ R'_1.}\)
Jeśli \(\displaystyle{ R_2}\) rozszerza \(\displaystyle{ R_1}\), to symetrycznie on prowadzi do wniosku, że: \(\displaystyle{ R'_1}\) rozszerza \(\displaystyle{ R'_2. \square}\)
Udowodnimy na koniec, że jeśli \(\displaystyle{ (X,R); (Y,S)}\) są zbiorami liniowo uporządkowanymi, takimi, że zbiór \(\displaystyle{ X}\) rozszerza zbiór \(\displaystyle{ Y}\), to porządek odwrotny do uzupełnienia porządku \(\displaystyle{ S}\) jest uzupełnieniem porządku odwrotnego do \(\displaystyle{ S}\), uzupełnieniem do porządku odwrotnego \(\displaystyle{ R^{-1}}\) w całym nadzbiorze \(\displaystyle{ X}\), czyli:
\(\displaystyle{ \left( S'\right) ^{-1}= \left( S ^{-1}\right)' _{R^{-1}}. }\)
W tym celu przypomnijmy prosty fakt, że relacja odwrotna do prostokąta \(\displaystyle{ A \times B}\) jest prostokąt \(\displaystyle{ B \times A}\), tzn. \(\displaystyle{ \left( A \times B\right) ^{-1} =B \times A}\), w szczególności (gdy relacja jest ze zbioru w ten sam zbiór), dla zbioru \(\displaystyle{ A,}\) podzbioru zbioru, w którym jest określona relacja, mamy: \(\displaystyle{ (A \times A ) ^{-1} =A \times A}\). Ten fakt nam się przyda. Przejdźmy do naszego dowodu.
Dowód:
Zauważmy najpierw, że obydwa liniowe porządki są porządkami na \(\displaystyle{ Y'=X \setminus Y}\). Mamy:
\(\displaystyle{ \left( S' \right) ^{-1}= \left( R _{|Y'} \right) ^{-1}= \left[ R \cap \left( Y' \times Y'\right) \right] ^{-1}=R ^{-1} \cap \left( Y' \times Y'\right) ^{-1}=}\)
i teraz korzystając ze wspomnianego przed tym dowodem prawa, otrzymujemy, że to jest równe:
\(\displaystyle{ =R ^{-1} \cap \left[ Y' \times Y'\right] .}\)
Tymczasem:
\(\displaystyle{ \left( S ^{-1} \right)' _{R ^{-1} }=R ^{-1} _{| Y'}=R ^{-1} \cap \left( Y' \times Y'\right).}\)
A zatem \(\displaystyle{ \left( S ^{-1} \right)' _{R^{-1}}=\left( S'\right) ^{-1}.\square}\)
Dodajmy jeszcze, że jeśli \(\displaystyle{ (X,R); (Y,S)}\) są zbiorami liniowo uporządkowanymi, takimi, że zbiór liniowo uporządkowany \(\displaystyle{ \left( X,R\right)}\) rozszerza zbiór \(\displaystyle{ (Y,S)}\), to: \(\displaystyle{ (S' )'=S}\)- uzupełnienie uzupełnienia porządku \(\displaystyle{ S}\) jest porządkiem \(\displaystyle{ S}\), łatwo to można udowodnić.
