Lemat Banacha

Algebra zbiorów. Relacje, funkcje, iloczyny kartezjańskie... Nieskończoność, liczby kardynalne... Aksjomatyka.
Jakub Gurak
Użytkownik
Użytkownik
Posty: 1392
Rejestracja: 20 lip 2012, o 21:19
Płeć: Mężczyzna
Lokalizacja: Rzeszów
Podziękował: 60 razy
Pomógł: 83 razy

Lemat Banacha

Post autor: Jakub Gurak »

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}\) :lol:
Jakub Gurak
Użytkownik
Użytkownik
Posty: 1392
Rejestracja: 20 lip 2012, o 21:19
Płeć: Mężczyzna
Lokalizacja: Rzeszów
Podziękował: 60 razy
Pomógł: 83 razy

Re: Lemat Banacha

Post autor: Jakub Gurak »

Od przedprzedwczoraj zastanawiało mnie, czy jeśli \(\displaystyle{ X,Y}\) są zbiorami, a \(\displaystyle{ f,g:X \rightarrow Y}\) dowolnymi funkcjami, to czy można czterema zbiorami \(\displaystyle{ X_1,X_2\subset X, Y_1,Y_2\subset Y }\) podzielić odpowiednio zbiory \(\displaystyle{ X}\) i \(\displaystyle{ Y}\), tak że \(\displaystyle{ \stackrel{\rightarrow }{ f} (X_1)=Y_1 }\) i \(\displaystyle{ \stackrel{\rightarrow }{ g} (X_2)=Y_2. }\) Oto ilustracja .

Niestety, to niemożliwe (tzn. w przypadku ogólnym nie musi to zachodzić). Jeśli funkcje \(\displaystyle{ f,g}\) nie są 'na', np.\(\displaystyle{ X=Y=\left\{ 0,1,2\right\} , f,g:X \rightarrow Y,}\), \(\displaystyle{ f}\) jest stale równa \(\displaystyle{ 0}\), \(\displaystyle{ g}\) jest stale równa \(\displaystyle{ 1}\), wtedy obraz przez funkcję \(\displaystyle{ f}\) każdego podzbioru \(\displaystyle{ A\subset X}\) spelnia \(\displaystyle{ \stackrel{\rightarrow }{ f} (A)\subset \stackrel{\rightarrow }{ f} (X)=\left\{ 0\right\} }\), podobnie obraz przez funkcję \(\displaystyle{ g}\) każdego podzbioru \(\displaystyle{ A\subset X}\) spelnia \(\displaystyle{ \stackrel{\rightarrow }{ g} (A)\subset \stackrel{\rightarrow }{ g} (X)=\left\{ 1\right\} }\), zatem nie może być \(\displaystyle{ Y_1 \cup Y_2=\left\{ 0,1,2\right\}= Y}\), gdyż suma tych obrazów zawiera się w \(\displaystyle{ \left\{ 0,1\right\}.}\)

Jeśli funkcje \(\displaystyle{ f,g}\) są 'na' a nie są różnowartościowe, też raczej teza twierdzenia nie musi zachodzić. Natomiast gdy funkcje \(\displaystyle{ f,g}\) są bijekcjami (czyli są różnowartościowe i 'na') to teza będzie zachodzić, co udowodniłem na dwa sposoby. Przedstawię teraz rezultaty. Może doprecyzujmy. Będziemy dowodzić, że

jeśli \(\displaystyle{ X,Y}\) są zbiorami, a \(\displaystyle{ f,g:X \rightarrow Y}\) bijekcjami (różnowartościowe i 'na'), to istnieją cztery zbiory \(\displaystyle{ X_1,X_2\subset X, Y_1,Y_2\subset Y}\), takie, że zbiory \(\displaystyle{ X_1,X_2}\) są rozłączne, i \(\displaystyle{ X_1 \cup X_2=X}\), oraz zbiory \(\displaystyle{ Y_1,Y_2}\) są rozłączne i \(\displaystyle{ Y_1 \cup Y_2=Y}\), tak że \(\displaystyle{ \stackrel{\rightarrow }{ f} (X_1)=Y_1 }\) i \(\displaystyle{ \stackrel{\rightarrow }{ g} (X_2)=Y_2. }\)

Dowód 1 (analogiczny do dowodu Lematu Banacha):

Rozważmy funkcję \(\displaystyle{ H:P\left( X\right) \rightarrow P(X)}\), tak, że dla dowolnego \(\displaystyle{ A\subset X}\):

\(\displaystyle{ H(A)= X \setminus \left[ \stackrel{\rightarrow }{ g ^{-1} } (Y \setminus \stackrel{\rightarrow }{ f} (A)\right].}\)

Czyli najpierw bierzemy obraz zbioru \(\displaystyle{ A}\) przez funkcję \(\displaystyle{ f}\), potem bierzemy jego dopełnienie do zbioru \(\displaystyle{ Y}\), potem dla takiego zbioru bierzemy jego przeciwobraz przez funkcję \(\displaystyle{ g}\), a na koniec bierzemy jego dopełnienie do zbioru \(\displaystyle{ X}\). Jeśli \(\displaystyle{ H(A)=A}\), to łatwo przypuścić, że uda się to zrobić.

Jednak aby wykazać, że funkcja \(\displaystyle{ H}\) ma zbiór stały, należy wykazać, że jest monotoniczna ze względu na inkluzję.

Aby to wykazać, weźmy dwa zbiory \(\displaystyle{ A_1,A_2\subset X}\), takie, że \(\displaystyle{ A_1 \subset A_2}\). Pokażemy, że \(\displaystyle{ H(A_1)\subset H(A_2)}\). Ponieważ \(\displaystyle{ A_1\subset A_2}\), więc ze zgodności brania obrazów z inkluzją , otrzymujemy

\(\displaystyle{ \stackrel{\rightarrow }{ f} (A_1)\subset \stackrel{\rightarrow }{ f} (A_2),}\) i dalej
\(\displaystyle{ Y \setminus \stackrel{\rightarrow }{ f} (A_1)\supset Y \setminus \stackrel{\rightarrow }{ f} (A_2),}\)
następnie ze zgodności brania przeciwobrazów z inkluzją, otrzymujemy
\(\displaystyle{ \stackrel{\rightarrow }{ g ^{-1} } (Y \setminus \stackrel{\rightarrow }{ f} (A_1))\supset \stackrel{\rightarrow }{ g ^{-1} } (Y \setminus \stackrel{\rightarrow }{ f} (A_2) ), }\) i dalej
\(\displaystyle{ H(A_1)=X \setminus \stackrel{\rightarrow }{ g ^{-1} } (Y \setminus \stackrel{\rightarrow }{ f} (A_1))\subset X \setminus \stackrel{\rightarrow }{ g ^{-1} } (Y \setminus \stackrel{\rightarrow }{ f} (A_2) )=H(A_2), }\)
a więc \(\displaystyle{ H(A_1)\subset H(A_2)}\), i otrzymujemy, że funkcja \(\displaystyle{ H}\) jest monotoniczna.

Skoro \(\displaystyle{ H}\) jest monotoniczna, to na mocy twierdzenia Knastra-Tarskiego funkcja \(\displaystyle{ H}\) ma zbiór stały \(\displaystyle{ A_1\subset X}\). Zdefiniujmy teraz poszukiwane zbiory:

\(\displaystyle{ X_1\stackrel {def} {\equiv}A_1}\),
\(\displaystyle{ X_2\stackrel {def} {\equiv}X\setminus A_1,}\)
\(\displaystyle{ Y_1\stackrel {def} {\equiv} \stackrel{\rightarrow }{ f} (A_1)}\), i dalej
\(\displaystyle{ Y_2\stackrel {def} {\equiv}Y \setminus Y_1.}\)

Z definicji tych zbiorów wnioskujemy, że zbiory \(\displaystyle{ X_1,X_2}\) są rozłączne, i \(\displaystyle{ X_1 \cup X_2=X,}\) podobnie zbiory \(\displaystyle{ Y_1,Y_2}\) są rozłączne, i sumują się do zbioru \(\displaystyle{ Y}\), również \(\displaystyle{ Y_1= \stackrel{\rightarrow }{ f} (A_1)=\stackrel{\rightarrow }{ f} (X_1),}\) pozostaje pokazać, że \(\displaystyle{ \stackrel{\rightarrow }{ g} (X_2)=Y_2. }\)

Ponieważ zbiór \(\displaystyle{ A_1}\) jest zbiorem stałym, więc \(\displaystyle{ A_1=H(A_1)=X \setminus \left[ \stackrel{\rightarrow }{ g ^{-1} } (Y \setminus \stackrel{\rightarrow }{ f} (A_1)\right]}\). Ponieważ

\(\displaystyle{ \stackrel{\rightarrow }{ f} (A_1)=Y_1}\), więc \(\displaystyle{ A_1=X \setminus \left[ \stackrel{\rightarrow }{ g ^{-1} } (Y \setminus Y_1)\right]=X \setminus \left[ \stackrel{\rightarrow }{ g ^{-1} } (Y )\setminus \stackrel{\rightarrow }{ g ^{-1} } (Y_1 )\right]= X \setminus \left[ X \setminus \stackrel{\rightarrow }{ g ^{-1} } ( Y_1)\right]=\stackrel{\rightarrow }{ g ^{-1} } ( Y_1) . }\) a więc \(\displaystyle{ A_1=\stackrel{\rightarrow }{ g ^{-1} } ( Y_1)}\), wobec czego \(\displaystyle{ \stackrel{\rightarrow }{ g} (X_2)=\stackrel{\rightarrow }{ g} (X\setminus A_1) }\), ponieważ \(\displaystyle{ g}\) jest bijekcją, więc to jest równe \(\displaystyle{ Y \setminus \stackrel{\rightarrow }{ g} ( A_1)= Y \setminus \left[ \stackrel{\rightarrow }{ g} ( \stackrel{\rightarrow }{ g ^{-1} } ( Y_1))\right]}\) , ponieważ \(\displaystyle{ g}\) jest bijekcją, więc to jest równe \(\displaystyle{ Y \setminus Y_1=Y_2.}\) Tak więc \(\displaystyle{ \stackrel{\rightarrow }{ g} (X_2)=Y_2}\). Dowód jest zakończony. \(\displaystyle{ \square}\) :D

Podajmy jeszcze jeden dowód, wprost z Lematu Banacha.

PROSTY DOWÓD:

Zauważmy najpierw, że ponieważ \(\displaystyle{ g}\) jest bijekcją, to relacja odwrotna \(\displaystyle{ g^{-1}}\) jest funkcją (bijekcją). W takim razie \(\displaystyle{ f:X \rightarrow Y, g^{-1}:Y \rightarrow X.}\) Możemy zatem do tych funkcji zastosować Lemat Banacha. Czyniąc to dostaniemy cztery zbiory \(\displaystyle{ X_1, X_2\subset X, Y_1,Y_2\subset Y}\), takie, że zbiory \(\displaystyle{ X_1,X_2}\) są rozłączne, i \(\displaystyle{ X_1 \cup X_2=X}\), oraz zbiory \(\displaystyle{ Y_1 }\) i \(\displaystyle{ Y_2}\) są rozłączne i sumują się do \(\displaystyle{ Y}\), oraz \(\displaystyle{ \stackrel{\rightarrow }{ f} (X_1)=Y_1 }\) i \(\displaystyle{ \stackrel{\rightarrow }{ h} (Y_2)=X_2,}\) gdzie \(\displaystyle{ h=g^{-1}.}\) Jako poszukiwane cztery zbiory połóżmy te same cztery zbiory co przed chwilą otrzymane. Wystarczy zatem pokazać, że \(\displaystyle{ \stackrel{\rightarrow }{ g} (X_2)=Y_2.}\) Ponieważ \(\displaystyle{ g=\left( g ^{-1} \right) ^{-1}}\), więc \(\displaystyle{ \stackrel{\rightarrow }{ g} (X_2)=\overrightarrow{\left( g ^{-1} \right) ^{-1} }(X_2)=\stackrel{\rightarrow }{ h ^{-1} } (X_2),}\) (\(\displaystyle{ h=g^{-1}}\)) ponieważ \(\displaystyle{ \stackrel{\rightarrow }{ h} (Y_2)=X_2,}\) więc to jest równe \(\displaystyle{ \stackrel{\rightarrow }{ h ^{-1} } (\stackrel{\rightarrow }{ h} (Y_2) ),}\) ponieważ \(\displaystyle{ g}\) jest bijekcją, to \(\displaystyle{ h=g^{-1}}\) jest również bijekcją, a więc to jest równe \(\displaystyle{ Y_2}\). Zatem \(\displaystyle{ \stackrel{\rightarrow }{ g} (X_2)=Y_2.\square }\) :lol: 8-)
Awatar użytkownika
Dasio11
Moderator
Moderator
Posty: 10211
Rejestracja: 21 kwie 2009, o 19:04
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 40 razy
Pomógł: 2359 razy

Re: Lemat Banacha

Post autor: Dasio11 »

Parę uwag:

1.
Jakub Gurak pisze: 25 wrz 2020, o 21:34jeśli \(\displaystyle{ X,Y}\) są zbiorami, a \(\displaystyle{ f,g:X \rightarrow Y}\) bijekcjami (różnowartościowe i 'na'), to istnieją cztery zbiory \(\displaystyle{ X_1,X_2\subset X, Y_1,Y_2\subset Y}\), takie, że zbiory \(\displaystyle{ X_1,X_2}\) są rozłączne, i \(\displaystyle{ X_1 \cup X_2=X}\), oraz zbiory \(\displaystyle{ Y_1,Y_2}\) są rozłączne i \(\displaystyle{ Y_1 \cup Y_2=Y}\), tak że \(\displaystyle{ \stackrel{\rightarrow }{ f} (X_1)=Y_1 }\) i \(\displaystyle{ \stackrel{\rightarrow }{ g} (X_2)=Y_2. }\)
To prawda - wystarczy wziąć \(\displaystyle{ X_1 = Y_1 = \varnothing}\) i \(\displaystyle{ X_2 = X, Y_2 = Y}\).


2.
Jakub Gurak pisze: 25 wrz 2020, o 21:34Jeśli funkcje \(\displaystyle{ f,g}\) są 'na' a nie są różnowartościowe, też raczej teza twierdzenia nie musi zachodzić.
Musi - i to nie tylko z podanego wyżej, trywialnego powodu. Metoda podobna do Twojej zadziała przy założeniu, że funkcja \(\displaystyle{ g}\) jest "na". W skrócie: definiujemy przekształcenie \(\displaystyle{ H : \mathcal{P}(X) \to \mathcal{P}(X)}\) wzorem

\(\displaystyle{ H(A) = X \setminus \Big[ g^{-1} \big[ Y \setminus f[A] \big] \Big]}\)

lub równoważnie: \(\displaystyle{ H(A) = g^{-1} \big[ f[A] \big]}\). Potem dowodzimy, że jest ona monotoniczna (co jest dość oczywiste, bo obraz i przeciwobraz takie są). Z twierdzenia KT otrzymujemy zbiór \(\displaystyle{ A \subseteq X}\), taki że \(\displaystyle{ g^{-1} \big[ f[A] \big] = A}\). Pozostaje sprawdzić, że \(\displaystyle{ X_1 = A, X_2 = X \setminus A}\) i \(\displaystyle{ Y_1 = f[A], Y_2 = Y \setminus f[A]}\) spełniają zadane warunki, korzystając po drodze z własności \(\displaystyle{ g[g^{-1}[Y_2]] = Y_2}\) (wynikającej z surjektywności \(\displaystyle{ g}\)).


3. Nawet używając twierdzenia KT nie można bez dodatkowych założeń zagwarantować, że znalezione rozkłady \(\displaystyle{ X = X_1 \cup X_2, Y = Y_1 \cup Y_2}\) są nietrywialne, tj. takie że żaden ze zbiorów nie jest pusty. Świadczy o tym przykład: \(\displaystyle{ X = Y = \{ 0, 1, \ldots, n-1 \}, f(x) = x, g(x) = (x+1) (\bmod{n})}\), dla którego nietrywialny rozkład spełniający żądane warunki nie istnieje.
Jakub Gurak
Użytkownik
Użytkownik
Posty: 1392
Rejestracja: 20 lip 2012, o 21:19
Płeć: Mężczyzna
Lokalizacja: Rzeszów
Podziękował: 60 razy
Pomógł: 83 razy

Re: Lemat Banacha

Post autor: Jakub Gurak »

Jakub Gurak pisze: 25 wrz 2020, o 21:34Jeśli funkcje \(\displaystyle{ f,g}\) są 'na' a nie są różnowartościowe, też raczej
teza twierdzenia nie musi zachodzić.
Dasio11 pisze: 26 wrz 2020, o 14:56Musi - i to nie tylko z podanej wyżej, trywialnego powodu.
Myślałem, że mam (trochę kombinowany, dlatego go nie podawałem) kontrprzykład. Ale może rzecz w ścisłości, czyli rozkład gdzie występuje zbiór pusty. Niech \(\displaystyle{ X=\left\{ 1,2,3,4,5,6\right\}; Y=\left\{ 0,1\right\} }\) \(\displaystyle{ f\left( 1\right)=1, f(2)=0, f(3)=1}\), dalej jakkolwiek np. stale \(\displaystyle{ 0}\). Natomiast \(\displaystyle{ g(4)=0, g(5)=g(6)=1}\), na pierwszych trzech elementach jakkolwiek np. stale \(\displaystyle{ 0}\). Wtedy \(\displaystyle{ f,g}\) są 'na' \(\displaystyle{ \left\{ 0,1\right\} }\), nie są różnowartościowe, i jak to rozłożyć :?: , jeśli \(\displaystyle{ X _{1}\subset \left\{ 1,2,3\right\}}\), to \(\displaystyle{ X_2\supset\left\{ 4,5,6\right\}}\), i wtedy \(\displaystyle{ g[X_2]=\left\{ 0,1\right\}}\) , i taki zbiór nie jest rozłączny z \(\displaystyle{ Y_1=f[X_1]}\), jeśli natomiast \(\displaystyle{ X_2\subset \left\{ 4,5,6\right\}}\), to \(\displaystyle{ X_1\supset \left\{ 1,2,3\right\}}\), a zatem \(\displaystyle{ Y_1=f[X_1]=\left\{ 0,1\right\}}\), i taki zbiór znowu nie jest rozłączny z \(\displaystyle{ Y_2=g[X_2].}\) Stąd myślałem, że się nie da, ale może czegoś nie widzę.

I może rzecz w rozkładzie z użyciem zbioru pustego.
ODPOWIEDZ