Aksjomat wyboru

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

Aksjomat wyboru

Post autor: Jakub Gurak »

Mam takie zadanie:

Niech \(\displaystyle{ X}\) będzie zbiorem, a \(\displaystyle{ R\subset X\times X}\) będzie dowolną relacją. Wykazać (przy pomocy aksjomatu wyboru), że istnieje wtedy maksymalny pod względem inkluzji zbiór \(\displaystyle{ B\subset X}\), taki, że \(\displaystyle{ B\times B\subset R.}\)

Czyli, że w relacji można zawrzeć maksymalny kwadrat- hm, ciekawe. Spróbuje to udowodnić.

Dowód:
Rozważmy zbiór: \(\displaystyle{ B=\left\{ A\subset X\Biggl| \ \ A\times A\subset R \right\}.}\)

i uporządkujmy go inkluzją- wiemy, że inkluzja na każdej rodzinie podzbiorów \(\displaystyle{ X}\) jest relacją porządku, zatem tu też tak jest, czyli \(\displaystyle{ \left( B,\subset\right)}\) jest zbiorem uporządkowanym.

Będziemy chcieli zastosować lemat Zorna do takiego zbioru uporządkowanego. W tym celu ustalmy dowolny łańcuch \(\displaystyle{ D}\) w \(\displaystyle{ \left( B,\subset\right)}\). Jako ograniczenie górne kładziemy \(\displaystyle{ \bigcup D}\), jednak wpierw musimy wykazać, że \(\displaystyle{ \bigcup D\in B}\). Suma rodziny \(\displaystyle{ D}\)- podzbiorów \(\displaystyle{ X}\) jest podzbiorem \(\displaystyle{ X}\). Pokażemy, że \(\displaystyle{ \left( \bigcup D\right) \times \left( \bigcup D\right) \subset R.}\) W tym celu, niech \(\displaystyle{ \left( x,y \right) \in \left( \bigcup D\right) \times \left( \bigcup D\right).}\) Wtedy oczywiście \(\displaystyle{ x,y\in\bigcup D}\), a więc \(\displaystyle{ x\in A\in D}\) dla pewnego zbioru \(\displaystyle{ A}\), oraz \(\displaystyle{ y\in C\in D}\), dla pewnego zbioru \(\displaystyle{ C}\). Ponieważ \(\displaystyle{ D}\) jest łańcuchem, zbiory \(\displaystyle{ A,C}\) są porównywalne pod względem inkluzji, więc \(\displaystyle{ A\subset C}\) lub \(\displaystyle{ C\subset A.}\) Zajmijmy się najpierw pierwszym przypadkiem. Wtedy \(\displaystyle{ x,y\in C}\), a więc ponieważ \(\displaystyle{ C\in D\subset B}\), więc \(\displaystyle{ C\in B}\), a więc z określenia zbioru \(\displaystyle{ B}\) otrzymujemy, że \(\displaystyle{ C\times C\subset R}\), a ponieważ \(\displaystyle{ \left( x,y \right) \in C\times C}\), to \(\displaystyle{ \left( x,y \right) \in R.}\) W drugim przypadku \(\displaystyle{ C\subset A}\) analogicznie pokazujemy, że \(\displaystyle{ \left( x,y \right) \in R.}\) Zatem \(\displaystyle{ \left( \bigcup D\right) \times \left( \bigcup D\right) \subset R,}\) a więc \(\displaystyle{ \bigcup D\in B.}\) Wiemy, że każdy zbiór z rodziny \(\displaystyle{ D}\) jest podzbiorem \(\displaystyle{ \bigcup D}\), czyli jeśli \(\displaystyle{ A\in D}\), to \(\displaystyle{ A\subset\bigcup D.}\) Stąd \(\displaystyle{ \bigcup D}\) jest ograniczeniem górnym zbioru \(\displaystyle{ D}\), i z dowolności wyboru takiego zbioru, każdy łańcuch w \(\displaystyle{ \left( B,\subset\right)}\) ma ograniczenie górne.

Stosując aksjomat wyboru (pod postacią lematu Zorna) wnioskujemy, że w\(\displaystyle{ \left( B,\subset\right)}\) jest element maksymalny- jest to poszukiwany kwadrat maksymalny (pod względem inkluzji) zawarty w relacji \(\displaystyle{ R. \square}\)

Mam jeszcze takie zadanie:

Czy dla istnienia funkcji \(\displaystyle{ f:\mathcal{P}(\mathbb{Q})\rightarrow \mathbb{Q}}\) takiej, że \(\displaystyle{ f(A)\in A}\) dla każdego niepustego \(\displaystyle{ A\subseteq \mathbb{Q}}\) niezbędny jest aksjomat wyboru?

Odpowiedź brzmi nie- nie wiem dlaczego.
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

Aksjomat wyboru

Post autor: Dasio11 »

Jakub Gurak pisze:Czy dla istnienia funkcji \(\displaystyle{ f:\mathcal{P}(\mathbb{Q})\rightarrow \mathbb{Q}}\) takiej, że \(\displaystyle{ f(A)\in A}\) dla każdego niepustego \(\displaystyle{ A\subseteq \mathbb{Q}}\) niezbędny jest aksjomat wyboru?
Podpowiedź: gdyby \(\displaystyle{ \QQ}\) zastąpić przez \(\displaystyle{ \NN}\), to umiałbyś taką funkcję zdefiniować?
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: Aksjomat wyboru

Post autor: Jakub Gurak »

Tak, wystarczy niepustemu podzbiorowi \(\displaystyle{ A\subset\NN}\) przypisać jego liczbę najmniejszą. Wtedy \(\displaystyle{ f\left( A\right)\in A}\), bo element najmniejszy w \(\displaystyle{ A}\) należy do \(\displaystyle{ A}\).

Teraz już chyba wiem, trzeba ustalić bijekcję \(\displaystyle{ g:\NN \rightarrow \QQ}\). I zdefiniować \(\displaystyle{ h:P\left( \QQ\right) \rightarrow \QQ}\) jako:

\(\displaystyle{ h\left( \left\{ \right\} \right) =0,}\)
\(\displaystyle{ h\left( A\right)=g\left( f\left( \stackrel { \rightarrow } {g ^{-1} } \left( A\right) \right) \right),}\) gdy \(\displaystyle{ A \neq \left\{ \right\} .}\)

Czyli odwracamy zbiór \(\displaystyle{ A}\), potem bierzemy liczbę najmniejszą w otrzymanym podzbiorze \(\displaystyle{ \NN}\), a potem wartość funkcji \(\displaystyle{ g}\) na tym elemencie.

Łatwo sprawdzić, że wtedy \(\displaystyle{ h\left( A\right) \in A.}\)

Nie użyliśmy aksjomatu wyboru - chciałbym się upewnić, więc proszę o odpowiedź.
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: Aksjomat wyboru

Post autor: Dasio11 »

Nie użyliśmy.
a4karo
Użytkownik
Użytkownik
Posty: 22173
Rejestracja: 15 maja 2011, o 20:55
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 38 razy
Pomógł: 3748 razy

Re: Aksjomat wyboru

Post autor: a4karo »

A co jeżeli `B` jest pusty?
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: Aksjomat wyboru

Post autor: Jakub Gurak »

\(\displaystyle{ h( \emptyset)=0\not\in\emptyset}\), w zadaniu był warunek dla wszystkich niepustych podzbiorów zbioru liczb wymiernych. Zresztą musi tak być, bo do zbioru pustego nic nie należy, (w szczególności \(\displaystyle{ \emptyset\notin \emptyset}\) :mrgreen:).
a4karo
Użytkownik
Użytkownik
Posty: 22173
Rejestracja: 15 maja 2011, o 20:55
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 38 razy
Pomógł: 3748 razy

Re: Aksjomat wyboru

Post autor: a4karo »

Ale nie w tym miejscu.
Jeżeli dla każdego `x\in X` zachodzi ` \neg xRx`, to zbiór \(\displaystyle{ B=\left\{ A\subset X\Biggl| \ \ A\times A\subset R \right\}=\{\emptyset\}}\)
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: Aksjomat wyboru

Post autor: Jakub Gurak »

Też co najmniej dwuelementowa relacja antysymetryczna podobnie w niej zawrzeć można tylko kwadrat kartezjański zbioru pustego.

Ale w jednoelementowym zbiorze uporządkowanym jego jedyny element jest jego elementem maksymalnym, taki oczywisty fakt w nieoczywistej formie trzeba wykorzystać tutaj.

Nie spodziewałem się tego, jak się tym zajmowałem na intuicje mi się wydawało, że w niepustej relacji zawsze się zmieści kwadrat kartezjański, choćby bardzo mały, ale miałem podejście "ciągłe", nie dyskretne. Teraz widzę, że ten fakt nie jest taki całkiem naturalny, np. można rozwažyć relacje: prosta pozioma(kwadraty kartezjańskie jednopunktowe), prosta pionowa(podobnie kwadraty jednopunktowe), przekątna (również). Nie jest już dla mnie to takie naturalne .

Dodano po 19 godzinach 45 minutach 37 sekundach:
Jakub Gurak pisze: 7 gru 2020, o 22:05 Też co najmniej dwuelementowa relacja antysymetryczna podobnie w niej zawrzeć można tylko kwadrat kartezjański zbioru pustego.
Tu pomyłka z mojej strony, jeśli rozważymy relację \(\displaystyle{ R}\) która jest podzbiorem przekątnej co najmniej dwuelementowym, to jest ona antysymetryczna, i jeśli \(\displaystyle{ \left( x,x\right) \in R}\), to dla \(\displaystyle{ \left\{ x\right\}}\) , mamy \(\displaystyle{ \left\{ x\right\} \times \left\{ x\right\} \subset R}\), co więcej takich zbiorów jednoelementowych może być więcej.
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: Aksjomat wyboru

Post autor: Jakub Gurak »

Mamy tez taki fakt, że jeśli mamy dwa zbiory, i dowolną relację pomiędzy nimi, to istnieje maksymalny prostokąt kartezjański zawarty w tej relacji, który to fakt udowodniłem TU.

interesuje mnie pewien problem, którego chyba nie dam rady sam rozwiązać, bo mam kiepską wyobraźnię przestrzenną. Otóż:
Rozważmy podzbiór \(\displaystyle{ A}\) przestrzeni trójwymiarowej \(\displaystyle{ \RR^3}\), mający dodatnią objętość, tzn. zawierający pewną kostkę otwartą, czyli iloczyn kartezjański pewnych trzech przedziałów otwartych, i jeszcze ograniczony, czyli zawarty w pewnej kostce, poza tym dowolny. Podejrzewam, ale nie dam rady sam tego udowodnić, ze względu na to, że mam kiepską wyobraźnię przestrzenną, ale podejrzewam, że wtedy istnieje maksymalna, względem inkluzji, kula otwarta( czyli kula bez sfery) zawarta w tym podzbiorze \(\displaystyle{ A}\) przestrzeni \(\displaystyle{ \RR^3}\). Pomoże ktoś :?:
a4karo
Użytkownik
Użytkownik
Posty: 22173
Rejestracja: 15 maja 2011, o 20:55
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 38 razy
Pomógł: 3748 razy

Re: Aksjomat wyboru

Post autor: a4karo »

FYI Mieć dodatnią objętość to nie to samo co zawierać kostkę otwartą. Takie przykłady robi się na pierwszym roku. (zbiór Cantora, dywan Sierpińskiego, kostka Mengera).
Możesz tez z sześcianu usunąć punkty o wszystkich współrzędnych wymiernych i dalej dostaniesz zbiór o dodatniej objętości
Zatem to, co napisałeś nie jest prawdą
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: Aksjomat wyboru

Post autor: Dasio11 »

Odpowiedź jest twierdząca nawet bez założenia o dodatniej objętości, wystarczy ograniczoność i niepuste wnętrze. I nawiasem mówiąc - zbiór Cantora ma zerową objętość (jednowymiarową), a dodatnią miałby na przykład tłusty zbiór Cantora.

Dowód: niech

\(\displaystyle{ R = \sup \{ r > 0 : A \text{ zawiera kulę otwartą o promieniu } r \}}\)

i weźmy ciąg kul \(\displaystyle{ B(x_n, r_n) \subseteq A}\) o promieniach dążących do \(\displaystyle{ R}\). Ciąg \(\displaystyle{ x_n}\) jest ograniczony, więc ma podciąg zbieżny do pewnego \(\displaystyle{ x \in \RR^3}\), a dla uproszczenia notacji możemy przyjąć, że owym podciągiem jest sam \(\displaystyle{ x_n}\). Pokażemy, że \(\displaystyle{ B(x, R)}\) jest szukaną maksymalną kulą zawartą w \(\displaystyle{ A}\).

Wystarczy wykazać zawieranie \(\displaystyle{ B(x, R) \subseteq A}\), bo większa kula o tej własności w oczywisty sposób istnieć nie może. Weźmy więc dowolny \(\displaystyle{ y \in B(x, R)}\) i dla \(\displaystyle{ \varepsilon := R - d(x, y) > 0}\) znajdźmy takie \(\displaystyle{ n}\), takie że \(\displaystyle{ d(x_n, x) < \frac{\varepsilon}{2}}\) i \(\displaystyle{ r_n > R - \frac{\varepsilon}{2}}\). Wtedy

\(\displaystyle{ d(x_n, y) \le d(x_n, x) + d(x, y) < \frac{\varepsilon}{2} + R - \varepsilon = R - \frac{\varepsilon}{2} < r_n}\),

czyli \(\displaystyle{ y \in B(x_n, r_n) \subseteq A}\) i stąd \(\displaystyle{ y \in A}\).
Awatar użytkownika
timon92
Użytkownik
Użytkownik
Posty: 1654
Rejestracja: 6 paź 2008, o 16:47
Płeć: Mężczyzna
Lokalizacja: Katowice
Podziękował: 7 razy
Pomógł: 472 razy

Re: Aksjomat wyboru

Post autor: timon92 »

Dasio11 pisze: 24 gru 2021, o 11:50nawet bez założenia o dodatniej objętości, wystarczy ograniczoność i niepuste wnętrze
:?: :?: :?: przecież niepuste wnętrze implikuje dodatnią objętość
a4karo
Użytkownik
Użytkownik
Posty: 22173
Rejestracja: 15 maja 2011, o 20:55
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 38 razy
Pomógł: 3748 razy

Re: Aksjomat wyboru

Post autor: a4karo »

Dasio11 pisze: 24 gru 2021, o 11:50 Odpowiedź jest twierdząca nawet bez założenia o dodatniej objętości, wystarczy ograniczoność i niepuste wnętrze. I nawiasem mówiąc - zbiór Cantora ma zerową objętość (jednowymiarową), a dodatnią miałby na przykład tłusty zbiór Cantora.
Tak, to prawda.
Ale trudno mi wyobrazić sobie pasjonata teorii mnogości, który świeżo ukończył studia i nie zna takich przykładów.
Jan Kraszewski
Administrator
Administrator
Posty: 34125
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 3 razy
Pomógł: 5192 razy

Re: Aksjomat wyboru

Post autor: Jan Kraszewski »

timon92 pisze: 24 gru 2021, o 22:26przecież niepuste wnętrze implikuje dodatnią objętość
A jak zbiór ma niepuste wnętrze i jest niemierzalny?

JK
Awatar użytkownika
timon92
Użytkownik
Użytkownik
Posty: 1654
Rejestracja: 6 paź 2008, o 16:47
Płeć: Mężczyzna
Lokalizacja: Katowice
Podziękował: 7 razy
Pomógł: 472 razy

Re: Aksjomat wyboru

Post autor: timon92 »

@up racja, zapomniałem, że zbiory mogą być niemierzalne :oops:
ODPOWIEDZ