Niech \(\displaystyle{ (X,R);(Y,S)}\) będą zbiorami liniowo uporządkowanymi takimi, że \(\displaystyle{ R}\) nie rozszerza \(\displaystyle{ S}\) i \(\displaystyle{ S}\) nie rozszerza \(\displaystyle{ R}\). Pokażemy, że \(\displaystyle{ R\cup S}\) nie jest liniowym porządkiem w \(\displaystyle{ X\cup Y.}\)
Dowód:
Ponieważ \(\displaystyle{ R}\) nie rozszerza \(\displaystyle{ S}\), to \(\displaystyle{ R\not\supset S}\), i podobnie, ponieważ \(\displaystyle{ S}\) nie rozszerza \(\displaystyle{ R}\), to \(\displaystyle{ S\not\supset R}\). Ponieważ zbiór pusty jest podzbiorem każdego zbioru, to relacje \(\displaystyle{ R,S}\) są niepuste. Zatem zaprzeczając definicji zawierania zbiorów otrzymujemy, że istnieje para \(\displaystyle{ (a,b)\in S}\) taka, że \(\displaystyle{ (a,b)\not\in R}\), i podobnie istnieje para \(\displaystyle{ (c,d)\in R}\), taka, że \(\displaystyle{ (c,d)\not\in S}\). Wtedy \(\displaystyle{ a\in S_L}\), ale \(\displaystyle{ S}\) jest zwrotna w \(\displaystyle{ Y}\), więc \(\displaystyle{ S_L=Y}\), a więc \(\displaystyle{ a\in Y}\). Podobnie, mamy \(\displaystyle{ c\in R_L}\), ale \(\displaystyle{ R}\) jest zwrotna w \(\displaystyle{ X}\), wobec czego \(\displaystyle{ R_L=X}\), a więc \(\displaystyle{ c\in X}\). Zatem również \(\displaystyle{ a,c\in X\cup Y.}\)
I.Rozważmy najpierw przypadek gdy zbiory \(\displaystyle{ X,Y}\) są rozłączne. Wtedy \(\displaystyle{ R\cup S}\) jest relacją częściowego porządku (suma dwóch relacji porządku na zbiorach rozłącznych jest relacją porządku). Przypuśćmy, nie wprost, ze jest to liniowy porządek. Wtedy \(\displaystyle{ R\cup S}\) jest relacją spójną w \(\displaystyle{ X\cup Y}\). A zatem \(\displaystyle{ (a,c)\in R\cup S}\) lub \(\displaystyle{ (c,a)\in R\cup S.}\)
Jeśli \(\displaystyle{ (a,c)\in R}\), to \(\displaystyle{ a\in R_L}\), ale ponieważ \(\displaystyle{ R}\) jest zwrotna w \(\displaystyle{ X}\), więc \(\displaystyle{ R_L=X}\), więc \(\displaystyle{ a\in X}\), a \(\displaystyle{ a\in Y}\), więc \(\displaystyle{ a\in X\cap Y}\), a zbiory \(\displaystyle{ X,Y}\) są rozłączne- sprzeczność.
Jeśli \(\displaystyle{ (a,c)\in S}\), to \(\displaystyle{ c\in S_P}\), ale \(\displaystyle{ S}\) jest zwrotna w \(\displaystyle{ Y}\), więc \(\displaystyle{ S_P=Y}\), więc \(\displaystyle{ c\in Y}\), a mamy \(\displaystyle{ c\in X}\), co daje sprzeczność z tym, że zbiory \(\displaystyle{ X}\) i \(\displaystyle{ Y}\) są rozłączne.
Zatem \(\displaystyle{ (a,c)\not\in R\cup S. }\)
Jeśli \(\displaystyle{ (c,a)\in R}\), to \(\displaystyle{ a\in R_P=X}\) (\(\displaystyle{ R}\) jest zwrotna w \(\displaystyle{ X}\)), lecz \(\displaystyle{ a\in Y}\), co wobec rozłączności zbiorów \(\displaystyle{ X}\) i \(\displaystyle{ Y}\) daje sprzeczność.
Jeśli \(\displaystyle{ (c,a)\in S}\), to \(\displaystyle{ c\in S_L=Y}\) (\(\displaystyle{ S}\) jest zwrotna w \(\displaystyle{ Y}\)), więc \(\displaystyle{ c\in Y}\), a mamy \(\displaystyle{ c\in X}\), co podobnie daje sprzeczność.
II. Rozważmy teraz przypadek gdy pewien element \(\displaystyle{ x\in X\cap Y}\) jest elementem wspólnym zbiorów \(\displaystyle{ X}\) i \(\displaystyle{ Y}\).
1.Rozważmy podprzypadek gdy \(\displaystyle{ Y \setminus X=\emptyset.}\)
Wtedy \(\displaystyle{ Y\subset X}\), więc \(\displaystyle{ X\cup Y=X}\), ponieważ \(\displaystyle{ (X,R)}\) jest zbiorem liniowo uporządkowanym \(\displaystyle{ a,b\in Y\subset X}\), więc \(\displaystyle{ a,b\in X}\), mamy \(\displaystyle{ (a,b)\not\in R}\), więc pozostaje możliwość \(\displaystyle{ (b,a)\in R}\), więc \(\displaystyle{ (b,a)\in R\cup S}\), mamy \(\displaystyle{ (a,b)\in S}\), więc para \(\displaystyle{ (a,b)\in R\cup S}\). Mamy również \(\displaystyle{ a \neq b}\), gdyż \(\displaystyle{ a,b \in Y\cap X}\), więc ze zwrotności \(\displaystyle{ R}\), mamy \(\displaystyle{ (a,a)\in R}\), więc nie może być \(\displaystyle{ a=b}\), gdyż \(\displaystyle{ (a,b)\not\in R}\). A zatem mamy \(\displaystyle{ a \neq b, (b,a)\in R\cup S, (a,b)\in R\cup S}\), co oznacza, ze \(\displaystyle{ R\cup S}\) nie jest antysymetryczna, a więc nie jest liniowym porządkiem.
2. Jeśli \(\displaystyle{ X \setminus Y=\left\{ \right\}}\), to rozumujemy analogicznie jak w poprzednim punkcie.
3.0. \(\displaystyle{ X \setminus Y \neq \left\{ \right\}}\) i \(\displaystyle{ Y \setminus X \neq \left\{ \right\} }\), i dla pewnego \(\displaystyle{ x'\in X \setminus Y}\) zachodzi \(\displaystyle{ x'(R)x}\); oraz dla pewnego \(\displaystyle{ x''\in Y \setminus X}\), zachodzi \(\displaystyle{ x(S) x''.}\)
Wtedy \(\displaystyle{ (x',x)\in R}\), i \(\displaystyle{ (x',x)\in R\cup S}\), i podobnie \(\displaystyle{ (x,x'')\in R\cup S}\), lecz \(\displaystyle{ (x',x'') \not\in R \cup S}\) (łatwo się o tym przekonać rozumując nie wprost). a zatem \(\displaystyle{ R\cup S}\) nie jest przechodnia, i nie jest liniowym porządkiem.
3a) \(\displaystyle{ X \setminus Y \neq \left\{ \right\}}\) i \(\displaystyle{ Y \setminus X \neq \left\{ \right\}}\), i gdy dla każdego \(\displaystyle{ x'\in X \setminus Y}\) zachodzi \(\displaystyle{ x(R)x'.}\)
Niech \(\displaystyle{ x' \in X \setminus Y \neq \left\{ \right\}}\), niech \(\displaystyle{ x'' \in Y \setminus X \neq \left\{ \right\}}\), wtedy oczywiście, z założenia \(\displaystyle{ x(R)x'}\), więc \(\displaystyle{ (x,x')\in R\cup S}\). Mamy \(\displaystyle{ x''\in Y, x\in Y}\). Ponieważ \(\displaystyle{ (Y,S)}\) jest zbiorem liniowo uporządkowanym, więc \(\displaystyle{ (x'',x)\in S}\) lub \(\displaystyle{ (x,x'')\in S. }\)
Jeśli \(\displaystyle{ (x,x'')\in S}\). to ja stwierdzam, że elementy \(\displaystyle{ x',x''}\) są nieporównywalne względem relacji \(\displaystyle{ R\cup S}\). Jeśli bowiem \(\displaystyle{ (x',x'')\in R\cup S}\), to naturalnie jest rozważyć dwa przypadki.
\(\displaystyle{ (x',x'')\in R}\), wtedy \(\displaystyle{ x''\in R_P,}\) ale \(\displaystyle{ R}\) jest zwrotna w \(\displaystyle{ X}\), więc \(\displaystyle{ R_P=X}\), a więc \(\displaystyle{ x''\in X}\), a \(\displaystyle{ x''\in Y \setminus X}\)- sprzeczność.
Jeśli \(\displaystyle{ (x',x'')\in S}\), to \(\displaystyle{ x'\in S_L=Y}\)( \(\displaystyle{ S}\) jest zwrotna w \(\displaystyle{ Y}\)), a \(\displaystyle{ x'\in X \setminus Y}\)-sprzeczność.
Jeśli \(\displaystyle{ (x'',x')\in R\cup S}\), to znowu rozpatrujemy dwa przypadki, i łatwo otrzymujemy (w obydwu przypadkach) sprzeczność.
A zatem \(\displaystyle{ (x',x'')\not\in R\cup S}\), i \(\displaystyle{ (x'',x')\not\in R\cup S}\), a więc \(\displaystyle{ R\cup S}\) nie jest spójna, i nie jest liniowym porządkiem.
jeśli \(\displaystyle{ (x,x'')\not\in S}\), więc pozostaje możliwość \(\displaystyle{ (x'',x)\in S}\); wtedy \(\displaystyle{ (x'',x)\in R\cup S}\), \(\displaystyle{ (x,x')\in R\cup S}\), lecz \(\displaystyle{ (x'',x')\not\in R\cup S}\) (łatwo to- rozważając dwa przypadki, łatwo się o tym przekonać); a zatem to oznacza, że relacja \(\displaystyle{ R\cup S}\) nie jest przechodnia.
3b)\(\displaystyle{ X \setminus Y \neq \left\{ \right\}}\) i \(\displaystyle{ Y \setminus X \neq \left\{ \right\}}\), i gdy dla każdego \(\displaystyle{ x''\in Y \setminus X}\) zachodzi \(\displaystyle{ x''(S)x.}\)
Rozumujemy analogicznie jak poprzednio, może podam tylko szkic dowodu. Niech \(\displaystyle{ x'' \in Y \setminus X \neq \left\{ \right\}}\), niech \(\displaystyle{ x' \in X \setminus Y \neq \left\{ \right\} }\), wtedy, z założenia \(\displaystyle{ x''(S) x}\). Ponieważ \(\displaystyle{ x\in X\cap Y, x'\in X}\), a \(\displaystyle{ (X,R)}\) jest zbiorem liniowo uporządkowanym, więc \(\displaystyle{ (x,x')\in R}\) lub \(\displaystyle{ (x',x)\in R}\) . Jeśli \(\displaystyle{ (x',x)\in R}\), to ja stwierdzam, że elementy \(\displaystyle{ x', x'' }\) są nieporównywalne względem \(\displaystyle{ R\cup S}\) (co uzasadniam sprawdzając cztery proste przypadki, i doprowadzam je do sprzeczności), a zatem \(\displaystyle{ R\cup S}\) nie jest spójna. Jeśli \(\displaystyle{ (x,x')\in R}\), to \(\displaystyle{ (x,x');(x'',x)\in R\cup S}\), lecz \(\displaystyle{ (x'',x')\in R\cup S}\) (co uzasadniam sprawdzając dwa proste przypadki), co oznacza, że \(\displaystyle{ R\cup S}\) nie jest przechodnia.
Wystarczy chyba tylko dodać, że ponieważ porządek \(\displaystyle{ R}\) na \(\displaystyle{ X}\) jest liniowy, i porządek \(\displaystyle{ S}\) na \(\displaystyle{ Y}\) jest liniowy, to są to wszystkie przypadki, co kończy dowód. \(\displaystyle{ \square}\)
A jeśli \(\displaystyle{ R}\) rozszerza \(\displaystyle{ S}\) lub \(\displaystyle{ S}\) rozszerza \(\displaystyle{ R}\), to \(\displaystyle{ R\cup S}\) jest liniowym porządkiem w \(\displaystyle{ X\cup Y.}\)
BARDZO PROSTY DOWÓD:
Jeśli \(\displaystyle{ R}\) rozszerza \(\displaystyle{ S}\), to \(\displaystyle{ R\supset S}\), a zatem \(\displaystyle{ R\cup S=R}\), ponieważ \(\displaystyle{ R}\) rozszerza \(\displaystyle{ S}\), więc również \(\displaystyle{ X\supset Y}\), a więc \(\displaystyle{ X\cup Y=X}\), ponieważ \(\displaystyle{ (X, R)}\) jest zbiorem liniowo uporządkowanym, czyli relacja \(\displaystyle{ R}\) jest liniowym porządkiem na \(\displaystyle{ X=X\cup Y}\), więc to oznacza, że również \(\displaystyle{ R\cup S=R}\) (jako ta sama relacja) jest liniowym porządkiem na \(\displaystyle{ X=X\cup Y}\). Jeśli \(\displaystyle{ S}\) rozszerza \(\displaystyle{ R}\), to rozumujemy symetrycznie.
Podobnie, jeśli \(\displaystyle{ R}\) rozszerza \(\displaystyle{ S}\) lub \(\displaystyle{ S}\) rozszerza \(\displaystyle{ R}\), to \(\displaystyle{ R\cap S}\) jest liniowym porządkiem w \(\displaystyle{ X\cap Y.}\)
PODOBNIE PROSTY DOWÓD:
Jeśli \(\displaystyle{ R}\) rozszerza \(\displaystyle{ S}\), to \(\displaystyle{ R\supset S}\), wtedy \(\displaystyle{ R\cap S=S}\), ponieważ \(\displaystyle{ R}\) rozszerza \(\displaystyle{ S}\), to \(\displaystyle{ X\supset Y,}\) a więc \(\displaystyle{ X\cap Y=Y}\), ponieważ \(\displaystyle{ S}\) jest liniowym porządkiem w \(\displaystyle{ Y=X\cap Y}\), a \(\displaystyle{ R\cap S=S}\), więc również \(\displaystyle{ R\cap S}\) (jako ta sama relacja) jest liniowym porządkiem w \(\displaystyle{ Y=X\cap Y}\). Jeśli \(\displaystyle{ S}\) rozszrza \(\displaystyle{ R}\), to rozumujemy symetrycznie.\(\displaystyle{ \square}\)
Jest to po prostu krótszy z tych dwóch liniowych porządków, podobnie dla sumy liniowych porządków- jest to po prostu dłuższy z tych dwóch liniowych porządków. Skończone łańcuchy liniowych porządków są mało ciekawe- wtedy ich suma to po prostu najdłuższy z tych liniowych porządków. Znacznie ciekawsze są nieskończone łańcuchy liniowych porządków, i wtedy gdy mamy takich łańcuch (dla ilustracji niech będzie przeliczalny), to jego suma jest liniowym porządkiem, i jest to supremum tej rodziny liniowych porządków. Jest to powszechnie znany fakt, ale ciekawy, więcej na ten temat można przeczytać TUTAJ