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 \).
\( \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
\( h(0, \emptyset) = \{e(A)\} \)
oraz
\( h(n',\emptyset) = h(n,\emptyset)\cup \{e(A\setminus h(n))\}. \)
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 \).
Kolejną konsekwencję podajemy w formie ćwiczenia.
Ćwiczenie 4.1
Rozważmy przedział \( [-1,3] \) w zbiorze liczb rzeczywistych. Niech funkcja \( f:\mathcal{P}([-1,3]) \rightarrow \mathbb{R} \) będzie "miłą miarą zbiorów", jeśli:
\( 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:
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
\( f(\bigcup_r C_r) = \sum_r f(C_r) = \sum_r f(C), \)
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.