Twierdzenie Knastra-Tarskiego
: 15 sie 2016, o 02:10
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
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