Dowód tw. Bourbakiego-Witta i tw. o maksymalnym łańcuchu
: 23 wrz 2016, o 01:58
A więc zapowiedziany kilka dni temu dowód.
Przypomnijmy treść twierdzenia Bourbakiego-Witta:
Jeśli w zbiorze uporządkowanym \(\displaystyle{ \left( A, \le \right)}\) każdy łańcuch posiada supremum oraz dla funkcji \(\displaystyle{ f}\) przeprowadzającej \(\displaystyle{ A}\) w \(\displaystyle{ A}\) i spełniającej \(\displaystyle{ x \le f\left( x\right)}\) dla dowolnego \(\displaystyle{ x}\) to funkcja \(\displaystyle{ f}\) posiada punkt stały, czyli istnieje \(\displaystyle{ x_{0}}\) że \(\displaystyle{ f \left( x_{0}\right) =x_{0}}\).
Dla łańcucha \(\displaystyle{ C}\) jego supremum będziemy oznaczać \(\displaystyle{ \bigvee C}\). W czasie tego dowodu zostaną pokazane trzy lematy. Są one częścią całego dowodu. Dowód:
Ustalmy \(\displaystyle{ a\in A}\)( jeśli \(\displaystyle{ A}\) jest pusty, to twierdzenie jest prawdziwe, gdyż w zbiorze pustym jest dokładnie jeden łańcuch- łańcuch pusty, więc ... twierdzenie jest prawdziwe ) Zdefiniujmy rodzinę zbiorów 'nadmaksymalnych':
\(\displaystyle{ S=\left\{ B \subset A | \ \ \textbf{(1)} \wedge \textbf{(2)} \wedge \textbf{(3)} \right\}}\) gdzie
(1) \(\displaystyle{ \ a\in B}\)
(2) \(\displaystyle{ \ \hbox{ jeśli } x\in B \hbox { to również } f\left( x\right)\in B}\)
(3) \(\displaystyle{ \ \hbox{ jeśli } \left\{ \right\} \neq C \subseteq
B \hbox{ jest niepustym łańcuchem to } \bigvee C \in B}\)
Zbiory spełniające wszystkie te trzy warunki nazwiemy nadmaksymalnymi . Intuicja bowiem podpowiada mi że zawierają one maksymalny łańcuch wyznaczony przez element \(\displaystyle{ a}\) i funkcję \(\displaystyle{ f}\). Istnieją zbiory nadmaksymalne, gdyż cały zbiór \(\displaystyle{ A}\) jest nadmaksymalny (rozpatrywane elementy należą do zbioru uporządkowanego \(\displaystyle{ A}\)).
Zauważmy że jeśli \(\displaystyle{ M}\) jest niepustym zbiorem zbiorów nadmaksymalnych to \(\displaystyle{ \bigcap M}\) jest również zbiorem nadmaksymalnym.
Udowodnijmy punkt (3)
Niech \(\displaystyle{ C \subseteq \bigcap M}\) będzie niepustym łańcuchem. Pokażemy że \(\displaystyle{ \bigvee C \in \bigcap M}\). Wystarczy zatem pokazać ze \(\displaystyle{ \bigvee C \in B}\) dla każdego zbioru \(\displaystyle{ B\in M}\)Aby to pokazać niech \(\displaystyle{ B\in M}\). Z własności iloczynu mnogościowego \(\displaystyle{ \bigcap M \subset B}\). Nasze założenia dają \(\displaystyle{ C \subset \bigcap M \subset B}\), czyli \(\displaystyle{ C \subset B}\). Ponieważ \(\displaystyle{ C}\) jest łańcuchem i ponieważ zbiory \(\displaystyle{ B\in M}\) są nadmaksymalne to z własności (3) dostajemy \(\displaystyle{ \bigvee C \in B}\). Dowolność wyboru \(\displaystyle{ B\in M}\) kończy dowód.
Dowody punktów 2 i 1 są podobne (i mogą być tylko łatwiejsze) więc pozostawimy je czytelnikowi.
Zdefiniujmy zbiór \(\displaystyle{ B_{0}=\bigcap S}\) jako iloczyn wszystkich zbiorów nadmaksymalnych. Otrzymujemy zatem że \(\displaystyle{ B_{0}}\) jest nadmaksymalny. Z własności iloczynu jest on podzbiorem każdego nadmaksymalnego zbioru, jest najmniejszym zbiorem nadmaksymalnym.
\(\displaystyle{ \tikz{\draw[black!10!white] (0,0) -- (0.25,0)}}\) Pokażemy że zbiór \(\displaystyle{ B_{0}}\) jest łańcuchem- nie będzie to łatwe
Lemat 0 ( dla zgody numeracji z ważniakiem) Każdy element \(\displaystyle{ x}\) z \(\displaystyle{ B_{0 }}\) jest większy lub równy \(\displaystyle{ a}\)- \(\displaystyle{ x \ge a}\). Dowód(ukryty):Zdefiniujmy zbiór:
\(\displaystyle{ B_{1}=\left\{ x\in B_{0}| \ \ y\in B_{0} \wedge y<x \longrightarrow f\left( y\right) \le x\right\}}\)
Jest to zbiór tych \(\displaystyle{ x}\)-ów z \(\displaystyle{ B_{0}}\) że razem z elementem silnie mniejszym od \(\displaystyle{ x}\) wartość \(\displaystyle{ f}\) na nim też nie przekracza \(\displaystyle{ x}\). Potem pokażemy że jest on równy całemu \(\displaystyle{ B_{0}}\). Wpierw udowodnijmy inny, bardzo pomocny lemat.
Lemat 1 Jeśli \(\displaystyle{ x\in B_{1}}\) to dla każdego \(\displaystyle{ y\in B_{0}}\) zachodzi: \(\displaystyle{ y \le x \vee f\left( x\right) \le y}\). Dowód:
Niech \(\displaystyle{ x\in B_{1}}\) Zdefiniujmy zbiór \(\displaystyle{ B_{x}}\):
\(\displaystyle{ B_{x}=\left\{ y\in B_{0}| \ \ y \le x \vee f\left( x\right) \le y\right\} \subset B_{0}}\)
Jest to zbiór tych elementów dla których dowodzony lemat zachodzi. Pokażemy że zbiór \(\displaystyle{ B_{x}}\) jest nadmaksymalny.
(1) Pokażmy że \(\displaystyle{ a\in B_{x}}\). Niewątpliwie \(\displaystyle{ a\in B_{0}}\) ( bo \(\displaystyle{ B_{0}}\) jest nadmaksymalny) Z lematu 0 wynika że \(\displaystyle{ x \ge a}\), czyli \(\displaystyle{ a\in B_{x}}\).
(2) Niech \(\displaystyle{ y\in B_{x}}\). Pokażmy że \(\displaystyle{ f\left( y\right)\in B_{x}}\). Ponieważ \(\displaystyle{ y\in B_{0}}\) to z nadmaksymalności \(\displaystyle{ B_{0}}\) mamy \(\displaystyle{ f\left( y\right)\in B_{0}}\). Pozostaje pokazać ze \(\displaystyle{ f\left( y\right) \le x \vee f\left( x\right) \le f\left( y\right)}\). Wiemy że \(\displaystyle{ y\in B_{x}}\), więc jeśli \(\displaystyle{ f\left( x\right) \le y}\) to ponieważ \(\displaystyle{ y \le f\left( y\right)}\) więc \(\displaystyle{ f\left( x\right) \le f\left( y\right)}\), co należało pokazać.
W przeciwnym przypadku mamy \(\displaystyle{ y \le x}\), wiec jeśli \(\displaystyle{ y=x}\), to \(\displaystyle{ f\left( y\right) =f \left( x\right)}\), zatem \(\displaystyle{ f\left( x\right) \le f\left( y\right)}\), a jeśli \(\displaystyle{ y<x}\) to z określenia \(\displaystyle{ B_{1}}\) dostajemy \(\displaystyle{ f\left( y\right) \le x}\). Zatem w każdym przypadku \(\displaystyle{ f\left( y\right) \le x \vee f\left( x\right) \le f\left( y\right)}\), więc \(\displaystyle{ f\left( y\right)\in B_{x}}\)
(3) Niech \(\displaystyle{ \left\{ \right\} \neq C\subset B_{x}}\) będzie łańcuchem niepustym. Pokażemy że \(\displaystyle{ \bigvee C \in B_{x}}\). Ponieważ \(\displaystyle{ B_{x}\subset B_{0}}\), więc \(\displaystyle{ C\subset B_{0}}\). Mamy że \(\displaystyle{ B_{0}}\) jest nadmaksymalny, więc \(\displaystyle{ \bigvee C \in B_{0}}\). Jeśli dla każdego \(\displaystyle{ y\in C}\) zachodzi \(\displaystyle{ y \le x}\), to \(\displaystyle{ x}\) jest ograniczeniem górnym zbioru \(\displaystyle{ C}\), ponieważ \(\displaystyle{ \bigvee C}\) jest najmniejszym ograniczeniem górnym dla \(\displaystyle{ C}\), więc \(\displaystyle{ \bigvee C \le x}\) i \(\displaystyle{ \bigvee C \in B_{x}}\). W przeciwnym przypadku (\(\displaystyle{ C}\) jest niepusty i jest podzbiorem \(\displaystyle{ B_{x}}\)), więc dla pewnego \(\displaystyle{ y\in C}\) zachodzi druga możliwość, czyli \(\displaystyle{ f\left( x\right) \le y}\). Wtedy \(\displaystyle{ y \le \bigvee C}\), więc \(\displaystyle{ f\left( x\right) \le \bigvee C}\), a zatem \(\displaystyle{ \bigvee C \in B_{x}}\)
Zatem \(\displaystyle{ B_{x}}\) jest nadmaksymalny. Ponieważ zbiór \(\displaystyle{ B _{0}}\) jest najmniejszym nadmaksymalnym to \(\displaystyle{ B_{0}\subset B_{x}}\) i \(\displaystyle{ B_{0}= B_{x}}\). Czyli dla każdego \(\displaystyle{ y\in B_{0}}\) zachodzi: \(\displaystyle{ y \le x \vee f\left( x\right) \le y}\) \(\displaystyle{ \square}\)
W kolejnym lemacie dowodzimy że zbiory \(\displaystyle{ B_{0}}\) i \(\displaystyle{ B_{1}}\) są równe. Dowód(ukryty):Tak więc \(\displaystyle{ B _{0} =B _{1}}\), więc dla dowolnych \(\displaystyle{ x}\) i \(\displaystyle{ y}\) w \(\displaystyle{ B_{0}}\) mamy na podstawie lematu 1:\(\displaystyle{ y \le x \vee f\left( x\right) \le y}\). W pierwszym przypadku mamy \(\displaystyle{ y \le x}\) a więc elementy są porównywalne, w przeciwnym przypadku \(\displaystyle{ x \le f\left( x\right) \le y}\), więc \(\displaystyle{ x \le y}\), zatem również elementy są porównywalne. Z dowolności wyboru elementów \(\displaystyle{ x}\) i \(\displaystyle{ y}\) wnioskujemy że zbiór \(\displaystyle{ B _{0}}\) jest łańcuchem. Mając to już łatwo zakończymy dowód tego twierdzenia.
\(\displaystyle{ \tikz{\draw[black!10!white] (0,0) -- (0.25,0)}}\) Więc \(\displaystyle{ B_{0}}\) jest łańcuchem. Ponieważ zbiór \(\displaystyle{ B_{0}}\) jest też nadmaksymalny to stosując punkt 3 wnioskujemy że \(\displaystyle{ \bigvee B_{0}\in B_{0}}\), więc również \(\displaystyle{ f\left( \bigvee B_{0}\right) \in B_{0}}\)-znowu z nadmaksymalności \(\displaystyle{ B_{0}}\). Ponieważ jednak \(\displaystyle{ \bigvee B_{0}}\) jest większe lub równe od każdego elementu \(\displaystyle{ B_{0}}\), więc również \(\displaystyle{ f\left( \bigvee B_{0}\right) \le \bigvee B_{0}}\), nasze założenia dają \(\displaystyle{ \bigvee B_{0} \le f\left( \bigvee B_{0}\right)}\), wobec czego \(\displaystyle{ f\left( \bigvee B_{0}\right) = \bigvee B_{0}}\), co oznacza że \(\displaystyle{ \bigvee B_{0}}\) jest punktem stałym. \(\displaystyle{ \square}\)
Dodam że ten dowód, oparty na ważniaku, został tam przedstawiony w sposób dużo bardziej skrótowy.
To twierdzenie jest bardzo pomocne w udowodnieniu twierdzenia o maksymalnym łańcuchu.
Przypomnijmy treść twierdzenia Bourbakiego-Witta:
Jeśli w zbiorze uporządkowanym \(\displaystyle{ \left( A, \le \right)}\) każdy łańcuch posiada supremum oraz dla funkcji \(\displaystyle{ f}\) przeprowadzającej \(\displaystyle{ A}\) w \(\displaystyle{ A}\) i spełniającej \(\displaystyle{ x \le f\left( x\right)}\) dla dowolnego \(\displaystyle{ x}\) to funkcja \(\displaystyle{ f}\) posiada punkt stały, czyli istnieje \(\displaystyle{ x_{0}}\) że \(\displaystyle{ f \left( x_{0}\right) =x_{0}}\).
Dla łańcucha \(\displaystyle{ C}\) jego supremum będziemy oznaczać \(\displaystyle{ \bigvee C}\). W czasie tego dowodu zostaną pokazane trzy lematy. Są one częścią całego dowodu. Dowód:
Ustalmy \(\displaystyle{ a\in A}\)( jeśli \(\displaystyle{ A}\) jest pusty, to twierdzenie jest prawdziwe, gdyż w zbiorze pustym jest dokładnie jeden łańcuch- łańcuch pusty, więc ... twierdzenie jest prawdziwe ) Zdefiniujmy rodzinę zbiorów 'nadmaksymalnych':
\(\displaystyle{ S=\left\{ B \subset A | \ \ \textbf{(1)} \wedge \textbf{(2)} \wedge \textbf{(3)} \right\}}\) gdzie
(1) \(\displaystyle{ \ a\in B}\)
(2) \(\displaystyle{ \ \hbox{ jeśli } x\in B \hbox { to również } f\left( x\right)\in B}\)
(3) \(\displaystyle{ \ \hbox{ jeśli } \left\{ \right\} \neq C \subseteq
B \hbox{ jest niepustym łańcuchem to } \bigvee C \in B}\)
Zbiory spełniające wszystkie te trzy warunki nazwiemy nadmaksymalnymi . Intuicja bowiem podpowiada mi że zawierają one maksymalny łańcuch wyznaczony przez element \(\displaystyle{ a}\) i funkcję \(\displaystyle{ f}\). Istnieją zbiory nadmaksymalne, gdyż cały zbiór \(\displaystyle{ A}\) jest nadmaksymalny (rozpatrywane elementy należą do zbioru uporządkowanego \(\displaystyle{ A}\)).
Zauważmy że jeśli \(\displaystyle{ M}\) jest niepustym zbiorem zbiorów nadmaksymalnych to \(\displaystyle{ \bigcap M}\) jest również zbiorem nadmaksymalnym.
Udowodnijmy punkt (3)
Niech \(\displaystyle{ C \subseteq \bigcap M}\) będzie niepustym łańcuchem. Pokażemy że \(\displaystyle{ \bigvee C \in \bigcap M}\). Wystarczy zatem pokazać ze \(\displaystyle{ \bigvee C \in B}\) dla każdego zbioru \(\displaystyle{ B\in M}\)Aby to pokazać niech \(\displaystyle{ B\in M}\). Z własności iloczynu mnogościowego \(\displaystyle{ \bigcap M \subset B}\). Nasze założenia dają \(\displaystyle{ C \subset \bigcap M \subset B}\), czyli \(\displaystyle{ C \subset B}\). Ponieważ \(\displaystyle{ C}\) jest łańcuchem i ponieważ zbiory \(\displaystyle{ B\in M}\) są nadmaksymalne to z własności (3) dostajemy \(\displaystyle{ \bigvee C \in B}\). Dowolność wyboru \(\displaystyle{ B\in M}\) kończy dowód.
Dowody punktów 2 i 1 są podobne (i mogą być tylko łatwiejsze) więc pozostawimy je czytelnikowi.
Zdefiniujmy zbiór \(\displaystyle{ B_{0}=\bigcap S}\) jako iloczyn wszystkich zbiorów nadmaksymalnych. Otrzymujemy zatem że \(\displaystyle{ B_{0}}\) jest nadmaksymalny. Z własności iloczynu jest on podzbiorem każdego nadmaksymalnego zbioru, jest najmniejszym zbiorem nadmaksymalnym.
\(\displaystyle{ \tikz{\draw[black!10!white] (0,0) -- (0.25,0)}}\) Pokażemy że zbiór \(\displaystyle{ B_{0}}\) jest łańcuchem- nie będzie to łatwe
Lemat 0 ( dla zgody numeracji z ważniakiem) Każdy element \(\displaystyle{ x}\) z \(\displaystyle{ B_{0 }}\) jest większy lub równy \(\displaystyle{ a}\)- \(\displaystyle{ x \ge a}\). Dowód(ukryty):
Ukryta treść:
\(\displaystyle{ B_{1}=\left\{ x\in B_{0}| \ \ y\in B_{0} \wedge y<x \longrightarrow f\left( y\right) \le x\right\}}\)
Jest to zbiór tych \(\displaystyle{ x}\)-ów z \(\displaystyle{ B_{0}}\) że razem z elementem silnie mniejszym od \(\displaystyle{ x}\) wartość \(\displaystyle{ f}\) na nim też nie przekracza \(\displaystyle{ x}\). Potem pokażemy że jest on równy całemu \(\displaystyle{ B_{0}}\). Wpierw udowodnijmy inny, bardzo pomocny lemat.
Lemat 1 Jeśli \(\displaystyle{ x\in B_{1}}\) to dla każdego \(\displaystyle{ y\in B_{0}}\) zachodzi: \(\displaystyle{ y \le x \vee f\left( x\right) \le y}\). Dowód:
Niech \(\displaystyle{ x\in B_{1}}\) Zdefiniujmy zbiór \(\displaystyle{ B_{x}}\):
\(\displaystyle{ B_{x}=\left\{ y\in B_{0}| \ \ y \le x \vee f\left( x\right) \le y\right\} \subset B_{0}}\)
Jest to zbiór tych elementów dla których dowodzony lemat zachodzi. Pokażemy że zbiór \(\displaystyle{ B_{x}}\) jest nadmaksymalny.
(1) Pokażmy że \(\displaystyle{ a\in B_{x}}\). Niewątpliwie \(\displaystyle{ a\in B_{0}}\) ( bo \(\displaystyle{ B_{0}}\) jest nadmaksymalny) Z lematu 0 wynika że \(\displaystyle{ x \ge a}\), czyli \(\displaystyle{ a\in B_{x}}\).
(2) Niech \(\displaystyle{ y\in B_{x}}\). Pokażmy że \(\displaystyle{ f\left( y\right)\in B_{x}}\). Ponieważ \(\displaystyle{ y\in B_{0}}\) to z nadmaksymalności \(\displaystyle{ B_{0}}\) mamy \(\displaystyle{ f\left( y\right)\in B_{0}}\). Pozostaje pokazać ze \(\displaystyle{ f\left( y\right) \le x \vee f\left( x\right) \le f\left( y\right)}\). Wiemy że \(\displaystyle{ y\in B_{x}}\), więc jeśli \(\displaystyle{ f\left( x\right) \le y}\) to ponieważ \(\displaystyle{ y \le f\left( y\right)}\) więc \(\displaystyle{ f\left( x\right) \le f\left( y\right)}\), co należało pokazać.
W przeciwnym przypadku mamy \(\displaystyle{ y \le x}\), wiec jeśli \(\displaystyle{ y=x}\), to \(\displaystyle{ f\left( y\right) =f \left( x\right)}\), zatem \(\displaystyle{ f\left( x\right) \le f\left( y\right)}\), a jeśli \(\displaystyle{ y<x}\) to z określenia \(\displaystyle{ B_{1}}\) dostajemy \(\displaystyle{ f\left( y\right) \le x}\). Zatem w każdym przypadku \(\displaystyle{ f\left( y\right) \le x \vee f\left( x\right) \le f\left( y\right)}\), więc \(\displaystyle{ f\left( y\right)\in B_{x}}\)
(3) Niech \(\displaystyle{ \left\{ \right\} \neq C\subset B_{x}}\) będzie łańcuchem niepustym. Pokażemy że \(\displaystyle{ \bigvee C \in B_{x}}\). Ponieważ \(\displaystyle{ B_{x}\subset B_{0}}\), więc \(\displaystyle{ C\subset B_{0}}\). Mamy że \(\displaystyle{ B_{0}}\) jest nadmaksymalny, więc \(\displaystyle{ \bigvee C \in B_{0}}\). Jeśli dla każdego \(\displaystyle{ y\in C}\) zachodzi \(\displaystyle{ y \le x}\), to \(\displaystyle{ x}\) jest ograniczeniem górnym zbioru \(\displaystyle{ C}\), ponieważ \(\displaystyle{ \bigvee C}\) jest najmniejszym ograniczeniem górnym dla \(\displaystyle{ C}\), więc \(\displaystyle{ \bigvee C \le x}\) i \(\displaystyle{ \bigvee C \in B_{x}}\). W przeciwnym przypadku (\(\displaystyle{ C}\) jest niepusty i jest podzbiorem \(\displaystyle{ B_{x}}\)), więc dla pewnego \(\displaystyle{ y\in C}\) zachodzi druga możliwość, czyli \(\displaystyle{ f\left( x\right) \le y}\). Wtedy \(\displaystyle{ y \le \bigvee C}\), więc \(\displaystyle{ f\left( x\right) \le \bigvee C}\), a zatem \(\displaystyle{ \bigvee C \in B_{x}}\)
Zatem \(\displaystyle{ B_{x}}\) jest nadmaksymalny. Ponieważ zbiór \(\displaystyle{ B _{0}}\) jest najmniejszym nadmaksymalnym to \(\displaystyle{ B_{0}\subset B_{x}}\) i \(\displaystyle{ B_{0}= B_{x}}\). Czyli dla każdego \(\displaystyle{ y\in B_{0}}\) zachodzi: \(\displaystyle{ y \le x \vee f\left( x\right) \le y}\) \(\displaystyle{ \square}\)
W kolejnym lemacie dowodzimy że zbiory \(\displaystyle{ B_{0}}\) i \(\displaystyle{ B_{1}}\) są równe. Dowód(ukryty):
Ukryta treść:
\(\displaystyle{ \tikz{\draw[black!10!white] (0,0) -- (0.25,0)}}\) Więc \(\displaystyle{ B_{0}}\) jest łańcuchem. Ponieważ zbiór \(\displaystyle{ B_{0}}\) jest też nadmaksymalny to stosując punkt 3 wnioskujemy że \(\displaystyle{ \bigvee B_{0}\in B_{0}}\), więc również \(\displaystyle{ f\left( \bigvee B_{0}\right) \in B_{0}}\)-znowu z nadmaksymalności \(\displaystyle{ B_{0}}\). Ponieważ jednak \(\displaystyle{ \bigvee B_{0}}\) jest większe lub równe od każdego elementu \(\displaystyle{ B_{0}}\), więc również \(\displaystyle{ f\left( \bigvee B_{0}\right) \le \bigvee B_{0}}\), nasze założenia dają \(\displaystyle{ \bigvee B_{0} \le f\left( \bigvee B_{0}\right)}\), wobec czego \(\displaystyle{ f\left( \bigvee B_{0}\right) = \bigvee B_{0}}\), co oznacza że \(\displaystyle{ \bigvee B_{0}}\) jest punktem stałym. \(\displaystyle{ \square}\)
Dodam że ten dowód, oparty na ważniaku, został tam przedstawiony w sposób dużo bardziej skrótowy.
To twierdzenie jest bardzo pomocne w udowodnieniu twierdzenia o maksymalnym łańcuchu.