Twierdzenie Knastra-Tarskiego

Algebra zbiorów. Relacje, funkcje, iloczyny kartezjańskie... Nieskończoność, liczby kardynalne... Aksjomatyka.
Jakub Gurak
Użytkownik
Użytkownik
Posty: 1392
Rejestracja: 20 lip 2012, o 21:19
Płeć: Mężczyzna
Lokalizacja: Rzeszów
Podziękował: 60 razy
Pomógł: 83 razy

Twierdzenie Knastra-Tarskiego

Post autor: Jakub Gurak »

Po raz drugi zrozumiałem ten dowód pochodzący z ważniaka, z tą jednak różnicą, że go zapisałem na kartce krok po kroku, na ważniaku są trochę skróty myślowe, więc się z Wami podzielę tym dowodem dokładnym

Funkcja \(\displaystyle{ f: P \left( X\right) \rightarrow P \left( X\right)}\) jest monotoniczna ze względu na inkluzję, gdy dla \(\displaystyle{ A,B \subset X}\) spełnia

\(\displaystyle{ A \subset B \rightarrow f\left( A\right) \subset f\left( B\right)}\)

Przypomnijmy że argumentami i wartościami funkcji \(\displaystyle{ f}\) są podzbiory \(\displaystyle{ X}\), i warunek ten mówi że jeśli pomiędzy argumentami \(\displaystyle{ A,B}\) zachodzi inkluzja to pomiędzy odpowiadającymi im wartościami również zachodzi inkluzja i to w tą samą stronę

Przykładem może być dla niepustego zbioru \(\displaystyle{ X}\) funkcja \(\displaystyle{ f: P \left( X\right) \rightarrow P \left( X\right)}\) stale równa zbiorowi pustemu \(\displaystyle{ \left\{ \right\}}\)
Jest monotoniczna, bo \(\displaystyle{ f\left( A\right)= \left\{ \right\} \subseteq \left\{ \right\}=f\left( B\right)}\)

Dla funkcji \(\displaystyle{ f: P \left( X\right) \rightarrow P \left( X\right)}\) zbiór \(\displaystyle{ C \subset X}\) jest największym punktem stałym gdy:
Po pierwsze jest punktem stałym, czyli \(\displaystyle{ f\left( C\right)=C}\)

I gdy każdy inny punkt stały jest jego podzbiorem \(\displaystyle{ f\left( D\right)=D \rightarrow D \subset C}\)

Analogicznie definiujemy najmniejszy punkt stały, jako punkt stały, który jest podzbiorem każdego innego punktu stałego

Największy punkt stały i najmniejszy punkt stały mogą nie istnieć, i to nawet gdy istnieją punkty stałe. Jak ktoś zechce, to bardzo chętnie o tym napisze Będziemy dowodzić, że

Każda funkcja monotoniczna ze względu na inkluzję \(\displaystyle{ f: P \left( X\right) \rightarrow P \left( X\right)}\) posiada największy punkt stały i najmniejszy punkt stały

Przed rozpoczęciem dowodu zanotujmy, że jeśli \(\displaystyle{ L}\) jest zbiorem zbiorów to oczywiście każdy zbiór \(\displaystyle{ A\in L}\) jest podzbiorem \(\displaystyle{ \bigcup L}\), formalnie

Każdy element \(\displaystyle{ L}\) jest podzbiorem \(\displaystyle{ \bigcup L}\)

Zanotujmy jeszcze że jeśli \(\displaystyle{ L}\) jest dowolnym zbiorem podzbiorów ustalonego zbioru \(\displaystyle{ Z}\) to \(\displaystyle{ \bigcup L}\) jest również podzbiorem \(\displaystyle{ Z}\)

Dowód Niech

\(\displaystyle{ L=\left\{ x \subset X \ \ \bigl( x\in P\left( X\right) \bigr) \Bigl | \quad f\left( x\right) \supset x \right\}}\) Pokażemy że \(\displaystyle{ \bigcup L}\) jest największym punktem stałym

Z określenia rodziny \(\displaystyle{ L}\) dla każdego \(\displaystyle{ x\in L}\)

\(\displaystyle{ x \subset f\left( x\right)}\) Jednocześnie, z własności sumy każdy zbiór \(\displaystyle{ x\in L}\) jest podzbiorem sumy rodziny \(\displaystyle{ L}\)

\(\displaystyle{ x \subset \bigcup L}\) więc z monotoniczności \(\displaystyle{ f}\) otrzymujemy że

\(\displaystyle{ f\left( x\right) \subset f\left( \bigcup L\right)}\) Więc otrzymujemy ze dla każdego \(\displaystyle{ x\in L}\)

\(\displaystyle{ x \subset f\left( x\right) \subset f\left( \bigcup L\right)}\) więc również \(\displaystyle{ x \subset f\left( \bigcup L\right)}\)

Zauważmy że \(\displaystyle{ f\left( \bigcup L\right)}\) jest to jeden ustalony zbiór

I ponieważ każdy zbiór \(\displaystyle{ x\in L}\) jest podzbiorem \(\displaystyle{ f\left( \bigcup L\right)}\), więc również \(\displaystyle{ \bigcup L}\) jest podzbiorem tego zbioru

\(\displaystyle{ \bigcup L \subset f\left( \bigcup L\right)}\) (*)

zatem \(\displaystyle{ \bigcup L\in L}\) Przekształcając (*) z monotoniczności \(\displaystyle{ f}\) dostaniemy

\(\displaystyle{ f\left( \bigcup L\right) \subset f\left( f\left( \bigcup L\right)\right)}\) Zatem z określenia rodziny \(\displaystyle{ L}\) mamy \(\displaystyle{ f\left( \bigcup L\right) \in L}\)

I ponieważ każdy element \(\displaystyle{ L}\) jest podzbiorem \(\displaystyle{ \bigcup L}\) więc również \(\displaystyle{ f\left( \bigcup L\right) \subset \bigcup L}\) Stąd i na podstawie (*) mamy \(\displaystyle{ f\left( \bigcup L\right) = \bigcup L}\)
co oznacza że \(\displaystyle{ \bigcup L}\) jest punktem stałym funkcji \(\displaystyle{ f}\)

Co więcej, jeśli \(\displaystyle{ c}\) jest punktem stałym, to \(\displaystyle{ f\left( c\right)=c}\), zatem również \(\displaystyle{ f\left( c\right) \supseteq c}\), zatem wszystkie punkty stałe należą do \(\displaystyle{ L}\), a skoro tak to z własności sumy każdy z nich jest podzbiorem \(\displaystyle{ \bigcup L}\), co oznacza że \(\displaystyle{ \bigcup L}\) jest największym punktem stałym \(\displaystyle{ \square}\)

W dowodzie najmniejszego punktu stałego rozpatrujemy

\(\displaystyle{ U=\left\{ x \subset X \ \ \Bigl | \quad f\left( x\right) \subset x \right\}}\) I pokazujemy że \(\displaystyle{ \bigcap U}\) jest najmniejszym punktem stałym. Dowód jest analogiczny
Jakub Gurak
Użytkownik
Użytkownik
Posty: 1392
Rejestracja: 20 lip 2012, o 21:19
Płeć: Mężczyzna
Lokalizacja: Rzeszów
Podziękował: 60 razy
Pomógł: 83 razy

Re: Twierdzenie Knastra-Tarskiego

Post autor: Jakub Gurak »

Ale jednak idei dowodu nie widziałem, i dalej mam z tym problem. Teraz podejrzewam, że ten największy zbiór stały to pojęciowo to jest o wiele gorszy problem niż twierdzenie Bourbakiego-Witta. Podejrzewam, że to jest również dowolnie nieskończony problem- tak samo jak twierdzenie Bourbakiego-Witta, ale może o wiele gorzej, bo chyba trzeba te (bardzo nieskończone) łańcuchy zbiorów utworzyć z różnych kierunków- wielu kierunków, bardzo wielu kierunków, nawet nie wiem czy dowolnie wielu... :? A potem jak to wszystko wysumujemy, to moze otrzymamy największy zbiór stały... :? Może... A ten Alfred Tarski to miał głowę. 8-) A przydaje się to, dzięki temu możemy udowodnić twierdzenie Cantora-Bernsteina, jakże przydatne twierdzenie teorii mocy zbiorów. Dokładniej, mając to twierdzenie o punkcie (zbiorze) stałym można łatwo udowodnić lemat Banacha PATRZ DOWÓD, a potem twierdzenie Cantora-Bernsteina DOWÓD I PRZYKŁADY ZASTOSOWAŃ.

Podam teraz jeszcze jeden przykład zastosowania twierdzenia Knastra-Tarskiego.

Niech \(\displaystyle{ \mathbb{X} }\) będzie rodziną induktywną (czyli rodziną spełniającą aksjomat nieskończoności, tzn. taką, że \(\displaystyle{ 1.\emptyset\in\mathbb{X}}\), oraz \(\displaystyle{ 2.A\in\mathbb{X} \rightarrow A \cup \left\{ A\right\}\in\mathbb{X}}\) ). Rozważmy funkcję \(\displaystyle{ f:P\left( \mathbb{X}\right) \rightarrow P(\mathbb{X})}\), tak, że dla dowolnego \(\displaystyle{ \mathbb{A}\subset\mathbb{X}}\) niech:

\(\displaystyle{ f\left( \mathbb{A}\right)=\mathbb{A} \cup \left\{ x \cup \left\{ x\right\}\Bigl| \ \ x\in \mathbb{A}\right\} \cup \left\{ \emptyset\right\}. }\)

Czyli do rodziny \(\displaystyle{ \mathbb{A}}\) dodajemy (jako elementy) następniki zbiorów z \(\displaystyle{ \mathbb{A}}\) oraz zbiór pusty.

Poniewaz \(\displaystyle{ \mathbb{X}}\) jest rodziną induktywną, więc łatwo sprawdzić, że zawsze \(\displaystyle{ f\left( \mathbb{A}\right)\subset\mathbb{X}}\), a więc \(\displaystyle{ f:P\left( \mathbb{X}\right)\rightarrow P(\mathbb{X})}\). Pokażemy, że funkcja \(\displaystyle{ f}\) jest monotoniczna.

Niech \(\displaystyle{ \mathbb{A},\mathbb{B}\subset\mathbb{X},}\) będą takie, że \(\displaystyle{ \mathbb{A}\subset\mathbb{B}}\), wtedy jeśli \(\displaystyle{ x\in f(\mathbb{A})=\mathbb{A} \cup \left\{ x \cup \left\{ x\right\}\Bigl| \ \ x\in A \right\} \cup \left\{ \emptyset\right\},}\) to albo\(\displaystyle{ x\in\mathbb{A} \cup \left\{ \emptyset\right\}}\) , i wtedy ponieważ \(\displaystyle{ \mathbb{A}\subset\mathbb{B}}\), to \(\displaystyle{ x\in\mathbb{B} \cup \left\{ \emptyset\right\} }\), a więc \(\displaystyle{ x\in f\left( \mathbb{B} \right)=\mathbb{B} \cup \left\{ x \cup \left\{ x\right\}\Bigl| \ \ x\in \mathbb{B} \right\} \cup \left\{ \emptyset\right\}}\), albo \(\displaystyle{ x}\) jest postaci \(\displaystyle{ a \cup \left\{ a\right\} }\), gdzie \(\displaystyle{ a\in\mathbb{A}}\) , wtedy \(\displaystyle{ a\in\mathbb{B}}\), a więc \(\displaystyle{ x\in \left\{ b \cup \left\{ b\right\}\Bigl| \ \ b\in\mathbb{B} \right\}}\) , a więc \(\displaystyle{ x\in f\left( \mathbb{B}\right)}\), a zatem \(\displaystyle{ f(\mathbb{A}) \subset f(\mathbb{B})}\), i otrzymujemy, że funkcja \(\displaystyle{ f}\) jest monotoniczna.

Ponieważ ta funkcja jest monotoniczna, więc na mocy twierdzenia Knastra-Tarskiego ma najmniejszy zbiór stały i największy zbiór stały. Zauważmy, że każdy zbiór stały tej funkcji jest zbiorem induktywnym- łatwo to można sprawdzić. Największym zbiorem stałym jest cały zbiór \(\displaystyle{ \mathbb{X}}\), to też łatwo sprawdzić. Na ważniaku piszą: "Znacznie ciekawszy jest najmniejszy punkt stały, nazwijmy go \(\displaystyle{ \omega}\). Jest to najmniejszy zbiór induktywny będący podzbiorem \(\displaystyle{ \mathbb{X}}\)" No bo tutaj ,każdy punkt stały, jak mówiliśmy, jest zbiorem induktywnym, i oczywiście jest podzbiorem zbioru \(\displaystyle{ \mathbb{X}.}\) Potem utożsamiają go ze zbiorem liczb naturalnych von Neumanna. Wygłąda na to, że to jest ten sam zbiór. Służy on nam jako \(\displaystyle{ \NN}\). :lol: 8-)
Jan Kraszewski
Administrator
Administrator
Posty: 34123
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 3 razy
Pomógł: 5192 razy

Re: Twierdzenie Knastra-Tarskiego

Post autor: Jan Kraszewski »

Jakub Gurak pisze: 26 kwie 2020, o 02:35bo chyba trzeba te (bardzo nieskończone) łańcuchy zbiorów utworzyć z różnych kierunków- wielu kierunków, bardzo wielu kierunków, nawet nie wiem czy dowolnie wielu... :? A potem jak to wszystko wysumujemy, to moze otrzymamy największy zbiór stały... :?
Myślę, że patrzysz na to trochę zbyt jednostronnie.
Jakub Gurak pisze: 26 kwie 2020, o 02:35Na ważniaku piszą: "Znacznie ciekawszy jest najmniejszy punkt stały, nazwijmy go \(\displaystyle{ \omega}\). Jest to najmniejszy zbiór induktywny będący podzbiorem \(\displaystyle{ \mathbb{X}}\)" No bo tutaj ,każdy punkt stały, jak mówiliśmy, jest zbiorem induktywnym, i oczywiście jest podzbiorem zbioru \(\displaystyle{ \mathbb{X}.}\)
Można i tak, ale wykorzystywanie tw. Knastera-Tarskiego do tego dowodu to dla mnie spora przesada, która w dodatku zaciemnia obraz sytuacji. Dużo prościej jest wziąć przekrój wszystkich induktywnych podzbiorów \(\displaystyle{ \mathbb{X}}\) - dostajemy to samo szybciej i bez zbędnych ornamentów w stylu "punkt stały".
Jakub Gurak pisze: 26 kwie 2020, o 02:35Potem utożsamiają go ze zbiorem liczb naturalnych von Neumanna. Wygłąda na to, że to jest ten sam zbiór. Służy on nam jako \(\displaystyle{ \NN}\). :lol: 8-)
To nie jest takie proste, czego na ważniaku zapewne nie napisali.

Powtórzę Ci jeszcze raz tę samą radę, którą już kilka razy dostałeś: czytaj inne rzeczy niż ważniak. Poczytaj np. "Teorię mnogości" Błaszczyka, Turka - w kwestii poznawania teorii mnogości będzie to dużo lepsze niż uparte wałkowanie ważniaka.

JK
Jakub Gurak
Użytkownik
Użytkownik
Posty: 1392
Rejestracja: 20 lip 2012, o 21:19
Płeć: Mężczyzna
Lokalizacja: Rzeszów
Podziękował: 60 razy
Pomógł: 83 razy

Re: Twierdzenie Knastra-Tarskiego

Post autor: Jakub Gurak »

To może Pan znaleźć link do jakiejś strony z klasyczną matematyką :?: (biblioteka moja nieczynna teraz ). A, Teorię Mnogości, Błaszczyka, Turka- miałem w ręku, raczej nieciekawie wspominam, i tam jest dużo dziwnych rzeczy- jakieś filtry, ultrafirty- nieciekawie. A to co tutaj poruszamy, czyli nieskończoność, też specjalnie mnie nie porywa- ja dużo bardziej lubię kontrprzykłady do twierdzeń ogólnych na zbiorach skończonych. Z matematyki, to chyba najbardziej lubię ogólne fakty, które w dodatku można w pewien sposób zilustrować, np. liniowe porządki, suma porządkowa liniowych porządków,...
Ale jak już kiedyś mówiłem interesuje mnie głównie klasyczna matematyka, gdy np. na studiach zaczyna materiał przybierać dziwną formę( a tak jest zazwyczaj niestety), to mi się to wydaje to trudne do zapamiętania, jakieś takie dziwne, trudne. Także klasyczna matematyka. I, im więcej ilustracji- tym lepiej( w Błaszczyku,Turku zapamiętałem sobie, że ta książka jest niestety pozbawiona ilustracji).

No, ważniak ma ten plus dla mnie, że są tam zebrane takie same ogólne, klasyczne fakty, więc pasuje do moich zainteresowań matematycznych. Także szukam zamiennika :)
Jan Kraszewski
Administrator
Administrator
Posty: 34123
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 3 razy
Pomógł: 5192 razy

Re: Twierdzenie Knastra-Tarskiego

Post autor: Jan Kraszewski »

Jakub Gurak pisze: 26 kwie 2020, o 22:53A, Teorię Mnogości, Błaszczyka, Turka- miałem w ręku, raczej nieciekawie wspominam, i tam jest dużo dziwnych rzeczy- jakieś filtry, ultrafirty- nieciekawie.
To jest dopiero w drugiej części książki. A ta książka to obecnie najlepsza pozycja po polsku jeśli chodzi o teorię mnogości.

Nawiasem mówiąc filtry i ultrafiltry to bardzo ciekawe obiekty (choć ja osobiście wolę ideały...).
Jakub Gurak pisze: 26 kwie 2020, o 22:53Także klasyczna matematyka. I, im więcej ilustracji- tym lepiej( w Błaszczyku,Turku zapamiętałem sobie, że ta książka jest niestety pozbawiona ilustracji).
Przykro mi, ale nie kojarzę podręczników z teorii mnogości na poziomie akademickim z obrazkami.
Jakub Gurak pisze: 26 kwie 2020, o 22:53No, ważniak ma ten plus dla mnie, że są tam zebrane takie same ogólne, klasyczne fakty, więc pasuje do moich zainteresowań matematycznych.
Twój wybór, ale przez to w zakresie teorii mnogości cały czas pozostajesz (z mojego punktu widzenia) na poziomie studenta pierwszego roku studiów matematycznych (jeśli chodzi o pewne rozumowania, to nawet dobrego studenta). Dokładności i staranności Ci nie brakuje, ale daje się zauważyć odtwórczość - starasz się czytać i poprawiać rozumowania już przez kogoś napisane, zamiast dążyć do samodzielnego tworzenia tych rozumowań. Ale jeżeli sprawia Ci to przyjemność, to OK, każdy sam decyduje, czym będzie się zajmował.

JK
Jakub Gurak
Użytkownik
Użytkownik
Posty: 1392
Rejestracja: 20 lip 2012, o 21:19
Płeć: Mężczyzna
Lokalizacja: Rzeszów
Podziękował: 60 razy
Pomógł: 83 razy

Re: Twierdzenie Knastra-Tarskiego

Post autor: Jakub Gurak »

Udowodniłem wczoraj i przedwczoraj, że dla dowolnego zbioru \(\displaystyle{ x}\), mamy:\(\displaystyle{ }\)

\(\displaystyle{ \bigcap x=x \Leftrightarrow x=\emptyset}\),

przekrój rodziny \(\displaystyle{ x}\) jest jej równy, tylko wtedy, gdy rodzina \(\displaystyle{ x}\) jest rodziną pustą.

Niestety, podobna własność nie zachodzi dla sum uogólnionych, tzn. istnieje niepusty zbiór \(\displaystyle{ x}\), taki, że: \(\displaystyle{ \bigcup x=x}\).

Wykazałem też, że dla dowolnego zbioru \(\displaystyle{ x}\), mamy: \(\displaystyle{ \prod x \neq x}\)- uogólniony iloczyn kartezjański rodziny \(\displaystyle{ x}\) jest od niej różny. Przedstawię teraz dowody tych formalnych faktów.


Niech \(\displaystyle{ x}\) będzie zbiorem. Wykażemy, że:

\(\displaystyle{ \bigcap x=x \Leftrightarrow x=\emptyset}\),

czyli, że przekrój rodziny \(\displaystyle{ x}\) jest jej równy, dokładnie wtedy, gdy ta rodzina jest rodziną pustą.

DOWÓD TEGO FAKTU:

Z definicji przekroju mnogościowego, mamy \(\displaystyle{ \bigcap\emptyset \subset \bigcup\emptyset=\emptyset}\), a ponieważ jedynym podzbiorem zbioru pustego jest on sam, więc \(\displaystyle{ \bigcap\emptyset =\emptyset}\), co dowodzi implikacji w lewo.

Pozostaje wykazać, że jeśli zbiór \(\displaystyle{ x \neq \emptyset}\), to \(\displaystyle{ \bigcap x \neq x. }\)

Przypuśćmy nie wprost, że \(\displaystyle{ \bigcap x=x}\).
Ponieważ \(\displaystyle{ x \neq \emptyset}\), to również \(\displaystyle{ \bigcap x \neq \emptyset}\), istnieje więc zbiór \(\displaystyle{ b\in \bigcap x}\), a więc \(\displaystyle{ b\in c,}\) dla każdego zbioru \(\displaystyle{ c\in x \neq \emptyset;}\), ponieważ \(\displaystyle{ b\in \bigcap x=x}\), a więc z zasady równości zbiorów: \(\displaystyle{ b\in x}\); podstawiając zatem za \(\displaystyle{ c}\) zbiór \(\displaystyle{ b}\), otrzymujemy: \(\displaystyle{ b\in b}\), co przeczy aksjomatowi regularności. Wobec czego \(\displaystyle{ \bigcap x \neq x}\), i:

\(\displaystyle{ \bigcap x=x \Leftrightarrow x=\emptyset.\square }\) 8-)


Zauważmy, że podobna własność nie zachodzi dla sum uogólnionych, tzn. istnieje niepusty zbiór \(\displaystyle{ x}\), taki, że: \(\displaystyle{ \bigcup x=x.}\)

Wystarczy wziąć \(\displaystyle{ x=\omega=\NN}\).

Wtedy \(\displaystyle{ \omega \neq \emptyset}\), i jeśli \(\displaystyle{ n\in\NN=\omega}\) ( chodzi o zbiór liczb naturalnych von Neumanna), to \(\displaystyle{ n\subset \NN=\omega}\), gdyż mamy twierdzenie, że każdy element liczby naturalnej von Neumanna jest liczbą naturalną von Neumanna. Wobec czego, z dowolności wyboru \(\displaystyle{ n\in\omega}\), otrzymujemy, że kazdy zbiór \(\displaystyle{ n\in\omega}\): \(\displaystyle{ n\subset \omega}\), więc również \(\displaystyle{ \bigcup\omega\subset \omega.}\)

Aby pokazać inkluzję w drugą stronę,
to niech \(\displaystyle{ n\in\omega}\), wtedy \(\displaystyle{ n\in n'=n \cup \left\{ n\right\}}\), a więc \(\displaystyle{ n\in n'\in\omega}\), a więc \(\displaystyle{ n\in\bigcup\omega}\),

i \(\displaystyle{ \bigcup\omega=\omega}\), gdzie \(\displaystyle{ \omega \neq \emptyset.\square}\)


Wykażemy jeszcze, że dla każdego zbioru \(\displaystyle{ x}\), mamy:

\(\displaystyle{ \prod x \neq x}\),

czyli, że produkt uogólniony rodziny \(\displaystyle{ x}\) jest od niej różny.

DOWÓD TEGO FAKTU:

Przypomnijmy definicję produktu uogólnionego zbioru \(\displaystyle{ x}\):

\(\displaystyle{ \prod x=\left\{ f:x \rightarrow \bigcup x\Bigl| \ \ f(a)\in a, \hbox { dla każdego zbioru } a\in x \right\}.}\)

Zauważmy, że \(\displaystyle{ \prod\emptyset =\left\{ \hbox{ FUNKCJA PUSTA}\right\}}\), a funkcja pusta to funkcja określona na zbiorze pustym, więc formalnie jest to podzbiór zbioru \(\displaystyle{ \emptyset \times \left( \bigcup\emptyset\right) =\emptyset}\), więc otrzymujemy, że: \(\displaystyle{ \prod\emptyset = \left\{ \emptyset \right\} \neq \emptyset}\), bo \(\displaystyle{ \emptyset\not\in\emptyset}\), czyli: \(\displaystyle{ \prod\emptyset \neq \emptyset.}\)

Jeśli \(\displaystyle{ x \neq \emptyset.}\)

Przypuśćmy nie wprost, że: \(\displaystyle{ \prod x=x}\). Wtedy istnieje zbiór \(\displaystyle{ a\in x}\), a więc \(\displaystyle{ a\in \prod x}\), a zatem \(\displaystyle{ a:x \rightarrow \bigcup x}\), i \(\displaystyle{ a(b)\in b}\), dla każdego zbioru \(\displaystyle{ b\in x}\). Ponieważ \(\displaystyle{ a\in x}\), to \(\displaystyle{ a\in a_L=x}\), a więc \(\displaystyle{ (a,b)\in a}\), dla pewnego zbioru \(\displaystyle{ b\in \bigcup x}\). Wtedy, z definicji pary uporządkowanej: \(\displaystyle{ \left\{ \left\{ a\right\}, \left\{ a,b\right\} \right\} \in a}\), a zatem:

\(\displaystyle{ a\in \left\{ a\right\} \in \left\{ \left\{ a\right\},\left\{ a,b\right\} \right\} \in a}\),

a taka 'pętlę' na zbiorach wyklucza aksjomat regularności- sprzeczność.

Wobec czego: \(\displaystyle{ \prod x \neq x.\square}\) :lol:


Zauważmy na koniec, że dla każdego zbioru \(\displaystyle{ x}\), mamy: \(\displaystyle{ P(x) \neq x}\)- zbiór potęgowy zbioru \(\displaystyle{ x}\) jest od niego różny.

Gdyby bowiem byłoby: \(\displaystyle{ P(x)=x}\), to ponieważ \(\displaystyle{ x\subset x}\), to \(\displaystyle{ x\in P(x)=x}\), a więc z zasady równości zbiorów moglibyśmy wnioskować, że: \(\displaystyle{ x\in x}\)- sprzeczność. Wobec czego \(\displaystyle{ P(x) \neq x}\), dla każdego zbioru \(\displaystyle{ x}\).
Jan Kraszewski
Administrator
Administrator
Posty: 34123
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 3 razy
Pomógł: 5192 razy

Re: Twierdzenie Knastra-Tarskiego

Post autor: Jan Kraszewski »

Jakub Gurak pisze: 1 kwie 2022, o 21:04Wystarczy wziąć \(\displaystyle{ x=\omega=\NN}\).

Wtedy \(\displaystyle{ \omega \neq \emptyset}\), i jeśli \(\displaystyle{ n\in\NN=\omega}\) ( chodzi o zbiór liczb naturalnych von Neumanna), to \(\displaystyle{ n\subset \NN=\omega}\), gdyż mamy twierdzenie, że każdy element liczby naturalnej von Neumanna jest liczbą naturalną von Neumanna. Wobec czego, z dowolności wyboru \(\displaystyle{ n\in\omega}\), otrzymujemy, że kazdy zbiór \(\displaystyle{ n\in\omega}\): \(\displaystyle{ n\subset \omega}\), więc również \(\displaystyle{ \bigcup\omega\subset \omega.}\)
Utożsamienie \(\displaystyle{ \NN=\omega}\) wymaga solidnego komentarza (który możesz znaleźć we wspomnianej wyżej książce Błaszczyka, Turka), bo \(\displaystyle{ \NN}\) to zbiór liczb naturalnych, a \(\displaystyle{ \omega}\) to najmniejszy zbiór induktywny.

Natomiast ten dowód tak naprawdę wymaga faktu, że zbiór \(\displaystyle{ \omega}\) jest tranzytywny (który udowadniasz wprost z definicji \(\displaystyle{ \omega}\)).

JK
Awatar użytkownika
Dasio11
Moderator
Moderator
Posty: 10211
Rejestracja: 21 kwie 2009, o 19:04
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 40 razy
Pomógł: 2359 razy

Re: Twierdzenie Knastra-Tarskiego

Post autor: Dasio11 »

Jakub Gurak pisze: 1 kwie 2022, o 21:04Z definicji przekroju mnogościowego, mamy \(\displaystyle{ \bigcap\emptyset \subset \bigcup\emptyset}\)
Zaiste ciekawa własność. ;>
Jan Kraszewski
Administrator
Administrator
Posty: 34123
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 3 razy
Pomógł: 5192 razy

Re: Twierdzenie Knastra-Tarskiego

Post autor: Jan Kraszewski »

Dasio11 pisze: 1 kwie 2022, o 22:24Zaiste ciekawa własność. ;>
To akurat korzysta z definicji \(\displaystyle{ \bigcap x=\left\{ y\in \bigcup x: (\forall t\in x)y\in t\right\}. }\)

JK
Jakub Gurak
Użytkownik
Użytkownik
Posty: 1392
Rejestracja: 20 lip 2012, o 21:19
Płeć: Mężczyzna
Lokalizacja: Rzeszów
Podziękował: 60 razy
Pomógł: 83 razy

Re: Twierdzenie Knastra-Tarskiego

Post autor: Jakub Gurak »

NA TEŚCIE Z WAŻNIAKA pisze: Czy dla dowolnego zbioru \(\displaystyle{ A}\), mamy: \(\displaystyle{ \bigcap A \le _m A}\) ?
Można zatem zadać pytanie analogiczne:

Czy istnieje rodzina zbiorów \(\displaystyle{ \mathcal{A}}\), taka, że: \(\displaystyle{ \bigcup\mathcal{A} <_m \mathcal {A} }\) ?

gdzie \(\displaystyle{ <_m}\) oznacza silną nierówność mocy zbiorów.

Albo czy istnieje rodzina \(\displaystyle{ \mathcal{A}}\) zbiorów niepustych, taka, że \(\displaystyle{ \left| \bigcup\mathcal{A}\right| <_m\left| \mathcal{A}\right|}\) ?

Odpowiedż na te dwa pytania jest twierdząca- przedwczoraj to udowodniłem (tzn. fakt odpowiadający na to ostatnie trudniejsze pytanie, na poprzednie pytanie odpowiedziałem już wcześniej). Udowodniłem też wczoraj, że istnieje niepusta rodzina zbiorów \(\displaystyle{ x}\), taka, że: \(\displaystyle{ \bigcap x \subset x}\). Przedstawię teraz dowody tych formalnych faktów.


A więc podamy przykład rodziny zbiorów \(\displaystyle{ \mathcal{A}}\), takiej, że: \(\displaystyle{ \left| \bigcup\mathcal{A}\right| <\left| \mathcal{A}\right|.}\)

Wystarczy rozważć liczbę naturalną von Neumanna \(\displaystyle{ 2=\left\{ 0,1\right\} =\left\{ \emptyset, \left\{ \emptyset\right\} \right\}.}\)

Wtedy \(\displaystyle{ \left| \bigcup 2\right| = \left| \emptyset \cup \left\{ \emptyset\right\} \right| = \left| \left\{ \emptyset\right\} \right| =1<2}\), co kończy dowód.


Odpowemy teraz na pytanie trudniejsze, tzn. pokażemy przykład rodziny \(\displaystyle{ \mathcal{A}}\) zbiorów niepusrtych, tzn. takiej, że \(\displaystyle{ \emptyset\not\in \mathcal{A}}\), i takiej, że jednocześnie \(\displaystyle{ \left| \bigcup\mathcal{A}\right|<\left| \mathcal{A}\right|.}\)

Niech \(\displaystyle{ \mathcal{A}= \left\{ \ \left\{ \emptyset\right\}; \ \left\{ \left\{ \emptyset\right\} \right\}; \ \left\{ \emptyset, \left\{ \emptyset\right\} \right\} \ \ \right\}.}\)

Wtedy \(\displaystyle{ \bigcup\mathcal{A}= \left\{ \emptyset , \left\{ \emptyset\right\} \right\},}\) a więc \(\displaystyle{ \left| \bigcup\mathcal{A}\right|=2.}\)

A mamy: \(\displaystyle{ \left| \mathcal{A}\right| =3}\), gdyż (musimy się jeszcze upewnić, że te trzy elementy są różne), mamy: \(\displaystyle{ \left\{ \emptyset \right\} \neq \left\{ \left\{\emptyset \right\}\right\} }\), bo \(\displaystyle{ \emptyset \neq \left\{ \emptyset\right\}}\) .

i mamy \(\displaystyle{ \left\{ \emptyset , \left\{ \emptyset\right\} \right\} \neq \left\{ \emptyset\right\}}\) , bo \(\displaystyle{ \left\{ \emptyset\right\} \not\in \left\{ \emptyset\right\}}\), chociażby z takiego powodu, że żaden zbiór nie jest elementem samego siebie.

I mamy \(\displaystyle{ \left\{ \emptyset, \left\{ \emptyset\right\} \right\} \neq \left\{ \left\{ \emptyset\right\} \right\} }\) , bo \(\displaystyle{ \emptyset \not\in \left\{ \left\{ \emptyset\right\} \right\}}\) , bo \(\displaystyle{ \emptyset \neq \left\{ \emptyset\right\}.}\)

A zatem \(\displaystyle{ \left| \mathcal{A}\right| =3, a \left| \bigcup\mathcal{A}\right| =2<3= \left| \mathcal{A}\right|,}\) i \(\displaystyle{ \emptyset\not\in \mathcal{A} .\square}\) :lol:


Wykażemy teraz, że istnieje niepusta rodzina zbiorów \(\displaystyle{ x}\), taka, że: \(\displaystyle{ \bigcap x\subset x}\).

Wystarczy wziąć dowolną rodzinę zbiorów \(\displaystyle{ x}\), do której należą dwa zbiory rozłączne \(\displaystyle{ a,b.}\) Wtedy \(\displaystyle{ x\supset \left\{ a,b\right\}}\). A ponieważ przekrój większej rodziny zbiorów jest mniejszy, o ile mniejsza rodzina zbiorów nie jest pusta, a przecież rodzina \(\displaystyle{ \left\{ a,b\right\}}\) jest oczywiście niepusta, a zatem \(\displaystyle{ \bigcap x\subset \bigcap \left\{ a,b\right\} =a \cap b=}\) i ponieważ zbiory \(\displaystyle{ a,b }\) są rozłączne, to to jest równe:

\(\displaystyle{ =\emptyset}\),

i ponieważ jedymeym podzbiorem zbioru pustego jest on sam, więc również \(\displaystyle{ \bigcap x=\emptyset.}\)

Ponieważ zbiór pusty jest podzbiorem każdego zbioru, więc również:

\(\displaystyle{ \bigcap x=\emptyset \subset x}\), i gdzie \(\displaystyle{ x \neq \emptyset. \square }\)

Jednak, dla niepustej rodziny zbiorów \(\displaystyle{ x,}\) wtedy inkluzja: \(\displaystyle{ \bigcap x\supset x}\), jest niemoliwa.

Przypuśćmy nie wprost, że \(\displaystyle{ \bigcap x\supset x.}\)

Niech \(\displaystyle{ a\in x \neq \left\{ \right\}.}\) Wtedy, z założonej inkluzji, wynika, że \(\displaystyle{ a\in \bigcap x}\), a więc, z definicji przkroju mnofgościowego: \(\displaystyle{ a\in b}\), dla kazdego zbioru \(\displaystyle{ b\in x}\). Mamy \(\displaystyle{ a\in x}\), więc podstawijac za \(\displaystyle{ b}\) zbiór \(\displaystyle{ a}\) otrzymamy: \(\displaystyle{ a\in a}\)-sprzeczność\(\displaystyle{ .\square}\)


Na koniec wykażemy, że dla dowolnej relacji \(\displaystyle{ R}\) ze zbioru \(\displaystyle{ X}\) w zbiór \(\displaystyle{ Y}\), mamy:

\(\displaystyle{ \bigcup \bigcup R= R_L \cup R_P}\),

(przy definicji pary uporządkowanej według Kuratowskiego, żeby polecenie miało sens) .

DOWÓD TEGO FAKTU:

Pokażemy inkluzję w obydwie strony:

Zacznijmy od inklizuji w prawo:
Weźmy dowolny element \(\displaystyle{ x\in \bigcup \left( \bigcup R \right) }\). Wtedy, z definicji sumy, istnieje element \(\displaystyle{ y\in \bigcup R}\), taki, że \(\displaystyle{ x\in y}\). Skoro \(\displaystyle{ y \in \bigcup R}\), to podobnie istnieje para \(\displaystyle{ \left( a,b\right) \in R}\), taka, że \(\displaystyle{ y \in \left( a,b\right) }\). Ponieważ \(\displaystyle{ \left( a,b\right)= \left\{ \left\{ a\right\} , \left\{ a,b\right\} \right\},}\) to \(\displaystyle{ y=\left\{ a\right\}}\) lub \(\displaystyle{ y=\left\{ a,b\right\} }\). Ponieważ \(\displaystyle{ x\in y}\), to \(\displaystyle{ x=a,}\) i wtedy \(\displaystyle{ x\in R_L}\) (bo \(\displaystyle{ \left( a,b\right)\in R}\) ) ; lub \(\displaystyle{ x=b,}\) i wtedy \(\displaystyle{ x \in R_P}\). Wobec czego (w obydwu przypadkach): \(\displaystyle{ x\in R_L \cup R_P}\), i \(\displaystyle{ \bigcup \left( \bigcup R\right) \subset R_L \cup R_P.}\)

Niech teraz \(\displaystyle{ a\in R_L}\), wtedy \(\displaystyle{ \left( a,b\right)\in R}\), dla pewnego elementu \(\displaystyle{ b\in Y}\). Wtedy \(\displaystyle{ \left\{ \left( a,b\right) \right\} \subset R}\), a zatem, poniewaz suma większej (słabo większej), względem inkluzji, rodziny zbiorów jest większa (słabo większa)- jest to prosty fakt, więc:

\(\displaystyle{ \bigcup \left\{ \left( a,b\right) \right\} \subset \bigcup R}\), i dalej:

\(\displaystyle{ \bigcup \left( \bigcup \left\{ \left( a,b\right) \right\} \right)\subset \bigcup \left( \bigcup R\right).}\)

Ponieważ:

\(\displaystyle{ \bigcup \left( \bigcup \left\{ \left( a,b\right) \right\}\right) = \bigcup \left( a,b\right) = \bigcup \left\{ \left\{ a\right\}, \left\{ a,b\right\} \right\} =\left\{ a,b\right\} }\),

a zatem \(\displaystyle{ \left\{ a,b\right\} \subset \bigcup \bigcup R}\), a więc \(\displaystyle{ a\in \bigcup \left( \bigcup R\right).}\)


A jesli \(\displaystyle{ b\in R_P}\), to w sposób analogiczny pokazujemy, że \(\displaystyle{ b\in \bigcup \left( \bigcup R\right).}\)

Łącząc te dwa fakty otrzymujemy, że \(\displaystyle{ R_L \cup R_P\subset \bigcup \bigcup R}\), i

\(\displaystyle{ \bigcup\left( \bigcup R\right)= R_L \cup R_P . \square}\) :lol:
Jakub Gurak
Użytkownik
Użytkownik
Posty: 1392
Rejestracja: 20 lip 2012, o 21:19
Płeć: Mężczyzna
Lokalizacja: Rzeszów
Podziękował: 60 razy
Pomógł: 83 razy

Re: Twierdzenie Knastra-Tarskiego

Post autor: Jakub Gurak »

Mamy też taki fakt:
Dla dowolnej liczby naturalnej von Neumanna \(\displaystyle{ n}\): jeśli \(\displaystyle{ n \neq 0}\), to: \(\displaystyle{ \bigcup n \in \NN}\) i \(\displaystyle{ \left( \bigcup n\right)'= n.}\)
Oraz dla dowolnej liczby naturalnej von Neumanna \(\displaystyle{ n}\), mamy: \(\displaystyle{ \bigcap n= \emptyset=0. }\)

Zauważmy, że dla funkcji \(\displaystyle{ f:X \rightarrow X}\) może nie istnieć punkt stały,
np. dla funkcji \(\displaystyle{ f= \left\{ \left( 0,1\right); \left( 1,0\right) \right\}}\) nie istnieje punkt stały.

Inny przykład:

Niech \(\displaystyle{ X}\) będzie niepustym zbiorem.
Wykażemy, że dla funkcji \(\displaystyle{ f:P\left( X\right) \rightarrow P\left( X\right)}\), danej jako:

\(\displaystyle{ f(A)= X \setminus A}\),

nie istnieje zbiór stały.
DOWÓD TEGO FAKTU::    
Autorzy ważniaka podają przykład na to, że może nie istnieć największy zbiór stały, w sytuacji której istnieją zbiory stałe. Jednak zrobili tam, dość podstawowy, błąd.

Dla niepustego zbioru \(\displaystyle{ X}\) rozważają funkcję \(\displaystyle{ f:P\left( P(X)\right) \rightarrow P(P\left( X\right) )}\), taką, że dla dowolnej rodziny \(\displaystyle{ x\subset P(X),}\) rozważają funkcję daną jako:

\(\displaystyle{ f\left( x\right) = \left\{ \bigcap x\right\}}\),

która rodzinie podzbiorów zbioru \(\displaystyle{ X}\) przypisuje zbiór jednoelementowy złożony z przekroju tej rodziny.

Według mnie zbiorami stałymi mogą być tutaj tylko rodziny jednoelementowe. Bo jeśli \(\displaystyle{ A}\) jest rodziną stałą, to \(\displaystyle{ f\left( A\right)=A}\), ale wartość \(\displaystyle{ f\left( A\right)}\) z definicji jest zbiorem jednoelementowym złożonym z przekroju rodziny \(\displaystyle{ A}\), a więc zbiorami stałymi mogą być tu tylko rodziny jednoelementowe, żaden zbiór pusty, co napisali.


Jeśli \(\displaystyle{ X}\) jest niepustym zbiorem, to dla funkcji \(\displaystyle{ f:P\left( P\left( X\right) \right) \rightarrow P\left( P(X)\right) }\), takiej, że dla dowolnej rodziny \(\displaystyle{ x \subset P(X)}\) podzbiorów zbioru \(\displaystyle{ X}\), określamy:

\(\displaystyle{ f\left( x\right)= \left\{ \bigcup x\right\}}\) ,

czyli rozważamy tu funkcję, która rodzinie podzbiorów zbioru \(\displaystyle{ X}\) przypisuje zbiór jednoelementowy złożony z sumy tej rodziny.

Wtedy nie istnieje największy zbiór staly.

Aby to uzasadnić to:

Zauważmy najpierw, że z podobnych przyczyn jak powyżej zbiorami stałymi mogą być tu tylko rodziny jednoelementowe.
A jeśli mamy tutaj taką rodzinę postaci \(\displaystyle{ \left\{ A\right\}}\) , gdzie \(\displaystyle{ A \subset X}\), to:

\(\displaystyle{ f\left( \left\{ A\right\} \right)= \left\{ \bigcup \left\{ A\right\} \right\} = \left\{ A\right\} }\),

a więc rodzina \(\displaystyle{ \left\{ A\right\}}\) jest zbiorem stałym, i dla tej funkcji zbiorami stałymi są tutaj dokładnie rodziny jednoelementowe.

Skoro zbiór \(\displaystyle{ X}\) jest niepusty, to ma co najmniej dwa różne podzbiory (\(\displaystyle{ \emptyset}\) i \(\displaystyle{ X \neq \left\{ \right\}}\) ) nazwijmy je jako \(\displaystyle{ A}\) i \(\displaystyle{ B.}\)
Wtedy, na mocy powyższej obserwacji: rodziny \(\displaystyle{ \left\{ A\right\}}\) i \(\displaystyle{ \left\{ B\right\}}\) są zbiorami stałymi. Ponieważ \(\displaystyle{ A \neq B}\), więc również \(\displaystyle{ \left\{ A\right\} \neq \left\{ B\right\}}\) . A więc ta funkcja ma co najmniej dwa zbiory stałe. Gdyby istniał tutaj największy zbiór stały, to wtedy musiałby być nadzbiorem tych dwóch zbiorów stałych, a więc musiałby być co najmniej dwuelementowy (zbiory \(\displaystyle{ A}\) i \(\displaystyle{ B}\) musiałyby do niego należeć), a ponieważ zbiorami stałymi są tutaj dokładnie rodziny jednoelementowe, więc otrzymujemy sprzeczność. Wobec czego nie istnieje tutaj największy zbiór stały (mimo, że istnieje co najmniej dwa zbiory stałe). \(\displaystyle{ \square}\)

Czytając kiedyś uważnie ważniaka zwróciłem uwagę, że powiedzieli, że
istnienie najmniejszego i największego zbioru stałego nie musi być wcale oczywiste,
jednak w ogóle tego nie uzasadnili (mam tu na myśli najmniejszy zbiór stały).

Ale ja to uzasadniłem:

Rozważmy ten sam kontrprzykład co powyżej.

Wtedy zbiorami stałymi dla tej funkcji są dokładnie rodziny jednoelementowe, czyli zbiory postaci \(\displaystyle{ \left\{ A\right\}}\), gdzie \(\displaystyle{ A \subset X.}\)
Ponieważ zbiór \(\displaystyle{ X}\) jest niepusty, więc ma co najmniej dwa różne podzbiory (\(\displaystyle{ \emptyset}\) i \(\displaystyle{ X}\) ),oznaczmy je jako \(\displaystyle{ A}\) i \(\displaystyle{ B.}\)
Wtedy rodziny \(\displaystyle{ \left\{ A\right\}}\) i \(\displaystyle{ \left\{ B\right\}}\) są zbiorami stałymi (różnymi).
Gdyby istniał tutaj najmniejszy zbiór stały, to byłby postaci \(\displaystyle{ \left\{ C\right\}}\) , gdzie \(\displaystyle{ C \subset X}\). A ponieważ jest to najmniejszy zbiór stały, a zbiory \(\displaystyle{ \left\{ A\right\} }\), \(\displaystyle{ \left\{ B\right\}}\) są zbiorami stałymi, więc: \(\displaystyle{ \left\{ C\right\} \subset \left\{ A\right\}, \left\{ B\right\}}\), skąd: \(\displaystyle{ B=C=A}\), czyli \(\displaystyle{ A=B}\)- sprzeczność. Wobec czego nie istnieje tutaj najmniejszy zbiór stały( mimo, że istnieją, przynajmniej dwa, zbiory stałe).\(\displaystyle{ \square}\)


Jednak dla zbioru \(\displaystyle{ X}\), każda monotoniczna funkcja \(\displaystyle{ f:P(X) \rightarrow P(X)}\) posiada najmniejszy zbiór stały i posiada największy zbiór stały, co udowodniłem (w zasadzie fakt tylko dla największych zbiorów stałych) w pierwszym poście tego wątku.

Jako przykład funkcji monotonicznej rozważmy zbiór \(\displaystyle{ X}\) oraz dowolny ustalony podzbiór \(\displaystyle{ A \subset X}\).
Rozważmy funkcję \(\displaystyle{ f:P(X) \rightarrow P(X)}\), taką, że dla każdego zbioru \(\displaystyle{ B \subset X}\) określamy:

\(\displaystyle{ f(B)= A.}\)

Jest to funkcja stała, stale równa zbiorowi \(\displaystyle{ A.}\)

I jest monotoniczna, gdyż dla \(\displaystyle{ B_1 \subset B_2}\) mamy: \(\displaystyle{ f\left( B_1\right) = A \subset A= f(B_2),}\)

a więc ta funkcja jest monotoniczna.

Inny przykład:

Rozważmy funkcję:

\(\displaystyle{ f:P\left( P(\NN)\right) \rightarrow P\left( P\left( \NN\right) \right),}\)

taką, że dla dowolnej rodziny \(\displaystyle{ x \subset P(\NN)}\) podzbiorów zbioru liczb naturalnych definiujemy:
\(\displaystyle{ }\)
\(\displaystyle{ f\left( x\right) = \left\{ a \cup b\Bigl| \ a,b \in x\right\} \cup \left\{ \left\{ n\right\}\Bigl| \ n \in \NN \right\} = \left\{ a \cup b\Bigl| \ \left( a,b\right) \in x \times x \right\} \cup \left\{ \left\{ n\right\}\Bigl| \ \ n \in \NN \right\}. }\)

Czyli rodzina \(\displaystyle{ f(x)}\) jest to rodzina złożona z wszystkich sum dwóch zbiorów rodziny \(\displaystyle{ x}\) oraz z wszystkich jednoelementowych podzbiorów zbioru liczb naturalnych.

Pokażemy teraz, że ta funkcja jest monotoniczna.

Weźmy dowolne zbiory \(\displaystyle{ A,B \subset P(\NN)}\), takie, że: \(\displaystyle{ A \subset B}\). Pokażemy, że \(\displaystyle{ f(A) \subset f(B)}\) (nie chodzi tu o żadne obrazy zbiorów przez funkcję, bo są tu to wartości funkcji dla zbiorów \(\displaystyle{ A}\) i \(\displaystyle{ B}\), które oczywiście są tutaj zbiorami).

Niech \(\displaystyle{ x\in f(A).}\)
Z definicji zbioru \(\displaystyle{ f(A)}\) otrzymujemy, że zbiór \(\displaystyle{ x}\) jest postaci \(\displaystyle{ x=\left\{ n\right\}}\), dla pewnej liczby naturalnej \(\displaystyle{ n}\) lub \(\displaystyle{ x= a \cup b}\), dla pewnych zbiorów \(\displaystyle{ a,b \in A. }\)

W pierwszym przypadku, ponieważ z definicji funkcji \(\displaystyle{ f}\) mamy \(\displaystyle{ f(B)\supset\left\{ \left\{ n\right\}\Bigl| \ \ n \in \NN \right\}}\) , a zatem \(\displaystyle{ x=\left\{ n\right\} \in f(B)}\), co należało pokazać.

W drugim przypadku, ponieważ \(\displaystyle{ a,b \in A \subset B}\), więc \(\displaystyle{ a,b \in B}\) i z definicji zbioru \(\displaystyle{ f(B)}\) otrzymujemy: \(\displaystyle{ x=a \cup b \in f(B).}\)

A zatem \(\displaystyle{ f(A) \subset f(B)}\), i funkcja \(\displaystyle{ f}\) jest monotoniczna.

A zatem, na mocy twierdzenia Knastra- Tarskiego funkcja \(\displaystyle{ f}\) ma najmniejszy zbiór stały. Wykażemy, że jest nim rodzina wszystkich niepustych skończonych podzbiorów zbioru liczb naturalnych.

DOWÓD TEGO FAKTU:

Niech \(\displaystyle{ C}\) będzie rodziną wszystkich niepustych skończonych podzbiorów zbioru liczb naturalnych.

Wykażemy, że każdy zbiór stały tej funkcji jest nadzbiorem zbioru \(\displaystyle{ C.}\)

Niech \(\displaystyle{ S}\) będzie zbiorem stałym funkcji \(\displaystyle{ f}\). Wykażemy, że: \(\displaystyle{ S\supset C}\).

W tym celu rodzinę \(\displaystyle{ C}\) zbiorów skończonych dzielimy na podrodziny \(\displaystyle{ C_1, C_2,C_3,\ldots}\) złożone odpowiednio z podzbiorów jednoelementowych, podzbiorów dwuelementowych, trójelementowych,\(\displaystyle{ \ldots}\) i wykazujemy indukcyjnie, że \(\displaystyle{ S\supset C_n}\).

Jeśli \(\displaystyle{ n=1}\), to dla dowolnego zbioru \(\displaystyle{ A \subset P(\NN)}\) każdy zbiór jednoelementowy \(\displaystyle{ \left\{ m\right\}}\), gdzie \(\displaystyle{ m \in \NN}\) należy do rodziny \(\displaystyle{ f\left( A\right)}\) (z definicji funkcji \(\displaystyle{ f}\) ). Ponieważ \(\displaystyle{ S}\) jest zbiorem stałym, tak więc \(\displaystyle{ f(S)=S}\), a zatem \(\displaystyle{ \left\{ m\right\} \in S}\), co daje \(\displaystyle{ S\supset C_1}\).

Krok indukcyjny:
Dla \(\displaystyle{ n \ge 1}\), jeśli \(\displaystyle{ S\supset C_n}\), to \(\displaystyle{ S\supset C _{n+1}.}\)

Aby wykazać, że \(\displaystyle{ C _{n+1} \subset S}\), to niech: \(\displaystyle{ A \in C _{n+1}.}\) Wtedy zbiór \(\displaystyle{ A}\) ma dokładnie \(\displaystyle{ \left( n+1\right)}\) elementów. Niech \(\displaystyle{ a \in A \neq \left\{ \right\}}\). Wtedy zbiór \(\displaystyle{ A \setminus \left\{ a\right\}}\) ma \(\displaystyle{ n}\) (\(\displaystyle{ n>0}\)) elementów, a zatem \(\displaystyle{ A \setminus \left\{ a\right\} \in C_n}\). Z załozenia indukcyjnego otrzymujemy
\(\displaystyle{ A \setminus \left\{ a\right\} \in S}\). Z bazy indukcji otrzymujemy: \(\displaystyle{ \left\{ a\right\} \in S}\). Ponieważ również \(\displaystyle{ A \setminus \left\{ a\right\} \in S}\), więc z definicji tej funkcji \(\displaystyle{ A\stackrel{a \in A}{=}\left( A \setminus \left\{ a\right\}\right) \cup \left\{ a\right\} \in f\left( S\right)}\) . Skoro jednak zbiór \(\displaystyle{ S}\) jest zbiorem stałym, tak więc \(\displaystyle{ f\left( S\right) =S}\), a zatem, z zasady równości zbiorów: \(\displaystyle{ A \in S}\), i \(\displaystyle{ S\supset C _{n+1}}\), co dowodzi kroku indukcyjnego.

Na mocy zasady indukcji dla liczb naturalnych (ale autorzy ważniaka powinni zwrócić tu uwagę, że ta konstrukcja wyprzedza u nich rozdział o liczbach naturalnych, a obeszli to bez słowa :?: ), dla każdego \(\displaystyle{ n \ge 1}\), mamy: \(\displaystyle{ S\supset C_n}\).

Skoro dla każdego \(\displaystyle{ n \ge 1}\): \(\displaystyle{ C_n \subset S}\), więc również: \(\displaystyle{ C=\bigcup_{n \in \NN_+} C_n \subset S}\), czyli
\(\displaystyle{ S\supset C}\), i każdy zbiór stały funkcji \(\displaystyle{ f}\) jest nadzbiorem zbioru \(\displaystyle{ C.}\)

Wykażemy teraz, że zbiór \(\displaystyle{ C}\) jest zbiorem stałym funkcji \(\displaystyle{ f}\).

Zauważmy najpierw, że \(\displaystyle{ f(C)\supset C}\), bo dla każdego \(\displaystyle{ x \in C}\) możemy dobrać zbiór \(\displaystyle{ x \cup x=x}\), i wtedy, zgodnie z definicją funkcji \(\displaystyle{ f}\), otrzymamy: \(\displaystyle{ x=x \cup x \in f(C)}\), co dowodzi tej inkluzji.

Aby pokazać inkluzję w drugą stronę, to niech \(\displaystyle{ y \in f(C)}\).
Wtedy, z definicji funkcji \(\displaystyle{ f}\) zbiór \(\displaystyle{ y}\) jest postaci \(\displaystyle{ y=\left\{ n\right\}}\), gdzie \(\displaystyle{ n \in \NN}\) lub \(\displaystyle{ y=a \cup b}\), gdzie \(\displaystyle{ a,b \in C}\).

W pierwszym przypadku zbiór \(\displaystyle{ y}\) jest jednoelementowym (a więc skończonym) podzbiorem zbioru liczb naturalnych, a zatem: \(\displaystyle{ y \in C. }\)

W drugim przypadku zbiory \(\displaystyle{ a,b \in C}\) są niepustymi skończonymi podzbiorami zbioru liczb naturalnych, a więc ich suma też jest niepustym skończonym podzbiorem zbioru liczb naturalnych, a stąd \(\displaystyle{ y=a \cup b \in C.}\)

A zatem \(\displaystyle{ f(C)=C}\), a zatem zbiór \(\displaystyle{ C}\) jest zbiorem stałym funkcji \(\displaystyle{ f.}\)

Ponadto każdy zbiór stały funkcji \(\displaystyle{ f}\) jest nadzbiorem zbioru \(\displaystyle{ C,}\) i \(\displaystyle{ C}\) jest zbiorem stałym funkcji \(\displaystyle{ f}\), a zatem zbiór \(\displaystyle{ C}\) jest najmniejszym zbiorem stałym funkcji \(\displaystyle{ f.\square}\) 8-)


Podamy jeszcze kilka przykładów zbiorów stałych dla funkcji określonej w poniższy sposób:

Jeśli \(\displaystyle{ X}\) jest zbiorem, to rozważmy funkcję \(\displaystyle{ f:P\left( P\left( X\right) \right) \rightarrow P\left( P(X)\right)}\), która rodzinie \(\displaystyle{ x \subset P(X)}\) podzbiorów zbioru \(\displaystyle{ X}\) przypisuje zbiór dwuelementowy dany jako:

\(\displaystyle{ f(x)= \left\{ \bigcup x, \bigcap x\right\};}\)

funkcja \(\displaystyle{ f}\) rodzinie \(\displaystyle{ x}\) podzbiorów zbioru \(\displaystyle{ X}\) przypisuje zbiór dwuelementowy złożony z sumy tej rodziny i z przekroju tej rodziny.

Podamy kilka przykładów zbiorów stałych dla tej funkcji.

Dla dowolnego zbioru \(\displaystyle{ A \subset X}\), mamy:

\(\displaystyle{ f\left( \left\{ A\right\} \right) = \left\{ \bigcup \left\{ A\right\}, \bigcap \left\{ A\right\} \right\} =\left\{ A,A\right\} = \left\{ A\right\},}\)

a więc zbiór \(\displaystyle{ \left\{ A\right\}}\) jest zbiorem stałym.

Dla dowolnego zbioru \(\displaystyle{ A \subset X}\), mamy:

\(\displaystyle{ f\left( \left\{ A, \emptyset\right\} \right) = \left\{ \bigcup \left\{ A, \emptyset\right\}; \bigcap \left\{ A, \emptyset\right\} \right\}= \left\{ A \cup \emptyset, A \cap \emptyset\right\} = \left\{ A,\emptyset \right\} }\),

a więc zbiór \(\displaystyle{ \left\{ A, \emptyset\right\}}\) jest zbiorem stałym.

Dla dowolnych zbiorów \(\displaystyle{ A,B \subset X}\), takich, że \(\displaystyle{ A \subset B}\) mamy:

\(\displaystyle{ f\left( \left\{ A,B\right\} \right) = \left\{ A \cup B, A \cap B\right\} = \left\{ B, A\right\} = \left\{ A,B\right\}. }\)


Na koniec dodam taki fakt, trochę z innej beczki, bo mam na tej samej kartce narysowaną sytuację mówiącą, że przekrój łańcucha porządków ciągłych nie musi być gęsty.

W tym celu rozważmy odcinek trój-jednostkowy \(\displaystyle{ \left[ 0,3\right].}\)
I rozważmy ciąg porządków ciągłych na podzbiorach zbioru \(\displaystyle{ \left[ 0,3\right].}\)

\(\displaystyle{ \left( X_0= \left[0,3 \right] , \le _0:= \le _{|X_0}\right) ,}\) i
\(\displaystyle{ \left( X_n= \left[ 0,1+ \frac{1}{n+1} \right) \cup \left[ 2,3\right], \le _n:= \le _{|X_n}\right) , \hbox{ dla } n>0.}\)

Wtedy jest to łańcuch porządków ciągłych, i \(\displaystyle{ \bigcap_{n \in \NN} \le _{n}= \left[ 0,1\right] \cup \left[ 2,3\right]}\) nie jest zbiorem liniowo uporządkowanym gęstym, gdyż pomiędzy \(\displaystyle{ 1}\) a \(\displaystyle{ 2}\) nie ma tutaj elementu pośredniego, a więc nie jest to porządek gęsty.

Wynika stąd, że przekrój łańcucha porządków gęstych nie musi być gęsty i przekrój łańcucha porządków ciągłych nie musi być porządkiem ciągłym, gdyż:
Ten przykład świadczy o tym, że przekrój łańcucha porządków ciągłych, a więc i gęstych nie musi być gęsty; i
przekrój łańcucha ciągłych nie musi być ciągły, bo może nie być gęsty; a wtedy nie jest ciągły, bo gdyby był ciągły, to byłby i gęsty, a nie jest gęsty. A zatem przekrój łańcucha porządków ciągłych nie musi być porządkiem ciągłym. 8-)

Dasio11 tego nie zna. 8-)
Awatar użytkownika
Dasio11
Moderator
Moderator
Posty: 10211
Rejestracja: 21 kwie 2009, o 19:04
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 40 razy
Pomógł: 2359 razy

Re: Twierdzenie Knastra-Tarskiego

Post autor: Dasio11 »

ODPOWIEDZ