Twierdzenie Knastra-Tarskiego posłuży nam do udowodnienia lematu
Banacha, który z kolei wykorzystamy w wykładzie "Teoria mocy twierdzenie Cantora-Bernsteina, twierdzenie Cantora. Zbiory przeliczalne, zbiory mocy kontinuum" dotyczącym teorii mocy.
Twierdzenie 7.8.
Dla dowolnych zbiorów \( X,Y \) oraz funkcji \( f:X \rightarrow Y \) i \( g:Y \rightarrow X \) istnieją zbiory \( A_1,A_2 \subset X \) oraz \( B_1,B_2 \subset Y \) takie, że:
Dowód
Rozważmy funkcję \( F:\mathcal{P}(X) \rightarrow \mathcal{P}(X) \) zdefiniowaną następująco. Dla dowolnego \( A\subset X \) niech
\( F(A)= X\setminus \vec{g}(Y\setminus \vec{f}(A)). \)
Pokażemy najpierw, że \( F \) jest monotoniczna. Weźmy dowolne zbiory \( C_1,C_2 \subset X \) takie, że \( C_1 \subset C_2 \). Wtedy
\( \vec{f}(C_1) \subset \vec{f}(C_2), \)
więc
\( Y \setminus \vec{f}(C_1) \supset Y\setminus \vec{f}(C_2) \)
\( \vec{g}( Y \setminus \vec{f}(C_1)) \supset \vec{g}(Y\setminus \vec{f}(C_2)) \)
\( X \setminus \vec{g}( Y \setminus \vec{f}(C_1)) \subset X \setminus \vec{g}(Y\setminus \vec{f}(C_2)), \)
a więc \( F(C_1) \subset F(C_2) \).
Skoro \( F \) jest monotoniczna, to na mocy twierdzenia 7.6 Knastra-Tarskiego posiada najmniejszy punkt stały. Oznaczmy go przez \( A_1 \). Zdefiniujemy teraz pozostałe zbiory z tezy twierdzenia. Niech:
\( A_2\stackrel{\textrm{def}}{\equiv} X \setminus A_1, \)
\( B_1 \stackrel{\textrm{def}}{\equiv} \vec{f}(A_1), \)
\( B_2 \stackrel{\textrm{def}}{\equiv} Y \setminus B_1. \)
Z definicji zbiorów \( A_1,A_2,B_1,B_2 \) natychmiast wynika, że zbiory \( \{A_1,A_2\} \) oraz \( \{B_1,B_2\} \) tworzą odpowiednio podziały zbiorów \( X \) i \( Y \). Również z definicji spełniony jest punkt trzeci tezy (czyli \( B_1 \stackrel{\textrm{def}}{\equiv} \vec{f}(A_1) \)). Pozostaje pokazać, że zachodzi punkt czwarty. Skoro \( A_1 \) jest punktem stałym funkcji \( F \), to
\( A_1= X\setminus \vec{g}(Y\setminus \vec{f}(A_1)). \)
Podstawiając kolejno w powyższym wzorze zdefiniowane zbiory, otrzymujemy:
\( A_1= X\setminus \vec{g}(Y\setminus B_1), \)
\( A_1= X\setminus \vec{g}( B_2). \)
Odejmując obie strony od \( X \), otrzymamy:
\( X \setminus A_1 = \vec{g}( B_2). \)
Ponieważ jednak lewa strona w powyższej równości jest z definicji równa \( A_2 \), to otrzymujemy: \( A_2 = \vec{g}( B_2). \)