Twierdzenie Knastra-Tarskiego

W tym rozdziale przedstawimy podstawową wersję twierdzenia

Knastra-Tarskiego o punktach stałych funkcji monotonicznych oraz kilka przykładów zastosowań.

Definicja 7.1.

Funkcję \( f:\mathcal{P}(X) \rightarrow \mathcal{P}(X) \) nazwiemy monotoniczną ze względu na inkluzję, jeśli

\( \forall_{x\subset X} \forall_{y \subset X} (x\subset y \Rightarrow f(x) \subset f(y)). \)

Funkcje monotoniczne ze względu na inkluzję zachowują relację inkluzji pomiędzy przekształcanymi zbiorami. Nie oznacza to jednak wcale, że argument funkcji musi byc podzbiorem wartości funkcji na tym argumencie.

Ćwiczenie 7.1

Podaj przykład funkcji monotonicznej \( f:\mathcal{P}(X) \rightarrow \mathcal{P}(X) \), dla której nieprawdą jest, że dla każdego zbioru \( A\subset X \), zachodzi \( f(A) \supset A \).

Rozwiązanie

Dla dowolnego niepustego zbioru \( X \) funkcja stale równa \( \emptyset \) spełnia żądane założenia. Jest monotoniczna, gdyż prawa strona implikacji w definicji monotoniczności jest zawsze spełniona
(\( \emptyset \subset \emptyset \)). Dla zbioru \( X \) mamy \( f(X) =\emptyset \), a więc nieprawdą jest, że \( f(X) \supset X \).

Definicja 7.2.

Element \( x \in X \) jest punktem stałym funkcji \( f:X \rightarrow X \), jeśli

\( f(x)=x. \)

Ćwiczenie 7.2

Podaj przykłady punktów stałych następujących funkcji:

1. \( f: R \rightarrow R \) jest określona wzorem \( f(x)= \frac{x}{2} \),

2. \( f:\mathcal{P}(\mathcal{P}(X)) \rightarrow \mathcal{P}(\mathcal{P}(X)) \) jest określona wzorem \( f(x) = \{\bigcup x,\bigcap x \} \),

3. \( f:\mathcal{P}(X^2)\rightarrow \mathcal{P}(X^2) \) jest określona wzorem \( f(r) =r^{-1} \).

Rozwiązanie 1

0 jest jedynym punktem stałym funkcji \( f \), \( 0 = \frac{0}{2} \).

Rozwiązanie 2

Kilka przykładów punktów stałych

(a) dla dowolnego \( x\in X \) mamy \( f(\{x\})=\{\bigcup \{x\}, \bigcap \{x\}\}= \{x,x\}=\{x\} \),

(b) dla dowolnego \( A\subset X \) mamy \( f(\{A,\emptyset\})=\{(A\cup \emptyset), (A\cap\emptyset)\}=\{A,\emptyset\} \),

Rozwiązanie 3

\( r\subset X^2 \) jest punktem stałym funkcji \( f \) wtedy i tylko wtedy, gdy \( r=r^{-1} \). Wynika stąd, że punktami stałymi są relacje symetryczne będące podzbiorami \( X^2 \). Jedną z takich relacji jest \( \mathbb{I}_{X} \).

Zwróćmy uwagę, że istnieją funkcje, które nie mają punktów stałych. Prostym przykładem może być funkcja \( \{(0,1),(1,0)\} \).

Ćwiczenie 7.3

Niech \( X \) będzie niepustym zbiorem. Udowodnij, że dla funkcji \( f:\mathcal{P}(X) \rightarrow\mathcal{P}(X) \) zdefiniowanej wzorem \( f(A)= X \setminus A \) nie istnieje punkt stały.

Rozwiązanie

Dla dowodu niewprost przypuścmy, że istnieje punkt stały \( F \) dla funkcji \( f \). Oznacza to, że \( f(F)=F \). Z definicji \( f \) wynika, że \( f(F)=X \setminus F \), a więc mamy

\( F=X\setminus F, \)

co prowadzi do sprzeczności, gdyż zbiór \( X \) jest niepusty.

Definicja 7.3.

Punkt \( x_0 \subset X \) jest najmniejszym punktem stałym funkcji \( f:\mathcal{P}(X) \rightarrow
\mathcal{P}(X) \), jeśli \( f(x_0)=x_0 \) oraz

\( \forall_{x_1\subset X} f(x_1)= x_1 \Rightarrow x_0 \subset x_1. \)

Czyli wtedy, kiedy każdy inny punkt stały jest jego nadzbiorem.

Definicja 7.4.

Punkt \( x_0 \subset X \) jest największym punktem stałym funkcji \( f:\mathcal{P}(X) \rightarrow
\mathcal{P}(X) \), jeśli \( f(x_0)=x_0 \) oraz

\( \forall_{x_1\subset X} f(x_1)= x_1 \Rightarrow x_0 \supset x_1. \)

Czyli wtedy, kiedy każdy inny punkt stały jest jego podzbiorem.

Poniższy przykład ilustruje, że istnienie najmniejszego i największego punktu stałego wcale nie jest oczywiste.

Przykład 7.5.

Dla funkcji \( f:\mathcal{P}(\mathcal{P}(X)) \rightarrow \mathcal{P}(\mathcal{P}(X)) \) określonej wzorem \( f(A) = \{\bigcap A\} \) punktami stałymi są \( \emptyset \) oraz singletony zawierające podzbiory zbioru \( X \) (czyli zbiory postaci \( \{A\} \) dla \( A\subset X \)). Jeśli \( X \) jest niepusty, to istnieją przynajmniej dwa różne punkty stałe będące singletonami. Nie istnieje wtedy punkt stały będący ich nadzbiorem, gdyż musiałby zawierać przynajmniej dwa elementy. Wobec tego nie istnieje największy punkt stały funkcji \( f \).

Każda monotoniczna funkcja \( f:\mathcal{P}(X) \rightarrow \mathcal{P}(X) \) posiada najmniejszy i największy punkt stały.

Dowód

Niech \( L=\{x \subset X: f(x) \supset x\} \). Pokażemy, że \( \bigcup L \) jest największym punktem stałym funkcji \( f \). Zauważmy, że dla każdego \( x\in L \) z monotoniczności \( f \) otrzymujemy

\( f(\bigcup L) \supset f(x) \supset x. \)

Wobec tego również

\( f(\bigcup L) \supset \bigcup L, \quad \mbox{(7.1)} \)

skąd otrzymujemy, że \( \bigcup L \in L \). Przekształcając obie strony poprzedniego równania przez \( f \) dzięki monotoniczności tej funkcji, otrzymamy

\( f(f(\bigcup L)) \supset f(\bigcup L). \)

Wobec czego również \( f(\bigcup L) \in L \). Ponieważ każdy element \( L \) jest podzbiorem \( \bigcup L \), to również \( f(\bigcup L) \subset \bigcup L \). Stąd i z równania 7.1 otrzymujemy

\( f(\bigcup L) = \bigcup L, \)

a więc \( \bigcup L \) jest punktem stałym funkcji \( f \). Co więcej, wszystkie punkty stałe należą do zbioru \( L \), wobec czego każdy z nich jest podzbiorem \( \bigcup L \), co oznacza dokładnie, że \( \bigcup L \) jest największym punktem stałym.

Analogicznie wykażemy istnienie najmniejszego punktu stałego. Niech \( U=\{x \subset X: f(x) \subset x\} \). Pokażemy, że \( \bigcap U \) jest najmniejszym punktem stałym. Z monotoniczności \( f \) mamy dla każdego \( x\in U \)

\( f(\bigcap U) \subset f(x) \subset x, \)

skąd otrzymujemy

\( f(\bigcap U) \subset \bigcap U, \quad \mbox{(7.2)} \) wobec czego \( \bigcap U \in U \). Przekształcając obie strony ostatniego równania przez \( f \), dzięki monotoniczności tej fukcji, otrzymamy

\( f(f(\bigcap U)) \subset f(\bigcap U), \)

skąd wynika, że \( f(\bigcap U) \in U \). Ponieważ \( \bigcap U \) jest podzbiorem każdego elementu \( U \), więc również \( \bigcap U \subset f(\bigcap U) \). Stąd i z równania 7.2 otrzymujemy \( f(\bigcap U) = \bigcap U \). Oznacza to, że \( \bigcap U \) jest punktem stałym funkcji \( f \). Ponieważ wszystkie punkty stałe należą do zbioru \( U \), to \( \bigcap U \) jest najmniejszym punktem stałym.

Przykład 7.7.

Niech \( X \) będzie zbiorem induktywnym (czyli takim, którego istnienie jest gwarantowane przez aksjomat nieskończoności). Zdefiniujmy funkcję \( f:\mathcal{P}(X) \rightarrow \mathcal{P}(X) \) w następujący sposób. Dla dowolnego \( A\subset X \) niech

\( f(A) \stackrel{\textrm{def}}{\equiv} A\cup \{x \cup \{x\}: x\in A\} \cup \{\emptyset\}. \)

Zwróćmy uwagę, że \( f(A)\subset X \) dzięki temu, że zbiór \( X \) jest induktywny. Z definicji łatwo wynika, że funkcja \( f \) jest monotoniczna. Wobec tego z twierdzenia 7.6 wynika, że ma najmniejszy i największy punkt stały. Zauważmy, że z definicji funkcji \( f \) wynika, że każdy punkt stały tej funkcji jest zbiorem induktywnym. Największy punkt stały łatwo wskazać, gdyż jest to cały zbiór \( X \). Znacznie ciekawszy jest najmniejszy punkt stały, nazwijmy go \( \omega \). Jest to najmniejszy zbiór induktywny będący podzbiorem \( X \). W wykładzie "Konstrukcja von Neumanna liczb naturalnych, twierdzenie o indukcji, zasady minimum, maksimum, definiowanie przez indukcje" dotyczącym liczb naturalnych pokażemy, że zbiór \( \omega \) jest również podzbiorem każdego innego zbioru induktywnego (dociekliwi mogą spróbować udowodnić to już teraz).

Ćwiczenie 7.4

Niech \( X \) będzie ustalonym zbiorem i \( R\subset X^2 \) będzie dowolną relacją. Zdefiniujmy funkcję \( f:\mathcal{P}(X^2) \rightarrow X^2 \) następująco: \( f(S)= (S \circ S) \cup R \). Udowodnij, że funkcja \( f \) jest monotoniczna. Co jest najmniejszym, a co największym punktem stałym funkcji \( f \)?

Rozwiązanie

Monotoniczność wynika z podstawowych własności złożenia relacji. Weźmy dowolne zbiory \( A\subset B\subset X^2 \). Wtedy

\( f(B)= (B \circ B) \cup R \supset (A\circ A) \cup R = f(A). \) Łatwo sprawdzić, że największy punkt stały to \( X^2 \).

Z definicji funkcji wynika, że każdy punkt stały jest nadzbiorem \( R \). Przypuśćmy, że \( S \) jest punktem stałym, wtedy \( S= S\circ S \cup R \), a więc \( S \supset S \circ S \). Wynika stąd, że \( S \) musi być relacją przechodnią. Podsumowując, każdy punkt stały funkcji \( f \) jest relacją przechodnią będącą nadzbiorem \( R \). Niech \( \bar{R} \) będzie przechodnim domknięciem relacji \( R \). Wiemy, że jest to najmniejsza relacja przechodnia będąca nadzbiorem \( R \). Jest więc mniejsza od wszystkich punktów stałych funkcji \( f \). Pokażemy, że jest ona punktem stałym. Wiemy, że

\( f(\bar{R})= (\bar{R} \circ \bar{R}) \cup R \subset \bar{R}. \)

W dowodzie twierdzenia 7.6 Knastra-Tarskiego pokazujemy, że najmniejszy punkt stały jest równy \( \bigcap U \), gdzie \( U=\{x: f(x) \subset x\} \). W rozważanym przypadku pokazaliśmy, że relacja \( \bar{R} \in U \) oraz że wszystkie punkty stałe są od niej większe. Wynika stąd, że \( \bar{R} \) jest najmniejszym punktem stałym funkcji \( f \).

Ćwiczenie 7.5

Niech \( f:\mathcal{P}(\mathcal{P}(N)) \rightarrow \mathcal{P}(\mathcal{P}(N)) \) będzie zdefiniowana tak, że dla każdego \( A\subset N \)

\( f(A)= \{x \cup y: x,y\in A\} \cup \{\{n\}: n\in N\}. \)

Czyli funkcja \( f \) przekształca rodziny zbiorów liczb w rodziny zbiorów liczb. Udowodnij, że funkcja \( f \) jest monotoniczna. Co jest najmniejszym punktem stałym funkcji \( f \)? Czy \( \emptyset \) jest elementem tego punktu stałego?

Rozwiązanie

Najpierw pokażemy monotoniczność. Weźmy dowolne zbiory \( A\subset B\subset \mathcal{P}(N) \). Weźmy dowolny zbiór \( x\in f(A) \). Z definicji funkcji \( f \) wynika, że \( x \) jest postaci \( \{n\} \) dla pewnej liczby \( n\in N \) lub \( x \) jest postaci \( a\cup b \) dla pewnych \( a,b \in A \). W pierwszym przypadku \( x\in f(B) \) dlatego, że z definicji \( f(B) \supset \{\{n\}: n\in N\} \). W drugim przypadku \( x\in f(B) \) dlatego, że \( B\supset A \), a więc \( a,b \in B \) i z definicji \( f(B) \) otrzymujemy \( a\cup b \in f(B) \).

Pokażemy teraz, że każdy punkt stały funkcji \( f \) zawiera wszystkie niepuste skończone podzbiory \( N \). Dowód przeprowadzimy przez indukcję ze względu na liczbę elementów zbioru. Niech \( S \) będzie punktem stałym funkcji \( f \).

1. Baza indukcji. Z definicji funkcji \( f \) wynika, że dla dowolnego zbioru \( A\subset \mathcal{P}(N) \) rodzina \( f(A) \) zawiera wszystkie zbiory jednoelementowe. Skoro \( S \) jest punktem stałym, to \( S= f(S) \), a więc musi zawierać wszystkie zbiory jednoelementowe.

2. Krok indukcji. Dla dowolnego \( n\in N \) takiego, że \( n\geq 1 \) pokażemy, że jeśli \( S \) zawiera wszystkie \( n \)-elementowe podzbiory \( N \), to zawiera również wszystkie \( n+1 \)-elementowe podzbiory \( N \). Weźmy dowolne \( n\in N \) takie, że \( n\geq 1 \) i załóżmy, że \( S \) zawiera wszystkie \( n \)-elementowe podzbiory \( N \). Pokażemy, że \( S \) zawiera wszystkie \( n+1 \)-elementowe podzbiory \( N \). Weźmy dowolny \( n+1 \)-elementowy podzbiór \( N \) i nazwijmy go \( A \). Niech \( a\in A \) (zbiór \( A \) jest niepusty). Wtedy z założenia indukcyjnego \( A\setminus \{a\} \in S \). Z bazy indukcji otrzymujemy, że \( \{a\} \in S \). Z definicji funkcji \( f \) wynika, że \( (A\setminus \{a\}) \cup \{a\} \in f(S) \), czyli \( A\in f(S) \). Skoro jednak \( S \) jest punktem stałym (czyli \( f(S)=S \)), to \( A\in S \). Wobec dowolności wyboru \( A \) krok indukcyjny jest udowodniony.

Wystarczy teraz pokazać, że zbiór niepustych skończonych podzbiorów \( N \) jest punktem stałym funkcji \( f \). Niech \( F \) będzie tym zbiorem. Zauważmy, że \( f(F) \supset F \), ponieważ dla każdego \( x\in F \) możemy dobrać element \( x\cup x \in f(F) \). Wystarczy więc pokazać, że wszystkie zbiory z \( f(F) \) są skończone. Weźmy dowolny \( y\in f(F) \). Zgodnie z definicją funkcji \( f \) zbiór \( y \) jest postaci \( \{n\} \) dla pewnego \( n\in N \) lub postaci \( a \cup b \) dla pewnych \( a,b\in F \). W pierwszym przypadku \( y \) jest jednoelementowy, a więc skończony. W drugim przypadku jest sumą dwóch zbiorów skończonych, a więc również jest skończony. Pokazaliśmy więc, że \( f(F)=F \).

\( F \) jest punktem stałym i każdy punkt stały funkcji \( f \) jest nadzbiorem \( F \), więc \( F \) jest najmniejszym punktem stałym.

Zauważmy na koniec, że \( \emptyset \notin F \). Łatwo pokazać, że \( F\cup\{\emptyset\} \) jest również punktem stałym funkcji \( f \).