Zbiory, funkcje- aksjomat wyboru

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

Zbiory, funkcje- aksjomat wyboru

Post autor: Jakub Gurak » 7 sie 2019, o 01:11

Mam na myśli poniższy fakt równoważny aksjomatów wyboru.

Dla dowolnych zbiorów \(\displaystyle{ X, Y}\) oraz dowolnej funkcji \(\displaystyle{ f:X \rightarrow Y}\) 'na' \(\displaystyle{ Y}\) istnieje funkcja \(\displaystyle{ g:Y \rightarrow X}\), taka, że złożenie \(\displaystyle{ f\circ g}\) jest funkcją identyczności na zbiorze \(\displaystyle{ Y}\).

To nie takie straszne, jeśli się sprawę objaśni. Aby to zrobić rozważmy funkcję \(\displaystyle{ f:X \rightarrow Y}\) na \(\displaystyle{ Y}\), i rozważmy rodzinę \(\displaystyle{ \mathbb{B}}\) wszystkich przeciwobrazów zbiorów jednoelementowych. Ponieważ \(\displaystyle{ f}\) jest "na" zbiór Y, to takie przeciwobrazy są zawsze niepuste. Są również rozłączne. Przypiszmy elementowi \(\displaystyle{ y \in Y}\) element jego przeciwobrazu; gdy tak zrobimy, to w wyniku złożenia z funkcją f element \(\displaystyle{ y}\) powróci, tzn. złożenie będzie mieć punkt stały. Jeśli dowolnemu elementowi \(\displaystyle{ y \in Y}\) będziemy przypisywać element jego przeciwobrazu, stąd łatwo przepuścić, że złożenie będzie mieć w każdym punkcie \(\displaystyle{ y}\) punkt stały, stąd będzie identycznością na \(\displaystyle{ Y}\). Jeśli natomiast przypisalibyśmy element spoza przeciwobrazu zbioru \(\displaystyle{ \left\{ y\right\}}\) , to złożenie nie będzie mieć punktu stałego, stąd nie będzie identycznością na \(\displaystyle{ Y}\). Tyle tylko, aby możliwe było utworzenie funkcji musimy wybrać jeden element z wielu (na ogół ) elementów jego przeciwobrazu. I tak dla dowolnego \(\displaystyle{ y \in Y}\)... Dlatego to jest równoważne aksjomatowi wyboru, ale musimy to też udowodnić.

Pokażemy najpierw, że z aksjomatu wyboru wynika powyższe stwierdzenie.

Weźmy zbiory \(\displaystyle{ X,Y}\) oraz dowolną funkcję \(\displaystyle{ f:X\rightarrow Y}\) 'na' zbiór \(\displaystyle{ Y}\). Rozważmy rodzinę wszystkich przeciwobrazów zbiorów jednoelementowych, tzn.

\(\displaystyle{ \mathbb{B}=\left\{A\subset X\Bigl| \ \ \bigvee\limits_{y\in Y} \ A=\stackrel{\rightarrow} {f^{-1}} \{ y \} \ \right\}.}\)

Ponieważ \(\displaystyle{ f}\) jest "na" to takie przeciwobrazy są zawsze niepuste, skąd \(\displaystyle{ \emptyset\not\in B,}\) Jeśli zbiory \(\displaystyle{ X_1,X_2\in B}\) są różne to są rozłączne. Wtedy \(\displaystyle{ X_1=\stackrel {\rightarrow}{f^{-1}} \left\{y_1\right\}}\) DLA pewnego \(\displaystyle{ y_1}\) oraz \(\displaystyle{ X_2=\stackrel {\rightarrow}{f^{-1}}\left\{ y_2 \right\}}\) dla pewnego \(\displaystyle{ y_2}\). Ponieważ \(\displaystyle{ X_1\neq X_2}\), więc również \(\displaystyle{ y_1\neq y_2}\), więc zbiory \(\displaystyle{ X_1,X_2}\) jako przeciwobrazy różnych zbiorów jednoelementowych będą rozłączne. Wobec powyższych do rodziny \(\displaystyle{ \mathbb{B}}\) możemy zastosować aksjomatu wyboru, i otrzymujemy zbiór \(\displaystyle{ S}\) mający po dokładnie jednym elemencie wspólnym z każdym zbiorem rodziny \(\displaystyle{ \mathbb{B}}\). Wtedy rozważmy relacje \(\displaystyle{ g}\), określoną jako

\(\displaystyle{ g =\left\{ (y,x)\in Y\times X\Bigl| \ \ \left\{x \right\}=\stackrel {\rightarrow}{f^{-1}}\left\{ y\right\}\cap S \ \right\}.}\)

Relacja \(\displaystyle{ g}\) jest funkcją z definicji i z własności zbioru \(\displaystyle{ S}\). A więc \(\displaystyle{ g: Y\rightarrow X.}\) Pokażemy, że złożenie \(\displaystyle{ g}\) z \(\displaystyle{ f}\) jest identycznością na \(\displaystyle{ Y}\). Niech \(\displaystyle{ y\in Y.}\) Wtedy \(\displaystyle{ g(y)=:x}\) oznacza, że \(\displaystyle{ (y,x)\in g,}\) a więc( z definicji \(\displaystyle{ g}\)) \(\displaystyle{ \left\{ x\right\}= \stackrel{\rightarrow}{f^{-1}} \left\{y \right\}\cap S,}\) a więc \(\displaystyle{ x\in \stackrel{\rightarrow}{f^{-1}} \left\{y \right\}}\), czyli \(\displaystyle{ f(x)=y}\), a więc \(\displaystyle{ (f\circ g)(y)=y}\), i \(\displaystyle{ f \circ g=I_Y. \square}\)

Reszta później.
Ostatnio zmieniony 7 sie 2019, o 10:00 przez Dasio11, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Rekrutacja Instytut Matematyczny, Uniwersytet Wrocławski (gif)

Jakub Gurak
Użytkownik
Użytkownik
Posty: 629
Rejestracja: 20 lip 2012, o 21:19
Płeć: Mężczyzna
Lokalizacja: Rzeszów
Podziękował: 20 razy
Pomógł: 46 razy

Re: Zbiory, funkcje- aksjomat wyboru

Post autor: Jakub Gurak » 7 wrz 2019, o 02:59

Pokażemy teraz, że z powyzszej wypowiedzi wynika aksjomat wyboru.

Niech \(\displaystyle{ \mathbb {X} }\) będzie rodziną zbiorów rozłącznych, tak że \(\displaystyle{ \emptyset\not\in\mathbb{X} }\), czyli niepustych. Rozważmy relację \(\displaystyle{ f:\bigcup\mathbb {X}\rightarrow \mathbb{X} }\) określoną jako:

\(\displaystyle{ f(a) =b\Longleftrightarrow a\in b.}\)

Relacja \(\displaystyle{ f}\) jest funkcją, gdyż każdy element zbioru \(\displaystyle{ \bigcup\mathbb{X} }\) należy do dokładnie jednego zbioru w \(\displaystyle{ \mathbb {X}}\) (gdyby element \(\displaystyle{ a\in A,B\in\mathbb{X},}\)) gdzie \(\displaystyle{ A\neq B,}\) to wtedy \(\displaystyle{ a\in A\cap B,}\) co jest sprzeczne z tym, że zbiory rodziny \(\displaystyle{ X}\) są rozłączne, z definicji sumy każdy element zbioru \(\displaystyle{ \bigcup\mathbb{X} }\) należy do co najmniej jednego zbioru rodziny \(\displaystyle{ X}\)). A więc \(\displaystyle{ f}\) jest funkcją, czyli \(\displaystyle{ f:\bigcup\mathbb {X}\rightarrow \mathbb {X}.}\) Jest to funkcja " na". Aby się o tym przekonać, to niech \(\displaystyle{ A\in\mathbb {X}.}\) Ponieważ \(\displaystyle{ \emptyset\not\in\mathbb {X}, }\) więc \(\displaystyle{ A\neq\emptyset, }\) a więc istnieje \(\displaystyle{ a\in A. }\) Ustalmy taki element. Wtedy \(\displaystyle{ a\in \bigcup\mathbb {X}, }\) i \(\displaystyle{ a\in A,}\) a więc z definicji funkcji \(\displaystyle{ f}\) otrzymujemy, że \(\displaystyle{ f(a)= A,}\) i wnioskujemy, że \(\displaystyle{ f}\) jest "na".

Na mocy zakładanego twierdzenia istnieje funkcja \(\displaystyle{ g:\mathbb {X}\rightarrow\bigcup\mathbb {X}, }\) taka, że złożenie \(\displaystyle{ f\circ g}\) jest identycznością na \(\displaystyle{ \mathbb {X}.}\) Niech \(\displaystyle{ A\in\mathbb {X}. }\) Wtedy \(\displaystyle{ (f \circ g)(A)=A= f(g(A)),}\) co oznacza z definicji funkcji \(\displaystyle{ f}\), że \(\displaystyle{ g(A)\in A,}\) a ponieważ \(\displaystyle{ g}\) jest funkcją, to jej zbiór wartości \(\displaystyle{ g_P}\) ma z każdym zbiorem \(\displaystyle{ A\in\mathbb {X} }\) ma dokładnie jeden element wspólny, co oznacza prawdziwość aksjomatu wyboru.\(\displaystyle{ \square}\)

A więc jest to równoważnik aksjomatowi wyboru. Możemy dzięki temu scharakteryzować funkcje "na":

Funkcja \(\displaystyle{ f:X\rightarrow Y}\) jest "na" zbiór \(\displaystyle{ Y}\), wtedy i tylko wtedy, gdy istnieje funkcja \(\displaystyle{ g:Y \rightarrow X}\), taka, że \(\displaystyle{ f \circ g=I_Y.}\)

Dowód odwołuje się do aksjomatu wyboru. Wtedy rzeczywiście pokazaliśmy implikacje \(\displaystyle{ \Longrightarrow. }\) Natomiast dowód implikacji w drugą stronę jest bardzo prosty.

Załóżmy, że istnieje funkcja \(\displaystyle{ g:Y\rightarrow X}\) taka, że \(\displaystyle{ f \circ g=I_Y. }\) Aby pokazać, że \(\displaystyle{ f}\) jest " na" zbiór \(\displaystyle{ Y}\), to niech \(\displaystyle{ y\in Y.}\) Ponieważ \(\displaystyle{ g:Y\rightarrow X}\), więc oznaczmy \(\displaystyle{ g(y)=:x.}\) Ponieważ \(\displaystyle{ f\circ g=I_Y, }\) więc \(\displaystyle{ (f\circ g)(y)=y}\). Zatem z definicji złożenia funkcji dostajemy \(\displaystyle{ f(g(y))=y}\). Podstawiając za \(\displaystyle{ g(y)}\) wartość \(\displaystyle{ x}\) otrzymujemy \(\displaystyle{ f(x)= y,}\) czyli \(\displaystyle{ y}\) jest wartością funkcji \(\displaystyle{ f}\). Z dowolności wyboru elementu \(\displaystyle{ y}\), wnioskujemy, że \(\displaystyle{ f}\) jest " na". \(\displaystyle{ \square }\)

Jakub Gurak
Użytkownik
Użytkownik
Posty: 629
Rejestracja: 20 lip 2012, o 21:19
Płeć: Mężczyzna
Lokalizacja: Rzeszów
Podziękował: 20 razy
Pomógł: 46 razy

Re: Zbiory, funkcje- aksjomat wyboru

Post autor: Jakub Gurak » 4 sty 2020, o 00:21

Inne twierdzenie równoważne aksjomatowi wyboru, to twierdzenie o funkcji wyboru:

Dla dowolnej rodziny \(\displaystyle{ \mathbb{X}}\) niepustych zbiorów istnieje funkcja wyboru, tzn. funkcja \(\displaystyle{ f:\mathbb{X}\rightarrow\bigcup \mathbb{X}}\) taka, że \(\displaystyle{ f(A)\in A,}\) dla każdego \(\displaystyle{ A\in\mathbb{X}.}\)

Poniżej przedstawiamy dowód, że z aksjomat wyboru wynika powyższe twierdzenie.

Dowód

Aby to wykazać, ustalmy dowolną niepustą rodzinę ( dla pustej rodziny wystarczy rozważyć funkcję pustą) \(\displaystyle{ \mathbb{X} \neq \emptyset}\) zbiorów niepustych, tzn. taką, że \(\displaystyle{ \emptyset\notin \mathbb{X}}\). Skonstruujemy rodzinę \(\displaystyle{ \mathbb{X_0}}\), do której stosować będziemy aksjomat wyboru. Rodzina

\(\displaystyle{ \mathbb{X_0} = \{\{A\}\times A\,:\, A\in \mathbb{X}\}}\)

jest rodziną zbiorów rozłącznych, gdyż jeśli \(\displaystyle{ A,B\in X}\), i \(\displaystyle{ A \neq B}\), to \(\displaystyle{ \left( \left\{ A\right\} \times A \right) \cap \left( \left\{ B\right\} \times B \right)=\emptyset,}\) gdyż \(\displaystyle{ A \neq B}\). A więc jest to rodzina zbiorów rozłącznych, niepustych( gdyż \(\displaystyle{ \mathbb{X} }\) jest rodziną zbiorów niepustych). W związku z czym do rodziny \(\displaystyle{ \mathbb{X_0}}\) możemy zastosować aksjomat wyboru, i otrzymać zbiór \(\displaystyle{ S}\) mający po dokładnie jednym elemencie wspólnym z każdym zbiorem \(\displaystyle{ A\in\mathbb{X_0}}\). Wtedy \(\displaystyle{ S \cap \bigcup \mathbb{X}_{0} \subset\bigcup\mathbb X_{0} \subset \mathbb{X}\times \bigcup \mathbb{X}}\). Ponieważ z każdego zbioru z \(\displaystyle{ \mathbb{X _{0} }}\) wybraliśmy dokładnie jeden element, to \(\displaystyle{ S}\) jest funkcją z \(\displaystyle{ \mathbb{X}}\) do \(\displaystyle{ \bigcup \mathbb{X}}\). Definicja \(\displaystyle{ \mathbb{X_0}}\) gwarantuje również, że \(\displaystyle{ S(A)\in A,}\) dla każdego \(\displaystyle{ A\in\mathbb{X}}\). Wnioskujemy, że \(\displaystyle{ S}\) może być wzięte jako \(\displaystyle{ f}\), i że z aksjomatu wyboru wynika twierdzenie o funkcji wyboru. \(\displaystyle{ \square}\)

Uff, ważniak jest ciężki. :? Pokażemy teraz implikacje odwrotną:

(Twierdzenie o funkcji wyboru) \(\displaystyle{ \Longrightarrow}\) (Aksjomat wyboru):

PROSTY DOWÓD:

Niech \(\displaystyle{ \mathbb{X}}\) bedzię rodzinę zbiorów niepustych, rozłącznych. W takim razie możemy do tej rodziny zbiorów zastosować twierdzenie o funkcji wyboru, i otrzymać funkcję \(\displaystyle{ f:\mathbb{X}→ \bigcup \mathbb{X}}\) taką, że \(\displaystyle{ f(A) \in A,}\) dla każdego \(\displaystyle{ A\in \mathbb{X}.}\) Ponieważ jest to funkcja, i zbiory tej rodziny są rozłączne, to zbiór wartości tej funkcji \(\displaystyle{ f_P}\) ma z każdym zbiorem \(\displaystyle{ A\in \mathbb{X}}\) ma dokładnie jeden element wspólny. \(\displaystyle{ \square}\)

ODPOWIEDZ