Lemat Banacha

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:

$\{A_1,A_2\}$ jest podziałem zbioru

$X$ ,

$\{B_1,B_2\}$ jest podziałem zbioru

$Y$ ,

$\vec{f}(A_1)= B_1$ ,

$\vec{g}(B_2)= A_2$ .

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).$