Suma typów liniowych porządków

[Jakub Gurak]

Poszukuję dowodu twierdzenia, że suma typów dwóch liniowych porządków jest typem liniowego porządku. Wystarczy sam dowód, że jest to liniowy porządek. W Guzickim, było formułowane stosowne twierdzenie, nie pamiętam czy był dowód. Gdzie mogę go znaleźć

Być może dowód jest prosty, ale tym razem, zgodnie z poradą, może sięgnę po książki, tym bardziej, że to twierdzenie, w niektórych sytuacjach użyte, może być zaskakujące. Potrzebuje do kompendium.

[Jakub Gurak]

Spróbuję to udowodnić (w sposób elementarny). Niech \(\displaystyle{ \left( A, \le _{A} \right) ; \left( B, \le _{B} \right)}\) będą zbiorami liniowo uporządkowanymi, przy czym zbiory \(\displaystyle{ A,B}\) są rozłączne. Rozważamy sumę \(\displaystyle{ \left( A, \le _{A} \right) \oplus \left( B, \le _{B} \right)=\left( A \cup B,\le _{A} \cup \le _{B} \cup \left( A \times B\right) \right).}\) Czyli na zbiorach \(\displaystyle{ A,B}\) porządki są takie same jak we wejściowych zbiorach, i do tego każdy element zbioru \(\displaystyle{ A}\) jest mniejszy od każdego elementu zbioru \(\displaystyle{ B}\).

Po pierwsze, zauważmy, że tak zdefiniowana suma relacji jest relacją na \(\displaystyle{ A \cup B}\). Ponieważ \(\displaystyle{ \le _{A}}\) jest relacją liniowego porządku na \(\displaystyle{ A}\), więc formalnie jest podzbiorem \(\displaystyle{ A \times A}\), a więc tym bardziej jest podzbiorem \(\displaystyle{ \left( A \cup B\right) \times \left( A \cup B\right),}\) Podobnie ponieważ \(\displaystyle{ \le _{B}}\) jest relacją liniowego porządku na \(\displaystyle{ B}\), więc formalnie jest podzbiorem \(\displaystyle{ B \times B}\), a więc tym bardziej jest podzbiorem \(\displaystyle{ \left( A \cup B\right) \times \left( A \cup B\right)}\) i również \(\displaystyle{ A\times B \subset \left( A \cup B\right) \times \left( A \cup B\right).}\) W efekcie ich suma jest również podzbiorem \(\displaystyle{ \left( A \cup B\right) \times \left( A \cup B\right)}\) a więc jest relacją w \(\displaystyle{ A \cup B}\) Będziemy ją oznaczać \(\displaystyle{ \le _{\oplus}}\)

Sprawdzamy zwrotność, antysymetrię, przechodniość i spójność.

Zwrotność. Ponieważ \(\displaystyle{ \le _{A}}\) jest relacją liniowego porządku na \(\displaystyle{ A}\), więc jest zwrotna w zbiorze \(\displaystyle{ A}\), a więc zawiera \(\displaystyle{ I_A}\) identyczność na \(\displaystyle{ A}\). Podobnie \(\displaystyle{ \le _{B}}\) zawiera \(\displaystyle{ I_B}\) identyczność na \(\displaystyle{ B}\), wobec czego \(\displaystyle{ \le _{\oplus}}\) zawiera \(\displaystyle{ I_A \cup I _{B}.}\) Ponieważ zbiory \(\displaystyle{ A,B}\) są rozłączne więc \(\displaystyle{ I _{A \cup B}=I_A \cup I _{B}.}\) W efekcie \(\displaystyle{ \le _{\oplus}}\) zawiera \(\displaystyle{ I _{A \cup B}}\), a więc jest zwrotna w zbiorze \(\displaystyle{ A\cup B}\).

Antysymetria. Załóżmy, że \(\displaystyle{ x\le _{\oplus}y}\) i \(\displaystyle{ y\le _{\oplus}x.}\)

Dobra, nie chcę mi się. Czas na takie dowody był kilka lat temu, wtedy dowodziłem tylko bardzo konkretny fakt, że zbiorem liniowo uporządkowanym jest zbiór liczb rzeczywistych z dodanym elementem \(\displaystyle{ - \infty}\) jako najmniejszym i \(\displaystyle{ + \infty}\) jako największym. A resztę (twierdzenie z tego tematu) jakoś przełknąłem. Może powinienem wtedy to przestudiować. Ale teraz czasu nie cofnę, a teraz musiałbym też, dowodząc to, uważać żeby korzystać tylko z elementarnych faktów.

\(\displaystyle{ \left( \RR, \le \right) \oplus \left( \RR,\le \right) \not\approx \left( \RR ,\le \right).}\)

Przypomnijmy, że gdy zbiory nie są rozłączne (tak jak teraz), to rozpatrujemy tu \(\displaystyle{ \RR\times\left\{ 0\right\}}\) i \(\displaystyle{ \RR\times\left\{ 1\right\}}\) Wtedy będziemy mieli rozłączność. Porządki na tych zmienionych zbiorach wyglądają prawie tak samo jak zwykły porządek na liczbach rzeczywistych( z tą różnicą, że rozpatrujemy te punkty płaszczyzny w drugim przypadku na prostej \(\displaystyle{ y=1}\), w pierwszym na osi \(\displaystyle{ x}\), ale też są to formalnie pary). I teraz mamy sumę porządkową, gdzie każda (dowolnie duża) liczba rzeczywista na poziomie \(\displaystyle{ 0}\)( na osi \(\displaystyle{ x}\)) jest mniejsza od każdej (dowolnie małej) liczby rzeczywistej na poziomie \(\displaystyle{ 1}\)( na prostej \(\displaystyle{ y=1}\)) Tak, zbiory nieskończone są niezwykłe.

Ponieważ w \(\displaystyle{ \RR}\) ze zwykłym porządkiem nie ma liczby największej, więc w podobnym porządku \(\displaystyle{ \RR \times \left\{ 0\right\}}\) nie ma elementu największego. Podobnie, ponieważ w w \(\displaystyle{ \RR}\) ze zwykłym porządkiem nie ma liczby najmniejszej, więc w podobnym porządku \(\displaystyle{ \RR \times \left\{ 1\right\}}\) nie ma elementu najmniejszego.

Para zbiorów \(\displaystyle{ \left( \RR \times \left\{ 0\right\}, \RR \times \left\{ 1\right\}\right)}\) tworzy niewątpliwie przekrój Dedekinda w \(\displaystyle{ \RR \times \left\{ 0,1\right\}.}\) Ponieważ w klasie dolnej nie ma elementu największego i w klasie górnej nie ma elementu najmniejszego, to ten przekrój Dedekinda daje lukę, a więc zbiór liniowo uporządkowany \(\displaystyle{ \left( \RR \times \left\{ 0,1\right\}, \le _{\oplus} \right)}\) nie jest ciągły. Ponieważ zbiór liczb rzeczywistych z naturalnym porządkiem jest ciągły, i ponieważ ciągłość jest przenoszona przez podobieństwo zbiory liniowo uporządkowane \(\displaystyle{ \left( \RR \times \left\{ 0,1\right\}, \le _{\oplus} \right)}\) oraz \(\displaystyle{ \left( \RR , \le\right)}\) nie mogą być podobne, a więc \(\displaystyle{ \left( \RR \times \left\{ 0,1\right\}, \le _{\oplus} \right) \approx \left( \RR, \le \right) \oplus \left( \RR,\le \right) \not\approx \left( \RR ,\le \right).}\)


Parę wyjaśnień muszę podać.

Ukryta treść:    

Wiadomo co to jest przekrój Dedekinda w zbiorze liniowo uporządkowanym \(\displaystyle{ \left( X, \le \right)}\). Jest to para \(\displaystyle{ \left( A,B\right)}\) podzbiorów \(\displaystyle{ X}\), która tworzy 'rozcięcie' zbioru \(\displaystyle{ X}\). Zbiór \(\displaystyle{ A}\) nazywamy klasą dolną przekroju, zbiór \(\displaystyle{ B}\) nazywamy klasą górną przekroju. Zobacz ilustrację:



Przekrój \(\displaystyle{ \left( A,B\right)}\) w \(\displaystyle{ \left( X, \le \right)}\) zbiorze liniowo uporządkowanym, przekrój daję lukę jeśli w klasie dolnej nie ma elementu największego, i w klasie górnej \(\displaystyle{ B}\) nie ma elementu najmniejszego. Na 'rozcięciu' tych zbiorów jest więc 'luka'.



Zbiór liniowo uporządkowany \(\displaystyle{ \left( X, \le \right)}\) nazywamy (prawie)ciągłym gdy żaden przekrój nie daję luki.

Użyłem słowa prawie ciągły, bo ja niechętny jestem na taką definicję, gdyż przy takiej definicji zbiór liczb naturalnych ze zwykłym porządkiem jest ciągły- właśnie w takim sensie- żaden przekrój nie daję luki.

Przekrój \(\displaystyle{ \left( A,B\right)}\) w \(\displaystyle{ \left( X, \le \right)}\) zbiorze liniowo uporządkowanym, przekrój daję skok jeśli w klasie dolnej jest elementu największy, i w klasie górnej jest element najmniejszy. Zobacz ilustrację:
[url=https://naforum.zapodaj.net/8665e89c540e.jpg.html][/url]

Zbiór liniowo uporządkowany \(\displaystyle{ \left( X, \le \right)}\) nazywamy gęstym gdy dla dowolnych elementów \(\displaystyle{ x,y\in X}\), takich, że \(\displaystyle{ x<y}\) można dobrać \(\displaystyle{ z\in X}\) tak, że \(\displaystyle{ x<z<y.}\) Czyli gdy pomiędzy dwoma dowolnymi różnymi elementami możemy znaleźć trzeci element pośredni pomiędzy nimi.

Twierdzenie Zbiór liniowo uporządkowany \(\displaystyle{ \left( X, \le \right)}\) jest gęsty równoważnie gdy żaden przekrój nie daję skoku.

Właśnie ponieważ w zbiorze liczb naturalnych ze zwykłym porządkiem są przekroje dające skok lub równoważnie porządek nie jest gęsty, stąd taka patologiczna sytuacja powstała. Warto wiec żądać na zbiór liniowo uporządkowany ciągły aby był gęsty, lub równoważnie, aby żaden przekrój nie dawał skoku.

Twierdzenie

Niech \(\displaystyle{ \left( X, \le \right)}\) będzie zbiorem liniowo uporządkowanym. Wtedy poniższe warunki są równoważne

(1) \(\displaystyle{ \left( X, \le \right)}\) jest (prawie) ciągły
(2) Każdy niepusty zbiór \(\displaystyle{ A \subset X}\) ograniczony od góry ma supremum
(3) Każdy niepusty zbiór \(\displaystyle{ A \subset X}\) ograniczony od dołu ma infimum.

Pokażemy wynikanie (2)\(\displaystyle{ \rightarrow}\)(3)

Załóżmy (2) Aby pokazać (3) weźmy dowolny niepusty zbiór \(\displaystyle{ A\subset X}\) ograniczony od dołu. Pokażemy, ze \(\displaystyle{ A}\) ma infimum. Rozważmy zbiór \(\displaystyle{ B}\) wszystkich ograniczeń dolnych \(\displaystyle{ A}\). Ponieważ \(\displaystyle{ A}\) jest ograniczony od dołu, to zbiór \(\displaystyle{ B}\) jest niepusty. Jest on ograniczony od góry przez elementy \(\displaystyle{ A \neq \left\{ \right\}}\). Zatem w myśl (2) zbiór \(\displaystyle{ B}\) ma supremum, i pokazujemy że to supremum jest infimum zbioru \(\displaystyle{ A}\) na prawo. Zobacz ilustrację obok:

[url=https://naforum.zapodaj.net/8647e8e2dabc.jpg.html][/url]

(3)\(\displaystyle{ \rightarrow}\)(2)- symetrycznie

Twierdzenie Gęstość jest przenoszona przez podobieństwo.

Zbiór liniowo uporządkowany \(\displaystyle{ \left( X, \le \right)}\) nazywamy ciągłym, gdy jest gęsty i żaden przekrój Dedekinda nie daje luki.(Nie ma w nim dziur)

Przypomnijmy, że podobieństwem między zbiorami liniowo uporządkowanymi \(\displaystyle{ \left( X, \le _{X} \right),\left( Y, \le _{Y} \right)}\) nazywamy funkcję \(\displaystyle{ f: X\rightarrow Y}\), która jest bijekcją, taką że \(\displaystyle{ x\le _{X}y \Longleftrightarrow f(x)\le _{Y} f(y)}\), dla dowolnych \(\displaystyle{ x,y\in X.}\)

Twierdzenie Ciągłość jest przenoszona przez podobieństwo.

Szkic dowodu: Niech \(\displaystyle{ \left( X, \le _{X} \right),\left( Y, \le _{Y} \right)}\) będą zbiorami liniowo uporządkowanymi, takimi że zbiór uporządkowany \(\displaystyle{ \left( X, \le _{X} \right)}\) jest ciągły. A \(\displaystyle{ f:X \rightarrow Y}\) będzie podobieństwem. Pokażemy, że zbiór \(\displaystyle{ \left( Y, \le _{Y} \right)}\) jest ciągły. Ponieważ \(\displaystyle{ \left( X, \le _{X} \right)}\) jest ciągły, a więc i gęsty, więc również w myśl poprzedniego twierdzenia \(\displaystyle{ \left( Y, \le _{Y} \right)}\) jest również gęsty. Pokażemy, że żaden przekrój w \(\displaystyle{ \left( Y, \le _{Y} \right)}\) nie daję luki. Weźmy dowolny przekrój \(\displaystyle{ \left( Y _{1} ,Y _{2} \right)}\) zbioru \(\displaystyle{ Y}\). Rozważmy przeciwobrazy \(\displaystyle{ \stackrel{ \rightarrow }{f ^{-1} }\left( Y _{1}\right), \stackrel{ \rightarrow }{f ^{-1} }\left( Y _{2}\right)}\) oznaczmy je przez \(\displaystyle{ X_1,X_2.}\) Pokazujemy, że \(\displaystyle{ \left( X _{1} ,X _{2} \right)}\) tworzy przekrój zbioru \(\displaystyle{ X}\). Ponieważ \(\displaystyle{ \left( X, \le \right)}\) jest ciągły, to w \(\displaystyle{ X_1}\) jest element największy lub w \(\displaystyle{ X_2}\) jest element najmniejszy. Załóżmy, że \(\displaystyle{ x _{1}}\) jest elementem największym w \(\displaystyle{ X_{1}}\). Pokazujemy, że (korzystając z podobieństwa- ale do końca to nawet ja sam się nie zagłębiałem ) \(\displaystyle{ f\left( x _{1}\right)}\) jest elementem największym w \(\displaystyle{ Y_1}\). Podobnie, gdy w \(\displaystyle{ X_2}\) jest element najmniejszy \(\displaystyle{ x_2}\), to pokazujemy że \(\displaystyle{ f\left( x _{2}\right)}\) jest elementem najmniejszym w \(\displaystyle{ Y_2}\). Łącznie to oznacza, że w \(\displaystyle{ Y_1}\) jest element największy lub w \(\displaystyle{ Y_2}\) jest element najmniejszy. Oznacza to, że przekrój \(\displaystyle{ \left( Y _{1} ,Y _{2} \right)}\) nie daje luki. Wobec dowolności przekroju, żaden przekrój \(\displaystyle{ Y}\) nie daje luki,i \(\displaystyle{ Y}\) jest gęsty, a więc \(\displaystyle{ \left( Y, \le \right)}\) jest ciągły.\(\displaystyle{ \square}\)

Twierdzenie \(\displaystyle{ \left( \RR, \le \right)}\) jest ciągły.

Szkic konstrukcji:

Weźmy przekrój \(\displaystyle{ \left( X,Y\right)}\) w \(\displaystyle{ \RR}\) Ustalmy na początek liczby wymierne \(\displaystyle{ x_0}\) w \(\displaystyle{ X}\) i \(\displaystyle{ y_0}\) w \(\displaystyle{ Y}\)( to też wymaga pewnego (prostego) uzasadnienia). Definiujemy indukcyjnie dwa ciągi liczb wymiernych \(\displaystyle{ \left( x _{n} \right)}\) elementów \(\displaystyle{ X}\) oraz ciąg liczb wymiernych \(\displaystyle{ \left( y _{n} \right)}\) elementów \(\displaystyle{ Y}\), tak, że ciąg \(\displaystyle{ x}\) jest słabo rosnący, a ciąg \(\displaystyle{ y}\) jest (słabo) malejący( i chcemy liczbami wymiernymi przybliżać się do 'rozcięcia' przekroju). Zobacz ilustrację obok:

[url=https://naforum.zapodaj.net/909bac889572.jpg.html][/url]

Odcinek \(\displaystyle{ \left( x_0,y_0\right)}\) dzielimy na pół i tą środkową wartość zaliczamy jako kolejny element tego z ciągów \(\displaystyle{ x,y}\) w zależności od tego do którego ze zbiorów \(\displaystyle{ X,Y}\) ta liczba wymierna wpadnie- u mnie na rysunku wpadło do klasy górnej, więc to jest nasz \(\displaystyle{ y_1}\), w takim wypadku za \(\displaystyle{ x_1}\) pozostawiamy poprzedni wyraz \(\displaystyle{ x_0}\), czyli definiujemy \(\displaystyle{ x_1=x_0.}\) Dalej patrzymy na odcinek \(\displaystyle{ \left( x_1,y_1\right)}\) dzielimy go na pół, i ponieważ ta środkowa wartość (akurat u mnie) wpadła do klasy dolnej, więc to jest nasze \(\displaystyle{ x_2}\), nie wpadła do klasy górnej więc tam nowy wyraz ciągu pozostawiamy taki jaki był, czyli \(\displaystyle{ y_2=y_1}\), odcinek \(\displaystyle{ \left( x_n,y_n\right)}\) dzielimy na pół (niech \(\displaystyle{ a:= \frac{x_n+y_n}{2}}\)) , i jeśli \(\displaystyle{ a\in X}\) to to jest nasze \(\displaystyle{ x _{n+1}}\), wtedy pozostawiamy bez zmian \(\displaystyle{ y _{n+1}=y_n.}\) W przeciwnym przypadku jeśli \(\displaystyle{ a\in Y}\) to to jest nasze \(\displaystyle{ y _{n+1}}\), wtedy pozostawiamy bez zmian \(\displaystyle{ x _{n+1}=x_n.}\) W ten sposób przybliżamy się (liczbami wymiernymi) do rozcięcia przekroju.

[Jakub Gurak]

No nic, nuda na forum, a trzeba coś podziałać.

Podam przykład zbioru uporządkowanego liniowo \(\displaystyle{ \left( X, \le \right)}\), w którym jest element najmniejszy, każdy element w X ma następnik, a zbiór nie jest dobrze uporządkowany.

Niewiarygodne A jednak, łatwo to (używając sumy liniowych porządków) to zrobić.

Rozważmy zbiór \(\displaystyle{ A=\NN \times \left\{ 0\right\}}\) z porządkiem \(\displaystyle{ \le _{A}}\) przeniesionym ze zbioru liczb naturalnych ze zwykłym porządkiem.

Rozważmy zbiór \(\displaystyle{ B= \ZZ \times \left\{ 1\right\}}\) z porządkiem \(\displaystyle{ \le _{B}}\) przeniesionym ze zbioru \(\displaystyle{ \ZZ}\) liczb całkowitych ze zwykłym porządkiem.

Zauważmy,że te zbiory liniowo uporządkowane są rozłączne. Rozważmy teraz sumę porządkową \(\displaystyle{ \le}\) na \(\displaystyle{ X=A \cup B.}\)

Jego elementem najmniejszym jest para \(\displaystyle{ \left( 0,0\right)}\) Każdy element \(\displaystyle{ X=A \cup B}\) ma następnik, gdyż każdy element \(\displaystyle{ A}\) ma następnik( następnikiem pary \(\displaystyle{ \left( n,0\right)}\) jest para \(\displaystyle{ \left( n+1,0\right)}\) ), i każdy element \(\displaystyle{ B}\) ma następnik ( następnikiem pary \(\displaystyle{ \left( x,1\right)}\) jest para \(\displaystyle{ \left( x+1,1\right)}\)). Wobec czego każdy element \(\displaystyle{ X=A\cup B}\) ma następnik (również względem \(\displaystyle{ \le}\), uwzględniłem to). Zbiór \(\displaystyle{ X}\) nie jest dobrze uporządkowany, gdyż w \(\displaystyle{ B= \ZZ \times \left\{ 1\right\} \subset X}\), nie ma elementu najmniejszego (gdyż w \(\displaystyle{ \ZZ}\) z naturalnym porządkiem nie ma liczby najmniejszej, więc w podobnym porządku również nie ma elementu najmniejszego).\(\displaystyle{ \square}\)

[Jakub Gurak]

Wczoraj udowodniłem, że jeśli rozważymy porządek odwrotny do sumy porządkowej dwóch zbiorów liniowo uporządkowanych, to jest to identyczne z tym że, rozważymy porządek odwrotnym na drugim zbiorze, i weźmiemy sumę porządkową z porządkiem odwrotnym na pierwszym zbiorze. I to jest ciekawe, a nie jakieś żmudne, nudne obliczenia( kto powiedział, że matematyka musi mieć związek z obliczeniami- NIKT. Za to można powiedzieć,że matematyka MUSI mieć związek z ROZUMOWANIEM, a to się zaniedbuje pisząc bzdury \(\displaystyle{ f=f _{x} }\)- FUJ, dopuszczając dzielenie przez zero, mówiąc o funkcji, mówić tylko o dziedzinie, a kompletnie nic o przeciwdziedzinie, itd.- niestety takie rażące rzeczy już w tym roku akademickim u moich wykładowców zauważyłem, a dzisiaj to wykładowca 26 minut przeciągnął zajęcia, które były "strasznie" ciekawe- żmudne wzory, itd. Ja na takich zajęciach czuję się dziwnie). No ale może już przejdę do rzeczy, która jest o stokroć ciekawsza.

Przyjmijmy notację, że jeśli \(\displaystyle{ \left( X, \le \right) }\) jest zbiorem liniowo uporządkowanym, to porządek odwrotny będziemy oznaczać (w uproszczeniu) w tym poście jako \(\displaystyle{ \ge }\), a sumę porządkową zbiorów liniowo uporządkowanych \(\displaystyle{ \left( A, \le _{A} \right);\left( B, \le _{B} \right) }\) jako \(\displaystyle{ \left( \le _{A}\oplus \le _{B}\right) .}\)

Niech \(\displaystyle{ \left( A, \le _{A} \right) ; \left( B, \le _{B} \right) }\) bedą zbiorami liniowo uporządkowanymi, tak aby zbiory \(\displaystyle{ A,B}\) były rozłączne. Wykażemy, że \(\displaystyle{ \left( A \cup B, \left( \le _{A}\oplus\le _{B} \right) ^{-1}\right) =\left( B \cup A, \ge _{B}\oplus \ge _{A} \right). }\)

Aby to wykazać, to niech \(\displaystyle{ x,y \in A \cup B.}\) Wykażemy, że

\(\displaystyle{ x \left( \le _{A}\oplus \le _{B} \right) ^{-1} y\Longleftrightarrow x \left( \ge _{B}\oplus \ge _{A} \right) y.}\)

Lewa strona równoważności jest równoważna z tym że \(\displaystyle{ y \left( \le _{A}\oplus\le _{B} \right) x }\).Aby pokazać prawą stronę równoważności, dalej rozważymy przypadki, ze względu na definicje sumy porządkowej.

1. Jeśli \(\displaystyle{ x,y\in A}\), to z definicji sumy porządkowej \(\displaystyle{ y \le _{A} x, }\) wtedy \(\displaystyle{ x \ge _{A} y, }\) a więc tym bardziej \(\displaystyle{ x\left( \ge _{B}\oplus \ge _{A}\right) y.}\)

2. Jeśli \(\displaystyle{ x,y \in B}\), to rozumujemy analogicznie.

3.Jeśli \(\displaystyle{ y\in A, x\in B}\), to \(\displaystyle{ x\left( \ge _{B}\oplus \ge _{A} \right) y}\) gdyż porządek odwrotny do danego porządku na \(\displaystyle{ B}\) jest określony również na \(\displaystyle{ B}\), i analogicznie dla porządku odwrotnego na \(\displaystyle{ A}\), więc z definicji sumy porządkowej każdy element zbioru \(\displaystyle{ B}\) jest mniejszy od każdego elementu zbioru A, względem \(\displaystyle{ \ge _{B} \oplus \ge _{A}}\), a więc \(\displaystyle{ x\left( \ge _{B} \oplus \ge _{A} \right) y.}\)

4.Jeśli \(\displaystyle{ x \in A, y \in B}\), to ten przypadek możemy od razu wykluczyć, gdyż każdy element zbioru \(\displaystyle{ A}\) jest mniejszy od każdego elementu zbioru \(\displaystyle{ B}\), względem \(\displaystyle{ \le _{A}\oplus \le _{B}}\) (I na mocy antysymetrii porządku).

Kończy to dowód jednej implikacji. Aby pokazać drugą implikacje

załóżmy, że \(\displaystyle{ x\left( \ge _{B}\oplus \ge _{A} \right) y}\) i pokażmy, że \(\displaystyle{ y\left( \le _{A}\oplus\le _{B} \right) x. }\) Znowu rozważamy przypadki:

1. \(\displaystyle{ x,y \in B }\). Wtedy \(\displaystyle{ x \ge _B y}\), wtedy \(\displaystyle{ y \le _B x }\), a więc tym bardziej \(\displaystyle{ y\left( \le _{A}\oplus \le _{B} \right)x.}\)

2. \(\displaystyle{ x,y \in A }\)- rozumujemy analogicznie jak w poprzednim punkcie.

3.\(\displaystyle{ y \in A, x \in B}\)- poniewaz względem sumy porządkowej \(\displaystyle{ \le _{A}\oplus\le _{B} }\) każdy element zbior \(\displaystyle{ A}\) jest mniejszy od każdego elementu zbioru \(\displaystyle{ B}\), natychmiast otrzymujemy \(\displaystyle{ y \left( \le _{A}\oplus \le _{B} \right) \le x.}\)

4. \(\displaystyle{ x \in A, y \in B}\)- ten przypadek jest niemożliwy, bo on prowadzi do \(\displaystyle{ y\left( \ge _{B}\oplus\ge _{A} \right) x}\), a mamy \(\displaystyle{ x\left( \ge _{B}\oplus \ge _{A} \right) y}\)- sprzeczność.

Dowód jest zakończony. \(\displaystyle{ \square}\)

[Jakub Gurak]

Mamy też prawo, że jeśli mamy trzy zbiory liniowo uporządkowane \(\displaystyle{ A,B,C}\), to zachodzi łączność sumy porządkowej \(\displaystyle{ A\oplus (B\oplus C)=(A\oplus B)\oplus C.}\) Dowód jest dosyć żmudny( raczej nie trudny, tylko trzeba wiele przypadków rozważyć). Dzięki temu można rozważyć sumę porządkową \(\displaystyle{ n}\) zbiorów liniowo uporządkowanych na zbiorach rozłącznych. I wtedy jeśli mamy takich \(\displaystyle{ n}\) zbiorów \(\displaystyle{ X_1,X_2,\ldots, X_n}\), to mamy prawo:

\(\displaystyle{ (X_1\oplus X_2\oplus\ldots \oplus X_n)^{-1}= X_n^{-1}\oplus X_{n-1}^{-1}\oplus \ldots\oplus X_1^ {-1}.}\)

Wynika to z wcześniej udowodnionego prawa dla \(\displaystyle{ n=2}\): \(\displaystyle{ (A\oplus B )^{-1}=B^{-1}\oplus A^{-1},}\) łatwo to przez indukcję porządkową można udowodnić.

Udowodniłem wczoraj, że jeżeli mamy trzy zbiory liniowo uporządkowane \(\displaystyle{ A,B,C}\), tak aby zbiory \(\displaystyle{ B,C}\) były rozłączne, to (jeżeli porządek leksykograficzny zbiorów liniowo uporządkowanych \(\displaystyle{ X,Y}\) na \(\displaystyle{ X\times Y}\) oznaczymy przez \(\displaystyle{ X\otimes Y}\)), to \(\displaystyle{ (B\oplus C)\otimes A=(B\otimes A)\oplus (C \otimes A).}\)


Że to jest identyczny porządek, nie tylko podobny, lecz nawet taki sam, identyczny. Przedstawię teraz dowód.

Dowód:

Zauważmy najpierw, że zbiory \(\displaystyle{ B\times A}\) i \(\displaystyle{ C\times A}\) są rozłączne. Aby to uzasadnić, to: ponieważ zbiory \(\displaystyle{ B,C}\) są rozłączne, więc \(\displaystyle{ (B\times A)\cap (C\times A)=(B\cap C)\times A=\emptyset\times A=\emptyset}\), a zatem zbiory \(\displaystyle{ B\times A}\) i \(\displaystyle{ C\times A}\) są rozłączne. Możemy zatem rozważać sumę porządkową porządków \(\displaystyle{ B\otimes A}\) i \(\displaystyle{ C\otimes A}\). Zauważmy teraz, że \(\displaystyle{ (B\cup C)\times A=(B\times A)\cup (C\times A)}\), a więc te dwa liniowe porządki są określone w tym samym zbiorze. Aby wykazać, że te dwa porządki są równe, to niech \(\displaystyle{ (x_1,x_2);(y_1,y_2)\in (B\cup C)\times A}\), czyli \(\displaystyle{ x_1,y_1\in B\cup C, x_2,y_2\in A}\). Pokażemy, że:

\(\displaystyle{ (x_1,x_2) \le _{(B\oplus C)\otimes A} (y_1,y_2) \Longleftrightarrow (x_1,x_2) \le _{(B\otimes A)\oplus (C\otimes A)} (y_1,y_2).}\)

Załóżmy więc najpierw lewą stronę równoważności.

Rozważmy najpierw przypadek:

1.\(\displaystyle{ x_1 \neq y_1}\), wtedy z definicji porządku leksykograficznego \(\displaystyle{ x_1 \le _{B\oplus C} y_1.}\)

Rozważmy teraz przypadki:

a) \(\displaystyle{ x_1,y_1\in B}\)
Wtedy \(\displaystyle{ x_1 \le_B y_1}\), ponieważ \(\displaystyle{ x_1 \neq y_1}\), więc \(\displaystyle{ (x_1,x_2) \le _{B\otimes A} (y_1,y_2)}\), a więc tym bardziej \(\displaystyle{ (x_1,x_2) \le _{(B\otimes A)\oplus (C\otimes A)} (y_1,y_2).}\)
b)Przypadek \(\displaystyle{ x_1,y_1\in C}\) sprawdzamy w sposób symetryczny.
c)\(\displaystyle{ x_1\in B; y_1\in C}\), wtedy\(\displaystyle{ (x_1,x_2)\in B\times A; (y_1,y_2)\in C\times A}\), więc z definicji \(\displaystyle{ \oplus}\), ponieważ każdy element \(\displaystyle{ B\times A }\) jest mniejszy od każdego elementu \(\displaystyle{ C\times A}\), więc \(\displaystyle{ (x_1,x_2) \le _{(B\otimes A)\oplus (C\otimes A)} (y_1,y_2).}\)
d) \(\displaystyle{ x_1\in C; y_1\in B}\), ten przypadek jest niemożliwy, bo on prowadzi (z definicji sumy porządkowej- ponieważ każdy element \(\displaystyle{ B}\) jest mniejszy od każdego elementu \(\displaystyle{ C}\)), więc \(\displaystyle{ y_1 \le _{B\oplus C} x_1}\), a mamy nierówność w drugą stronę, więc z antysymetrii tego porządku, otrzymujemy \(\displaystyle{ x_1=y_1}\)- sprzeczność.

Rozważmy teraz przypadek:

2. \(\displaystyle{ x_1=y_1.}\) Wtedy \(\displaystyle{ x_2 \le _A y_2.}\) Jeśli

a)\(\displaystyle{ x_1=y_1\in B}\), to \(\displaystyle{ (x_1,x_2) \le _{B\otimes A} (y_1,y_2)}\), a więc tym bardziej \(\displaystyle{ (x_1,x_2) \le _{(B\otimes A)\oplus (C\otimes A) } (y_1,y_2).}\)
b) jeśli \(\displaystyle{ x_1=y_1\in C}\), to rozumujemy podobnie.

Kończy to dowód implikacji w jedną stronę. Aby pokazać implikację w drugą stronę, to:


Załóżmy, że \(\displaystyle{ (x_1,x_2) \le _{(B\otimes A)\oplus (C\otimes A)} (y_1,y_2).
}\)

Rozważmy dwa przypadki:

I. \(\displaystyle{ x_1 \neq y_1.}\)

Jeśli \(\displaystyle{ x_1 \le _{B\oplus C} y_1, to (x_1,x_2) \le _{(B\oplus C)\otimes A} (y_1,y_2)}\), co należało pokazać.

Pozostaje więc do rozważenia przypadek \(\displaystyle{ x_1\not \le _{B\oplus C} y_1.}\) Doprowadzimy go do sprzeczności.

Ponieważ \(\displaystyle{ x_1,y_1\in B\cup C}\), a \(\displaystyle{ \le _{B\oplus C} }\)jest porządkiem liniowym, i \(\displaystyle{ x_1 \not\le_{B\oplus C} y_1}\), więc \(\displaystyle{ y_1 \le _{B\oplus C} x_1}\); ze względu na definicję sumy porządkowej rozważmy teraz trzy przypadki:

1. \(\displaystyle{ y_1,x_1\in B.}\)
Wtedy \(\displaystyle{ y_1 \le _B x_1}\), ponieważ \(\displaystyle{ y_1 \neq x_1}\), więc \(\displaystyle{ (y_1,y_2) \le_{ B\otimes A} (x_1,x_2)}\), a więc tym bardziej \(\displaystyle{ (y_1,y_2) \le _{(B\otimes A)\oplus (C\otimes A)} (x_1,x_2)}\), lecz z głównego założenia mamy nierówność w drugą stronę, więc z antysymetrii tego porządku \(\displaystyle{ (y_1,y_2)=(x_1,x_2)}\), a więc \(\displaystyle{ x_1=y_1}\)-sprzeczność.

2.Jeśli \(\displaystyle{ y_1,x_1\in C}\), to rozumujemy analogicznie.

3.\(\displaystyle{ y_1\in B, x_1\in C.}\)
Wtedy \(\displaystyle{ (y_1,y_2)\in B\times A}\), oraz \(\displaystyle{ (x_1,x_2)\in C\times A}\), więc z definicji \(\displaystyle{ \oplus}\) ponieważ każdy element \(\displaystyle{ B\times A}\) jest mniejszy od każdego elementu \(\displaystyle{ C\times A}\) względem \(\displaystyle{ \le _{(B\otimes A)\oplus (C\otimes A)}}\), więc \(\displaystyle{ (y_1,y_2)\le _{(B\otimes A)\oplus (C\otimes A)} (x_1,x_2)}\), z założenia mamy nierówność w drugą stronę, więc z antysymetrii \(\displaystyle{ (y_1,y_2)=(x_1,x_2)}\), więc \(\displaystyle{ y_1=x_1}\)-sprzeczność.

Rozważmy teraz drugi przypadek:

II.\(\displaystyle{ x_1=y_1.}\)

Jeśli \(\displaystyle{ x_2 \le _A y_2}\), to \(\displaystyle{ (x_1,x_2) \le _{(B\oplus C)\otimes A} (y_1,y_2)}\), i dowód jest zakończony.

Pozostaje wiec do rozważenia przypadek \(\displaystyle{ x_2 \not\le_A y_2.}\)

Ponieważ \(\displaystyle{ x_2,y_2\in A}\), a \(\displaystyle{ \le _A}\) jest porządkiem liniowym, wiec w takim wypadku \(\displaystyle{ y_2<_A x_2.}\)
Ponieważ \(\displaystyle{ x_1=y_1\in B\cup C}\), więc jeśli \(\displaystyle{ x_1=y_1\in B}\), to \(\displaystyle{ (y_1,y_2) \le _{B\otimes A} (x_1,x_2)}\), a więc tym bardziej \(\displaystyle{ (y_1,y_2) \le _{(B\otimes A)\oplus (C \otimes A)} (x_1,x_2)}\), podobnie gdy \(\displaystyle{ x_1=y_1\in C}\), a z założenia mamy nierówność w drugą stronę, więc z antysymetrii \(\displaystyle{ y_1=x_1}\) i \(\displaystyle{ y_2=x_2}\),
więc ze zwrotności \(\displaystyle{ \le _A}\) otrzymujemy \(\displaystyle{ x_2 \le x_2=y_2}\)- sprzeczność.

Dowód jest zakończony.\(\displaystyle{ \square}\)