Tw. o maksymalnym łańcuchu
: 4 paź 2016, o 23:12
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
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