Czas w końcu, ( i to w \(\displaystyle{ 200}\) poście ) udowodnić twierdzenie o maksymalnym łańcuchu:
W każdym zbiorze uporządkowanym istnieje maksymalny łańcuch pod względem inkluzji.
Dokładniej to dowodzimy, że twierdzenie o funkcji wyboru implikuje to twierdzenie o maksymalnym łańcuchu. Dowód ten się opiera na twierdzeniu Bourbakiego-Witta , którego treść jest tu (i jego pracowity dowód ):
https://www.matematyka.pl/411530.htm#p5448849
Oto nasz dowód:
Ustalmy dowolny niepusty zbiór uporządkowany \(\displaystyle{ \left( X,\le \right)}\) ( w zbiorze pustym jest dokładnie jeden łańcuch- łańcuch pusty, wiec jest to łańcuch maksymalny i twierdzenie jest prawdziwe).
Rozważmy zbiór uporządkowany \(\displaystyle{ \left( B, \subset\right)}\) złożony z wszystkich łańcuchów uporządkowanych inkluzją:
\(\displaystyle{ B=\left\{ A \subset X| \ \ A \hbox{ jest łańcuchem w } \left( X,\le \right) \right\}}\)
\(\displaystyle{ \tikz{\draw[black!10!white] (0,0) -- (0.25,0)}}\) Dalej, ustalmy dowolny łańcuch \(\displaystyle{ D\subset B}\) w \(\displaystyle{ \left( B, \subset\right)}\). Jeśli \(\displaystyle{ D}\) jest pusty, to zauważmy że w \(\displaystyle{ \left( B, \subset\right)}\) jest element najmniejszy, jest to łańcuch pusty- więc ponieważ jest elementem najmniejszym więc jest to supremum zbioru pustego . W przeciwnym wypadku, jeśli \(\displaystyle{ D}\) jest niepusty, to za supremum kładziemy \(\displaystyle{ \bigcup D}\). Wpierw jednak musimy pokazać że \(\displaystyle{ \bigcup D \in B}\). Suma łańcuchów z \(\displaystyle{ D}\) (podzbiorów \(\displaystyle{ X}\)) niewątpliwie jest podzbiorem \(\displaystyle{ X}\). Suma łańcuchów \(\displaystyle{ \bigcup D}\) będzie łańcuchem, gdyż rodzina \(\displaystyle{ D}\) jest liniowo uporządkowana przez inkluzję, nietrudny dowód tego faktu zostawię Wam . A więc \(\displaystyle{ \bigcup D \in B}\). Niewątpliwie \(\displaystyle{ \bigcup D}\) ( z własności sumy) jest ograniczeniem górnym rodziny \(\displaystyle{ D}\) ze względu na inkluzję i jest najmniejszym takim zbiorem. A więc jest to supremum dla \(\displaystyle{ D}\). Z dowolności wyboru zbioru \(\displaystyle{ D}\), każdy łańcuch w \(\displaystyle{ \left( B, \subset\right)}\) posiada supremum.
Na mocy twierdzenia o funkcji wyboru definiujemy funkcję wyboru \(\displaystyle{ f}\) zwracającą dla każdego niepustego podzbioru \(\displaystyle{ X}\) element tego podzbioru.
Twierdzenie Bourbakiego-Witta będziemy stosować do funkcji \(\displaystyle{ g}\) przeprowadzającej zbiór łańcuchów \(\displaystyle{ B}\) w zbiór łańcuchów \(\displaystyle{ B}\) określonej:
\(\displaystyle{ g(C)= \begin{cases} C \cup \left\{ f\left( C ^{\prime} \right) \right\} \hbox{ gdy zbiór } C ^{\prime}= \left\{ x\in X \setminus C| \ \ x \hbox { jest porównywalne z każdym elementem } C\right\} \neq \left\{ \right\} \\ C \hbox{ w przeciwnym przypadku }\end{cases}}\)
Pokażmy dokładnie, że jeśli tylko jest możliwe rozszerzenie łańcucha \(\displaystyle{ C}\)- my to czynimy.
Aby tak było musi istnieć element nie należący do \(\displaystyle{ C}\), a ponieważ ma być to łańcuch musi być on porównywalny z każdym elementem \(\displaystyle{ C}\). Zatem zbiór elementów nie należących do \(\displaystyle{ C}\) porównywalnych z każdym elementem \(\displaystyle{ C}\) jest niepusty. A skoro tak to funkcja wyboru \(\displaystyle{ f}\) potrafi wybrać z niego jeden element. I my to czynimy wybierając \(\displaystyle{ f(C^{\prime})}\) i dodając go do łańcucha. Łatwo sprawdzić że \(\displaystyle{ C \cup \left\{ f\left( C ^{\prime} \right) \right\}}\) jest również łańcuchem. Niewątpliwie jest istotnym nadzbiorem łańcucha \(\displaystyle{ C}\).
Jeśli natomiast naszego łańcucha nie da się rozszerzyć, to funkcja zwraca go takiego samego.
A więc widzimy, funkcja \(\displaystyle{ g}\) przeprowadza zbiór łańcuchów \(\displaystyle{ B}\) w \(\displaystyle{ B}\) i spełnia że \(\displaystyle{ C \subseteq g(C)}\) dla dowolnego łańcucha \(\displaystyle{ C\in B}\). Wcześniej pokazaliśmy że każdy łańcuch w \(\displaystyle{ \left( B, \subset\right)}\) posiada supremum.
\(\displaystyle{ \tikz{\draw[black!10!white] (0,0) -- (0.25,0)}}\)Wobec czego spełnione są założenia twierdzenia Bourbakiego-Witta i na jego mocy istnieje taki łańcuch \(\displaystyle{ D}\) że \(\displaystyle{ g(D)=D}\). To gwarantuje że naszego łańcucha \(\displaystyle{ D}\) nie da się rozszerzyć, (bo jeśli się da jakiś łańcuch rozszerzyć to to czynimy otrzymując istotny nadzbiór, a tu otrzymaliśmy zbiór równy), wobec czego łańcucha \(\displaystyle{ D}\) nie da się rozszerzyć, a więc \(\displaystyle{ D}\) jest maksymalnym łańcuchem pod względem inkluzji. \(\displaystyle{ \square}\) -- 7 paź 2016, o 23:46 --Ilustrację ( i omówienie) do tego twierdzenia można znaleźć tu :
https://www.matematyka.pl/402442.htm
Tw. o maksymalnym łańcuchu
-
Jakub Gurak
- Użytkownik
- Posty: 1407
- Rejestracja: 20 lip 2012, o 21:19
- Płeć: Mężczyzna
- Lokalizacja: Rzeszów
- Podziękował: 66 razy
- Pomógł: 83 razy
-
Jakub Gurak
- Użytkownik
- Posty: 1407
- Rejestracja: 20 lip 2012, o 21:19
- Płeć: Mężczyzna
- Lokalizacja: Rzeszów
- Podziękował: 66 razy
- Pomógł: 83 razy
Re: Tw. o maksymalnym łańcuchu
Spróbuję zastosować analogiczne rozumowanie, aby wykazać, że z twierdzenia o funkcji wyboru ( i korzystając z twierdzenia Bourbakiego-Witta) udowodnić twierdzenie o maksymalnym antyłańcuchu:
W każdym zbiorze uporządkowanym \(\displaystyle{ \left( X, \le \right)}\) istnieje maksymalny antyłańcuch pod względem inkluzji.
Czyli w zbiorze uporządkowanym możemy znaleźć maksymalny antyłańcuch.
DOWÓD:
Weźmy zbiór uporządkowany \(\displaystyle{ \left( X,\le \right)}\). Rozważmy zbiór uporządkowany \(\displaystyle{ \left( B, \subset\right)}\) złożony z wszystkich antyłańcuchów uporządkowanych inkluzją:
\(\displaystyle{ B=\left\{ A \subset X| \ \ A \hbox{ jest antyłańcuchem w } \left( X,\le \right) \right\}.}\)
Wiemy, że inkluzja na każdej rodzinie podzbiorów \(\displaystyle{ X}\) jest porządkiem. Zatem tu też, wobec czego \(\displaystyle{ \left( B, \subset\right)}\) jest zbiorem uporządkowanym. Do takiej rodziny wszystkich antyłańcuchów stosujemy twierdzenie Bourbakiego-Witta. W tym celu:
Ustalmy dowolny łańcuch \(\displaystyle{ D\subset B}\) w \(\displaystyle{ \left( B, \subset\right)}\). Za supremum kładziemy \(\displaystyle{ \bigcup D}\). Wpierw jednak musimy pokazać, że \(\displaystyle{ \bigcup D \in B}\). Suma antyłańcuchów z \(\displaystyle{ D}\) (podzbiorów \(\displaystyle{ X}\)) niewątpliwie jest podzbiorem \(\displaystyle{ X}\). Aby wykazać, że \(\displaystyle{ \bigcup D}\) jest antyłańcuchem, weźmy dowolne dwa różne elementy \(\displaystyle{ x,y\in\bigcup D}\). Wtedy \(\displaystyle{ x\in A}\) dla pewnego zbioru \(\displaystyle{ A\in D}\), oraz \(\displaystyle{ y\in C}\) dla pewnego zbioru \(\displaystyle{ C\in D}\). Ponieważ \(\displaystyle{ D}\) jest łańcuchem pod względem inkluzji, to \(\displaystyle{ A\subset C}\) lub \(\displaystyle{ C\subset A}\). Jeśli \(\displaystyle{ A\subset C}\), to \(\displaystyle{ x,y\in C}\). Podobnie, w przeciwnym wypadku, jeśli \(\displaystyle{ C\subset A}\) to \(\displaystyle{ x,y\in A}\). Czyli \(\displaystyle{ x,y}\) są w \(\displaystyle{ C}\) lub \(\displaystyle{ x,y}\) są w \(\displaystyle{ A}\). Ponieważ \(\displaystyle{ C,A\in D}\), zbiory \(\displaystyle{ C,A}\) są antyłańcuchami, więc ponieważ \(\displaystyle{ x,y}\) są różnymi elementami takiego antyłańcucha, wnioskujemy, że elementy \(\displaystyle{ x,y}\) są nieporównywalne. Pokazaliśmy, że dowolne dwa różne elementy \(\displaystyle{ \bigcup D}\) są nieporównywalne, czyli \(\displaystyle{ \bigcup D}\) jest antyłańcuchem, i należy do \(\displaystyle{ B}\). A więc \(\displaystyle{ \bigcup D \in B}\). Niewątpliwie \(\displaystyle{ \bigcup D}\) ( z własności sumy) jest ograniczeniem górnym rodziny \(\displaystyle{ D}\), ze względu na inkluzję, i jest najmniejszym takim zbiorem. A więc jest to supremum dla \(\displaystyle{ D}\), tego łańcucha. Z dowolności wyboru zbioru \(\displaystyle{ D}\), każdy łańcuch w \(\displaystyle{ \left( B, \subset\right)}\) posiada supremum.
Na mocy twierdzenia o funkcji wyboru definiujemy funkcję wyboru \(\displaystyle{ f}\), zwracającą, dla każdego niepustego podzbioru \(\displaystyle{ X}\), element tego podzbioru.
Twierdzenie Bourbakiego-Witta będziemy stosować do funkcji \(\displaystyle{ g}\) przeprowadzającej zbiór antyłańcuchów \(\displaystyle{ B}\) w \(\displaystyle{ B}\) określonej:
\(\displaystyle{ g(C)= \begin{cases} C \cup \left\{ f\left( C ^{\prime} \right) \right\} \hbox{ gdy zbiór } C ^{\prime}= \left\{ x\in X \setminus C| \ \ x \hbox { jest nieporównywalne z żadnym elementem } C\right\} \neq \emptyset, \\ C \hbox{ w przeciwnym przypadku.}\end{cases}}\)
Funkcja \(\displaystyle{ g}\) dostaje jako argument antyłańcuch oznaczony przez \(\displaystyle{ C}\), i rozszerza go (jeśli tylko możliwe) o jeden element( przy pomocy funkcji wyboru \(\displaystyle{ f}\)) zbioru \(\displaystyle{ X}\), spoza \(\displaystyle{ C}\), nieporównywalny z żadnym elementem \(\displaystyle{ C}\), tworząc nowy większy antyłańcuch. Jeśli natomiast naszego antyłańcucha nie da się rozszerzyć, to funkcja zwraca go takiego samego.
A więc widzimy, funkcja \(\displaystyle{ g}\) przeprowadza zbiór antyłańcuchów \(\displaystyle{ B}\) w \(\displaystyle{ B}\), i spełnia, że \(\displaystyle{ C \subseteq g(C)}\), dla dowolnego antyłańcucha \(\displaystyle{ C\in B}\). Wcześniej pokazaliśmy, że każdy łańcuch w \(\displaystyle{ \left( B, \subset\right)}\) posiada supremum.
Wobec czego spełnione są założenia twierdzenia Bourbakiego-Witta, i na jego mocy istnieje taki antyłańcuch \(\displaystyle{ D}\), że \(\displaystyle{ g(D)=D}\). Z definicji funkcji \(\displaystyle{ g}\) oznacza to , że zbiór \(\displaystyle{ D'}\), elementów spoza \(\displaystyle{ D}\), nieporównywalnych z żadnym elementem \(\displaystyle{ D}\) jest pusty, a stąd łatwo wynika, że wtedy \(\displaystyle{ D}\) jest maksymalnym antyłańcuchem pod względem inkluzji.\(\displaystyle{ \square}\)
W każdym zbiorze uporządkowanym \(\displaystyle{ \left( X, \le \right)}\) istnieje maksymalny antyłańcuch pod względem inkluzji.
Czyli w zbiorze uporządkowanym możemy znaleźć maksymalny antyłańcuch.
DOWÓD:
Weźmy zbiór uporządkowany \(\displaystyle{ \left( X,\le \right)}\). Rozważmy zbiór uporządkowany \(\displaystyle{ \left( B, \subset\right)}\) złożony z wszystkich antyłańcuchów uporządkowanych inkluzją:
\(\displaystyle{ B=\left\{ A \subset X| \ \ A \hbox{ jest antyłańcuchem w } \left( X,\le \right) \right\}.}\)
Wiemy, że inkluzja na każdej rodzinie podzbiorów \(\displaystyle{ X}\) jest porządkiem. Zatem tu też, wobec czego \(\displaystyle{ \left( B, \subset\right)}\) jest zbiorem uporządkowanym. Do takiej rodziny wszystkich antyłańcuchów stosujemy twierdzenie Bourbakiego-Witta. W tym celu:
Ustalmy dowolny łańcuch \(\displaystyle{ D\subset B}\) w \(\displaystyle{ \left( B, \subset\right)}\). Za supremum kładziemy \(\displaystyle{ \bigcup D}\). Wpierw jednak musimy pokazać, że \(\displaystyle{ \bigcup D \in B}\). Suma antyłańcuchów z \(\displaystyle{ D}\) (podzbiorów \(\displaystyle{ X}\)) niewątpliwie jest podzbiorem \(\displaystyle{ X}\). Aby wykazać, że \(\displaystyle{ \bigcup D}\) jest antyłańcuchem, weźmy dowolne dwa różne elementy \(\displaystyle{ x,y\in\bigcup D}\). Wtedy \(\displaystyle{ x\in A}\) dla pewnego zbioru \(\displaystyle{ A\in D}\), oraz \(\displaystyle{ y\in C}\) dla pewnego zbioru \(\displaystyle{ C\in D}\). Ponieważ \(\displaystyle{ D}\) jest łańcuchem pod względem inkluzji, to \(\displaystyle{ A\subset C}\) lub \(\displaystyle{ C\subset A}\). Jeśli \(\displaystyle{ A\subset C}\), to \(\displaystyle{ x,y\in C}\). Podobnie, w przeciwnym wypadku, jeśli \(\displaystyle{ C\subset A}\) to \(\displaystyle{ x,y\in A}\). Czyli \(\displaystyle{ x,y}\) są w \(\displaystyle{ C}\) lub \(\displaystyle{ x,y}\) są w \(\displaystyle{ A}\). Ponieważ \(\displaystyle{ C,A\in D}\), zbiory \(\displaystyle{ C,A}\) są antyłańcuchami, więc ponieważ \(\displaystyle{ x,y}\) są różnymi elementami takiego antyłańcucha, wnioskujemy, że elementy \(\displaystyle{ x,y}\) są nieporównywalne. Pokazaliśmy, że dowolne dwa różne elementy \(\displaystyle{ \bigcup D}\) są nieporównywalne, czyli \(\displaystyle{ \bigcup D}\) jest antyłańcuchem, i należy do \(\displaystyle{ B}\). A więc \(\displaystyle{ \bigcup D \in B}\). Niewątpliwie \(\displaystyle{ \bigcup D}\) ( z własności sumy) jest ograniczeniem górnym rodziny \(\displaystyle{ D}\), ze względu na inkluzję, i jest najmniejszym takim zbiorem. A więc jest to supremum dla \(\displaystyle{ D}\), tego łańcucha. Z dowolności wyboru zbioru \(\displaystyle{ D}\), każdy łańcuch w \(\displaystyle{ \left( B, \subset\right)}\) posiada supremum.
Na mocy twierdzenia o funkcji wyboru definiujemy funkcję wyboru \(\displaystyle{ f}\), zwracającą, dla każdego niepustego podzbioru \(\displaystyle{ X}\), element tego podzbioru.
Twierdzenie Bourbakiego-Witta będziemy stosować do funkcji \(\displaystyle{ g}\) przeprowadzającej zbiór antyłańcuchów \(\displaystyle{ B}\) w \(\displaystyle{ B}\) określonej:
\(\displaystyle{ g(C)= \begin{cases} C \cup \left\{ f\left( C ^{\prime} \right) \right\} \hbox{ gdy zbiór } C ^{\prime}= \left\{ x\in X \setminus C| \ \ x \hbox { jest nieporównywalne z żadnym elementem } C\right\} \neq \emptyset, \\ C \hbox{ w przeciwnym przypadku.}\end{cases}}\)
Funkcja \(\displaystyle{ g}\) dostaje jako argument antyłańcuch oznaczony przez \(\displaystyle{ C}\), i rozszerza go (jeśli tylko możliwe) o jeden element( przy pomocy funkcji wyboru \(\displaystyle{ f}\)) zbioru \(\displaystyle{ X}\), spoza \(\displaystyle{ C}\), nieporównywalny z żadnym elementem \(\displaystyle{ C}\), tworząc nowy większy antyłańcuch. Jeśli natomiast naszego antyłańcucha nie da się rozszerzyć, to funkcja zwraca go takiego samego.
A więc widzimy, funkcja \(\displaystyle{ g}\) przeprowadza zbiór antyłańcuchów \(\displaystyle{ B}\) w \(\displaystyle{ B}\), i spełnia, że \(\displaystyle{ C \subseteq g(C)}\), dla dowolnego antyłańcucha \(\displaystyle{ C\in B}\). Wcześniej pokazaliśmy, że każdy łańcuch w \(\displaystyle{ \left( B, \subset\right)}\) posiada supremum.
Wobec czego spełnione są założenia twierdzenia Bourbakiego-Witta, i na jego mocy istnieje taki antyłańcuch \(\displaystyle{ D}\), że \(\displaystyle{ g(D)=D}\). Z definicji funkcji \(\displaystyle{ g}\) oznacza to , że zbiór \(\displaystyle{ D'}\), elementów spoza \(\displaystyle{ D}\), nieporównywalnych z żadnym elementem \(\displaystyle{ D}\) jest pusty, a stąd łatwo wynika, że wtedy \(\displaystyle{ D}\) jest maksymalnym antyłańcuchem pod względem inkluzji.\(\displaystyle{ \square}\)