Logika i teoria mnogości/Wykład 11: 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

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,⊑)$ jest dobrym porządkiem, jeśli

• jest porządkiem liniowym,

• każdy niepusty podzbiór $A$ zawiera element najmniejszy względem $⊑$.

Mówimy wtedy, że zbiór $A$ jest dobrze uporządkowany przez $⊑$.

Istnienie zbiorów dobrze uporządkowanych nie jest nowością. Zdefiniowany w Wykładzie 7 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,⊑)$ i dla dowolnego zbioru $B\subset A$ zbiór ten jest dobrze uporządkowany przez relację $⊑\cap B\times B$.

Dowód

Relacja $⊑\cap B\times B$ to relacja $⊑$ zawężona do elementów zbioru $B$. Mamy, dla każdego $a,b\in B$

$a⊑b⟺a(⊑\cap B\times B)b.$

Oczywistym wnioskiem jest, że zbiór $B$ jest uporządkowany liniowo przez $⊑\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 $⊑$. Ponieważ $C\subset B$, to ten sam element jest elementem najmniejszym w $C$ względem $⊑\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. 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

Tą część wykładu zaczniemy od przytoczenia aksjomatu wyboru w postaci w jakiej został wprowadzony w Wykładzie 4.

Aksjomat Wyboru. Następująca formuła jest prawdziwa

$\mathrm{\forall }x(\mathrm{\varnothing }\notin x\wedge \mathrm{\forall }y\mathrm{\forall }z(z\in x\wedge y\in x)⟹(z=y\vee z\cap y=\mathrm{\varnothing }))⟹\mathrm{\exists }w\mathrm{\forall }v(v\in x⟹\mathrm{\exists }uv\cap w=\{u\})$

Aksjomat ten mówi, że jeśli $x$ jest rodziną niepustych, parami rozłącznych zbiorów to istnieje zbiór mający z każdym elementem $x$ dokładnie jeden element wspólny. Zbiór $w$, którego istnienie gwarantuje aksjomat wyboru "wybiera" z każdego elementu rodziny dokładnie jeden element. Obrazek 3.1 Zbiory jako pionowe, nieregularne obszary, zbiór wybierający jako poziomy zbiór przecinający każdy z nich na dokładnie jednym elemencie

W dalszej części wykładu prezentujemy parę twierdzeń równoważnych aksjomatowi wyboru. To znaczy, że na gruncie aksjomatyki ZF, bez aksjomatu wyboru, założenie prawdziwości któregokolwiek z tych twierdzeń implikuje prawdziwość aksjomatu wyboru i vice versa. Bardzo istotną częścią dowodów jest wykazanie, że twierdzenia te są dokładnie równoważne aksjomatowi wyboru na gruncie ZF. Na gruncie aksjomatyki ZFC twierdzenia te dają się udowodnić przy użyciu aksjomatu wyboru.

Aby wykazać równoważność między aksjomatem wyboru a poniższymi twierdzeniami pokażemy, że każde twierdzenie implikuje następne i że ostatnie implikuje aksjomat wyboru. Jest to najprostszy sposób na wykazanie równoważności.

Twierdzenia dotyczące zbiorów

Pierwsze, równoważne aksjomatowi wyboru, twierdzenie mówi o istnieniu funkcji wybierającej. W aksjomacie wyboru, z rodziny zbiorów wybieraliśmy elementy przez utworzenie zbioru. Aby możliwe było wybranie dokładnie jednego elementu z każdego zbioru niezbędne było założenie o rozłączności tych zbiorów. Poniższe twierdzenie mówi o istnieniu funkcji wybierającej elementy ze zbiorów.

Twierdzenie 3.1.

Dla dowolnej rodziny niepustych zbiorów istnieje funkcja, która każdemu zbiorowi w tej rodzinie przyporządkowuje któryś z jego elementów. Formalnie

$\mathrm{\forall }x\mathrm{\varnothing }\notin x⟹\mathrm{\exists }ff:x\to \bigcup x\wedge (\mathrm{\forall }yy\in x⟹f(y)\in y)$

Poniżej przedstawiamy dowód, na gruncie ZF, że aksjomat wyboru implikuje powyższe twierdzenie.

Dowód

Aksjomat wyboru implikuje Twierdzenie 3.1 (patrz twierdzenie 3.1.) Ustalmy dowolny, nie zawierający zbioru pustego, zbiór $x$. Skonstruujemy zbiór $x_1$ do którego stosować będziemy aksjomat wyboru. Zbiór

$x_1=\{\{y\}\times y:y\in x\}$

jest rodziną zbiorów parami rozłącznych - elementy pochodzące z różnych zbiorów $x$ różnią się w $x_1$ na pierwszej współrzędnej. Do zbioru $x_1$ stosujemy aksjomat wyboru i otrzymujemy zbiór $w\subset x\times \bigcup x$. Ponieważ z każdego zbioru $x_1$ wybraliśmy dokładnie jeden element, to $w$ jest funkcją z $x$ do $\bigcup x$. Definicja $x_1$ gwarantuje również, że $w(y)\in y$ dla każdego $y\in x$. Wnioskujemy, że $w$ może być wzięte jako $f$ i że aksjomat wyboru implikuje Twierdzenie 3.1 (patrz twierdzenie 3.1.)

Kolejny fakt, równoważny aksjomatowi wyboru, przedstawiamy w formie ćwiczenia:

Ćwiczenie 3.1

{{{3}}}

Twierdzenia dotyczące porządków

Felix Hausdorff (1868-1942)
Zobacz biografię

Kolejne dwa twierdzenia dotyczą częściowych porządków. Pierwsze z

nich gwarantuje istnienie maksymalnych łańcuchów

Twierdzenie 3.2. [Zasada maksimum Felixa Hausdorff'a]

W każdym zbiorze częściowo uporządkowanym istnieje maksymalny, pod względem inkluzji, łańcuch.

Zgodnie z przyjętą strategią postępowania wykażemy, że Twierdzenie 3.1 (patrz twierdzenie 3.1.) implikuje zasadę maksimum Felixa Hausdorffa.

Dowód

Twierdzenie 3.1 (patrz twierdzenie 3.1.) implikuje zasadę maksimum Felixa Hausdorffa. Dowód tej implikacji opiera się na Twierdzeniu Bourbakiego-Witta z Wykładu 10. Ustalmy dowolny zbiór częściowo uporządkowany $(A,⊑)$. Jeśli $A=\mathrm{\varnothing }$ to zbiór ten posiada dokładnie jeden łańcuch i fakt jest dowiedziony. Jeśli $A\ne \mathrm{\varnothing }$, oznaczmy przez $(B,\subset )$ zbiór częściowo uporządkowany składający się z łańcuchów w $(A,⊑)$ uporządkowanych przez inkluzję

$B=\{C\subset A:C$ jest uporządkowany liniowo przez $⊑\}$

Zbiór częściowo uporządkowany $(B,\subset )$ jest łańcuchowo zupełny. Aby to pokazać ustalmy dowolny, uporządkowany liniowo przez inkluzję, zbiór $D\subset B$. Jeśli $\bigcup D$ należy do $B$ to jest to niewątpliwie supremum zbioru $D$. Aby wykazać że $\bigcup D$ jest elementem $B$ należy wykazać, że jest on uporządkowany liniowo przez $⊑$. Weźmy dwa elementy $\bigcup D$ - $x$ i $y$. Istnieje $C_x\in D$ i $C_y\in D$ takie, że $x\in C_x$ a $y\in C_y$. Ponieważ $D$ jest łańcuchem to, bez straty ogólności, możemy założyć, że $C_x\subset C_y$. Wtedy zarówno $x$, jak i $y$ należą do $C_y$ i ponieważ $C_y\in B$ wnioskujemy, że $x$ i $y$ są porównywalne. Wykazaliśmy, że dowolne dwa elementy $\bigcup D$ są porównywalne, czyli, że $\bigcup D$ jest uporządkowany liniowo przez $⊑$.

Na mocy Twierdzenia 3.1 (patrz twierdzenie 3.1.) definiujemy funkcję wyboru $f$ dla zbioru ${𝒫}(A)\setminus \{\mathrm{\varnothing }\}$ - zwracającą, dla każdego niepustego podzbioru $A$, jego element. Twierdzenie Bourbakiego-Witta będziemy stosować do funkcji $g$ przeprowadzającej $B$ w $B$ i zdefiniowanej następująco:

Parser nie mógł rozpoznać (nieznana funkcja „\begin{array}”): {\displaystyle g(C)=\left\{ \begin{array}{ll} C\cup \{f(C')\}& \quad \textrm{jeśli } C', \textrm{zbiór elementów porównywalnych z każdym elementem } C, \textrm{jest niepusty}\\ C & \quad \textrm{w przeciwnym przypadku} \end{array}}

Funkcja $g$ dostaje, jako argument łańcuch w $(A,⊑)$ oznaczony przez $C$ i przy pomocy funkcji $f$ rozszerza (jeśli jest to możliwe) $C$ o jeden element porównywalny ze wszystkimi elementami $C$ otrzymując w ten sposób nowy, większy łańcuch.

Zbiór $(B,\subset )$ i funkcja $g$ spełniają założenia Twierdzenia Bourbakiego-Witta i, na jego mocy, istnieje punkt stały $g$, czyli zbiór $D$ taki, że $g(D)=D$. To gwarantuje, że zbiór $D^{\prime }$ elementów porównywalnych z każdym elementem $D$ jest pusty, czyli, że $D$ jest maksymalnym pod względem inkluzji łańcuchem w $A$.

Równoważną wersję zasady Felixa Hausdorffa pozostawiamy jako ćwiczenie.

Ćwiczenie 3.2

{{{3}}}

Kolejne z równoważnych aksjomatowi wyboru twierdzeń nosi nazwę Lematu Maxa Augusta Zorn'a. Nazwa ta ma korzenie historyczne i dlatego pozostawiamy ją w tym brzmieniu.

Max August Zorn (1906-1993)
Zobacz biografię

Twierdzenie 3.3. [Lemat Maxa Augusta Zorn'a]

Jeśli w pewnym zbiorze częściowo uporządkowanym każdy łańcuch jest ograniczony od góry to istnieje w nim element maksymalny.

Dowodzimy kolejną implikację

Dowód

Zasada maksimum Felixa Hausdorffa implikuje Lemat Maxa Augusta Zorn'a. Dowód tej implikacji jest bardzo prosty. Wybierzmy dowolny zbiór częściowo uporządkowany spełniający założenia lematu Maxa Augusta Zorn'a, czyli taki, że każdy łańcuch jest w nim ograniczony od góry. Na mocy zasady maksimum Felixa Hausdorffa istnieje w tym zbiorze łańcuch maksymalny pod względem inkluzji. Łańcuch ten posiada ograniczenie górne, które musi być elementem łańcucha i równocześnie elementem maksymalnym zbioru. Jeśliby tak nie było, to dodając element istotnie większy od tego ograniczenia do łańcucha danego przez zasadę maksimum Hausdorff'a uzyskalibyśmy łańcuch istotnie większy pod względem inkluzji

Kolejne ćwiczenie mówi o istnieniu maksymalnego antyłańcucha.

Ćwiczenie 3.3

{{{3}}}

Poniższe ćwiczenie dotyczy rozszerzeń porządków.

Ćwiczenie 3.4

{{{3}}}

W Wykładzie 5 pokazaliśmy, że dla dowolnej relacji istnieje najmniejsza relacja równoważności zawierająca tą relację. W poniższym ćwiczeniu pokażemy, że dla niektórych relacji istnieje maksymalna, pod względem inkluzji, relacja równoważności zawarta w nich

Ćwiczenie 3.5

{{{3}}}

Kolejny warunek równoważny dotyczy zbiorów dobrze uporządkowanych.

Twierdzenie Ernsta Zermelo

Ernst Friedrich Ferdinand Zermelo (1871-1953)
Zobacz biografię

Twierdzenie Zermelo jest jedną z równoważnych postaci aksjomatu

wyboru w którą wyjątkowo trudno uwierzyć.

Twierdzenie 3.4. [Zermello]

Dla każdego zbioru istnieje relacja, która jest dobrym porządkiem na tym zbiorze.

Kolejny dowód to

Dowód

Lemat Maxa Augusta Zorn'a implikuje Twierdzenie Ernsta Zermelo. Ustalmy dowolny zbiór niepusty $A$ (dla zbioru pustego porządek pusty porządkuje go dobrze). Rozważmy zbiór $B$ składający się z podzbiorów $A$ które mogą być dobrze uporządkowane, wraz z dobrymi porządkami

$B=\{(C,⊑):C\subset A\wedge ⊑$ jest dobrym porządkiem na Parser nie mógł rozpoznać (błąd składni): {\displaystyle C}\}. }

i zdefiniujmy relację na elementach $B$ w następujący sposób

Parser nie mógł rozpoznać (nieznana funkcja „\begin{array}”): {\displaystyle \begin{array}{ll} \displaystyle & c\forall d\ c\in C \land d\in C \land c\sqsubseteq d\implies c\sqsubseteq' d, (C,\sqsubseteq) \preccurlyeq (C',\sqsubseteq') \\ \iff & C\subset C' \land \left\{\begin{array}{l}\forall c \forall d\ (c\in C\land d\in C) \implies (c\sqsubseteq d \iff c\sqsubseteq' d) \textrm{ oraz }\\ \forall c \forall d\ (c\in C\land d\in C'\setminus C) \implies c\sqsubseteq' d \end{array} \right \end{array}}

czyli dwa elementy $B$ są porównywalne wtedy i tylko wtedy, jeśli zbiory na których są określone są porównywalne w sensie inkluzji i porządek zdefiniowany na większym zbiorze jest rozszerzeniem porządku zdefiniowanego na mniejszym przez dodanie elementów większych od wszystkich zastanych. Aby zastosować Lemat Maxa Augusta Zorn'a do zbioru częściowo uporządkowanego $(B,\preccurlyeq )$ musimy wykazać, że każdy łańcuch w tym zbiorze ma ograniczenie górne.

Niech $D\subset B$ będzie łańcuchem w sensie $\preccurlyeq$. Zdefiniujmy $C_0$ jako unię wszystkich pierwszych współrzędnych elementów $D$ i ${⊑}_0$ jako unię drugich współrzędnych elementów $D$. Niewątpliwie $C_0\subset A$. Ponieważ $D$ jest łańcuchem w sensie $\preccurlyeq$ to relacja ${⊑}_0$ jest porządkiem liniowym na $C_0$. Aby wykazać, że ${⊑}_0$ jest dobrym porządkiem na $C_0$ ustalmy dowolny $E\subset C_0$. Niewątpliwie istnieje element $(C,⊑)\in D$ taki, że $E\cap C\ne \mathrm{\varnothing }$. Ponieważ $(C,⊑)\in B$ to $C$ jest dobrze uporządkowany przez $⊑$ i w związku z tym $E\cap C$ posiada element najmniejszy w $C,⊑)$ - oznaczmy go przez $x$. Element $x$, będzie również najmniejszym elementem $E$ w $C_0$. Aby to wykazać ustalmy $y\in E$. Jeśli $y\in C$ to niewątpliwie $x⊑y$ i w związku z tym $x{⊑}_{0}y$. Jeśli $y\notin C$ to $y\in C^{\prime }\setminus C$ dla jakiegoś $(C^{\prime },{⊑}^{\prime })\in D$. Ponieważ $D$ jest łańcuchem wnioskujemy, że $C\subset C^{\prime }$ i na mocy definicji $\preccurlyeq$, że $x{⊑}^{\prime }y$, czyli $x{⊑}_{0}y$ co należało wykazać.

Stosując Lemat Maxa Augusta Zorn'a wnioskujemy, że w zbiorze częściowo uporządkowanym $(B,\preccurlyeq )$ istnieje element maksymalny $(D,⊑)$. Jeśli $D=A$ to $⊑$ jest wymaganym dobrym porządkiem na $A$. Aby wykazać że tak musi być załóżmy niewprost, że $D⊊A$, czyli, że istnieje $d\in A\setminus D$. Wtedy zbiór $D\cup \{d\}$ wraz z dobrym porządkiem ${⊑}^{\prime }$ zdefiniowanym jako

$a{⊑}^{\prime }b⟺b=d\vee (a\in D\wedge b\in D\wedge a⊑b)$

jest większy w sensie relacji $\preccurlyeq$, co przeczy maksymalności $D$. Uzyskana w dowodzie niewprost sprzeczność kończy rozumowanie.

Twierdzenie Ernsta Zermelo jest sprzeczne z intuicją wielu matematyków. Gwarantuje ono między innymi istnienie dobrego porządku na liczbach rzeczywistych -- takiego, liniowego, uporządkowania liczb rzeczywistych w którym każdy zbiór posiada element najmniejszy. Porządek taki jest trudnym do wyobrażenia konceptem matematycznym.

Aby zamknąć ciąg rozumowań wystarczy wykazać, że Twierdzenie Zermello implikuje aksjomat wyboru.

Dowód

Twierdzenie Zermello implikuje akjomat wyboru. Niech $x$ będzie dowolnym zbiorem spełniającym założenia aksjomatu wyboru, to znaczy takim, że $\mathrm{\varnothing }\notin x$ i że wszystkie elementy $x$ są parami rozłączne. Niech $⊑$ będzie istniejącym, na podstawie Twierdzenia Zermello, dobrym uporządkowaniem zbioru $\bigcup x$. Zbiór wybierający po jednym elemencie z każdego elementu $x$ otrzymujemy stosując zasadę wycinania do $\bigcup x$

$w=\{y\in \bigcup x:\mathrm{\exists }zy\in z\in x\wedge y$ jest najmniejszym elementem $z$ względem relacji $⊑\}.$

Zbiór $w$ posiada po dokładnie jednym elemencie wspólnym z każdym zbiorem $z\in x$ - jest to element najmniejszy w $z$ względem dobrego uporządkowania $\bigcup x$.

Nasze rozumowanie wykazało, że wszystkie powyższe fakty są równoważne na gruncie ZF. Jak wspomnieliśmy na początku aksjomat wyboru jest kontrowersyjnym aksjomatem. Niektóre z równoważnych mu stwierdzeń są intuicyjnie oczywiste inne przeczą intuicji. Podsumujemy rozdział żartem autorstwa Jerrego Bona:

The Axiom of Choice is obviously true; the Well Ordering Principle is obviously false; and who can tell about Max August Zorn's Lemma? (Aksjomat wyboru jest oczywiście prawdziwy; twierdzenie Ernsta Zermelo jest oczywiście fałszem; lemat Zorn'a kto wie?)

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 9 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\to A$. Ponieważ nie istnieje bijekcja pomiędzy $n$ a $A$ wnioskujemy, że $\overrightarrow{f}(n)⊊A$, czyli, że istnieje $a\in A\setminus \overrightarrow{f}(n)$. Zdefiniujmy $f^{\prime }:n^{\prime }\to A$ jako

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \displaystyle f'(m)=\left\{\aligned f(m)\\a\endaligned \right}

Funkcja $f^{\prime }$ 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{\mathbb{N}}$.

Dowód 2

Dowód przy użyciu aksjomatu wyboru. Aby udowodnić istnienie iniekcji z $\mathbb{\mathbb{N}}$ w $A$ skorzystamy z Twierdzenia twierdzenie 3.1. równoważnego aksjomatowi wyboru. Zastosujmy je do zbioru ${𝒫}(A)\setminus \{\mathrm{\varnothing }\}$ dostając funkcję $e:{𝒫}(A)\setminus \{\mathrm{\varnothing }\}\to A$ taką, że $e(B)\in B$ dla każdego $B$ jeśli tylko $\mathrm{\varnothing }\ne B\subset A$. Aby udowodnić istnienie żądanej funkcji zastosujemy twierdzenie o definiowaniu przez indukcję. Dzięki temu twierdzeniu dostaniemy funkcję $h:\mathbb{\mathbb{N}}\times \{\mathrm{\varnothing }\}\to {𝒫}(A)$ taką, że

$h(0,\mathrm{\varnothing })=\{e(A)\}$

oraz

$h(n^{\prime },\mathrm{\varnothing })=h(n,\mathrm{\varnothing })\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⟺h(n^{\prime },\mathrm{\varnothing })\setminus h(n,\mathrm{\varnothing })=\{x\}$

Funkcja $f$ jest dobrze zdefiniowana ponieważ dla każdego $n$ zbiór $h(n^{\prime },\mathrm{\varnothing })\setminus h(n^{\prime },\mathrm{\varnothing })$ jest jednoelementowy (co gwarantuje definicja funkcji $e$). A jest iniekcją, ponieważ $h(m,\mathrm{\varnothing })\subset h(n,\mathrm{\varnothing })$ jeśli tylko $m\le n$.

Kolejną konsekwencję podajemy w formie ćwiczenia.

Ćwiczenie 4.1

{{{3}}}

Podsumowanie

W powyższym wykładzie przedstawiliśmy twierdzenia równoważne aksjomatowi wyboru i udowodniliśmy parę 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ą.

Bertrand Arthur William Russell (1872-1970)
Zobacz biografię

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.