Niech \(\displaystyle{ \left( X, \le\right) }\) będzie zbiorem liniowo uporządkowanym, a zbiory \(\displaystyle{ A,B\subset X}\) niech będą przedziałami początkowymi; wtedy \(\displaystyle{ (A, \le _A); \left( B, \le_B \right)}\) są zbiorami liniowo uporządkowanymi. Wykażemy, że zbiór \(\displaystyle{ B}\) jest przedziałem początkowym zbioru \(\displaystyle{ \left( A, \le _A\right) }\) lub zbiór \(\displaystyle{ A}\) jest przedziałem początkowym zbioru \(\displaystyle{ (B, \le _B).}\)
Dowód:
Ponieważ wiemy, że w zbiorze liniowo uporządkowanym, dla dwóch przedziałów początkowych jeden się zawiera w drugim, więc \(\displaystyle{ A\subset B}\) lub \(\displaystyle{ B\subset A.}\)
Jeśli \(\displaystyle{ A\subset B}\), to \(\displaystyle{ A}\) jest przedziałem początkowym zbioru \(\displaystyle{ \left( B, \le _B\right) }\)- musimy to jednak wykazać. W tym celu weźmy \(\displaystyle{ a\in A}\), oraz weźmy \(\displaystyle{ b\in B}\), takie, że \(\displaystyle{ b \le _B a}\), i pokażmy, że \(\displaystyle{ b\in A}\). Mamy, że porządek \(\displaystyle{ \le}\) jest rozszerzeniem porządku \(\displaystyle{ \le _B}\), a zatem \(\displaystyle{ b \le a}\). Ponieważ \(\displaystyle{ X\supset B\ni b \le a\in A}\), i \(\displaystyle{ A}\) jest przedziałem początkowym, więc wnioskujemy, że \(\displaystyle{ b\in A}\). A zatem \(\displaystyle{ A}\) jest przedziałem początkowym zbioru \(\displaystyle{ \left( B, \le _B\right).}\)
Jeśli \(\displaystyle{ B\subset A}\), to zbiór \(\displaystyle{ B}\) jest przedziałem początkowym zbioru \(\displaystyle{ \left( A, \le _A\right) }\)- dowód jest symetryczny, co kończy dowód.\(\displaystyle{ \square}\)
Wykażemy teraz, że jeśli zbiory \(\displaystyle{ A,B\subset X}\) są przedziałami początkowymi zbioru liniowo uporządkowanego \(\displaystyle{ \left( X, \le\right) }\), to zbiór liniowo uporządkowany \(\displaystyle{ \left( A, \le _A \right) }\)jest rozszerzeniem zbioru liniowo uporządkowanego \(\displaystyle{ \left( B, \le _B\right) }\) lub zbiór \(\displaystyle{ \left( B, \le _B\right) }\) rozszerza zbiór \(\displaystyle{ \left( A, \le _A\right). }\)
Dowód:
Ponieważ dla dwóch przedziałów początkowych jeden się zawiera w drugim, więc \(\displaystyle{ A\subset B}\) lub \(\displaystyle{ B\subset A.}\)
Jeśli \(\displaystyle{ A\subset B}\), to \(\displaystyle{ \left( B, \le _B\right) }\) rozszerza \(\displaystyle{ \left( A, \le _A\right) }\). Aby to wykazać, to: mamy \(\displaystyle{ \le _A= \le \cap \left( A \times A\right)}\), i mamy \(\displaystyle{ \le _B= \le \cap \left( B \times B\right). }\) Ponieważ \(\displaystyle{ A\subset B}\), to \(\displaystyle{ A \times A\subset B \times B}\), i dalej \(\displaystyle{ \le _A= \left[ \le \cap \left( A \times A\right)\right] \subset \left[ \le \cap \left( B \times B\right)\right] = \le _B}\), a zatem \(\displaystyle{ \left( \le _B\right)\supset \left( \le _A\right)}\), i ponieważ porządek \(\displaystyle{ \le _B}\) jest nadzbiorem porządku \(\displaystyle{ \le _A}\), to porządek \(\displaystyle{ \le _B}\) rozszerza porządek \(\displaystyle{ \le _A}\).
Jeśli \(\displaystyle{ B\subset A,}\) to \(\displaystyle{ \left( A, \le _A\right)}\) rozszerza \(\displaystyle{ \left( B, \le _B\right)}\). Aby to wykazać, to mamy \(\displaystyle{ \le _A= \le \cap \left( A \times A\right) }\) i \(\displaystyle{ \le _B= \le \cap \left( B \times B\right).}\) Ponieważ \(\displaystyle{ B\subset A}\), to \(\displaystyle{ B \times B\subset A \times A}\), i dalej \(\displaystyle{ \le _A= \left[ \le \cap \left( A \times A\right)\right] \supset \left[ \le \cap \left( B \times B\right)\right] = \le _B}\), a więc \(\displaystyle{ (\le _A)\supset \left( \le _B\right)}\), więc ponieważ porządek \(\displaystyle{ \le _A}\) jest nadzbiorem porządku \(\displaystyle{ \le _B}\), więc porządek \(\displaystyle{ \le _A}\) rozszerza porządek \(\displaystyle{ \le _B. \square }\)
Wykażemy teraz analogiczne fakty dla dwóch reszt, tzn.:
Jeśli \(\displaystyle{ \left( X, \le\right) }\) jest zbiorem liniowo uporządkowanym, a zbiory \(\displaystyle{ A,B\subset X}\) są to reszty, (wtedy \(\displaystyle{ (A, \le _A); (B, \le _B)}\) są zbiorami liniowo uporządkowanymi), i wtedy \(\displaystyle{ A}\) jest resztą \(\displaystyle{ \left( B, \le _B\right) }\) lub \(\displaystyle{ B}\) jest resztą \(\displaystyle{ \left( A, \le _A\right). }\)
O reszcie zbioru liniowo uporządkowanego można przeczytać tutaj.
Przypomnę może najpierw prosty fakt, że jeśli w zbiorze liniowo uporządkowanym \(\displaystyle{ \left( X, \le\right) }\) zbiór \(\displaystyle{ C}\) jest resztą, to w porządku odwrotnym \(\displaystyle{ \left( X, \le ^{-1}\right) }\) zbiór \(\displaystyle{ C}\) jest przedziałem początkowym. I, podobnie, jeśli \(\displaystyle{ C}\) jest przedziałem początkowym w \(\displaystyle{ \left( X, \le\right), }\) to w porządku odwrotnym \(\displaystyle{ C}\) jest resztą.
Przypominam również, ze w zbiorze liniowo uporządkowanym, dla dwóch reszt jedna się zawiera w drugiej.
Przejdźmy zatem do naszego dowodu.
Dowód:
Ponieważ zbiory \(\displaystyle{ A,B}\) są to reszty w \(\displaystyle{ \left( X, \le\right) }\) , to w porządku odwrotnym \(\displaystyle{ \left( X, \le ^{-1}\right) }\) zbiory \(\displaystyle{ A,B}\) są przedziałami początkowymi. Na mocy pierwszego twierdzenia udowodnionego w tym poście otrzymujemy, że zbiór \(\displaystyle{ A}\) jest przedziałem początkowym zbioru \(\displaystyle{ \left( B,\left( \le ^{-1} \right)_{|B}\right) }\) lub zbiór \(\displaystyle{ B}\) jest przedziałem początkowym zbioru \(\displaystyle{ \left( A, \left( \le ^{-1}\right) _{|A}\right)}\), gdzie \(\displaystyle{ \left( \le ^{-1}\right) _{|B} }\) oznacza porządek odwrotny \(\displaystyle{ \le ^{-1}}\) zawężony do zbioru \(\displaystyle{ B}\), podobnie \(\displaystyle{ \left( \le ^{-1}\right) _{|A} }\) oznacza tu ten porządek odwrotny zawężony do zbioru \(\displaystyle{ A}\). Jeśli \(\displaystyle{ A}\) jest przedziałem początkowym zbioru \(\displaystyle{ \left( B,\left( \le ^{-1} \right)_{|B}\right) }\), to \(\displaystyle{ A}\) jest resztą w \(\displaystyle{ \left( B,\left( \left( \le ^{-1} \right) _{|B} \right) ^{-1} \right) .}\) Chcemy natomiast pokazać, że zbiór \(\displaystyle{ A}\) jest resztą w \(\displaystyle{ \left( B, \le _B\right). }\) Pozostaje zatem pokazać, że porządek \(\displaystyle{ \left( \left( \le ^{-1} \right) _{|B} \right) ^{-1}}\) jest równy porządkowi \(\displaystyle{ \le _B.}\) Ponieważ relacja odwrotna do przekroju dwóch relacji jest przekrojem relacji odwrotnych, więc otrzymujemy:
\(\displaystyle{ \left( \left( \le ^{-1} \right) _{|B} \right) ^{-1} =\left[ \left( \le ^{-1} \right) \cap \left( B \times B \right) \right] ^{-1}= \left( \le ^{-1} \right) ^{-1} \cap \left( B \times B\right) ^{-1}=}\)
i ponieważ mamy prosty fakt, że jeśli w iloczynie kartezjańskim \(\displaystyle{ Y \times Z}\) mamy iloczyn \(\displaystyle{ C \times D}\)(gdzie \(\displaystyle{ C\subset Y, D\subset Z}\)), to \(\displaystyle{ \left( C \times D\right) ^{-1}= D \times C}\)- relacją odwrotną do prostokąta \(\displaystyle{ C \times D}\) jest prostokąt \(\displaystyle{ D \times C}\) (to bardzo prosty fakt), więc u nas \(\displaystyle{ \left( B \times B\right) ^{-1} =B \times B}\), więc kontynuując równości otrzymujemy, że ostatnie wyrażenie jest równe:
\(\displaystyle{ =\le \cap \left( B \times B\right) = \le _B.}\)
Ponieważ zbiór \(\displaystyle{ A}\) jest resztą w zbiorze \(\displaystyle{ B}\) względem \(\displaystyle{ \left( \left( \le ^{-1} \right) _{|B} \right) ^{-1}}\), a ten porządek jest tym samym porządkiem co porządek \(\displaystyle{ \le _B}\), to również zbiór \(\displaystyle{ A}\) jest resztą w zbiorze \(\displaystyle{ B}\) względem \(\displaystyle{ \le _B.}\)
jeśli zbiór \(\displaystyle{ B}\) jest przedziałem początkowym zbioru \(\displaystyle{ \left( A, \left( \le ^{-1}\right) _{|A}\right),}\) to \(\displaystyle{ B}\) jest resztą w porządku odwrotnym \(\displaystyle{ \left( A, \left( \left( \le ^{-1}\right) _{|A} \right) ^{-1}\right) .}\) Chcemy natomiast pokazać, że zbiór \(\displaystyle{ B}\) jest resztą w zbiorze \(\displaystyle{ \left( A, \le _A\right). }\) Pozostaje pokazać, że te dwa porządki są równe. Mamy:
\(\displaystyle{ \left( \left( \le ^{-1}\right) _{|A} \right) ^{-1} =\left[ \le ^{-1} \cap \left( A \times A\right) \right] ^{-1}= \left( \le ^{-1} \right) ^{-1} \cap \left( A \times A\right) ^{-1}= \le \cap \left( A \times A\right) = \le _A,}\)
więc również zbiór \(\displaystyle{ B}\) jest resztą w zbiorze liniowo uporządkowanym \(\displaystyle{ \left( A, \le _A \right). \square}\)
Wykażemy na koniec, że jeśli \(\displaystyle{ \left( X, \le\right) }\) jest zbiorem liniowo uporządkowanym, oraz mamy dwie reszty \(\displaystyle{ A,B\subset X}\), (wtedy \(\displaystyle{ \left( A, \le _A\right) ; \left( B, \le _B\right)}\) są zbiorami liniowo uporządkowanymi ), i wtedy zbiór liniowo uporządkowany \(\displaystyle{ \left( A, \le\right) }\) rozszerza zbiór liniowo uporządkowany \(\displaystyle{ \left( B, \le _B\right) }\) lub zbiór \(\displaystyle{ \left( B, \le _B\right) }\) rozszerza zbiór \(\displaystyle{ \left( A, \le _A\right).}\)
Nim to udowodnimy, przypomnijmy prosty fakt, że dopełnienie reszty jest zawsze przedziałem początkowym i dopełnienie przedziału początkowego jest zawsze resztą.
Podajmy jeszcze taki dziwny lemat (ale będzie za to bardzo pomocny), że jeśli \(\displaystyle{ (X, \le)}\) jest zbiorem liniowo uporządkowanym, a zbiory \(\displaystyle{ A,B\subset X}\) są jego podzbiorami, jeśli rozważymy zbiory liniowo uporządkowane \(\displaystyle{ \left( A, \le _A\right) ; \left( B, \le _B\right)}\), i jeśli zbiór \(\displaystyle{ \left( B, \le _B\right) }\) rozszerza zbiór \(\displaystyle{ \left( A , \le _A\right) }\), to dla dopełnień zbiorów ( do zbioru \(\displaystyle{ X}\)) mamy, że zbior \(\displaystyle{ \left( A^{\prime} \le _{A^{\prime} }\right) }\) rozszerza zbiór \(\displaystyle{ \left( B^{\prime}, \le _{B^{\prime}}\right) . }\)
Coś dziwny ten lemat, ale będzie nam za to bardzo pomocny. W ukrytej treści przedstawiam dowód tego lematu:
DOWÓD:
Dowód:
Ponieważ zbiory \(\displaystyle{ A,B}\) są to reszty, to ich dopełnienia \(\displaystyle{ A^{\prime}, B^{\prime}}\) są przedziałami początkowymi. Są one podzbiorami \(\displaystyle{ X}\), naszego zbioru liniowo uporządkowanego, (i są przedziałami początkowymi ) więc zgodnie z jednym faktów który wykazałem, o tym, że dla dwóch przedziałów początkowych jeden jest rozszerzeniem drugiego, więc \(\displaystyle{ \left( A^{\prime}, \le _{|A^{\prime}}\right) }\) rozszerza \(\displaystyle{ \left( B^{\prime}, \le _{|B^{\prime}}\right) }\) lub \(\displaystyle{ (B^{\prime} ,\le _{|B^{\prime}})}\) rozszerza \(\displaystyle{ \left( A^{\prime}, \le _{|A^{\prime}}\right) .}\) Jeśli \(\displaystyle{ \left( A^{\prime}, \le _{|A^{\prime}}\right) }\) rozszerza \(\displaystyle{ \left( B^{\prime}, \le _{|B^{\prime}}\right) }\), to na mocy lematu powyżej \(\displaystyle{ \left( B=(B^{\prime})^{\prime}, \le _B\right)}\) rozszerza \(\displaystyle{ \left( A=(A^{\prime})^{\prime}, \le _A\right) }\). Jeśli \(\displaystyle{ \left( B^{\prime}, \le _{|B^{\prime}}\right) }\) rozszerza \(\displaystyle{ \left( A^{\prime}, \le _{|A^{\prime}} \right) }\), to podobnie, na mocy tego samego lematu, \(\displaystyle{ \left( A=(A^{\prime})^{\prime}, \le _A\right)}\) rozszerza \(\displaystyle{ \left( B=(B^{\prime})^{\prime}, \le _B\right) .\square}\)
Dodam jeszcze, że jak już chyba chyba można było zauważyć, że w zbiorze liniowo uporządkowanym dla dwóch przedziałów początkowych jeden się zawiera w drugim. Wynika stąd, że suma dwóch przedziałów początkowych jest przedziałem początkowym- jest to prostu dłuższy z tych dwóch przedziałów początkowych. Podobnie przekrój dwóch przedziałów początkowych jest przedziałem początkowym- jest to po prostu krótszy z tych dwóch przedziałów początkowych. Podobne zależności dostrzegamy dla reszty- ponieważ w zbiorze liniowo uporządkowanym dla dwóch reszt jedna się zawiera w drugiej, to suma dwóch reszt jest resztą (dłuższą), i przekrój dwóch reszt jest resztą ( krótszą). Mamy też fakt, że dopełnienie przedziału początkowego jest resztą, i dopełnienie reszty jest przedziałem początkowym.