Lemat Banacha

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:

1. \( \{A_1,A_2\} \) jest podziałem zbioru \( X \),
2. \( \{B_1,B_2\} \) jest podziałem zbioru \( Y \),
3. \( \vec{f}(A_1)= B_1 \),
4. \( \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). \)