Lemat Kuratowskiego-Zorna

Algebra zbiorów. Relacje, funkcje, iloczyny kartezjańskie... Nieskończoność, liczby kardynalne... Aksjomatyka.
Merlinka51
Użytkownik
Użytkownik
Posty: 15
Rejestracja: 12 sty 2017, o 22:12
Płeć: Kobieta
Lokalizacja: Kraków

Lemat Kuratowskiego-Zorna

Post autor: Merlinka51 »

1) Udowodnij, że każdy zbiór można dobrze uporządkować.
2) Udowodnić, że w zbiorze częściowo uporządkowanym każdy antyłańcuch da się rozszerzyć do pewnego antyłańcucha maksymalnego w sensie zawierania.
Proszę o w tych zadankach
Awatar użytkownika
Dasio11
Moderator
Moderator
Posty: 10211
Rejestracja: 21 kwie 2009, o 19:04
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 40 razy
Pomógł: 2359 razy

Lemat Kuratowskiego-Zorna

Post autor: Dasio11 »

Wiesz, jaki jest schemat działania z lematem Kuratowskiego-Zorna? Znajdujesz odpowiedni porządek częściowy, pokazujesz, że każdy łańcuch ma ograniczenie górne i stąd wnioskujesz, że w tym częściowym porządku jest pewien element maksymalny, który najczęściej jest obiektem, którego istnienie próbujemy udowodnić.

W pierwszym: ustalmy zbiór \(\displaystyle{ X}\) i rozważmy rodzinę

\(\displaystyle{ \mathcal{W} = \{ (A, \preccurlyeq) : A \subseteq X \wedge {\preccurlyeq} \text{ jest dobrym porządkiem na } A \}}\)

z relacją

\(\displaystyle{ {(A, \preccurlyeq) \mathrel{\leqslant \hskip{-4pt} \raise 2pt \tiny{|} \hskip{-1.7pt} \tiny{|} \hskip{4pt}} (B, \preccurlyeq') \text{ gdy } (A, \preccurlyeq) \text{ jest przedziałem początkowym } (B, \preccurlyeq')}.}\)

Przypomnę, że porządek \(\displaystyle{ (A, \preccurlyeq)}\) nazywamy przedziałem początkowym porządku \(\displaystyle{ (B, \preccurlyeq'),}\) gdy zachodzą następujące warunki:

\(\displaystyle{ \begin{align*}
(\mathrm{i}) \, \, & A \subseteq B \\
(\mathrm{ii}) \, \, & {\preccurlyeq} = {\preccurlyeq'} \Big|_{A \times A} \\
(\mathrm{iii}) \, \, & (\forall a \in A) \, \{ b \in B : b \preccurlyeq' a \} \subseteq A
\end{align*} }\)


Teraz trzeba udowodnić, że porządek \(\displaystyle{ (\mathcal{W}, \mathrel{\leqslant \hskip{-4pt} \raise 2pt \tiny{|} \hskip{-1.7pt} \tiny{|} \hskip{4pt}})}\) spełnia założenia lematu Kuratowskiego-Zorna.
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

Lemat Kuratowskiego-Zorna

Post autor: Jakub Gurak »

Dasio11 pisze:z relacją

\(\displaystyle{ {(A, \preccurlyeq) \mathrel{\leqslant \hskip{-4pt} \raise 2pt \tiny{|} \hskip{-1.7pt} \tiny{|} \hskip{4pt}} (B, \preccurlyeq') \text{ gdy } (A, \preccurlyeq) \text{ jest przedziałem początkowym } (B, \preccurlyeq')}.}\)

Przypomnę, że porządek \(\displaystyle{ (A, \preccurlyeq)}\) nazywamy przedziałem początkowym porządku \(\displaystyle{ (B, \preccurlyeq'),}\) gdy zachodzą następujące warunki:

\(\displaystyle{ \begin{align*}
(\mathrm{i}) \, \, & A \subseteq B \\
(\mathrm{ii}) \, \, & {\preccurlyeq} = {\preccurlyeq'} \Big|_{A \times A} \\
(\mathrm{iii}) \, \, & (\forall a \in A) \, \{ b \in B : b \preccurlyeq' a \} \subseteq A
\end{align*} }\)
Czyli chodzi pewnie o tę samą relację, co na ważniaku była w tym dowodzie twierdzenia Zermelo , a więc:

\(\displaystyle{ (C,\sqsubseteq) \preccurlyeq (C',\sqsubseteq') \iff C\subset C' \land \begin{cases} \bigwedge\limits_{c,d\in C} (c\sqsubseteq d \iff c\sqsubseteq' d) \textrm{ oraz }\\ \ c\in C,d\in C'\setminus C\ \Longrightarrow c\sqsubseteq' d \end{cases}}\)

Czyli jeden zbiór dobrze uporządkowany jest mniejszy od drugiego zbioru dobrze uporządkowanego dokładnie wtedy gdy pierwszy zbiór na którym jest określony pierwszy dobry porządek jest mniejszy pod względem inkluzji od drugiego zbioru na którym jest określony drugi dobry porządek i porządek na większym zbiorze jest rozszerzeniem porządku na mniejszym zbiorze przez dodanie elementów większych od wszystkich zastanych. To tak naprawdę bardzo naturalne, co ilustruje rysunek:

Obrazek

Nie zmienia to faktu, że pasowałoby udowodnić że rzeczywiście jest to relacja porządku, co na ważniaku przemilczeli.
Ostatnio zmieniony 9 lip 2019, o 11:00 przez Dasio11, łącznie zmieniany 1 raz.
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

Lemat Kuratowskiego-Zorna

Post autor: Jakub Gurak »

A więc sprawdźmy, potem coś spytam.

1.Zwrotność, czyli czy \(\displaystyle{ (C,\sqsubseteq) \preccurlyeq (C,\sqsubseteq)}\). A więc niewątpliwie \(\displaystyle{ C \subseteq C}\), dla dowolnych \(\displaystyle{ c,d\in C}\) mamy \(\displaystyle{ c\sqsubseteq d \Leftrightarrow c\sqsubseteq d}\) oczywiście i jeśli \(\displaystyle{ c\in C, d\in C \setminus C=\left\{ \right\}}\) więc warunek \(\displaystyle{ c\sqsubseteq d}\) będzie pusto spełniony, a więc \(\displaystyle{ (C,\sqsubseteq) \preccurlyeq (C,\sqsubseteq)}\).

2.Antysymetria. Niech \(\displaystyle{ (C,\sqsubseteq) \preccurlyeq (C',\sqsubseteq')}\) i \(\displaystyle{ (C',\sqsubseteq') \preccurlyeq (C,\sqsubseteq)}\). Z tego wynika ( ) że \(\displaystyle{ C \subset C'}\) oraz \(\displaystyle{ C' \subset C}\), a więc \(\displaystyle{ C=C'}\). Pokażemy że \(\displaystyle{ \left( \sqsubseteq\right) =\left( \sqsubseteq'\right)}\), to jednak łatwo wynika z warunku \(\displaystyle{ \bigwedge\limits_{c,d\in C} (c\sqsubseteq d \Leftrightarrow c\sqsubseteq' d)}\) i faktu że te relacje są określone na tym samym zbiorze. A więc \(\displaystyle{ \left( \sqsubseteq\right) =\left( \sqsubseteq'\right)}\) i co za tym idzie \(\displaystyle{ (C,\sqsubseteq) = (C',\sqsubseteq')}\), co kończy dowód antysymetrii.

3. Przechodniość. Niech \(\displaystyle{ (C,\sqsubseteq) \preccurlyeq (C',\sqsubseteq')}\) i \(\displaystyle{ (C',\sqsubseteq') \preccurlyeq (C'',\sqsubseteq'')}\). Pokażemy że \(\displaystyle{ (C,\sqsubseteq) \preccurlyeq (C'',\sqsubseteq'')}\). Pierwsze założenie daje \(\displaystyle{ C \subset C'}\), drugie podobnie \(\displaystyle{ C' \subset C''}\), a więc z przechodniości inkluzji \(\displaystyle{ C \subset C''}\), co jest pierwszym z trzech warunków na to by \(\displaystyle{ (C,\sqsubseteq) \preccurlyeq (C'',\sqsubseteq'')}\). Podobnie rozpoczynamy sprawdzać drugi warunek. Pierwsze założenie daje \(\displaystyle{ \bigwedge\limits_{c,d\in C} (c\sqsubseteq d \Leftrightarrow c\sqsubseteq' d)}\), drugie daje \(\displaystyle{ \bigwedge\limits_{c,d\in C'} (c\sqsubseteq' d \Leftrightarrow c\sqsubseteq'' d)}\). Ponieważ \(\displaystyle{ C \subset C'}\), więc dla dowolnych \(\displaystyle{ c,d}\) w \(\displaystyle{ C}\) mamy \(\displaystyle{ c\sqsubseteq' d \Leftrightarrow c\sqsubseteq'' d}\) oraz dla dowolnych \(\displaystyle{ c,d}\) w \(\displaystyle{ C}\) mamy \(\displaystyle{ c\sqsubseteq d \Leftrightarrow c\sqsubseteq' d}\), możemy zatem to połączyć \(\displaystyle{ \bigwedge\limits_{c,d\in C} (c\sqsubseteq d \Leftrightarrow c\sqsubseteq'' d)}\), co jest drugim sprawdzanym warunkiem. Podobnie rozpoczynamy sprawdzać trzeci warunek. Pierwsze założenie daje, że jeśli \(\displaystyle{ c\in C,d\in C'\setminus C}\) to \(\displaystyle{ c\sqsubseteq' d}\), drugie daje, że jeśli \(\displaystyle{ c\in C',d\in C''\setminus C'}\) to \(\displaystyle{ c\sqsubseteq'' d}\). Niech \(\displaystyle{ c\in C, d\in C''\setminus C}\). Pokażemy że \(\displaystyle{ c\sqsubseteq'' d}\). Ponieważ \(\displaystyle{ c\in C \subset C'}\), to \(\displaystyle{ c\in C'}\), i jeśli, \(\displaystyle{ d\in C''\setminus C'}\) to \(\displaystyle{ c\sqsubseteq'' d}\), co chciałem wykazać. Pozostaje zatem do rozważenia przypadek gdy: \(\displaystyle{ d\not\in C''\setminus C'}\) i \(\displaystyle{ d\in C''\setminus C}\) (założenia), czyli \(\displaystyle{ d \in C'', d\not\in C, d \in C'}\), mamy więc \(\displaystyle{ c\in C,d\in C'\setminus C}\), więc wnioskujemy że \(\displaystyle{ c\sqsubseteq' d}\), i ponieważ \(\displaystyle{ \sqsubseteq''}\) rozszerza \(\displaystyle{ \sqsubseteq'}\), a więc \(\displaystyle{ c\sqsubseteq'' d}\), co było trzecim ostatnim warunkiem. A więc \(\displaystyle{ (C,\sqsubseteq) \preccurlyeq (C'',\sqsubseteq'')}\).\(\displaystyle{ \square}\)

A więc \(\displaystyle{ \left( W,\preccurlyeq\right)}\) jest zbiorem uporządkowanym. Przypominam, \(\displaystyle{ W}\) jest zbiorem złożonym z wszystkich podzbiorów zbioru \(\displaystyle{ X}\) dobrze uporządkowanych, wraz z dobrymi porządkami.
Niech \(\displaystyle{ D\subset W}\) będzie łańcuchem w sensie \(\displaystyle{ \preccurlyeq}\). Zdefiniujmy \(\displaystyle{ C_0}\) jako unię wszystkich pierwszych współrzędnych elementów \(\displaystyle{ D}\) i \(\displaystyle{ \sqsubseteq_0}\) jako unię drugich współrzędnych elementów \(\displaystyle{ D}\). Niewątpliwie \(\displaystyle{ C_0\subset X}\). Ponieważ \(\displaystyle{ D}\) jest łańcuchem w sensie \(\displaystyle{ \preccurlyeq}\), to relacja \(\displaystyle{ \sqsubseteq_0}\) jest porządkiem liniowym na \(\displaystyle{ C_0}\).
Jest porządkiem liniowym, hm... Tu korzystają pewnie z tego, że jeśli \(\displaystyle{ S}\) jest dowolnym zbiorem złożonym z liniowych porządków na podzbiorach \(\displaystyle{ X}\), i takim, że dla dowolnych dwóch liniowych porządków w rodzinie \(\displaystyle{ S}\) jeden jest rozszerzeniem drugiego, to relacja \(\displaystyle{ \bigcup S}\) jest liniowym porządkiem. A czy jest takie twierdzenie Swoją drogą bardzo ciekawe.
Awatar użytkownika
Dasio11
Moderator
Moderator
Posty: 10211
Rejestracja: 21 kwie 2009, o 19:04
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 40 razy
Pomógł: 2359 razy

Lemat Kuratowskiego-Zorna

Post autor: Dasio11 »

Powszechnie znany fakt.
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: Lemat Kuratowskiego-Zorna

Post autor: Jakub Gurak »

Niech \(\displaystyle{ \mathbb{D}\subset \mathbb{B}}\) będzie łańcuchem w sensie \(\displaystyle{ \preccurlyeq}\). Zdefiniujmy:

\(\displaystyle{ S= \bigcup\left\{ C\subset X\Bigl| \ \ \bigvee\limits_{ R\subset X\times X} \left( C,R\right) \in\mathbb{D} \right\}}\) oraz \(\displaystyle{ \le := \bigcup\left\{ R\subset X \times X\Bigl| \ \ \bigvee\limits_{ C\subset X } \left( C,R\right) \in\mathbb{D} \right\}.}\)

Tzn. zbiór \(\displaystyle{ S}\) to suma wszystkich zbiorów dobrze uporządkowanych z łańcucha \(\displaystyle{ \mathbb{D}}\), a \(\displaystyle{ \le}\) jest sumą tych dobrych porządków określonych na tych zbiorach. Nim sprawdzimy, że \(\displaystyle{ \left( S, \le \right)}\) jest ograniczeniem górnym tego łańcucha musimy zapewnić niestety, że \(\displaystyle{ \left( S, \le \right) \in \mathbb{B}.}\) Niewątpliwie \(\displaystyle{ S\subset X}\). jako suma rodziny podzbiorów \(\displaystyle{ X}\). Ponieważ elementy \(\displaystyle{ \mathbb{D}}\) są zbiorami dobrze uporządkowanymi (a więc i liniowo) , ponieważ \(\displaystyle{ \mathbb{D}}\) jest łańcuchem w sensie \(\displaystyle{ \preccurlyeq}\), więc tzn. między innymi, że dla dowolnych takich dwóch liniowych porządków jeden jest rozszerzeniem drugiego, więc na mocy tego powszechnie znanego faktu \(\displaystyle{ \le}\) jest liniowym porządkiem na swoim polu. Łatwo się przekonać, że tym polem jest dokładnie zbiór \(\displaystyle{ S}\). Dowód, że \(\displaystyle{ \le}\) jest dobrym porządkiem na \(\displaystyle{ S}\) jest niestety bardzo żmudny (i zjadłem na nim zęby). Gdy to wykażemy, to \(\displaystyle{ \left( S, \le \right)}\) jest elementem \(\displaystyle{ \mathbb{B}.}\) Należy teraz sprawdzić, że taki element \(\displaystyle{ \left( S, \le \right)}\) jest ograniczeniem górnym tego łańcucha. W tym celu niech \(\displaystyle{ (C,\sqsubseteq) \in \mathbb{D}.}\) Należy pokazać, że \(\displaystyle{ (C,\sqsubseteq) \preccurlyeq \left( S, \le \right)}\). Należy pokazać trzy punkty w definicji, a ostatni jest dosyć żmudny niestety. Gdy to sprawdzimy, to \(\displaystyle{ \left( S, \le \right)}\) jest ograniczeniem górnym tego łańcucha \(\displaystyle{ \mathbb{D}}\), i otrzymujemy, ze każdy łańcuch w \(\displaystyle{ \left( \mathbb{B},\preccurlyeq\right)}\) ma ograniczenie górne.

Stosując Lemat Zorna wnioskujemy, że w zbiorze uporządkowanym \(\displaystyle{ \left( \mathbb{B},\preccurlyeq\right)}\) jest element maksymalny. Taki element maksymalny jest elementem zbioru uporządkowanego \(\displaystyle{ \mathbb{B}}\), czyli w tym wypadku podzbiorem zbioru \(\displaystyle{ X}\) dobrze uporządkowanym, oznaczmy go \(\displaystyle{ \left( C,\sqsubseteq\right)}\). Jeśli zatem \(\displaystyle{ C=X}\), to ten dobry porządek \(\displaystyle{ \sqsubseteq}\) na zbiorze \(\displaystyle{ C}\) równym \(\displaystyle{ X}\) świadczy o tym, że zbiór \(\displaystyle{ X}\) da się dobrze uporządkować. Pozostaje przyjąć dla dowodu nie wprost, że tak nie jest. Przypominam, element maksymalny \(\displaystyle{ \left( C,\sqsubseteq\right)}\) jest podzbiorem zbioru \(\displaystyle{ X}\) dobrze uporządkowanym. Przypuszczamy dla dowodu nie wprost, że jest on określony na istotnym podzbiorze \(\displaystyle{ X}\). Istnieje wtedy element \(\displaystyle{ a\in X \setminus C}\). Ustalmy taki element \(\displaystyle{ a}\). Rozważmy zbiór \(\displaystyle{ C}\) z dodanym jednym elementem \(\displaystyle{ a}\) jako największym (oznaczmy ten porządek jako \(\displaystyle{ \sqsubseteq'}\)). Jest to dobry porządek, gdyż \(\displaystyle{ \sqsubseteq}\) był dobrym porządkiem na \(\displaystyle{ C}\), zatem \(\displaystyle{ \left( C \cup \left\{ a\right\},\sqsubseteq'\right)}\) jest również zbiorem dobrze uporządkowanym, podzbiorem zbioru \(\displaystyle{ X}\) dobrze uporządkowanym, zatem jest elementem \(\displaystyle{ \mathbb{B}}\). I jest elementem silnie większym w sensie \(\displaystyle{ \preccurlyeq}\) od elementu maksymalnego \(\displaystyle{ \left( C,\sqsubseteq\right)}\). Jest od niego różny, bo jest określony na innym zbiorze, na większym zbiorze o jeden element \(\displaystyle{ a}\), zatem są to różne zbiory dobrze uporządkowane, i \(\displaystyle{ \left( C \cup \left\{ a\right\},\sqsubseteq'\right)}\) jest większy od \(\displaystyle{ \left( C,\sqsubseteq\right)}\) w sensie \(\displaystyle{ \preccurlyeq}\), gdyż jest jego rozszerzeniem przez dodanie jednego elementu \(\displaystyle{ a}\) większego od wszystkich zastanych, więc jest większy względem \(\displaystyle{ \preccurlyeq}\). A ponieważ \(\displaystyle{ \left( C,\sqsubseteq\right)}\) był elementem maksymalnym, to nie ma w \(\displaystyle{ \mathbb{B}}\) elementów od niego silnie większych. Otrzymaliśmy więc sprzeczność, która kończy rozumowanie.\(\displaystyle{ \square}\)


Odświeżam temat jednak w innym celu. Wyznaczyłem sobie sam takie ciekawe zadanie:

Niech \(\displaystyle{ X}\) będzie zbiorem. Rozważmy rodzinę \(\displaystyle{ \mathbb{B}}\) wszystkich liniowych porządków na jakichkolwiek podzbiorach zbioru \(\displaystyle{ X}\) (chyba tworzą one zbiór).

Rozważmy podobną relację \(\displaystyle{ \preccurlyeq}\) na elementach \(\displaystyle{ \mathbb{B}:}\) (jeśli \(\displaystyle{ \le}\) jest elementem \(\displaystyle{ \mathbb{B}:}\), to \(\displaystyle{ \le _{L} =\le _{P}:=X _{ \le }}\) )

\(\displaystyle{ \left( \le_{1}\right) \preccurlyeq \left( \le_{2}\right) \Longleftrightarrow\left( \bigwedge\limits_{x,y\in X _{ \le _{1} } } \left( x \le _{1}y \leftrightarrow x \le _{2}y\right) \right) \wedge \Bigl ( x \in X _{ \le _{1} },y \in X _{ \le _{2} } \setminus X _{ \le _{1} } \Longrightarrow x \le _{2}y\Bigr) .}\)

Czyli jeden liniowy porządek \(\displaystyle{ \le _{1}}\) na podzbiorze \(\displaystyle{ X}\) jest mniejszy od drugiego liniowego porządku \(\displaystyle{ \le _{2}}\), gdy \(\displaystyle{ \le _{2}}\) jest rozszerzeniem \(\displaystyle{ \le _{1}}\), i to przez dodanie elementów większych od wszystkich zastanych, co przedstawia ilustracja:



Mam teraz pytanie: czy to istotnie jest relacja porządku ( nie chciałoby mi się znowu robić takiego podobnego żmudnego dowodu).

Jeśli tak, to spróbuję wykazać, że w zbiorze uporządkowanym \(\displaystyle{ \left( \mathbb{B},\preccurlyeq\right)}\) każdy łańcuch posiada supremum, a bardziej wymownie chodzi o to, że jeśli weźmiemy dowolny łańcuch \(\displaystyle{ \mathbb{D} \subset \mathbb{B}}\) złożony z liniowych porządków, to chodzi o pokazanie, że relacja \(\displaystyle{ \bigcup \mathbb {D}}\) jest liniowym porządkiem na podzbiorze \(\displaystyle{ X}\), i jest supremum dla rodziny \(\displaystyle{ \mathbb{D}}\) takich liniowych porządków. Myślę, że to ciekawe.

Proszę najpierw o odpowiedź czy jest to zbiór uporządkowany
Awatar użytkownika
Dasio11
Moderator
Moderator
Posty: 10211
Rejestracja: 21 kwie 2009, o 19:04
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 40 razy
Pomógł: 2359 razy

Re: Lemat Kuratowskiego-Zorna

Post autor: Dasio11 »

Jakub Gurak pisze:Dowód, że \(\displaystyle{ \le}\) jest dobrym porządkiem na \(\displaystyle{ S}\) jest niestety bardzo żmudny (i zjadłem na nim zęby).
[...]
Należy pokazać, że \(\displaystyle{ (C,\sqsubseteq) \preccurlyeq \left( S, \le \right)}\). Należy pokazać trzy punkty w definicji, a ostatni jest dosyć żmudny niestety.
Nie wiem, jak się do tego zabierałeś, ale:

Aby wykazać, że zachodzi warunek \(\displaystyle{ (\mathrm{iii})}\) relacji \(\displaystyle{ (C, \sqsubseteq) \preccurlyeq (S, \le)}\), ustalmy \(\displaystyle{ c \in C, s \in S}\) takie, że \(\displaystyle{ s \le c}\). Wtedy istnieje \(\displaystyle{ (C', \sqsubseteq') \in \mathbb{D}}\) takie że \(\displaystyle{ s \in C'}\). Jeśli \(\displaystyle{ (C', \sqsubseteq') \preccurlyeq (C, \sqsubseteq)}\), to w szczególności \(\displaystyle{ C' \subseteq C}\), co od razu daje \(\displaystyle{ s \in C}\), tak jak chcemy. W przeciwnym razie \(\displaystyle{ (C, \sqsubseteq) \preccurlyeq (C', \sqsubseteq')}\) i wtedy \(\displaystyle{ c \in C, s \in C'}\) oraz \(\displaystyle{ s \sqsubseteq' c}\). Z warunku \(\displaystyle{ (\mathrm{iii})}\) dostajemy \(\displaystyle{ s \in C}\), co kończy dowód.

Dowód że \(\displaystyle{ \le}\) jest dobrym porządkiem na \(\displaystyle{ S}\) jest równie prosty. Ustalmy niepusty podzbiór \(\displaystyle{ B \subseteq S}\) i weźmy \(\displaystyle{ b \in B}\), a następnie wybierzmy \(\displaystyle{ (C, \sqsubseteq) \in \mathbb{D}}\), takie że \(\displaystyle{ b \in C}\). Wtedy

\(\displaystyle{ B_0 = \{ a \in S : a \le b \} \cap B = \{ a \in C : a \sqsubseteq b \} \cap B}\)

jest niepustym podzbiorem \(\displaystyle{ C}\) (wszak \(\displaystyle{ b \in B_0}\)), zatem istnieje element \(\displaystyle{ b_0 \in B_0}\) najmniejszy w \(\displaystyle{ B_0}\) względem \(\displaystyle{ \sqsubseteq}\), w szczególności więc \(\displaystyle{ b_0 \sqsubseteq b}\) oraz \(\displaystyle{ b_0 \le b}\). Pozostaje pokazać, że \(\displaystyle{ b_0}\) jest najmniejszy w \(\displaystyle{ B}\) względem \(\displaystyle{ \le}\), toteż ustalmy \(\displaystyle{ b' \in B}\). Jeśli \(\displaystyle{ b \le b'}\), to tym bardziej \(\displaystyle{ b_0 \le b'}\). Jeśli zaś \(\displaystyle{ b' \le b}\), to \(\displaystyle{ b' \in B_0}\), zatem \(\displaystyle{ b_0 \sqsubseteq b'}\) i stąd \(\displaystyle{ b_0 \le b'}\), QED.

Jakub Gurak pisze:Mam teraz pytanie: czy to istotnie jest relacja porządku ( nie chciałoby mi się znowu robić takiego podobnego żmudnego dowodu).
Tak, z tego samego powodu - bo w dowodzie, że \(\displaystyle{ \preccurlyeq}\) jest relacją częściowego porządku na \(\displaystyle{ \mathbb{B}}\), nie korzysta się nigdzie z faktu, że elementami \(\displaystyle{ \mathbb{B}}\) są dobre porządki.
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: Lemat Kuratowskiego-Zorna

Post autor: Jakub Gurak »

spróbuję wykazać, że w zbiorze uporządkowanym \(\displaystyle{ \left( \mathbb{B},\preccurlyeq\right)}\) każdy łańcuch posiada supremum, a bardziej wymownie chodzi o to, że jeśli weźmiemy dowolny łańcuch \(\displaystyle{ \mathbb{D} \subset \mathbb{B}}\) złożony z liniowych porządków, to chodzi o pokazanie, że relacja \(\displaystyle{ \bigcup \mathbb {D}}\) jest liniowym porządkiem na podzbiorze \(\displaystyle{ X}\), i jest supremum dla rodziny \(\displaystyle{ \mathbb{D}}\) takich liniowych porządków.
Udało się mi to pokazać.

Dowód:

Niech \(\displaystyle{ \mathbb {D} \subset \mathbb {B}}\) będzie dowolnym niepustym łańcuchem. Wtedy jeśli \(\displaystyle{ S _{1},S _{2}}\) są elementami \(\displaystyle{ \mathbb {D}}\), to \(\displaystyle{ S _{1},S _{2}}\) są liniowymi porządkami, i są porównywalne względem \(\displaystyle{ \preccurlyeq}\) , więc \(\displaystyle{ S _{1}}\) jest rozszerzeniem \(\displaystyle{ S _{2}}\) lub \(\displaystyle{ S _{2}}\) jest rozszerzeniem \(\displaystyle{ S _{1}}\), więc ten powszechny fakt gwarantuje, że relacja \(\displaystyle{ \bigcup \mathbb {D}}\) jest liniowym porządkiem na swoim polu, czyli na pewnym podzbiorze zbioru \(\displaystyle{ X.}\) Zatem jest elementem \(\displaystyle{ \mathbb{B}}\). Wykażemy teraz, że jest to supremum rodziny takich liniowych porządków.

Niech \(\displaystyle{ S \in\mathbb {D}.}\) Pokażemy najpierw, że \(\displaystyle{ S\preccurlyeq \bigcup \mathbb {D}.}\) Z własności sumy \(\displaystyle{ S\subset \bigcup \mathbb {D},}\) zatem relacja \(\displaystyle{ \bigcup \mathbb {D}}\) rozszerza \(\displaystyle{ S}\). Wykażemy teraz punkt drugi odnośnie warunku, że \(\displaystyle{ S \preccurlyeq\bigcup\mathbb{D}.}\) Niech \(\displaystyle{ x\in X _{S},y \in X_{ \bigcup D} \setminus X_{S}.}\) Pokażemy, że \(\displaystyle{ x\left( \bigcup\mathbb {D}\right) y.}\) Mamy \(\displaystyle{ x \in X _{S},y \in X _{ \bigcup D}, y \not\in X _{S}.}\) mamy \(\displaystyle{ y \in X_{ \bigcup D},}\) więc \(\displaystyle{ y \in X _{S _{0} },}\) dla pewnego \(\displaystyle{ S _{0} \in\mathbb {D}.}\) (gdyby \(\displaystyle{ y \not\in X _{C}}\) dla żadnego \(\displaystyle{ C \in \mathbb {D}}\), to również \(\displaystyle{ y\not\in \bigcup_{C \in \mathbb {D} }X _{C},}\) a \(\displaystyle{ y \in X_{ \bigcup D} = \bigcup_{C \in \mathbb {D}} X _{C}.}\)
LEMAT (DLA DOCIEKLIWYCH):    
zasada równości zbiorów daje więc sprzeczność) Zatem \(\displaystyle{ y \in X _{S _{0} },}\) dla pewnego \(\displaystyle{ S _{0} \in \mathbb {D}.}\) Ponieważ zbiory \(\displaystyle{ S _{0},S}\) są elementami \(\displaystyle{ \mathbb {D}}\), a \(\displaystyle{ \mathbb {D}}\) jest łańcuchem, więc są one porównywalne. Przypadek \(\displaystyle{ S _{0}\prec S}\) zajść nie może- bo on prowadzi do \(\displaystyle{ y \in X _{S _{0} } \subset X _{S }}\), a więc \(\displaystyle{ y \in X _{S}-}\) sprzeczność. Wobec czego musi być \(\displaystyle{ S\prec S _{0},}\) więc stosując definicję porządku \(\displaystyle{ \preccurlyeq}\) do \(\displaystyle{ x\in X _{S},y \in X _{S _{0} } \setminus X _{S },}\) wnioskujemy, że \(\displaystyle{ x\left( S _{0} \right) y}\), a więc tym bardziej (\(\displaystyle{ S _{0} \in \mathbb {D}}\) ),że \(\displaystyle{ x\left( \bigcup \mathbb {D}\right) y,}\) co należało pokazać.

Zatem \(\displaystyle{ S\preccurlyeq \bigcup \mathbb {D},}\) i \(\displaystyle{ \bigcup \mathbb {D}}\) jest ograniczeniem górnym dla \(\displaystyle{ \mathbb {D}.}\) Pozostaje wykazać, że jest to najmniejsze ograniczenie górne dla \(\displaystyle{ \mathbb {D}.}\) Niech \(\displaystyle{ S\in\mathbb {B}}\) będzie ograniczeniem górnym dla \(\displaystyle{ \mathbb {D}.}\) Pokażemy, że \(\displaystyle{ \bigcup \mathbb {D}\preccurlyeq S.}\) Ponieważ \(\displaystyle{ S}\) jest ograniczeniem górnym dla \(\displaystyle{ \mathbb {D}.}\) więc mamy \(\displaystyle{ A\preccurlyeq S,}\) dla każdego zbioru \(\displaystyle{ A \in \mathbb {D}.}\) Jeśli więc \(\displaystyle{ A \in \mathbb {D},}\) więc z definicji \(\displaystyle{ \preccurlyeq}\) otrzymujemy, że \(\displaystyle{ S}\) jest rozszerzeniem \(\displaystyle{ A}\), czyli \(\displaystyle{ S \supset A}\). Zatem dla każdego \(\displaystyle{ A \in \mathbb {D},}\) mamy \(\displaystyle{ A \subset S}\), więc również \(\displaystyle{ \bigcup \mathbb {D} \subset S.}\) Zatem liniowy porządek \(\displaystyle{ S}\) rozszerza liniowy porządek \(\displaystyle{ \left( \bigcup \mathbb {D}\right) .}\) Aby sprawdzić punkt drugi: niech \(\displaystyle{ x\in X_{ \bigcup D},y \in X_{ S} \setminus X_{\bigcup D}.}\) Pokażemy, że \(\displaystyle{ x\left( S\right) y.}\) Ponieważ \(\displaystyle{ x \in X_{ \bigcup D}}\), więc \(\displaystyle{ x \in X _{A}}\) dla pewnego \(\displaystyle{ A\in \mathbb {D}}\) (uzasadnienie takie samo jak wcześniej). Mamy \(\displaystyle{ y \not\in X_{\bigcup D},}\) więc \(\displaystyle{ y \not\in X_{ C},}\) dla żadnego \(\displaystyle{ C\in \mathbb {D}}\)( gdyby było \(\displaystyle{ y \in X_{ C}}\), to tym bardziej byłoby \(\displaystyle{ y \in \bigcup_{C \in \mathbb {D}} X _{C}=X_{ \bigcup D}}\), a więc \(\displaystyle{ y\in X_{\bigcup D}}\)- sprzeczność) więc \(\displaystyle{ y}\) nie jest elementem żadnego ze zbiorów \(\displaystyle{ X_{ C}}\)(gdzie \(\displaystyle{ C\in \mathbb {D}}\)), więc w szczególności \(\displaystyle{ y \not\in X _{A}}\). Ponieważ mamy \(\displaystyle{ A\in \mathbb {D},}\) więc \(\displaystyle{ A\preccurlyeq S,}\) więc stosując definicję \(\displaystyle{ \preccurlyeq}\) do \(\displaystyle{ y \in X _{S}, y \not\in X _{A}, x \in X _{A}}\) wnioskujemy, że \(\displaystyle{ x\left( S\right) y,}\) co należało pokazać.

Zatem \(\displaystyle{ \bigcup \mathbb {D}\preccurlyeq S.}\) i \(\displaystyle{ \bigcup \mathbb {D}}\) jest najmniejszym ograniczeniem górnym dla \(\displaystyle{ \mathbb {D},}\) a więc \(\displaystyle{ \bigcup \mathbb {D}}\) jest supremum dla \(\displaystyle{ \mathbb {D}.\square}\)

Można chyba też łatwo pokazać, że w zbiorze uporządkowanym \(\displaystyle{ \left( \mathbb{B}, \subset\right)}\) (czyli ta sama rodzina liniowych porządków, porządek liniowy jest większy od danego gdy jest jego rozszerzeniem, czy to znaczy to samo, że jest jego nadzbiorem tutaj pewny nie jestem) wtedy każdy niepusty łańcuch posiada supremum, a bardziej wymownie chodzi o to, że jeśli weźmiemy dowolny niepusty łańcuch \(\displaystyle{ \mathbb{D} \subset \mathbb{B}}\) złożony z liniowych porządków, to relacja \(\displaystyle{ \bigcup \mathbb {D}}\) jest liniowym porządkiem na podzbiorze \(\displaystyle{ X}\), i jest supremum dla rodziny \(\displaystyle{ \mathbb{D}}\) takich liniowych porządków- wynika to chyba łatwo z tego powszechnego faktu oraz własności sumy rodziny zbiorów (i związku z supremum).

Wszystko byłoby łatwe, tylko jednej rzeczy nadal nie jestem pewny: czy dla dwóch liniowych porządków na podzbiorach zbioru \(\displaystyle{ X}\) warunek, że jeden porządek jest rozszerzeniem drugiego znaczy to samo, że jest jego nadzbiorem

Przypomnę, że jeśli \(\displaystyle{ \left( X, \le _{X} \right)}\), \(\displaystyle{ \left( Y, \le _{Y} \right)}\) są zbiorami uporządkowanymi, to porządek \(\displaystyle{ \le _{Y}}\) jest rozszerzeniem porządku \(\displaystyle{ \le _{X}}\) gdy zachodzi warunek dla dowolnych \(\displaystyle{ a,b \in X:}\)

\(\displaystyle{ a\le _{X}b \Longrightarrow a\le _{Y}b.}\)

Tzn. jeśli \(\displaystyle{ a}\) jest mniejszy od \(\displaystyle{ b}\) względem danego porządku (na \(\displaystyle{ X}\)) to tym bardziej \(\displaystyle{ a}\) musi być mniejsze od \(\displaystyle{ b}\) względem porządku rozszerzającego.

Proszę o odpowiedź na moje pytanie.
Awatar użytkownika
Dasio11
Moderator
Moderator
Posty: 10211
Rejestracja: 21 kwie 2009, o 19:04
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 40 razy
Pomógł: 2359 razy

Re: Lemat Kuratowskiego-Zorna

Post autor: Dasio11 »

Tak, to samo.
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: Lemat Kuratowskiego-Zorna

Post autor: Jakub Gurak »

Można też rozważać, że gdy \(\displaystyle{ X}\) jest zbiorem, to dla rodziny \(\displaystyle{ \mathbb{B}}\) wszystkich liniowych porządków na podzbiorach zbioru \(\displaystyle{ X}\), relację porządku, taką, że liniowy porządek jest większy od danego gdy jest jego rozszerzeniem przez dodanie elementów mniejszych od wszystkich zastanych, formalnie definiujemy porządek \(\displaystyle{ \succcurlyeq}\) na \(\displaystyle{ \mathbb{B}}\)(jeśli \(\displaystyle{ R\in\mathbb{B}}\), to \(\displaystyle{ X_R}\) oznacza zbiór na którym jest określony porządek \(\displaystyle{ R}\):

\(\displaystyle{ R\succcurlyeq S \Longleftrightarrow\left(S \hbox{ rozszerza } R \hbox{ i } x\in X _{R},y\in X _{S} \setminus X _{R} \Longrightarrow y(S)x \right) .}\)

Chcę uzasadnić, że taka relacja jest relacją porządku, a następnie, że jeśli weźmiemy dowolny łańcuch \(\displaystyle{ \mathbb{D}\subset\mathbb{B}}\) to relacja \(\displaystyle{ \bigcup\mathbb{D} }\) jest liniowym porządkiem, i jest to takie supremum tej rodziny liniowych porządków. Wydaję mi się, że uda mi się to uzasadnić, ale pewny nie jestem.

Jeśli rozważymy rodzinę porządków odwrotnych do porządków liniowych tej rodziny, z relacją \(\displaystyle{ \sqsubseteq}\), która oznacza rozważany wcześniej porządek- rozszerzenie przez dodanie elementów większych:

\(\displaystyle{ \mathbb{D}=\left\{ R ^{-1}\Bigl| \ \ R\in\mathbb{B} \right\}, }\)

to intuicyjnie jest oczywiste, że zawsze

\(\displaystyle{ R\succcurlyeq S \Longleftrightarrow R^{-1}\sqsubseteq S ^{-1}. }\) :mrgreen:

Tak, jeśli porżądek liniowy \(\displaystyle{ S}\) jest rozszerzeniem porządku \(\displaystyle{ R}\) przez dodanie elementów mniejszych, to oznacza, że na odpowiadających porządkach odwrotnych mamy rozszerzenie przez dodanie elementów większych. Intuicyjnie jest to oczywiste, ale formalnie nie, więc musimy to udowodnić, bo jak mówi mój znajomy najtrudniej jest udowodnić rzeczy oczywiste. :) Spróbujmy:

Dowód:

Niech \(\displaystyle{ R,S\in\mathbb{B}.}\)

Załóżmy, że \(\displaystyle{ R\succcurlyeq S,}\) wnioskujemy stąd, że \(\displaystyle{ S}\) rozszerza \(\displaystyle{ R}\), czyli \(\displaystyle{ S\supset R}\), czyli \(\displaystyle{ R\subset S}\), z własności relacji otrzymujemy zatem \(\displaystyle{ R^{-1}\subset S^{-1}}\), a zatem porządek liniowy \(\displaystyle{ S^{-1}}\) rozszerza porządek liniowy \(\displaystyle{ R^{-1}}\).

Pozostaje pokazać punkt drugi( w pierwszej połowie dowodu). Niech \(\displaystyle{ x\in X _{R ^{-1} }, y\in X _{S ^{-1} } \setminus X _{R ^{-1} } }\), pokażemy, że \(\displaystyle{ x\left( S ^{-1} \right)y. }\)

Równoważnie mamy pokazać, że \(\displaystyle{ \left( x,y\right)\in S ^{-1}, }\) czyli że \(\displaystyle{ \left( y,x\right)\in S.}\)

Mamy \(\displaystyle{ x\in X_R}\)( bo \(\displaystyle{ X_{R^{-1}}=X_R }\)), oraz \(\displaystyle{ y\not\in X_R }\)(gdyby \(\displaystyle{ y\in X_R=X_{R^{-1}}}\) to \(\displaystyle{ y\in X_{R^{-1}}}\)- sprzeczność) oraz \(\displaystyle{ y\in X_S=X_{S^{-1}}}\), zatem \(\displaystyle{ x\in X_R, y\in X_S \setminus X_R}\), stosując zatem drugą część definicji porządku \(\displaystyle{ \succcurlyeq}\) otrzymujemy, że \(\displaystyle{ y(S)x}\), czyli \(\displaystyle{ (y,x)\in S,}\) czyli \(\displaystyle{ (x,y)\in S^{-1}.}\) Spełniony zatem jest punkt drugi, a więc \(\displaystyle{ R^{-1}\sqsubseteq S ^{-1}.}\)


Załóżmy teraz, że \(\displaystyle{ R^{-1}\sqsubseteq S ^{-1},}\) i pokażmy, że \(\displaystyle{ R\succcurlyeq S}\). Z definicji porządku \(\displaystyle{ \sqsubseteq}\) otrzymujemy, że porządek \(\displaystyle{ S^{-1}}\) rozszerza porządek \(\displaystyle{ R^{-1}}\), a więc \(\displaystyle{ R^{-1}\subset S^{-1}}\), z ogólnych własności relacji otrzymujemy, że \(\displaystyle{ R=\left( R ^{-1}\right) ^{-1} \subset \left( S ^{-1} \right)^{-1}=S,}\) a więc porządek liniowy \(\displaystyle{ S}\) rozszerza porządek liniowy \(\displaystyle{ R}\).

Pozostaje pokazać punkt drugi:

Niech \(\displaystyle{ x\in X_R, y\in X_S \setminus X _{R}.}\) Pokażemy, że \(\displaystyle{ y(S)x.}\)

Ponieważ \(\displaystyle{ X_R=X_{R^-1}}\), to \(\displaystyle{ x\in X _{R^-1} }\), ponieważ \(\displaystyle{ X_S=X_{S^-1}}\), to \(\displaystyle{ y\in X_{S^{-1}}}\), oraz \(\displaystyle{ y\not\in X_{R ^{-1} } }\) (Gdyby \(\displaystyle{ y\in X _{R ^{-1} }=X_R}\), to byłoby \(\displaystyle{ y\in X_R}\)- sprzeczność ). Mamy zatem \(\displaystyle{ x\in X_{R^{-1}} ,y\in X_{S^{-1}} \setminus X_{R ^{-1} }.}\) Stosując drugą część definicji porządku \(\displaystyle{ \sqsubseteq}\) otrzymujemy, że \(\displaystyle{ x(S^{-1}) y,}\) czyli, że \(\displaystyle{ \left( x,y\right)\in S^{-1}, }\) a więc \(\displaystyle{ (y,x)\in S}\), czyli \(\displaystyle{ y(S)x. }\)

Wobec czego spełniony jest również punkt drugi, a więc \(\displaystyle{ R\succcurlyeq S. \square}\) :D :lol:

Aby uzasadnić to co chciałem, to łatwo zauważyć, że rodzina porzadków odwrotnych \(\displaystyle{ \mathbb{D}}\) zawiera się w rodzinie \(\displaystyle{ \mathbb{B}}\). Inkluzja w drugą stronę: niech \(\displaystyle{ R\in\mathbb{B}}\), wtedy \(\displaystyle{ R}\) jest porządkiem liniowym na podzbiorze zbioru \(\displaystyle{ X}\), wtedy \(\displaystyle{ R^{-1}}\) jest również porządkiem liniowym na tym podzbiorze, a zatem \(\displaystyle{ R^{-1}\in\mathbb{B}}\), a zatem \(\displaystyle{ R=\left( R ^{-1}\right) ^{-1} \in\mathbb{D}, }\) otrzymujemy zatem, że \(\displaystyle{ \mathbb{B}=\mathbb{D}.}\) Skoro wiemy, że na rodzinie \(\displaystyle{ \mathbb{B}}\) relacja \(\displaystyle{ \sqsubseteq}\) jest relacją porządku, więc to oznacza, że również na rodzinie \(\displaystyle{ \mathbb{D}}\)(gdyż to ta sama rodzina) jest relacją porządku, to wobec udowodnionej równoważności \(\displaystyle{ \left( \mathbb{B},\succcurlyeq\right)=\left( \mathbb{D},\sqsubseteq\right) }\), a więc \(\displaystyle{ \left( \mathbb{B},\succcurlyeq\right)}\) jest zbiorem uporządkowanym, dobrze :?:

Skoro wykazałem (w ostatnie wakacje), że w \(\displaystyle{ \left( \mathbb{B},\sqsubseteq\right) }\) każdy niepusty łańcuch posiada supremum (którym, dla łańcucha \(\displaystyle{ \mathbb{D}\subset\mathbb{B}}\) jest \(\displaystyle{ \bigcup \mathbb{D}}\)), to pomysł jest taki żeby wziąć niepusty łańcuch \(\displaystyle{ \mathbb{D} \subset \left( \mathbb{B},\succcurlyeq\right) }\), i rozważyć nową rodzinę zbiorów \(\displaystyle{ \mathbb{D'}=\left\{ R^{-1} \Bigl| \ \ R\in\mathbb{D} \right\} }\) złożoną z porządków odwrotnych do porządków z łańcucha \(\displaystyle{ \mathbb{D}}\). Ponieważ łańcuch \(\displaystyle{ D}\) jest niepusty, to \(\displaystyle{ D'}\) rownież. A trzeba będzie jeszcze sprawdzić, że to istotnie jest łańcuch. A potem \(\displaystyle{ \bigcup\mathbb{D'}}\) jest jego supremum, i na koniec porządek (tą sumę) trzeba odwrócić. To dobry pomysł?
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: Lemat Kuratowskiego-Zorna

Post autor: Jakub Gurak »

Jakub Gurak pisze: 21 lut 2020, o 21:56 otrzymujemy zatem, że \(\displaystyle{ \mathbb{B}=\mathbb{D}.}\) Skoro wiemy, że na rodzinie \(\displaystyle{ \mathbb{B}}\) relacja \(\displaystyle{ \sqsubseteq}\) jest relacją porządku, więc to oznacza, że również na rodzinie \(\displaystyle{ \mathbb{D}}\)(gdyż to ta sama rodzina) jest relacją porządku, to wobec udowodnionej równoważności \(\displaystyle{ \left( \mathbb{B},\succcurlyeq\right)=\left( \mathbb{D},\sqsubseteq\right) }\),
Coś mi tu śmierdziało, i teraz widzę, że chyba to nie jest dobrze. Mamy (dla \(\displaystyle{ R,S\in\mathbb{B}}\)) mamy: \(\displaystyle{ R\succcurlyeq S \Longleftrightarrow R^{-1}\sqsubseteq S ^{-1}. }\) Jednak po prawej stronie równoważności nie stoją tak jak po lewej R i S, tylko \(\displaystyle{ R ^{-1}}\) i \(\displaystyle{ S ^{-1} }\), skąd chyba nie możemy wnioskować, że \(\displaystyle{ \left( \succcurlyeq\right) =\left( \sqsubseteq\right). }\) Da się to poprawić :?:

(Chcę uzasadnić, że \(\displaystyle{ \left( \mathbb {B},\succcurlyeq \right) }\) jest zbiorem uporządkowanym, a następnie, że jeśli wezmę dowolny łańcuch \(\displaystyle{ \mathbb {D} \subset\mathbb{B}}\) to zbiór \(\displaystyle{ \bigcup\mathbb {D}}\) jest jego supremum. I nie chcę tego robić w sposób analogiczny jak wcześniej- to zbyt żmudne, chciałbym prościej to zrobić ). :lol:
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: Lemat Kuratowskiego-Zorna

Post autor: Jakub Gurak »

Tym ciekawym problemem trzeba będzie się zająć, ale jeszcze się za to nie zabrałem (gdyż rozpoczęły się dla mnie od piątku wakacje, a do wakacji odkładałem zajęcie się tym problemem, jeszcze się nie zabrałem, póki co lżejsza matematyka).

Uzasadniłem wczoraj, że:
Jakub Gurak pisze: 17 mar 2017, o 11:33 jeśli \(\displaystyle{ S}\) jest dowolnym zbiorem złożonym z liniowych porządków na podzbiorach \(\displaystyle{ X}\), i takim, że dla dowolnych dwóch liniowych porządków w rodzinie \(\displaystyle{ S}\) jeden jest rozszerzeniem drugiego, to relacja \(\displaystyle{ \bigcup S}\) jest liniowym porządkiem.
Tego wczoraj nie uzasadniałem (kiedyś tak). Uzasadniłem, że jeśli prócz tego (prócz tych założeń tego twierdzenia), jeśli dodatkowo każdy liniowy porządek tej rodziny jest gęsty, to suma rodziny porządków gęstych jest gęsta, i gorsze (to już nie jest takie proste, w pewnym momencie nie do końca szczegółowo uzasadniłem, ale w miarę zrozumiale dla mnie) chodzi o to, że jeśli są spełnione założenia odnośnie sumy liniowych porządków, i jeśli każdy liniowy porządek tej rodziny jest ciągły, to suma liniowych porządków jest liniowym porządkiem ciągłym.

Oczywiście suma łańcucha (pod względem inkluzji, rozszerzenia) dobrych porządków nie musi być dobrym porządkiem. Jest to zadanie z testu z ważniaka( w którym początkowo zrobiłem błąd), ale mogę teraz się poprawić, podając prosty kontrprzykład:

Rozważmy dobre porządki na podzbiorach \(\displaystyle{ \NN}\):
\(\displaystyle{ \le _{0}= \left( 0\right), }\)
\(\displaystyle{ \le _{1}=\left( 1, 0\right) ,}\)
\(\displaystyle{ \le _{2}=\left(2, 1, 0\right),}\)
\(\displaystyle{ \le _{3}=\left(3, 2, 1, 0\right),}\)
\(\displaystyle{ \vdots}\)

Wtedy \(\displaystyle{ \bigcup_{n\in\NN} \le _{n}=\left( \ldots,3,2,1,0\right) }\) a więc w \(\displaystyle{ \NN}\) podobnie jak w \(\displaystyle{ \ZZ_{-}}\) nie ma elementu najmniejszego, a więc nie jest to dobry porządek na \(\displaystyle{ \NN}\).

Może dzięki temu zadaniu wpadłem na pomysł odpowiednich rozważań odnośnie porządków gęstych i ciągłych, bez tego nie wiem czy bym wpadł na pomysł rozważania tego.

Uzasadnijmy najpierw prostsze z tych dwóch zadań, że (w sytuacji gdy suma liniowych porządków jest liniowym porządkiem, gdy są spełnione założenia tego powszechnie znanego faktu), gdy jeszcze każdy porządek tej rodziny liniowych porządków \(\displaystyle{ \mathbb{B}}\) na podzbiorach zbioru \(\displaystyle{ X}\) jest gęsty, to\(\displaystyle{ \bigcup\mathbb{B}}\) jest liniowym porządkiem gęstym.

Aby pokazać, że \(\displaystyle{ \le :=\bigcup\mathbb{B}}\) jest gęsta, przypuśćmy nie wprost, że tak nie jest. Wtedy, zgodnie z charakteryzacją porządków gęstych, istnieje przekrój Dedekinda \(\displaystyle{ (X,Y)}\), który daje skok. Wtedy w \(\displaystyle{ x}\) jest element największy \(\displaystyle{ x\in X}\), w \(\displaystyle{ Y}\) jest element najmniejszy \(\displaystyle{ y\in Y}\). Wtedy \(\displaystyle{ x<y}\), a ponieważ \(\displaystyle{ \le}\) jest sumą liniowych porządków, więc \(\displaystyle{ x \le _{1} y}\), dla pewnego liniowego porządku \(\displaystyle{ \le _{1}}\) w \(\displaystyle{ \mathbb{B}}\). Ponieważ \(\displaystyle{ \mathbb{B}}\) jest rodziną porządków gęstych, to \(\displaystyle{ \le _{1}}\) jest gęsty, więc otrzymujemy element \(\displaystyle{ z}\) taki że \(\displaystyle{ x <_{1} z<_1 y. }\) A zatem (\(\displaystyle{ \le _{1} \in \mathbb{B} }\)) \(\displaystyle{ x<z<y}\), co prowadzi do sprzeczności z tym, że zbiory \(\displaystyle{ X,Y}\) tworzą przekroj Dedekinda, i że ten przekrój daje skok. No, ponieważ \(\displaystyle{ x<z}\), a \(\displaystyle{ x}\) jest największy w \(\displaystyle{ X}\), to \(\displaystyle{ z}\) nie należy do \(\displaystyle{ X}\), należy więc do \(\displaystyle{ Y}\), ponieważ element \(\displaystyle{ y}\) jest najmniejszy w \(\displaystyle{ Y}\), więc \(\displaystyle{ y \le z}\), a mamy \(\displaystyle{ z<y}\)- sprzeczność. \(\displaystyle{ \square }\)


Uzasadnimy teraz podobny fakt odnośnie liniowych porządków ciągłych.

Załóżmy, dla rodziny \(\displaystyle{ \mathbb{B}}\) liniowych porządków na podzbiorach zbioru \(\displaystyle{ X}\) podobne założenia, a dodatkowo, że każdy liniowy porządek tej rodziny jest ciągły. Pokażemy, że \(\displaystyle{ \le = \bigcup \mathbb{B}}\) jest liniowym porządkiem ciągłym. Ponieważ każdy liniowy porządek z tej rodziny \(\displaystyle{ \mathbb{B}}\) jest ciągly, a więc i gęsty, więc poprzedni fakt daje że \(\displaystyle{ \le = \bigcup\mathbb{B}}\) jest porządkiem gęstym. Aby wykazać, że \(\displaystyle{ \le}\) jest porządkiem ciągłym, przypuśćmy nie wprost, że tak nie jest. Wtedy istnieje przekrój Dedekinda \(\displaystyle{ (A_1,A_2)}\), który daje lukę. Na początek wyciągnijmy z niepustych zbiorów \(\displaystyle{ A_1,A_2}\) elementy \(\displaystyle{ y\in A_1, x\in A_2. }\) Wtedy ponieważ każdy element \(\displaystyle{ A _{1} }\) jest mniejszy od każdego elementu \(\displaystyle{ A_2}\), więc również \(\displaystyle{ y<x}\). Wtedy, ponieważ \(\displaystyle{ \le }\) jest sumą liniowych porządków, więc \(\displaystyle{ y \le _{0} x}\) gdzie \(\displaystyle{ \le _{0} }\) jest elementem \(\displaystyle{ \mathbb{B}}\). Niech \(\displaystyle{ X _{0} }\) oznacza zbiór na którym jest określony porządek \(\displaystyle{ \le _{0}. }\) Pokażemy, że para zbiorów \(\displaystyle{ \left( A _{1} \cap X _{0}, A _{2} \cap X_0 \right) }\) tworzy przekrój Dedekinda w \(\displaystyle{ \left( X_0, \le _{0}\right) . }\) Wynika to łatwo stąd , ze para zbiorów \(\displaystyle{ \left( A_1, A_2\right) }\) tworzy przekrój Dedekinda w \(\displaystyle{ \left( X _{ \le }, \le \right) ,}\) gdzie \(\displaystyle{ X _{ \le } }\) oznacza zbiór na którym określony jest ten porządek \(\displaystyle{ \le }\) będący sumą liniowych porządków.

Aby to wykazać: mamy \(\displaystyle{ \left( A _{1} \cap X _{0}\right) \cup \left( A _{2} \cap X_0 \right)=\left( A_1 \cup A_2\right) \cap X _{0}=X _{ \le } \cap X _{0}=X _{0}. }\) . Mamy \(\displaystyle{ y\in A_1 \cap X_0, x\in A_2 \cap X_0, }\) a więc są to zbiory niepuste. Niech teraz \(\displaystyle{ a\in A_1 \cap X_0}\), \(\displaystyle{ b\in A_2 \cap X _0}\), pokażemy, że \(\displaystyle{ a \le _{0} b.}\) Przypuśćmy, że tak nie jest. Wtedy \(\displaystyle{ b \le _{0} a}\). Zatem tymbardziej ( \(\displaystyle{ \le _{0} \in \mathbb{B}, \le= \bigcup \mathbb{B} }\)) \(\displaystyle{ b \le a}\), ponieważ \(\displaystyle{ b\in A_2, a \in A_1}\), i zbiory \(\displaystyle{ A_1,A_2}\) tworzą przekrój Dedekinda w \(\displaystyle{ \left( X _{ \le }, \le \right) ,}\) więc powinno być \(\displaystyle{ a<b}\)- sprzeczność. Wobec tego konieczne jest aby \(\displaystyle{ a \le _{0} b. }\) Udowodniliśmy zatem, że para zbiorów \(\displaystyle{ \left( A _{1} \cap X _{0}, A _{2} \cap X_0 \right) }\) tworzy przekrój Dedekinda w \(\displaystyle{ \left( X_0, \le _{0}\right) . }\).

Ponieważ liniowy porządek \(\displaystyle{ \le _{0} \in \mathbb{B}}\) jest ciągły, więc przekrój ten nie daję luki. Tzn. w \(\displaystyle{ A_1 \cap X _{0}}\) jest element największy lub w \(\displaystyle{ A _{2} \cap X_0}\) jest element najmniejszy. Zajmijmy się zatem najpierw pierwszym przypadkiem.
Wtedy element największy \(\displaystyle{ a\in A_1 \cap X_0}\), jest większy od każdego elementu \(\displaystyle{ b\in A_1 \cap X_0}\), względem \(\displaystyle{ \le _{0}}\), a więc również względem \(\displaystyle{ \le = \bigcup \mathbb {B}}\), ponieważ \(\displaystyle{ \bigcup \mathbb {B}}\) jest liniowym porządkiem i jest nadzbiorem liniowego porządku \(\displaystyle{ \le _{0} \in \mathbb{B}}\), to \(\displaystyle{ \le =\bigcup \mathbb {B}}\) jest rozszerzeniem \(\displaystyle{ \le _{0}}\), ponieważ para zbiorów \(\displaystyle{ (A_1,A_2)}\) tworzy przekrój w \(\displaystyle{ X}\) w \(\displaystyle{ \left( X _{ \le }, \le \right) ,}\) to również element \(\displaystyle{ a}\) jest największy w \(\displaystyle{ A_1}\) w \(\displaystyle{ \left( X _{ \le }, \le \right) ,}\) . Wnioskujemy stąd, że przekrój \(\displaystyle{ (A_1,A_2)}\) nie daje luki, i otrzymujemy sprzeczność. W drugim przypadku, gdy w \(\displaystyle{ A_2 \cap X_0 }\)jest element najmniejszy, analogicznie, w sposób symetryczny, otrzymujemy sprzeczność, co kończy dowód. \(\displaystyle{ \square}\) :D :lol: 8-)
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: Lemat Kuratowskiego-Zorna

Post autor: Jakub Gurak »

Niestety, pozwoliłem sobie na mniej szczegółowy dowód, i teraz mogę podać kontrprzykład mówiący, że suma łańcucha porządków ciągłych nie musi być porządkiem ciągłym.

Aby to pokazać rozważmy poniższy ciąg zbiorów liniowo uporządkowanych \(\displaystyle{ (X_n, \le _{n} )}\) na podzbiorach przedziału \(\displaystyle{ \left[ -1,2\right]}\) :

\(\displaystyle{ \left( X_0, \le _{0}\right) =\left( \left[ -1,0\right) \cup \left[ 1,2\right]; \le _{|X_0} \right)}\) , tzn. naturalny porządek \(\displaystyle{ \le}\) na \(\displaystyle{ X_0.}\)
\(\displaystyle{ \left( X_1, \le _1\right) =\left( \left[ -1,0\right) \cup \left[ \frac{1}{2},2 \right], \le _{|X_1} \right), }\)
\(\displaystyle{ \left( X_2, \le _{2} \right)=\left( \left[ -1,0\right) \cup \left[ \frac{1}{3},2 \right],\le _{|X_2} \right), }\)
\(\displaystyle{ \vdots}\)
\(\displaystyle{ \left( X_n, \le _n\right) =\left( \left[ -1,0\right) \cup \left[ \frac{1}{n+1},2 \right], \le _{|X_n}\right),
}\)


Jest to ciąg zbiorów liniowo uporządkowanych gęstych, gdyż w nich żaden przekrój Dedekinda nie daje skoku (polecam narysować to sobie), i ciągłych, gdyż w nich żaden przekrój Dedekinda nie daje luki (znowu widać na rysunku), i oczywiście tworzą łańcuch. Tymczasem \(\displaystyle{ \left( \bigcup_{n\in\NN} X_n=:X, \bigcup_{n\in\NN} \le _n\right) = \left( X=\left[ -1,0\right) \cup \left(0,2 \right] , \le _{|X}\right) }\), gdzie w przekroju Dedekinda \(\displaystyle{ \left( \left[ -1,0\right) ,\left( 0,2\right] \right)}\) mamy, że \(\displaystyle{ 0}\) jest luką, gdyż w \(\displaystyle{ \left[ -1,0\right)}\) nie ma liczby największej, i w \(\displaystyle{ \left(0,2 \right]}\) nie ma liczby najmniejszej, a więc ten przekrój daję lukę, a więc ten zbiór liniowo uporządkowany nie jest ciągły, niestety. :roll:

Dobrze to jest teraz, dobrze :?:
Dodam jeszcze taki prosty dowód,:    
ODPOWIEDZ