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: 1392
Rejestracja: 20 lip 2012, o 21:19
Płeć: Mężczyzna
Lokalizacja: Rzeszów
Podziękował: 60 razy
Pomógł: 83 razy

Operacje na zbiorach dobrze uporządkowanych

Post autor: Jakub Gurak »

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.
Jakub Gurak
Użytkownik
Użytkownik
Posty: 1392
Rejestracja: 20 lip 2012, o 21:19
Płeć: Mężczyzna
Lokalizacja: Rzeszów
Podziękował: 60 razy
Pomógł: 83 razy

Re: Operacje na zbiorach dobrze uporządkowanych

Post autor: Jakub Gurak »

Mamy twierdzenie, że każdy zbiór dobrze uporządkowany jest podobny do dokładnie jednej liczby porządkowej.
SZKIC DOWODU:    
Oczywiście każdy zbiór dobrze uporządkowany \(\displaystyle{ \left( X,\le\right)}\) jest podobny do co najwyżej jednej liczby porządkowej, gdyż jeśli liczby porządkowe \(\displaystyle{ a,b}\) są podobne do \(\displaystyle{ X}\), to \(\displaystyle{ a,b}\) są podobne (liczby porządkowe) skąd są równe- \(\displaystyle{ a=b}\). Otrzymujemy zatem, że każdy zbiór dobrze uporządkowany jest podobny do dokładnie jednej liczby porządkowej. \(\displaystyle{ \square}\)

Dzięki temu (oraz operacjom) na zbiorach dobrze uporządkowanych można wprowadzić działania dodawania i mnożenia liczb porządkowych (co wymaga krótkiego uzasadnienia- dla mnożenia, dla dodawania pewnie jeszcze gorzej, nie wiem czy wymyślę tu to).

Niech \(\displaystyle{ a,b}\) będą liczbami porządkowymi. Wtedy \(\displaystyle{ (a,\subset}\)) i \(\displaystyle{ (b,\subset)}\) są zbiorami dobrze uporządkowanymi. Wtedy na ich iloczynie kartezjańskim porządek leksykograficzny jest dobry. Zatem jest to zbiór dobrze uporządkowany, a zatem istnieje dokładnie jedna liczba porządkowa doń podobna, którą będziemy oznaczać \(\displaystyle{ a\cdot b}\).

Dodawanie: Może nie będę się trudził (żeby to dobrze, krok po kroku wprowadzić- na ważniaku są przeskoki myślowe, których nie lubię), wyjaśnię o co chodzi: dla liczb porządkowych \(\displaystyle{ a,b}\) liczba porządkowa \(\displaystyle{ a+b}\) odpowiada zbiorowi dobrze uporządkowanemu otrzymanemu po ustawieniu po zbiorze dobrze uporządkowanym typu \(\displaystyle{ a}\) (podobnym do \(\displaystyle{ a}\)) po ustawieniu za nim zbioru dobrze uporządkowanego typu \(\displaystyle{ b}\).

Nim podam własności dodawania i mnożenia liczb porządkowych, przypomnę parę rzeczy o podobieństwie.

Podobieństwo zachowuje elementy najmniejsze i największe, to znaczy, jeśli \(\displaystyle{ \left( X,\le\right); \left( Y, \sqsubseteq\right)}\) są zbiorami uporządkowanymi podobnymi, to jeśli zbiór \(\displaystyle{ X}\) ma element najmniejszy, to \(\displaystyle{ Y}\) również ma element najmniejszy. Podobnie, jeśli \(\displaystyle{ X}\) ma element największy, to \(\displaystyle{ Y}\) ma element największy.
DOWÓD:    
Fakt: Dla dwóch zbiorów liniowo uporządkowanych \(\displaystyle{ \left( X,\le\right); \left( Y, \sqsubseteq\right)}\) aby pokazać, że są podobne nalezy określić bijekcję \(\displaystyle{ f:X \rightarrow Y}\), monotoniczną, tzn. spełniającą:

\(\displaystyle{ x \le y \Longrightarrow f(x)\sqsubseteq f(y). }\)

Czyli nie trzeba żądać równoważności tych wzorów- wystarczy implikacja ( dla dwóch zbiorów liniowo uporządkowanych).

Przypominam, \(\displaystyle{ \omega}\) oznacza najmniejszą nieskończoną liczbę porządkową, która jest zbiorem liczb naturalnych von Neumanna. Własności liczb porządkowych:

1.\(\displaystyle{ 1+\omega=\omega.}\)
2.\(\displaystyle{ \omega+1\neq \omega.}\)

1.\(\displaystyle{ 1+\omega}\) to liczba porządkowa odpowiadająca zbiorowi liczb naturalnych z dodanym jednym elementem jako najmniejszym oznaczmy go przez \(\displaystyle{ S}\). Rozważmy funkcję \(\displaystyle{ f:\NN \cup \left\{ S\right\} \rightarrow \NN}\) daną jako:

\(\displaystyle{ f(S)=0,}\)
\(\displaystyle{ f(n)=n+1, dla n\in\NN.}\)

Taka funkcja jest bijekcją (jako suma bijekcji \(\displaystyle{ f_1:\left\{ S\right\} \rightarrow \left\{ 0\right\}}\) i bijekcji \(\displaystyle{ f_2:\NN \rightarrow \NN _{+} (f_2(n)=n+1)}\) ) z \(\displaystyle{ \left\{ S\right\} \cup \NN=\NN\cup \left\{ S\right\} }\) do \(\displaystyle{ \left\{ 0\right\} \cup\NN _{+}=\NN }\), i łatwo sprawdzić, że jest monotoniczna. Wobec czego jest podobieństwem, czyli zbiory dobrze uporządkowane \(\displaystyle{ \NN\cup\left\{ S\right\} }\)i \(\displaystyle{ \NN}\) są podobne, a więc odpowiadają jednej liczbie porządkowej \(\displaystyle{ \omega}\).

2. Równość nie jest prawdziwa, czyli te liczby porządkowe są różne.\(\displaystyle{ \omega+1}\) odpowiada zbiorowi liczb naturalnych z dodanym jednym elementem jako największym, podczas gdy \(\displaystyle{ \omega}\) odpowiada zbiorowi liczb naturalnych gdzie oczywiście nie ma elementu największego. Ponieważ podobieństwo zachowuje elementy największe, te zbiory dobrze uporządkowane nie mogą być podobne, a więc odpowiadająca im liczby porządkowe są różne.

Z 1. i 2. wnioskujemy, że dodawanie liczb porządkowych nie musi być przemienne.

Sprawdzimy czy dla dowolnych liczb porządkowych \(\displaystyle{ a,b,c:}\)

3.\(\displaystyle{ b+a=c+a \Longrightarrow b=c}\) (skracalność dodawania z prawej strony).
4. \(\displaystyle{ a+b=a+c \Longrightarrow b=c}\) (skracalność dodawania z lewej strony).

3. Mamy \(\displaystyle{ 0+\omega=\omega=1+\omega}\), podczas gdy \(\displaystyle{ 0 \neq 1}\) (Czyli dodawanie nie musi być skracalne z prawej strony).

4. Natomiast dodawanie jest skracalne z lewej strony. Dowodu formalnego nie zrobię (gdyż ciężko mi ten dowód z ważniaka zrozumieć), ale spróbuję to uzasadnić. Do liczby porządkowej \(\displaystyle{ a}\) dodajemy odpowiednio \(\displaystyle{ b}\) i \(\displaystyle{ c}\) aby otrzymać tą samą sumę. Jeśli \(\displaystyle{ b \neq c}\), to albo \(\displaystyle{ b<c}\), i wtedy \(\displaystyle{ a+b<a+c}\), więc \(\displaystyle{ a+b \neq a+c}\)- sprzeczność, albo \(\displaystyle{ b>c}\), i wtedy \(\displaystyle{ a+b>a+c}\)- sprzeczność. Wobec czego \(\displaystyle{ b=c}\).

5. Mnożenie nie jest przemienne.

Pokażemy najpierw, że \(\displaystyle{ \omega\cdot 2=\omega}\). Zdefiniujmy funkcję \(\displaystyle{ f:\omega \times \left\{ 0,1\right\} \rightarrow \omega}\) jako:

\(\displaystyle{ f(n,a)=2 \cdot n+a.}\)

Łatwo pokazać, że ta funkcja jest różnowarościowa. Niech pary \(\displaystyle{ (n,a);(m,b)\in\omega \times \left\{ 0,1\right\}}\) będą różne. Jeśli \(\displaystyle{ n \neq m}\), to gdy \(\displaystyle{ n<m}\), to \(\displaystyle{ f(n,a)=2 \cdot n+a \le 2n+1<2(n+1) \le 2m \le 2m+b=f(m,b)}\), a więc \(\displaystyle{ f(n,a)<f(m,b)}\), więc \(\displaystyle{ f(n,a) \neq f(m,b)}\). Jeśli \(\displaystyle{ n>m}\), to rozumujemy symetrycznie. Pozostaje przypadek \(\displaystyle{ n=m, a \neq b}\), wtedy \(\displaystyle{ f(n,a)=2n+a \neq 2n+b=2m+b=f(m,b)}\), otrzymujemy zatem, że \(\displaystyle{ f}\) jest różnowartościowa. Jest też 'na' gdyż, \(\displaystyle{ f_{P}=\stackrel{\rightarrow }{f}\left( \omega \times \left\{ 0,1\right\} \right) = \stackrel{\rightarrow }{f}\left( \omega \times \left\{ 0\right\} \right) \cup \stackrel{\rightarrow }{f}\left( \omega \times \left\{ 1\right\} \right)=\left\{ 2n+0=2n\Bigl| \ \ n\in\omega=\NN\right\} \cup \left\{ 2n+1\Bigl| \ \ n\in\omega=\NN\right\}=\NN=\omega}\), a więc \(\displaystyle{ f}\) jest 'na', a więc jest bijekcją. Pokażemy, że \(\displaystyle{ f}\) jest monotoniczna. Weźmy dowolne różne pary \(\displaystyle{ (n,a),(m,b) \in\omega\times \left\{ 0,1\right\} }\),takie, że \(\displaystyle{ (n,a)\le_{l} (m,b)}\), gdzie \(\displaystyle{ \le_{l}}\) jest porządkiem leksykograficznym. Jeśli \(\displaystyle{ n \neq m}\), to z definicji porządku leksykograficznego \(\displaystyle{ n<m}\), wtedy podobne szacowania pokażą, że \(\displaystyle{ f(n,a) < f(m,b)}\). Jeśli \(\displaystyle{ n=m}\), to \(\displaystyle{ a<b}\), wtedy musi być \(\displaystyle{ a=0}\) i \(\displaystyle{ b=1}\), i w konsekwencji \(\displaystyle{ f(n,0)=2n=2m<2m+1=f(m,1)}\), wobec czego \(\displaystyle{ f}\) jest monotoniczna, zatem jest podobieństwem, wobec czego \(\displaystyle{ \omega\cdot 2=\omega.}\)

Pokażemy teraz, że \(\displaystyle{ 2\cdot\omega \neq \omega}\). Rozważmy zbiór \(\displaystyle{ \left\{ 0,1\right\}\times\omega}\) z porządkiem leksykograficznym (otrzymanym ze zbiorów dobrze uporządkowanych \(\displaystyle{ \left( \left\{ 0,1\right\}, \subset \right), \left( \omega, \subset \right) }\) ). Weźmy zbiór \(\displaystyle{ \left\{ 0\right\} \times \omega}\), który jest istotnym podzbiorem zbioru \(\displaystyle{ \left\{ 0,1\right\} \times\omega. }\)Pokażemy, że jest on również istotnym przedziałem początkowym zbioru \(\displaystyle{ \left\{ 0,1\right\}\times\omega}\). Niech \(\displaystyle{ (0,n)\in\left\{ 0\right\} \times \omega}\). Niech \(\displaystyle{ (a,m)\in\left\{ 0,1\right\}\times\omega}\) będzie parą taką, że \(\displaystyle{ (a,m) \le_{l} (0,n).}\) Ponieważ \(\displaystyle{ a}\) musi należeć do \(\displaystyle{ \left\{ 0,1\right\}}\), to \(\displaystyle{ a}\) nie może być silnie mniejsze od \(\displaystyle{ 0}\), więc pozostaje przypadek \(\displaystyle{ a=0}\), wtedy \(\displaystyle{ (a,m)=(0,m)\in\left\{ 0\right\} \times \omega}\). Wobec czego zbiór \(\displaystyle{ \left\{ 0\right\} \times \omega}\) jest on również istotnym przedziałem początkowym zbioru \(\displaystyle{ \left\{ 0,1\right\}\times\omega}\). Łatwo sprawdzić, że jest podobny do \(\displaystyle{ \left( \omega,\subset\right)}\) . Gdyby zatem \(\displaystyle{ \left( \omega,\subset\right)}\) był podobny do \(\displaystyle{ \left\{ 0,1\right\}\times\omega, \le_{l}}\) to ostatni zbiór (dobrze uporządkowany) byłby podobny do swojego istotnego przedziału początkowego \(\displaystyle{ \left\{ 0\right\} \times \omega}\), a tak być nie może- sprzeczność. Wobec czego zbiory uporządkowane \(\displaystyle{ \left( \omega,\subset \right)}\) i \(\displaystyle{ \left( \left\{ 0,1\right\}\times\omega, \le_{l}\right) }\) nie mogą być podobne, a więc również \(\displaystyle{ \omega \neq 2 \cdot \omega.}\)

A więc mnożenie liczb porządkowych nie jest przemienne.
Ostatnio zmieniony 15 gru 2019, o 10:48 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
krl
Użytkownik
Użytkownik
Posty: 609
Rejestracja: 10 lis 2009, o 22:39
Płeć: Mężczyzna
Lokalizacja: Wrocław
Pomógł: 135 razy

Re: Operacje na zbiorach dobrze uporządkowanych

Post autor: krl »

Dodawanie, mnożenie i wszelkie wyższe działania arytmetyczne na liczbach porządkowych można zdefiniować rekurencyjnie, działają te same definicje co dla liczb naturalnych, modulo przejście graniczne w przypadku granicznych liczb porządkowych. Dla liczby porządkowej \(\displaystyle{ \beta}\), niech \(\displaystyle{ \beta'}\) oznacza jej następnik.
Dodawanie:
1. \(\displaystyle{ \alpha +0=\alpha}\)
2. \(\displaystyle{ \alpha + \beta'=(\alpha+\beta)'}\)
3. gdy \(\displaystyle{ \beta}\) jest graniczna, \(\displaystyle{ \alpha+\beta=\sup_{\gamma<\beta}(\alpha+\gamma)}\)
Widać, jak przypadek graniczny wpływa na nieprzemienność dodawania.
Mnożenie
1. \(\displaystyle{ \alpha\cdot 0=0}\)
2. \(\displaystyle{ \alpha\cdot\beta'=\alpha\cdot\beta+\alpha}\)
3. gdy \(\displaystyle{ \beta}\) jest graniczna, \(\displaystyle{ \alpha\cdot\beta=\sup_{\gamma<\beta}(\alpha\cdot\gamma)}\)
Przez indukcję można pokazać, że te rekurencyjne definicje zgadzają się z definicjami konkretnymi (podanymi przez Ciebie).
Z drobnym zastrzeżeniem: w konkretnej definicji iloczynu liczb porządkowych \(\displaystyle{ \alpha\cdot\beta}\) mylisz kolejność czynników. \(\displaystyle{ \alpha\cdot\beta}\) to typ porządkowy produktu kartezjańskiego \(\displaystyle{ \beta\times\alpha}\) z porządkiem leksykograficznym. Dlatego
\(\displaystyle{ 2\cdot \omega=\omega<\omega+\omega=\omega\cdot 2}\).
Możemy iterować te arytmetyczne operacje na liczbach porządkowych, jak w hierarchii Ackermanna.
\(\displaystyle{ *_0}\) to dodawanie, \(\displaystyle{ \alpha *_{n+1}\beta}\) to \(\displaystyle{ \beta}\)-krotne wykonanie operacji \(\displaystyle{ \cdot *_{n} \alpha}\) na zerze lub jedynce (tak, jak mnożenie \(\displaystyle{ n\times m}\) to \(\displaystyle{ m}\)-krotne dodanie \(\displaystyle{ n}\) do zera).
\(\displaystyle{ n}\) w \(\displaystyle{ *_n}\) można zastąpić przez dowolną liczbę porządkową \(\displaystyle{ \delta}\) (tzn. przedłużyć iterację przez rekursję pozaskończoną na całą klasę liczb porządkowych). Na krokach granicznych bierzemy supremum...
W szczególności \(\displaystyle{ *_2}\) to potęgowanie itd. Np.
\(\displaystyle{ \omega=2^{\omega}<2^{\omega+2}=2^{\omega}\cdot 2^2=\omega\cdot 4=\omega+\omega+\omega+\omega < \omega\cdot \omega=\omega^2}\)
Zadanie: podać konkretne reprezentacje wyników działań \(\displaystyle{ *_n}\), czy nawet \(\displaystyle{ *_{\delta}}\) dla \(\displaystyle{ n,
\delta\geq 2}\)
, podobnie jak dla dodawania i mnożenia.
Jakub Gurak
Użytkownik
Użytkownik
Posty: 1392
Rejestracja: 20 lip 2012, o 21:19
Płeć: Mężczyzna
Lokalizacja: Rzeszów
Podziękował: 60 razy
Pomógł: 83 razy

Re: Operacje na zbiorach dobrze uporządkowanych

Post autor: Jakub Gurak »

Jakub Gurak pisze: 15 gru 2019, o 04:23 Otrzymujemy zatem, że każdy zbiór dobrze uporządkowany jest podobny do dokładnie jednej liczby porządkowej.

Dzięki temu (oraz operacjom) na zbiorach dobrze uporządkowanych można wprowadzić działania dodawania i mnożenia liczb porządkowych (co wymaga krótkiego uzasadnienia- dla mnożenia, dla dodawania pewnie jeszcze gorzej, nie wiem czy wymyślę tu to)
No właśnie jak to wyjaśnić, jak rozumieć dokładniej tą definicję.
Dla dowolnych rozłącznych zbiorów dobrze uporządkowanych \(\displaystyle{ \left( A, \le _{A} \right);\left( B, \le _{B} \right) }\) następujące zbiory są dobrze uporządkowane

\(\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 jak w zbiorach wejściowych, a do tego każdy element zbioru \(\displaystyle{ A}\) jest mniejszy od każdego elementu zbioru \(\displaystyle{ B}\)
To raczej rozumiem- jest to suma porządkową zbiorów dobrze uporządkowanych( a więc i liniowo, na zbiorach rozłącznych ). Jest to liniowy porządek( a nawet dobry, co chyba łatwo można udowodnić ).

Ale dalej mam problem:
Niech a,b będą liczbami porządkowymi.

Liczbę porządkową podobną do \(\displaystyle{ \left( a,\subset \right)\oplus\left( b, \subset \right) }\) będziemy oznaczać przez \(\displaystyle{ a+b}\)
Mógłby ktoś to wyjaśnić dokładniej? Rozumiem, że liczby porządkowe są dobrze uporządkowane przez inkluzje, ale co tu się dzieje gdy zbiory \(\displaystyle{ a,b}\) nie są rozłączne :?:

Potrzebuje ścisłej definicji, aby udowodnić łączność dodawania (i może potem rozdzielność mnożenia względem dodawania).
Jan Kraszewski
Administrator
Administrator
Posty: 34126
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 3 razy
Pomógł: 5192 razy

Re: Operacje na zbiorach dobrze uporządkowanych

Post autor: Jan Kraszewski »

Jakub Gurak pisze: 4 maja 2020, o 22:12Mógłby ktoś to wyjaśnić dokładniej? Rozumiem, że liczby porządkowe są dobrze uporządkowane przez inkluzje, ale co tu się dzieje gdy zbiory \(\displaystyle{ a,b}\) nie są rozłączne :?:
Urozłącznia się je.

JK
Jakub Gurak
Użytkownik
Użytkownik
Posty: 1392
Rejestracja: 20 lip 2012, o 21:19
Płeć: Mężczyzna
Lokalizacja: Rzeszów
Podziękował: 60 razy
Pomógł: 83 razy

Re: Operacje na zbiorach dobrze uporządkowanych

Post autor: Jakub Gurak »

No dobrze, powiedzmy, że rozważa się \(\displaystyle{ a \times \left\{ 0\right\} , b \times\left\{ 1\right\}}\) , wtedy zbiory będą rozłączne, i co dalej :?: (mógłbym doczytać z ważniaka, tam było coś więcej, ale ciężko ..., a i tak teraz nie mam dostępu). Co rozumieć przez \(\displaystyle{ a+b}\) :?:
Jan Kraszewski
Administrator
Administrator
Posty: 34126
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 3 razy
Pomógł: 5192 razy

Re: Operacje na zbiorach dobrze uporządkowanych

Post autor: Jan Kraszewski »

Jakub Gurak pisze: 5 maja 2020, o 20:34Co rozumieć przez \(\displaystyle{ a+b}\) :?:
Typ porządkowy zbioru dobrze uporządkowanego \(\displaystyle{ \left\langle (a\times\{0\})\cup(b\times\{1\}),\prec\right\rangle }\), gdzie \(\displaystyle{ \prec}\) jest porządkiem antyleksykograficznym.

JK
Jakub Gurak
Użytkownik
Użytkownik
Posty: 1392
Rejestracja: 20 lip 2012, o 21:19
Płeć: Mężczyzna
Lokalizacja: Rzeszów
Podziękował: 60 razy
Pomógł: 83 razy

Re: Operacje na zbiorach dobrze uporządkowanych

Post autor: Jakub Gurak »

A co to jest porządek antyleksykograficzny :?: , słyszałem tylko o leksykograficznym.
a4karo
Użytkownik
Użytkownik
Posty: 22173
Rejestracja: 15 maja 2011, o 20:55
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 38 razy
Pomógł: 3748 razy

Re: Operacje na zbiorach dobrze uporządkowanych

Post autor: a4karo »

Wymyśl. To nietrudne.
Jakub Gurak
Użytkownik
Użytkownik
Posty: 1392
Rejestracja: 20 lip 2012, o 21:19
Płeć: Mężczyzna
Lokalizacja: Rzeszów
Podziękował: 60 razy
Pomógł: 83 razy

Re: Operacje na zbiorach dobrze uporządkowanych

Post autor: Jakub Gurak »

Ha, żebym zgadł... myślałem, że porządek odwrotny do leksykograficznego, ale chyba nie o to chodzi.

Nie lubię zgadywać co autor miał na myśli. :(
a4karo
Użytkownik
Użytkownik
Posty: 22173
Rejestracja: 15 maja 2011, o 20:55
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 38 razy
Pomógł: 3748 razy

Re: Operacje na zbiorach dobrze uporządkowanych

Post autor: a4karo »

A pamiętasz co chcesz osiągnąć? Myśl.
Jan Kraszewski
Administrator
Administrator
Posty: 34126
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 3 razy
Pomógł: 5192 razy

Re: Operacje na zbiorach dobrze uporządkowanych

Post autor: Jan Kraszewski »

Dokładnie, nazwa jest nieistotna. Pomyśl, jak powinieneś zadać porządek na tej urozłącznionej sumie, żeby było dobrze.

JK
Jakub Gurak
Użytkownik
Użytkownik
Posty: 1392
Rejestracja: 20 lip 2012, o 21:19
Płeć: Mężczyzna
Lokalizacja: Rzeszów
Podziękował: 60 razy
Pomógł: 83 razy

Re: Operacje na zbiorach dobrze uporządkowanych

Post autor: Jakub Gurak »

No to bym wziął sumę porządkową tych zbiorów dobrze uporządkowanych \(\displaystyle{ a \times \left\{ 0\right\};b \times \left\{ 1\right\}.}\) Dobrze :?:
Jan Kraszewski
Administrator
Administrator
Posty: 34126
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 3 razy
Pomógł: 5192 razy

Re: Operacje na zbiorach dobrze uporządkowanych

Post autor: Jan Kraszewski »

Tak, wyjdzie na to samo, ale wygodniej jest mieć zadany ten porządek bezpośrednim warunkiem, bo inaczej będziesz się strasznie męczył przy dowodach.

JK
Jakub Gurak
Użytkownik
Użytkownik
Posty: 1392
Rejestracja: 20 lip 2012, o 21:19
Płeć: Mężczyzna
Lokalizacja: Rzeszów
Podziękował: 60 razy
Pomógł: 83 razy

Re: Operacje na zbiorach dobrze uporządkowanych

Post autor: Jakub Gurak »

Tzn. jakim warunkiem?
ODPOWIEDZ