Dowód tw. Bourbakiego-Witta i tw. o maksymalnym łańcuchu

Projekty i prace naukowe i badawcze. Nowatorskie idee matematyczne. Literatura specjalistyczna.
Jakub Gurak
Użytkownik
Użytkownik
Posty: 566
Rejestracja: 20 lip 2012, o 21:19
Płeć: Mężczyzna
Lokalizacja: Rzeszów

Dowód tw. Bourbakiego-Witta i tw. o maksymalnym łańcuchu

Post autor: Jakub Gurak » 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 \(\left( A, \le \right)\) każdy łańcuch posiada supremum oraz dla funkcji \(f\) przeprowadzającej \(A\) w \(A\) i spełniającej \(x \le f\left( x\right)\) dla dowolnego \(x\) to funkcja \(f\) posiada punkt stały, czyli istnieje \(x_{0}\) że \(f \left( x_{0}\right) =x_{0}\).

Dla łańcucha \(C\) jego supremum będziemy oznaczać \(\bigvee C\). W czasie tego dowodu zostaną pokazane trzy lematy. Są one częścią całego dowodu. Dowód:

Ustalmy \(a\in A\)( jeśli \(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':

\(S=\left\{ B \subset A | \ \ \textbf{(1)} \wedge \textbf{(2)} \wedge \textbf{(3)} \right\}\) gdzie

(1) \(\ a\in B\)
(2) \(\ \hbox{ jeśli } x\in B \hbox { to również } f\left( x\right)\in B\)
(3) \(\ \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 \(a\) i funkcję \(f\). Istnieją zbiory nadmaksymalne, gdyż cały zbiór \(A\) jest nadmaksymalny (rozpatrywane elementy należą do zbioru uporządkowanego \(A\)).

Zauważmy że jeśli \(M\) jest niepustym zbiorem zbiorów nadmaksymalnych to \(\bigcap M\) jest również zbiorem nadmaksymalnym.

Udowodnijmy punkt (3)

Niech \(C \subseteq \bigcap M\) będzie niepustym łańcuchem. Pokażemy że \(\bigvee C \in \bigcap M\). Wystarczy zatem pokazać ze \(\bigvee C \in B\) dla każdego zbioru \(B\in M\)Aby to pokazać niech \(B\in M\). Z własności iloczynu mnogościowego \(\bigcap M \subset B\). Nasze założenia dają \(C \subset \bigcap M \subset B\), czyli \(C \subset B\). Ponieważ \(C\) jest łańcuchem i ponieważ zbiory \(B\in M\) są nadmaksymalne to z własności (3) dostajemy \(\bigvee C \in B\). Dowolność wyboru \(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 \(B_{0}=\bigcap S\) jako iloczyn wszystkich zbiorów nadmaksymalnych. Otrzymujemy zatem że \(B_{0}\) jest nadmaksymalny. Z własności iloczynu jest on podzbiorem każdego nadmaksymalnego zbioru, jest najmniejszym zbiorem nadmaksymalnym.

\(\tikz{\draw[black!10!white] (0,0) -- (0.25,0)}\) Pokażemy że zbiór \(B_{0}\) jest łańcuchem- nie będzie to łatwe

Lemat 0 ( dla zgody numeracji z ważniakiem) Każdy element \(x\) z \(B_{0 }\) jest większy lub równy \(a\)- \(x \ge a\). Dowód(ukryty):
Ukryta treść:    
Zdefiniujmy zbiór:

\(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 \(x\)-ów z \(B_{0}\) że razem z elementem silnie mniejszym od \(x\) wartość \(f\) na nim też nie przekracza \(x\). Potem pokażemy że jest on równy całemu \(B_{0}\). Wpierw udowodnijmy inny, bardzo pomocny lemat.

Lemat 1 Jeśli \(x\in B_{1}\) to dla każdego \(y\in B_{0}\) zachodzi: \(y \le x \vee f\left( x\right) \le y\). Dowód:

Niech \(x\in B_{1}\) Zdefiniujmy zbiór \(B_{x}\):

\(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 \(B_{x}\) jest nadmaksymalny.

(1) Pokażmy że \(a\in B_{x}\). Niewątpliwie \(a\in B_{0}\) ( bo \(B_{0}\) jest nadmaksymalny) Z lematu 0 wynika że \(x \ge a\), czyli \(a\in B_{x}\).
(2) Niech \(y\in B_{x}\). Pokażmy że \(f\left( y\right)\in B_{x}\). Ponieważ \(y\in B_{0}\) to z nadmaksymalności \(B_{0}\) mamy \(f\left( y\right)\in B_{0}\). Pozostaje pokazać ze \(f\left( y\right) \le x \vee f\left( x\right) \le f\left( y\right)\). Wiemy że \(y\in B_{x}\), więc jeśli \(f\left( x\right) \le y\) to ponieważ \(y \le f\left( y\right)\) więc \(f\left( x\right) \le f\left( y\right)\), co należało pokazać.
W przeciwnym przypadku mamy \(y \le x\), wiec jeśli \(y=x\), to \(f\left( y\right) =f \left( x\right)\), zatem \(f\left( x\right) \le f\left( y\right)\), a jeśli \(y<x\) to z określenia \(B_{1}\) dostajemy \(f\left( y\right) \le x\). Zatem w każdym przypadku \(f\left( y\right) \le x \vee f\left( x\right) \le f\left( y\right)\), więc \(f\left( y\right)\in B_{x}\)
(3) Niech \(\left\{ \right\} \neq C\subset B_{x}\) będzie łańcuchem niepustym. Pokażemy że \(\bigvee C \in B_{x}\). Ponieważ \(B_{x}\subset B_{0}\), więc \(C\subset B_{0}\). Mamy że \(B_{0}\) jest nadmaksymalny, więc \(\bigvee C \in B_{0}\). Jeśli dla każdego \(y\in C\) zachodzi \(y \le x\), to \(x\) jest ograniczeniem górnym zbioru \(C\), ponieważ \(\bigvee C\) jest najmniejszym ograniczeniem górnym dla \(C\), więc \(\bigvee C \le x\) i \(\bigvee C \in B_{x}\). W przeciwnym przypadku (\(C\) jest niepusty i jest podzbiorem \(B_{x}\)), więc dla pewnego \(y\in C\) zachodzi druga możliwość, czyli \(f\left( x\right) \le y\). Wtedy \(y \le \bigvee C\), więc \(f\left( x\right) \le \bigvee C\), a zatem \(\bigvee C \in B_{x}\)

Zatem \(B_{x}\) jest nadmaksymalny. Ponieważ zbiór \(B _{0}\) jest najmniejszym nadmaksymalnym to \(B_{0}\subset B_{x}\) i \(B_{0}= B_{x}\). Czyli dla każdego \(y\in B_{0}\) zachodzi: \(y \le x \vee f\left( x\right) \le y\) \(\square\)

W kolejnym lemacie dowodzimy że zbiory \(B_{0}\) i \(B_{1}\) są równe. Dowód(ukryty):
Ukryta treść:    
Tak więc \(B _{0} =B _{1}\), więc dla dowolnych \(x\) i \(y\) w \(B_{0}\) mamy na podstawie lematu 1:\(y \le x \vee f\left( x\right) \le y\). W pierwszym przypadku mamy \(y \le x\) a więc elementy są porównywalne, w przeciwnym przypadku \(x \le f\left( x\right) \le y\), więc \(x \le y\), zatem również elementy są porównywalne. Z dowolności wyboru elementów \(x\) i \(y\) wnioskujemy że zbiór \(B _{0}\) jest łańcuchem. Mając to już łatwo zakończymy dowód tego twierdzenia.

\(\tikz{\draw[black!10!white] (0,0) -- (0.25,0)}\) Więc \(B_{0}\) jest łańcuchem. Ponieważ zbiór \(B_{0}\) jest też nadmaksymalny to stosując punkt 3 wnioskujemy że \(\bigvee B_{0}\in B_{0}\), więc również \(f\left( \bigvee B_{0}\right) \in B_{0}\)-znowu z nadmaksymalności \(B_{0}\). Ponieważ jednak \(\bigvee B_{0}\) jest większe lub równe od każdego elementu \(B_{0}\), więc również \(f\left( \bigvee B_{0}\right) \le \bigvee B_{0}\), nasze założenia dają \(\bigvee B_{0} \le f\left( \bigvee B_{0}\right)\), wobec czego \(f\left( \bigvee B_{0}\right) = \bigvee B_{0}\), co oznacza że \(\bigvee B_{0}\) jest punktem stałym. \(\square\) :D :D

Dodam że ten dowód, oparty na ważniaku, został tam przedstawiony w sposób dużo bardziej skrótowy. :mrgreen:

To twierdzenie jest bardzo pomocne w udowodnieniu twierdzenia o maksymalnym łańcuchu.

Jakub Gurak
Użytkownik
Użytkownik
Posty: 566
Rejestracja: 20 lip 2012, o 21:19
Płeć: Mężczyzna
Lokalizacja: Rzeszów

Dowód tw. Bourbakiego-Witta i tw. o maksymalnym łańcuchu

Post autor: Jakub Gurak » 8 paź 2016, o 01:13


Jakub Gurak
Użytkownik
Użytkownik
Posty: 566
Rejestracja: 20 lip 2012, o 21:19
Płeć: Mężczyzna
Lokalizacja: Rzeszów

Dowód tw. Bourbakiego-Witta i tw. o maksymalnym łańcuchu

Post autor: Jakub Gurak » 1 lip 2017, o 04:50

Ponieważ na forum NUDA, jak dla mnie, pozwolę sobie parę zdań napisać, aby wyjaśnić o co tu chodzi.

Chodzi o to, że najpierw ustalamy element początkowy \(a\in A\). Teraz proszę zauważyć, że jeśli zdarzy się taki \(x\) że \(f\left( x\right) =x\), to jest to punkt stały i dowód twierdzenia jest zakończony. Pozostaje zatem przyjmować że nieustannie \(f\left( x\right) \neq x\), co w obliczu założeń \(x \le f\left( x\right)\) dla dowolnego \(x\in A\), pozwala nam przyjmować że wartość \(f\left( x\right)\) jest silnie większa od \(x\)

Mamy zatem \(a\in A\), znajdujemy wzrastającą wartość zgodnie z powyższym \(a_{1}=f\left( a\right)\), i dalej \(a=:a_{0}<f\left( a\right)=a_{1}<f\left( a_{1}\right)=:a_{2}<f\left( a_{2}\right)=:a_{3}<f\left( a_{3}\right)=:a_{4}< \ldots\)

Tworząc łańcuch nieskończony \(\left\{ a_{0},a_{1},\ldots \right\}\). Łańcuch ten posiada supremum (bo nasze założenia mówią że każdy łańcuch posiada supremum), nazwijmy je \(a_{\omega}\). I dalej, na mocy naszych uwag:

\(a_{0}<a_{1}<a_{2}<a_{3}<a_{4}< \ldots a_{\omega}<f\left( a_{\omega}\right)=:a_{\omega+1}<f\left( a_{\omega+1}\right)=:a_{\omega+2}< \ldots\)

Łańcuch taki posiada supremum ( na mocy naszych założeń), nazwijmy je \(a_{2\omega}\). I dalej możemy wyznaczyć wzrastającą wartość \(f\left( a_{2\omega}\right)\), potem wzrastającą wartość na poprzednim elemencie, itd., no ale może dość tych konstrukcji

I twierdzenie to mówi, że to nieskończone (gorzej- w ogóle nie wiadomo kiedy się miałoby to zakończyć), te wzrastanie, że w końcu musi się zakończyć ( bo chyba elementy zbioru się wyczerpią), to wzrastanie zostanie przerwane, i wartość funkcji na tym szczytowym elemencie nie będzie już silnie większa, zawsze jest słabo większa, no to będzie równa temu szczytowemu argumentowi, co jest zgodne z tezą zresztą.

Gdyby chodziło tylko o nieskończoność zbioru... Wtedy podejrzewam, że dowód byłby o wiele prostszy- wystarczyłoby wyznaczyć zbiór \(B_{0}\), wziąć jego supremum i koniec. I konstrukcja w dowodzie jest dokładnie taka sama. Ale tu chodzi jeszcze o porządek, a nie tylko o nieskończoność. Nasze założenia odnośnie zbioru uporządkowanego wiele nie upraszczają. Na zegarze 3:00 (trochę zasiedziałem i zagapiłem się) więc może nie będę tego uzasadniał o tej porze. Czyli całe bogactwo zbiorów uporządkowanych może wystąpić i cała sieć zbioru uporządkowanego może wystąpić... I właśnie aby wyłowić zbiór \(B_{0}\) z tej całej sieci zbioru uporządkowanego, aby przekonać się że on jest rzeczywiście łańcuchem, potrzebowaliśmy aż trzech żmudnych lematów. To był naprawdę trudny problem.

Dodam, że formalnie rzecz biorąc, udowodniliśmy bardzo niewiele- znaleźliśmy jeden element na którym wartość funkcji jest równa temu elementowi. Ale to jest przekroczenie pewnego progu nieskończonego jak wiemy, i było bardzo pomocne do udowodnienia twierdzenia o maksymalnym łańcuchu, a możliwe że też może być pomocne do innych dowodów twierdzeń związanych z aksjomatem wyboru.

Uwaga! Pomiędzy \(x\) a \(f\left( x\right)\) mogą być wartości pośrednie (ale też nie muszą). Także stosowanie oznaczeń podobnych do liczb porządkowych może być mylące. Nie musi to być dobry porządek.

Jakub Gurak
Użytkownik
Użytkownik
Posty: 566
Rejestracja: 20 lip 2012, o 21:19
Płeć: Mężczyzna
Lokalizacja: Rzeszów

Re: Dowód tw. Bourbakiego-Witta i tw. o maksymalnym łańcuch

Post autor: Jakub Gurak » 16 sie 2019, o 03:08

Jeszcze jeden przykład zastosowania tego twierdzenia jest też tu. Ale po przeprowadzeniu takiego analogicznego dowodu uznałem, że wygodniej jest stosować lemat Zorna niż to twierdzenie Bourbakiego-Witta+twierdzenie o funkcji wyboru- z lematu Zorna jest wygodniej.

Natomiast bardzo łatwo z lematu Zorna wynika twierdzenie Bourbakiego-Witta.

Bardzo prosty dowód:

Zakładamy lemat Zorna, i pokazujemy twierdzenie Bourbakiego-Witta. W tym celu bierzemy zbiór uporządkowany \(\left( X, \le \right)\) taki, że każdy łańcuch ma supremum oraz dowolną funkcję \(f\) określoną na tym zbiorze uporządkowanym \(X\) I o wartościach w nim, taką że zawsze \(x \le f\left( x\right).\) Pokazujemy, że funkcja ma punkt stały. Należy pokazać, że w \(\left( X, \le \right)\) spełnione są założenia lematu Zorna, czyli że każdy łańcuch ma ograniczenie górne. Ustalmy dowolny łańcuch \(A.\) Ale ponieważ każdy łańcuch ma supremum, więc łańcuch \(A\) ma supremum, które z definicji jest ograniczeniem górnym . Wnioskujemy, że każdy łańcuch w \(\left( X, \le \right)\) ma ograniczenie górne.

Stosując lematu Zorna wnioskujemy, że w zbiorze uporządkowanym \(\left( X, \le \right)\) jest element maksymalny \(x\). Wtedy z założenia o funkcji \(f\) mamy \(x \le f\left( x\right) ,\) ale \(x\) jest elementem maksymalnym, więc \(f\left( x\right) =x,\) czyli \(x\) jest punktem stałym funkcji \(f. \square\)

Nie znaczy to jednak, że taki żmudny dowód twierdzenia Bourbakiego- Witta był niepotrzebny, bo wtedy lemat Zorna albo twierdzenie o maksymalnym łańcuchu miałyby pewnie żmudny dowód. Twierdzenie Bourbakiego- Witta to nie łatwy problem, ale w obliczu innych twierdzeń związanych z aksjomatem wyboru jest " najczystszy " najbardziej uproszczony. Twierdzenie o maksymalnym łańcuchu nie jest już takie "czyste"- musimy uwzględnić rozmaite przypadki odnośnie zbioru uporządkowanego.

Awatar użytkownika
Dasio11
Moderator
Moderator
Posty: 8465
Rejestracja: 21 kwie 2009, o 19:04
Płeć: Mężczyzna
Lokalizacja: Wrocław

Re: Dowód tw. Bourbakiego-Witta i tw. o maksymalnym łańcuch

Post autor: Dasio11 » 16 sie 2019, o 09:19

Jakub Gurak pisze:Twierdzenie Bourbakiego- Witta to nie łatwy problem, ale w obliczu innych twierdzeń związanych z aksjomatem wyboru jest " najczystszy " najbardziej uproszczony.
Jeśli masz na myśli, że twierdzenie Bourbakiego-Witta jest najprostszą drogą do lematu Kuratowskiego-Zorna, to ośmielę się nie zgodzić, podając jako przykład: https://faculty.math.illinois.edu/~dan/ ... s/Zorn.pdf

ODPOWIEDZ