Operacje na zbiorach dobrze uporządkowanych

Algebra zbiorów. Relacje, funkcje, iloczyny kartezjańskie... Nieskończoność, liczby kardynalne... Aksjomatyka.
Jakub Gurak
Użytkownik
Użytkownik
Posty: 604
Rejestracja: 20 lip 2012, o 21:19
Płeć: Mężczyzna
Lokalizacja: Rzeszów
Podziękował: 18 razy
Pomógł: 43 razy

Operacje na zbiorach dobrze uporządkowanych

Post autor: Jakub Gurak » 24 paź 2019, o 03:10

Przypomnijmy, że zbiorem dobrze uporządkowanym nazywamy zbiór uporządkowany \(\displaystyle{ \left( X, \le \right) }\) w którym każdy niepusty podzbiór ma element najmniejszy. Wynika stąd, że wtedy w całym zbiorze \(\displaystyle{ X}\) musi istnieć element najmniejszy, o ile tylko zbiór jest niepusty.

Przykładem może być zbiór liczb naturalnych z naturalnym porządkiem. Zasada minimum mówi, że w każdy niepusty podzbiór \(\displaystyle{ \NN}\) ma liczbę najmniejszą, a więc \(\displaystyle{ \NN}\) jest dobrze uporządkowany. Innym przykładem jest dowolny skończony zbiór liniowo uporządkowany. Jest on dobrze uporządkowany, gdyż każdy niepusty skończony podzbiór liniowo uporządkowanego zbioru ma element najmniejszy, a więc jest to dobry porządek.

Fakt: Każdy zbiór dobrze uporządkowany jest również liniowo uporządkowany.

Dowód:
Ukryta treść:    
Fakt. Jeśli \(\displaystyle{ \left( A,\sqsubseteq\right)}\) jest zbiorem dobrze uporządkowanym, a \(\displaystyle{ B}\) dowolnym podzbiorem \(\displaystyle{ A}\), to zbiór \(\displaystyle{ B}\) jest dobrze uporządkowany przez \(\displaystyle{ \sqsubseteq\cap \left( B \times B\right) }\), czyli przez porządek \(\displaystyle{ \sqsubseteq}\) zawężony do elementów \(\displaystyle{ B}\), będziemy go dalej oznaczać jako \(\displaystyle{ \sqsubseteq_{B}. }\)

Dowód: Ponieważ \(\displaystyle{ \left( A,\sqsubseteq\right)}\) jest zbiorem uporządkowanym (liniowo), więc również \(\displaystyle{ B,\sqsubseteq_{B} }\) jest zbiorem liniowo uporządkowanym. Pokażemy, że jest to wręcz nawet dobry porządek. Ustalmy dowolny niepusty podzbiór \(\displaystyle{ C\subset B}\), ponieważ \(\displaystyle{ B\subset A}\), więc zbiór \(\displaystyle{ C}\) jest również podzbiorem \(\displaystyle{ A}\)(niepustym), więc ponieważ \(\displaystyle{ \left( A,\sqsubseteq\right)}\) jest zbiorem dobrze uporządkowanym, więc zbiór \(\displaystyle{ C}\) ma element najmniejszy \(\displaystyle{ c\in C}\) względem\(\displaystyle{ \sqsubseteq}\). Wtedy \(\displaystyle{ c\sqsubseteq x}\) dla dowolnego \(\displaystyle{ x\in C.}\) Ponieważ \(\displaystyle{ C\subset B}\), więc wtedy \(\displaystyle{ c,x\in B}\), skąd \(\displaystyle{ c\sqsubseteq _{B} x}\). Wynika stąd, że \(\displaystyle{ c}\) jest elementem najmniejszym \(\displaystyle{ C}\) względem \(\displaystyle{ \sqsubseteq _{B}}\), a więc \(\displaystyle{ B,\sqsubseteq_{B} }\) jest zbiorem dobrze uporządkowanym. \(\displaystyle{ \square}\)

Przykład: Dla dowolnej liczby naturalnej \(\displaystyle{ n}\), zbiór wszystkich liczb naturalnych mniejszych od \(\displaystyle{ n}\) jest dobrze uporządkowany przez naturalny porządek.


Niech \(\displaystyle{ \left( X, \le \right) }\) będzie zbiorem dobrze uporządkowanym, oraz niech \(\displaystyle{ T\not\in X}\) będzie ustalonym elementem (np. \(\displaystyle{ T=X}\)). Bardzo łatwo można pokazać, że zbiór \(\displaystyle{ Y=X \cup \left\{ T\right\}}\) z porządkiem \(\displaystyle{ \le _{Y}:= \le \cup \left( Y\times \left\{ T\right\} \right) }\), czyli z dodanym jednym elementem \(\displaystyle{ T}\) jako największym, taki zbiór uporządkowany jest zbiorem dobrze uporządkowanym. Aby to pokazać, niech \(\displaystyle{ A\subset Y}\) będzie niepustym podzbiorem. Pokażemy, że ma element najmniejszy. Jeżeli \(\displaystyle{ A \cap X \neq \left\{ \right\}}\), to ponieważ \(\displaystyle{ X}\) jest dobrze uporządkowany, więc ma \(\displaystyle{ A \cap X}\) element najmniejszy \(\displaystyle{ a}\). Oczywiście ten sam element jest elementem najmniejszym \(\displaystyle{ A}\), gdyż pozostały element największy \(\displaystyle{ T}\) nie wpływa na element najmniejszy zbioru \(\displaystyle{ A}\). Pozostaje przypadek gdy \(\displaystyle{ A \cap X= \left\{ \right\}}\), ale ponieważ \(\displaystyle{ \left\{ \right\} \neq A\subset Y=X \cup \left\{ T\right\}}\), więc pozostaje możliwość \(\displaystyle{ A=\left\{ T\right\}}\). Wtedy \(\displaystyle{ T}\) jako jedyny element \(\displaystyle{ A}\) jest jego elementem najmniejszym( i największym :) ). \(\displaystyle{ \square}\)

Ogólniej, dla dowolnych dwóch zbiorów dobrze uporządkowanych \(\displaystyle{ \left( A, \le _{A} \right),\left( B, \le _{B} \right) }\), gdzie zbiory \(\displaystyle{ A,B}\) są rozłączne na zbiorze \(\displaystyle{ A \cup B}\) dobrym porządkiem jest relacja \(\displaystyle{ \le _{A} \cup \le _{B} \cup \left( A\times B\right) }\), czyli na zbiorach \(\displaystyle{ A,B}\) porządki są takie jak we zbiorach wejściowych, a ponadto każdy element zbioru \(\displaystyle{ A}\) jest mniejszy od każdego elementu zbioru \(\displaystyle{ B}\).

Dowód:

Ponieważ zbiory \(\displaystyle{ A,B}\) są liniowo uporządkowane i zbiory \(\displaystyle{ A,B}\) są rozłączne, więc \(\displaystyle{ A \cup B}\) jest liniowo uporządkowany przez ten porządek. Aby pokazać, że jest dobrze uporządkowany to niech \(\displaystyle{ \left\{ \right\} \neq X \subset A \cup B}\). Pokażemy, że ten zbiór ma element najmniejszy. Rozważmy dwa przypadki:

Jeśli \(\displaystyle{ X \cap A \neq \left\{ \right\} }\) , to ponieważ \(\displaystyle{ A}\) jest dobrze uporządkowany, więc istnieje element \(\displaystyle{ x}\) najmniejszy w \(\displaystyle{ X \cap A}\) względem \(\displaystyle{ \le _{A} }\). Element ten należy do \(\displaystyle{ X \cap A}\), a więc również do zbioru \(\displaystyle{ X}\). Element ten będzie również elementem najmniejszym w \(\displaystyle{ X}\), gdyż ten element \(\displaystyle{ x}\) jest mniejszy od wszystkich elementów \(\displaystyle{ X \cap A}\) względem \(\displaystyle{ \le _{A}}\), a wiec również względem rozważanej sumy porządkowej, oraz \(\displaystyle{ x\in A}\), więc zgodnie z określeniem sumy porządkowej jest mniejszy od każdego elementu zbioru \(\displaystyle{ B}\), czyli również od wszystkich elementów \(\displaystyle{ X \cap B}\). Wobec czego jest mniejszy od każdego elementu \(\displaystyle{ \left( X \cap A\right) \cup \left( X \cap B\right) =X}\), wobec czego \(\displaystyle{ x}\) jest elementem najmniejszym \(\displaystyle{ X}\).

Jeśli \(\displaystyle{ X \cap A=\left\{ \right\}}\), to ponieważ zbiory \(\displaystyle{ A,B}\) są rozłączne, to\(\displaystyle{ X\subset B}\). Ponieważ \(\displaystyle{ X }\) jest niepustym podzbiorem zbioru dobrze uporządkowanego \(\displaystyle{ B}\), więc ma element najmniejszy względem \(\displaystyle{ \le _{B}}\), a więc również względem sumy porządkowej. \(\displaystyle{ \square}\)

Przykład: Jeśli rozważymy zbiór \(\displaystyle{ \NN \times \left\{ 0\right\}}\) z podobnym porządkiem do naturalnego na \(\displaystyle{ \NN}\), oraz \(\displaystyle{ \NN \times \left\{ 1\right\}}\) z podobnym porządkiem do naturalnego na \(\displaystyle{ \NN}\), to będą to zbiory dobrze uporządkowane na zbiorach rozłącznych, zatem z powyższego twierdzenia na \(\displaystyle{ \NN\times \left\{ 0\right\}\cup\NN\times \left\{ 1\right\} =\NN \times \left\{ 0,1\right\}}\) mamy taki dobry porządek, że dowolnie duża liczba naturalna na poziomie \(\displaystyle{ 0}\)( na osi \(\displaystyle{ x}\)) jest mniejsza od każdej liczby naturalnej (nawet \(\displaystyle{ 0}\)) na poziomie \(\displaystyle{ 1}\)( na prostej \(\displaystyle{ y=1}\)). Niestety, pojawiają się dłuższe porządki niż zbiór liczb naturalnych. Ale łatwiej sobie to wyobrazić gdy się rozważy na prostej rzeczywistej zbiór złożony z liczb postaci \(\displaystyle{ 1-\frac{1}{n}}\), gdzie \(\displaystyle{ n=1,2,3 ,...}\) oraz z liczb postaci \(\displaystyle{ 2-\frac{1}{n}, n=1,2,3,...}\) z naturalnym porządkiem. Te porządki są "równoważne"- a dokładniej podobne.

Przypominam, dla dwóch zbiorów liniowo uporządkowanych \(\displaystyle{ \left( X, \le _{X} \right),\left( Y, \le _{Y} \right) }\) porządek leksykograficzny (silny) na \(\displaystyle{ X \times Y}\) określamy tak:

\(\displaystyle{ \left( x_1,y_1\right)\sqsubset \left( x_2,y_2\right) \Longleftrightarrow x _{1} <_{X} x _{2} \vee \left( x _{1}=x _{2} \wedge y _{1} <_{Y} y _{2} \right). }\)

Porządek słaby wprowadzamy tak jak zwykle: \(\displaystyle{ \left( x_1,y_1\right)\sqsubseteq \left( x_2,y_2\right) \Longleftrightarrow \left( x_1,y_1\right)\sqsubset \left( x_2,y_2\right)\vee \left( x_1,y_1\right)= \left( x_2,y_2\right).}\)

Czyli z dwóch par różnych par o różnych pierwszych współrzędnych jest ta wcześniejsza(mniejsza), która pierwsza współrzędna jest wcześniejsza, a jeśli pierwsze współrzędne tych par są równe, to ta z nich jest wcześniejsza, która druga współrzędna jest wcześniejsza. Wynika stąd, że porządek leksykograficzny dwóch zbiorów liniowo uporządkowanych jest zawsze liniowy. Co więcej,

Porządek leksykograficzny dwóch zbiorów dobrze uporządkowanych jest dobry. Szkic dowodu, ilustracja i nie tylko

Zostało tam też to wzmocnione, że aby porządek leksykograficzny był dobry to obydwa zbiory muszą być dobrze uporządkowane( lub puste).

Na koniec jeśli w zbiorze uporządkowanym \(\displaystyle{ \left( X, \le\right) }\) istnieje nieskończony ciąg silnie malejący elementów \(\displaystyle{ X}\), to \(\displaystyle{ X}\) nie jest dobrze uporządkowany.

(Wystarczy rozważyć zbiór wyrazów tego ciągu, który nie ma elementu najmniejszego).

Twierdzenie można odwrócić, ale być może potrzeba wtedy aksjomatu wyboru.

Podamy prosty (ale zarazem bardzo kształcący) przykład zastosowania tego twierdzenia.Najpierw objaśnię co to są prefiksy, i porządek prefiksowy, jeśli mamy alfabet, np. \(\displaystyle{ \left\{ a,b,c,...,z\right\} }\), to przykładem porządku prefiksowego \(\displaystyle{ \prec}\) może być

\(\displaystyle{ tak\prec takt\prec taktyk\prec taktyka}\)

Czyli słowo krótsze jest prefiksem słowa dłuższego.

Niech teraz alfabetem będzie \(\displaystyle{ \left\{ 0,1\right\}}\). W zbiorze \(\displaystyle{ \left\{ 0,1\right\} ^{*} }\) wszystkich skończonych ciągów złożonych z \(\displaystyle{ 0}\) i \(\displaystyle{ 1}\) określamy porządek leksykograficzny jako:\(\displaystyle{ x\prec y}\) gdy, \(\displaystyle{ x}\) jest prefiksem \(\displaystyle{ y }\) lub gdy na pierwszej różniących je współrzędnej w \(\displaystyle{ x}\) wystepuje \(\displaystyle{ 0}\), a w \(\displaystyle{ y}\) występuje \(\displaystyle{ 1}\). Wykażemy, że ten porządek nie jest dobry.

Zauważmy, że \(\displaystyle{ \ldots00\black{0}1\prec 0\black{0}1\prec01}\)

Takie relacje wynikają z definicji. Otrzymujemy ciąg malejący elelementów \(\displaystyle{ \left\{ 0,1\right\} ^{*} }\), zatem ten zbiór nie może być dobrze uporządkowany.

ODPOWIEDZ