szukanie zaawansowane
 [ Posty: 2 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 4 paź 2016, o 22:12 
Użytkownik

Posty: 489
Lokalizacja: Rzeszów
Czas w końcu, ( i to w 200 poście :lol: :D) 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 :P ):
https://www.matematyka.pl/411530.htm#p5448849

Oto nasz dowód:

Ustalmy dowolny niepusty zbiór uporządkowany \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 \left( B, \subset\right) złożony z wszystkich łańcuchów uporządkowanych inkluzją:

B=\left\{ A \subset X| \  \ A \hbox{ jest łańcuchem w }  \left(  X,\le \right) \right\}

\tikz{\draw[black!10!white] (0,0) -- (0.25,0)} Dalej, ustalmy dowolny łańcuch D\subset B w \left( B, \subset\right). Jeśli D jest pusty, to zauważmy że w \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 D jest niepusty, to za supremum kładziemy \bigcup D. Wpierw jednak musimy pokazać że \bigcup D \in B. Suma łańcuchów z D (podzbiorów X) niewątpliwie jest podzbiorem X. Suma łańcuchów \bigcup D będzie łańcuchem, gdyż rodzina D jest liniowo uporządkowana przez inkluzję, nietrudny dowód tego faktu zostawię Wam . A więc \bigcup D \in B. Niewątpliwie \bigcup D ( z własności sumy) jest ograniczeniem górnym rodziny D ze względu na inkluzję i jest najmniejszym takim zbiorem. A więc jest to supremum dla D. Z dowolności wyboru zbioru D, każdy łańcuch w \left( B, \subset\right) posiada supremum.

Na mocy twierdzenia o funkcji wyboru definiujemy funkcję wyboru f zwracającą dla każdego niepustego podzbioru X element tego podzbioru.

Twierdzenie Bourbakiego-Witta będziemy stosować do funkcji g przeprowadzającej zbiór łańcuchów B w zbiór łańcuchów B określonej:

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 C- my to czynimy.
Aby tak było musi istnieć element nie należący do C, a ponieważ ma być to łańcuch musi być on porównywalny z każdym elementem C. Zatem zbiór elementów nie należących do C porównywalnych z każdym elementem C jest niepusty. A skoro tak to funkcja wyboru f potrafi wybrać z niego jeden element. I my to czynimy wybierając f(C^{\prime}) i dodając go do łańcucha. Łatwo sprawdzić że C \cup \left\{ f\left( C ^{\prime} \right) \right\} jest również łańcuchem. Niewątpliwie jest istotnym nadzbiorem łańcucha C. :D

Jeśli natomiast naszego łańcucha nie da się rozszerzyć, to funkcja zwraca go takiego samego.
A więc widzimy, funkcja g przeprowadza zbiór łańcuchów B w B i spełnia że C \subseteq g(C) dla dowolnego łańcucha C\in B. Wcześniej pokazaliśmy że każdy łańcuch w \left( B, \subset\right) posiada supremum.

\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 D że g(D)=D. To gwarantuje że naszego łańcucha 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 D nie da się rozszerzyć, a więc D jest maksymalnym łańcuchem pod względem inkluzji. \square :D :D

-- 7 paź 2016, o 23:46 --

Ilustrację ( i omówienie) do tego twierdzenia można znaleźć tu :wink: :

https://www.matematyka.pl/402442.htm
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2019
Góra
Mężczyzna Offline
PostNapisane: 14 mar 2019, o 16:42 
Użytkownik

Posty: 489
Lokalizacja: Rzeszów
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 \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 \left(  X,\le \right). Rozważmy zbiór uporządkowany \left( B, \subset\right) złożony z wszystkich antyłańcuchów uporządkowanych inkluzją:

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 X jest porządkiem. Zatem tu też, wobec czego \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 D\subset B w \left( B, \subset\right). Za supremum kładziemy \bigcup D. Wpierw jednak musimy pokazać, że \bigcup D \in B. Suma antyłańcuchów z D (podzbiorów X) niewątpliwie jest podzbiorem X. Aby wykazać, że \bigcup D jest antyłańcuchem, weźmy dowolne dwa różne elementy x,y\in\bigcup D. Wtedy x\in A dla pewnego zbioru A\in D, oraz y\in C dla pewnego zbioru C\in D. Ponieważ D jest łańcuchem pod względem inkluzji, to A\subset C lub C\subset A. Jeśli A\subset C, to x,y\in C. Podobnie, w przeciwnym wypadku, jeśli C\subset A to x,y\in A. Czyli x,y są w C lub x,y są w A. Ponieważ C,A\in D, zbiory C,A są antyłańcuchami, więc ponieważ x,y są różnymi elementami takiego antyłańcucha, wnioskujemy, że elementy x,y są nieporównywalne. Pokazaliśmy, że dowolne dwa różne elementy \bigcup D są nieporównywalne, czyli \bigcup D jest antyłańcuchem, i należy do B. A więc \bigcup D \in B. Niewątpliwie \bigcup D ( z własności sumy) jest ograniczeniem górnym rodziny D, ze względu na inkluzję, i jest najmniejszym takim zbiorem. A więc jest to supremum dla D, tego łańcucha. Z dowolności wyboru zbioru D, każdy łańcuch w \left( B, \subset\right) posiada supremum.

Na mocy twierdzenia o funkcji wyboru definiujemy funkcję wyboru f, zwracającą, dla każdego niepustego podzbioru X, element tego podzbioru.

Twierdzenie Bourbakiego-Witta będziemy stosować do funkcji g przeprowadzającej zbiór antyłańcuchów B w B określonej:

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 g dostaje jako argument antyłańcuch oznaczony przez C, i rozszerza go (jeśli tylko możliwe) o jeden element( przy pomocy funkcji wyboru f) zbioru X, spoza C, nieporównywalny z żadnym elementem 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 g przeprowadza zbiór antyłańcuchów B w B, i spełnia, że C \subseteq g(C), dla dowolnego antyłańcucha C\in B. Wcześniej pokazaliśmy, że każdy łańcuch w \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 D, że g(D)=D. Z definicji funkcji g oznacza to , że zbiór D', elementów spoza D, nieporównywalnych z żadnym elementem D jest pusty, a stąd łatwo wynika, że wtedy D jest maksymalnym antyłańcuchem pod względem inkluzji.\square :lol: :D
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 2 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Element najmniejszy w łańcuchu  TorrhenMathMeth  2
 Twierdzenie Hausdorffa o łańcuchu maksymalnym - dowód  darek77  2
 dowód z elementem maksymalnym  forget24  4
 przyklad zbioru z wiecej niz jednym elementem maksymalnym  fuqs  8
 Ilość elementów w największym łańcuchu.  pawlo392  15
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl