Zbiory dobrze uporządkowane. Lemat Kuratowskiego Zorna i twierdzenie Zermelo, przykłady
Wstęp
Poniższy wykład poświęcony jest konsekwencjom aksjomatu wyboru. Aksjomat wyboru jest niewątpliwie najbardziej kontrowersyjnym z aksjomatów ZFC. Wielu znanych matematyków poddawało go w wątpliwość. W chwili obecnej znakomita większość uważa, że aksjomat wyboru jest prawdziwy, nawet jeśli niektóre z jego konsekwencji są sprzeczne z intuicją.
W tym wykładzie przedstawiamy szereg twierdzeń, które są równoważne lub wynikają z aksjomatu wyboru. Zanim przejdziemy do wypowiedzi tych faktów, wprowadzimy jeszcze jeden koncept.
Zbiory dobrze uporządkowane
Zbiory dobrze uporządkowane
Definicja dobrego porządku nie zależy od aksjomatu wyboru. W aksjomatyce ZF istnieje wiele zbiorów dobrze uporządkowanych. Jednak w obecności aksjomatu wyboru zbiory dobrze uporządkowane nabierają zupełnie nowego znaczenia.
Definicja 2.1.
Częściowy porządek \( (A,\sqsubseteq) \) jest dobrym porządkiem, jeśli
jest porządkiem liniowym,
każdy niepusty podzbiór \( A \) zawiera element najmniejszy względem \( \sqsubseteq \).
Mówimy wtedy, że zbiór \( A \) jest dobrze uporządkowany przez \( \sqsubseteq \).
Istnienie zbiorów dobrze uporządkowanych nie jest nowością. Zdefiniowany w wykładzie 7 "Konstrukcja von Neumanna liczb naturalnych, twierdzenie o indukcji, zasady minimum, maksimum, definiowanie przez indukcje" zbiór liczb naturalnych jest dobrze uporządkowany na mocy dowiedzionych tam twierdzeń. Łatwo zauważyć, że również każda liczba naturalna \( n \) wraz z relacją inkluzji jest zbiorem dobrze uporządkowanym. Ogólnie, następujący fakt jest prawdziwy
Fakt 2.2.
Dla dowolnego dobrego porządku \( (A,\sqsubseteq) \) i dla dowolnego zbioru \( B\subset A \) zbiór ten jest dobrze uporządkowany przez relację \( \sqsubseteq\cap B\times B \).
Dowód
Relacja \( \sqsubseteq\cap B\times B \) to relacja \( \sqsubseteq \) zawężona do elementów zbioru \( B \). Mamy dla każdego \( a,b\in B \)
\( a\sqsubseteq b \iff a (\sqsubseteq\cap B\times B) b. \)
Oczywistym wnioskiem jest, że zbiór \( B \) jest uporządkowany liniowo przez \( \sqsubseteq\cap B\times B \). Pozostaje wykazać, że każdy podzbiór zbioru \( B \) ma element najmniejszy. Ustalmy dowolne \( C\subset B \), ponieważ \( B\subset A \) zbiór \( C \) jest również podzbiorem \( A \) i z definicji zbioru dobrze uporządkowanego wynika, że \( C \) posiada element najmniejszy względem \( \sqsubseteq \). Ponieważ \( C\subset B \), to ten sam element jest elementem najmniejszym w \( C \) względem \( \sqsubseteq\cap B\times B \), co kończy dowód faktu.
Dokładnej analizie własności zbiorów dobrze uporządkowanych jest poświęcony wykład 12 "Twierdzenie o indukcji. Liczby porządkowe. Zbiory liczb porządkowych. Twierdzenie o definiowaniu przez indukcje pozaskończoną". W dalszej części wykładu ograniczamy się do własności tych porządków bezpośrednio powiązanych z aksjomatem wyboru.
Aksjomat wyboru i twierdzenia mu równoważne
Twierdzenia wymagające aksjomatu wyboru
Twierdzenia wymagające aksjomatu wyboru
Wiele twierdzeń wymaga aksjomatu wyboru, choć założenie ich prawdziwości w ZF nie implikuje prawdziwości tego aksjomatu. W tej części wykładu przedstawimy kilka tego typu twierdzeń. Zwróćmy uwagę, że żadna z dostępnych w tej chwili technik dowodowych nie nadaje się do udowodnienia, że jakiś fakt jest słabszy od aksjomatu wyboru. Możemy pokazać, że jeśli aksjomat wyboru jest prawdą, to dane twierdzenie jest prawdziwe, ale nie możemy pokazać, że jeśli założymy dane twierdzenie, to aksjomat wyboru nie musi być prawdą. Nie jesteśmy w stanie zdecydować, czy aksjomat wyboru jest niezbędny do udowodnienia danego twierdzenia - tego typu dowody wykraczają poza zakres tego kursu i nie będą prezentowane.
Pierwszy z faktów, które będziemy dowodzić brzmi następująco:
Twierdzenie 4.1.
Dla dowolnego zbioru nieskończonego istnieje iniekcja ze zbioru liczb naturalnych w ten zbiór.
Dowód 1
Co możemy dowieść bez aksjomatu wyboru. Ustalmy dowolny zbiór nieskończony \( A \). Na mocy definicji z wykładu "Teoria mocy twierdzenie Cantora-Bernsteina, twierdzenie Cantora. Zbiory przeliczalne, zbiory mocy kontinuum" wiemy, że nie istnieje bijekcja między \( A \) a żadną liczbą naturalną. Pokażmy najpierw, że dla każdej liczby naturalnej \( n \) istnieje iniekcja z \( n \) do \( A \). Dowód przeprowadzamy przez indukcję na \( n \).
Jeśli \( n=0 \), to niewątpliwie istnieje iniekcja ze zbioru pustego w \( A \) - jest to funkcja pusta.
Załóżmy, że istnieje iniekcja \( f:n \rightarrow A \). Ponieważ nie istnieje bijekcja pomiędzy \( n \) a \( A \), wnioskujemy, że \( \vec{f}(n) ⊊ A \), czyli że istnieje \( a\in A\setminus \vec{f}(n) \). Zdefiniujmy \( f':n' \rightarrow A \) jako
\( \displaystyle f'(m)=\left\{\begin{array}{ll} f(m), & \quad \textrm{jeśli } m \in n, \\ a , & \quad \textrm{jeśli } m=n. \end {array} \right. \)
Funkcja \( f' \) jest iniekcją, co kończy dowód indukcyjny.
Wykazaliśmy jedynie, że dla każdej liczby naturalnej istnieje iniekcja z niej w \( A \). Nie udało nam się wykazać istnienia jednej funkcji dla całego zbioru \( \mathbb{N} \).
Dowód 2
Dowód przy użyciu aksjomatu wyboru. Aby udowodnić istnienie iniekcji z \( \mathbb{N} \) w \( A \), skorzystamy z Twierdzenia twierdzenie 3.1. równoważnego aksjomatowi wyboru. Zastosujmy je do zbioru \( \mathcal{P}(A)\setminus \{\emptyset\} \), dostając funkcję \( e:\mathcal{P}(A)\setminus \{\emptyset\} \rightarrow A \) taką, że \( e(B)\in B \) dla każdego \( B \), jeśli tylko \( \emptyset \neq B \subset A \). Aby udowodnić istnienie żądanej funkcji, zastosujemy twierdzenie o definiowaniu przez indukcję. Dzięki temu twierdzeniu dostaniemy funkcję \( h: \mathbb{N}\times\{\emptyset\} \rightarrow
\mathcal{P}(A) \) taką, że
Jest to funkcja, która każdej liczbie naturalnej przyporządkowuje zbiór o jeden element większy niż przyporządkowany poprzedniej liczbie naturalnej. Aby otrzymać żądaną iniekcję wystarczy zdefiniować:
\( f(n) = x \iff h(n',\emptyset)\setminus h(n,\emptyset) = \{x\}. \)
Funkcja \( f \) jest dobrze zdefiniowana, ponieważ dla każdego \( n \) zbiór \( h(n',\emptyset)\setminus h(n',\emptyset) \) jest jednoelementowy (co gwarantuje definicja funkcji \( e \)). A jest iniekcją, ponieważ \( h(m,\emptyset)\subset h(n,\emptyset) \), jeśli tylko \( m\leq n \).
dla każdego zbioru jego miara jest większa lub równa \( 0 \) i \( f([0,1])=1 \),
jeśli zbiór \( A \) ma miarę \( f(A) \) to \( f(\{x+r\,:\, x\in A\})=f(A) \) dla dowolnego \( r \) - to znaczy, że przesunięcie zbioru o wektor nie zmienia jego miary,
jeśli \( A_0, A_1,\dotsc \) są zbiorami parami rozłącznymi, to suma tych zbiorów ma miarę równą sumie miar
\( f(\bigcup_i A_i) =\sum_i f(A_i), \)
to znaczy, że sumowanie zbiorów rozłącznych zachowuje miarę.
Wykaż, że nie istnieje miła miara zbiorów.
Podpowiedź
Połóż dwie liczby w relacji ze sobą jeśli ich różnica jest wymierna.
Podpowiedź
Wybierz po jednym reprezentancie z każdej klasy równoważności i przesuń go o wektor.
Rozwiązanie
Załóżmy, niewprost, że istnieje miła miara \( f \). Zdefiniujmy relację równoważności \( \,\rho\, \) na zbiorze \( [0,1] \) w następujący sposób
\( x\,\rho\, y \iff x-y\in\mathbb{Q}. \)
Niewątpliwie relacja \( \,\rho\, \) jest relacją równoważności:
\( x\,\rho\, x \) ponieważ \( x-x=0\in\mathbb{Q} \),
\( x\,\rho\, y \Longrightarrow y\,\rho\, x \) ponieważ, jeśli \( x-y\in\mathbb{Q} \) to również \( y-x = -(x-y)\in\mathbb{Q} \),
\( x\,\rho\, y \land y\,\rho\, z \Longrightarrow x\,\rho\, z \) ponieważ jeśli \( x-y\in \mathbb{Q} \) i \( y-z\in \mathbb{Q} \), to również \( x-z = (x-y)+(y-z)\in\mathbb{Q} \).
W związku z tym zbiór \( [0,1] \) podzielony jest na klasy równoważności i, na mocy aksjomatu wyboru, możemy wybrać zbiór \( C \) posiadający po jednym elemencie z każdej klasy równoważności. Rozważmy przeliczalną rodzinę zbiorów \( \{C_r\} \), gdzie \( r \) jest liczbą wymierną z przedziału \( [-1,1] \), a zbiór \( C_r \) jest translacją zbioru \( C \) o liczbę \( r \)
\( C_r=\{c+r\,:\, c\in C\}. \)
Ponieważ każdy element zbioru \( [0,1] \) jest odległy o liczbę wymierną od jakiegoś elementu \( C \) (ponieważ jest z nim w tej samej klasie równoważności) i ponieważ ta odległość nie może być większa niż \( 1 \), to
\( [0,1] \subset \bigcup_r C_r \subset [-1,2], \)
czyli miara zbioru \( \bigcup_r C_r \) musi być pomiędzy \( f([0,1])=1 \), a \( f([-1,2])\leq 3 \). Ale, z założenia o mierze \( f \) mamy \( f(C) = f(C_r) \) dla każdego \( r \). Oraz
skąd wnioskujemy, że \( f(\bigcup_r C_r) \) musi być równe zero (w przeciwnym przypadku suma po prawej stronie równości byłaby nieskończona) i w związku z tym również \( \sum_r f(C_r) = 0 \), czyli zbiór \( C \) ma miarę \( 0 \), co jest żądaną sprzecznością. Skonstruowany przez nas zbiór \( C \) nazywa się, od nazwiska pomysłodawcy, zbiorem Vitaliego.
Podsumowanie
Podsumowanie
W powyższym wykładzie przedstawiliśmy twierdzenia równoważne aksjomatowi wyboru i udowodniliśmy kilka jego konsekwencji. Aksjomat wyboru jest kontrowersyjnym aksjomatem. Przyjęcie go, pociąga za sobą nieintuicyjne konsekwencje. Zakładając aksjomat wyboru, możemy wykazać, że zbiór liczb rzeczywistych daje się uporządkować w taki sposób, że każdy jego podzbiór ma element najmniejszy. Kolejną nieintuicyjną konsekwencją jest wykazany przez Stefana Banacha i Alfreda Tarskiego paradoksalny rozkład trójwymiarowej kuli na sześć części, z których, za pomocą obrotów i translacji, możemy skleić dwie kule identyczne z pierwszą.
Z drugiej strony, wiele intuicyjnych faktów wymaga aksjomatu wyboru lub jednej z jego słabszych wersji. Twierdzenie, że jeśli zbiór jest nieskończony, to istnieje iniekcja liczb naturalnych w ten zbiór, jest intuicyjnym faktem. Bertrand Russell powiedział o aksjomacie wyboru:
The Axiom of Choice is necessary to select a set from an infinite number of socks, but not an infinite number of shoes (Aksjomat wyboru jest niezbędny, aby wybrać zbiór z nieskończonej ilości skarpet, ale nie z nieskończonej ilości butów).
Znaczenie tego cytatu powinno być jasne. Jesteśmy w stanie wybrać po jednym bucie z nieskończonego zbioru par mówiąc "wybierzmy buty lewe". Nie jesteśmy w stanie przeprowadzić tego rozumowania, jeśli byty występujące w zbiorach są identyczne.