Lemat Banacha
: 6 paź 2019, o 03:59
Twierdzenie Knastra-Tarskiego mówi, że każda monotoniczna funkcja \(\displaystyle{ f:P(X) \rightarrow P(X) }\) ma punkt stały. Wykorzystamy to, aby udowodnić lemat Banacha.
Lemat Banacha Dla dowolnych zbiorów \(\displaystyle{ X,Y}\) oraz dowolnych funkcji \(\displaystyle{ f:X \rightarrow Y, g:Y \rightarrow X}\) istnieją rozłączne zbiory \(\displaystyle{ A_1,A_2 \subset X}\) wzajemnie uzupełniające się do \(\displaystyle{ X}\)( tzn. takie, że \(\displaystyle{ A_1 \cup A_2=X}\)) jak i istnieją rozłączne zbiory \(\displaystyle{ B_1,B_2\subset Y}\) wzajemnie uzupełniające się do \(\displaystyle{ Y}\), takie, że \(\displaystyle{ \stackrel{\rightarrow }{ f} (A_1)=B_1 }\) i \(\displaystyle{ \stackrel{\rightarrow }{ g} (B_2)=A_2. }\)
Oto ilustracja:
Jednak to twierdzenie nie jest oczywiste- mając zbiór \(\displaystyle{ A_1\subset X}\) zawsze możemy wziąć jego obraz, potem możemy wziąć jego dopełnienie do zbioru \(\displaystyle{ Y}\), następnie obraz otrzymanego zbioru przez \(\displaystyle{ g}\), a na koniec taki zbiór dopełnić do \(\displaystyle{ X}\). Tylko dowcip polega na tym, że mamy otrzymać dokładnie ten sam zbiór \(\displaystyle{ A_1}\)- nie jest to oczywiste, zwłaszcza, że \(\displaystyle{ f,g}\) są dowolnymi funkcjami (w odwrotnych kierunkach). Ale dzięki twierdzeniu o punkcie stałym możemy to udowodnić.
Dowod: Niech \(\displaystyle{ f:X \rightarrow Y, g:Y \rightarrow X.}\) Rozważmy funkcję \(\displaystyle{ H:P(X) \rightarrow P(X)}\) określoną w poniższy sposób: dla dowolnego zbioru \(\displaystyle{ A\subset X }\)
\(\displaystyle{ H(A)=X\setminus\stackrel{\rightarrow }{g} (Y\setminus\stackrel{\rightarrow }{f}(A) ).}\)
Czyli z dowolnym zbiorem \(\displaystyle{ A\subset X}\) postępujemy jak wyżej, potem znajdziemy specjalny zbiór, a potem pozostałe zbiory aby udowodnić tezę twierdzenia. Pokażemy najpierw, że \(\displaystyle{ H}\) jest monotoniczna. Weźmy dowolne zbiory \(\displaystyle{ A_1,A_2\subset X}\), takie, że \(\displaystyle{ A_1\subset A_2}\). Wtedy
\(\displaystyle{ \stackrel{\rightarrow }{f}(A_1) \subset \stackrel{\rightarrow }{f}(A_2) }\), więc
\(\displaystyle{ Y\setminus\stackrel{\rightarrow }{f}(A_1)\supset Y\setminus\stackrel{\rightarrow }{f}(A_2)}\), następnie
\(\displaystyle{ \stackrel{\rightarrow }{g} (Y\setminus\stackrel{\rightarrow }{f}(A_1) ) \supset \stackrel{\rightarrow }{g} (Y\setminus\stackrel{\rightarrow }{f}(A_2) )}\) i dalej
\(\displaystyle{ H(A_{1} )=X\setminus\stackrel{\rightarrow }{g} (Y\setminus\stackrel{\rightarrow }{f}(A _{1} ) ) \subset X\setminus\stackrel{\rightarrow }{g} (Y\setminus\stackrel{\rightarrow }{f}(A _{2} ) )= H(A_{2} )}\)
a więc \(\displaystyle{ H(A_{1} ) \subset H(A_{2} )}\), i \(\displaystyle{ H}\) jest monotoniczna.
Skoro \(\displaystyle{ H}\) jest monotoniczna, to na podstawie twierdzenia Knastra-Tarskiego ma najmniejszy punkt stały, nazwijmy go \(\displaystyle{ A_1}\).
Zdefiniujmy teraz pozostałe poszukiwane zbiory.
\(\displaystyle{ A_2\stackrel {def} {\equiv} X \setminus A _{1},}\)
\(\displaystyle{ B_1\stackrel {def} {\equiv} \stackrel{\rightarrow }{f}(A _{1} ),}\)
\(\displaystyle{ B_2\stackrel {def} {\equiv} Y \setminus B _{1}.}\)
Z definicji tych zbiorów wynika, że zbiory \(\displaystyle{ A_1,A_2}\) są rozłączne i sumują się do \(\displaystyle{ X}\) podobnie zbiory \(\displaystyle{ B_1,B_2}\), a także \(\displaystyle{ \stackrel{\rightarrow }{ f} (A_1)=B_1. }\) Pozostaje pokazać, że \(\displaystyle{ \stackrel{\rightarrow }{ g} (B_2)=A_2. }\) Skoro \(\displaystyle{ A_1}\) jest punktem stałym funkcji \(\displaystyle{ H}\), to \(\displaystyle{ H(A_1)=A_1=X\setminus\stackrel{\rightarrow }{g} (Y\setminus\stackrel{\rightarrow }{f}(A_1) )}\). Ponieważ \(\displaystyle{ \stackrel{\rightarrow }{f}(A _{1} )=B_1,
}\) więc \(\displaystyle{ A_1=X\setminus\stackrel{\rightarrow }{g} (Y\setminus B_1 )}\). Ponieważ \(\displaystyle{ Y \setminus B _{1}=B_2}\), więc \(\displaystyle{ A_1=X\setminus\stackrel{\rightarrow }{g} (B_2 )}\). Zatem \(\displaystyle{ X \setminus A_1=X \setminus \left( X\setminus\stackrel{\rightarrow }{g} (B_2 )\right) =\stackrel{\rightarrow }{ g} (B_2)}\), ponieważ jednak lewa strona tej równości z definicji jest równa zbiorowi \(\displaystyle{ A_2}\), więc \(\displaystyle{ A_2=\stackrel{\rightarrow }{ g} (B_2).}\) Dowód jest zakończony. \(\displaystyle{ \square}\)
Lemat Banacha Dla dowolnych zbiorów \(\displaystyle{ X,Y}\) oraz dowolnych funkcji \(\displaystyle{ f:X \rightarrow Y, g:Y \rightarrow X}\) istnieją rozłączne zbiory \(\displaystyle{ A_1,A_2 \subset X}\) wzajemnie uzupełniające się do \(\displaystyle{ X}\)( tzn. takie, że \(\displaystyle{ A_1 \cup A_2=X}\)) jak i istnieją rozłączne zbiory \(\displaystyle{ B_1,B_2\subset Y}\) wzajemnie uzupełniające się do \(\displaystyle{ Y}\), takie, że \(\displaystyle{ \stackrel{\rightarrow }{ f} (A_1)=B_1 }\) i \(\displaystyle{ \stackrel{\rightarrow }{ g} (B_2)=A_2. }\)
Oto ilustracja:
Jednak to twierdzenie nie jest oczywiste- mając zbiór \(\displaystyle{ A_1\subset X}\) zawsze możemy wziąć jego obraz, potem możemy wziąć jego dopełnienie do zbioru \(\displaystyle{ Y}\), następnie obraz otrzymanego zbioru przez \(\displaystyle{ g}\), a na koniec taki zbiór dopełnić do \(\displaystyle{ X}\). Tylko dowcip polega na tym, że mamy otrzymać dokładnie ten sam zbiór \(\displaystyle{ A_1}\)- nie jest to oczywiste, zwłaszcza, że \(\displaystyle{ f,g}\) są dowolnymi funkcjami (w odwrotnych kierunkach). Ale dzięki twierdzeniu o punkcie stałym możemy to udowodnić.
Dowod: Niech \(\displaystyle{ f:X \rightarrow Y, g:Y \rightarrow X.}\) Rozważmy funkcję \(\displaystyle{ H:P(X) \rightarrow P(X)}\) określoną w poniższy sposób: dla dowolnego zbioru \(\displaystyle{ A\subset X }\)
\(\displaystyle{ H(A)=X\setminus\stackrel{\rightarrow }{g} (Y\setminus\stackrel{\rightarrow }{f}(A) ).}\)
Czyli z dowolnym zbiorem \(\displaystyle{ A\subset X}\) postępujemy jak wyżej, potem znajdziemy specjalny zbiór, a potem pozostałe zbiory aby udowodnić tezę twierdzenia. Pokażemy najpierw, że \(\displaystyle{ H}\) jest monotoniczna. Weźmy dowolne zbiory \(\displaystyle{ A_1,A_2\subset X}\), takie, że \(\displaystyle{ A_1\subset A_2}\). Wtedy
\(\displaystyle{ \stackrel{\rightarrow }{f}(A_1) \subset \stackrel{\rightarrow }{f}(A_2) }\), więc
\(\displaystyle{ Y\setminus\stackrel{\rightarrow }{f}(A_1)\supset Y\setminus\stackrel{\rightarrow }{f}(A_2)}\), następnie
\(\displaystyle{ \stackrel{\rightarrow }{g} (Y\setminus\stackrel{\rightarrow }{f}(A_1) ) \supset \stackrel{\rightarrow }{g} (Y\setminus\stackrel{\rightarrow }{f}(A_2) )}\) i dalej
\(\displaystyle{ H(A_{1} )=X\setminus\stackrel{\rightarrow }{g} (Y\setminus\stackrel{\rightarrow }{f}(A _{1} ) ) \subset X\setminus\stackrel{\rightarrow }{g} (Y\setminus\stackrel{\rightarrow }{f}(A _{2} ) )= H(A_{2} )}\)
a więc \(\displaystyle{ H(A_{1} ) \subset H(A_{2} )}\), i \(\displaystyle{ H}\) jest monotoniczna.
Skoro \(\displaystyle{ H}\) jest monotoniczna, to na podstawie twierdzenia Knastra-Tarskiego ma najmniejszy punkt stały, nazwijmy go \(\displaystyle{ A_1}\).
Zdefiniujmy teraz pozostałe poszukiwane zbiory.
\(\displaystyle{ A_2\stackrel {def} {\equiv} X \setminus A _{1},}\)
\(\displaystyle{ B_1\stackrel {def} {\equiv} \stackrel{\rightarrow }{f}(A _{1} ),}\)
\(\displaystyle{ B_2\stackrel {def} {\equiv} Y \setminus B _{1}.}\)
Z definicji tych zbiorów wynika, że zbiory \(\displaystyle{ A_1,A_2}\) są rozłączne i sumują się do \(\displaystyle{ X}\) podobnie zbiory \(\displaystyle{ B_1,B_2}\), a także \(\displaystyle{ \stackrel{\rightarrow }{ f} (A_1)=B_1. }\) Pozostaje pokazać, że \(\displaystyle{ \stackrel{\rightarrow }{ g} (B_2)=A_2. }\) Skoro \(\displaystyle{ A_1}\) jest punktem stałym funkcji \(\displaystyle{ H}\), to \(\displaystyle{ H(A_1)=A_1=X\setminus\stackrel{\rightarrow }{g} (Y\setminus\stackrel{\rightarrow }{f}(A_1) )}\). Ponieważ \(\displaystyle{ \stackrel{\rightarrow }{f}(A _{1} )=B_1,
}\) więc \(\displaystyle{ A_1=X\setminus\stackrel{\rightarrow }{g} (Y\setminus B_1 )}\). Ponieważ \(\displaystyle{ Y \setminus B _{1}=B_2}\), więc \(\displaystyle{ A_1=X\setminus\stackrel{\rightarrow }{g} (B_2 )}\). Zatem \(\displaystyle{ X \setminus A_1=X \setminus \left( X\setminus\stackrel{\rightarrow }{g} (B_2 )\right) =\stackrel{\rightarrow }{ g} (B_2)}\), ponieważ jednak lewa strona tej równości z definicji jest równa zbiorowi \(\displaystyle{ A_2}\), więc \(\displaystyle{ A_2=\stackrel{\rightarrow }{ g} (B_2).}\) Dowód jest zakończony. \(\displaystyle{ \square}\)