Aksjomat wyboru

Ten rozdział poświęcony jest konsekwencjom aksjomatu wyboru. Jest to aksjomat, który wywołał dużą ilość kontrowersji. 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ą nieintuicyjne.

W tym rozdziale przedstawiamy szereg twierdzeń, które są równoważne lub wynikają z aksjomatu wyboru. Zanim przejdziemy do wypowiedzi tych faktów, wprowadzimy jeszcze jeden termin.

Dobre uporządkowanie

Zbiór uporządkowany [math]\left( X, \le \right)[/math] nazywamy zbiorem dobrze uporządkowanym, gdy każdy niepusty podzbiór [math]X[/math] ma element najmniejszy względem rozpatrywanego porządku [math]\le[/math]. Mówimy wtedy, że zbiór [math]X[/math] jest dobrze uporządkowany przez [math]\le[/math], oraz, że [math]\le[/math] jest dobrym porządkiem na zbiorze [math]X[/math].

Przykładem zbioru dobrze uporządkowanego może być [math]\mathbb{N}[/math] z naturalnym porządkiem. Zasada minimum mówi, że każdy niepusty podzbiór [math]\mathbb{N}[/math] ma liczbę najmniejszą, a więc [math]\mathbb{N}[/math] jest dobrze uporządkowany.

Fakt: Każdy zbiór dobrze uporządkowany jest również liniowo uporządkowany.

Dowód:

Niech [math]\left( X, \le\right)[/math] będzie zbiorem dobrze uporządkowanym. Pokażemy, że jest również zbiorem liniowo uporządkowanym przez [math]\le[/math]. Jeśli [math]X[/math] jest pusty lub jednoelementowy, to jest liniowo uporządkowany, W przeciwnym wypadku istnieją co najmniej dwa elementy [math]X[/math]. Weźmy więc dowolne dwa różne elementy [math]X[/math] - [math]x[/math] i [math]y[/math]. Rozważmy [math]\left\{ x,y\right\}[/math]. Jest to dwuelementowy podzbiór [math]X[/math]. A ponieważ [math]X[/math] jest dobrze uporządkowany, to istnieje element najmniejszy [math]a\in\left\{ x,y\right\}[/math]. Jeśli [math]a=x[/math], to [math]x\lt y[/math]. W przeciwnym przypadku [math]a=y[/math], i wtedy [math]y\lt x[/math]. A więc elementy [math]x[/math] i [math]y[/math] są porównywalne. Z dowolności wyboru takich elementów, otrzymujemy, że [math]X[/math] jest liniowo uporządkowany przez [math]\le[/math].[math]\square[/math]

Aksjomat wyboru

Zaczniemy od przytoczenia aksjomatu wyboru:

Dla dowolnej rodziny zbiorów [math]\mathbb{X}[/math] niepustych i rozłącznych to aksjomat wyboru głosi, że istnieje selektor tej rodziny zbiorów, tzn. taki zbiór [math]S[/math], że:

dla dowolnego zbioru [math]A\in \mathbb{X} : \ \ A \cap S=\left\{ a\right\}.[/math]

tzn. selektor to zbiór [math]S[/math], który ma po dokładnie jednym elemencie wspólnym z każdym zbiorem tej rodziny.

Intuicyjnie to znaczy, że mając rodzinę rozłącznych zbiorów możemy utworzyć zbiór wybierając po jednym elemencie z każdego zbioru.

Będziemy zmierzać do dowodu twierdzenia Zermelo, że każdy zbiór da się dobrze uporządkować. Poza tym dowodem będziemy prezentować (na razie) tylko krótkie, proste dowody.

Twierdzenia dotyczące zbiorów

Pierwsze równoważne aksjomatowi wyboru twierdzenie mówi o funkcji wybierającej elementy ze zbiorów.

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

Czyli mając rodzinę zbiorów niepustych możemy utworzyć funkcję, która tak: bierze zbiór niepusty i wybiera z niego jeden element, bierze następny zbiór niepusty i wybiera z niego jeden element, itd. dla dowolnego zbioru tej rodziny.

Zwróćmy uwagę, że co prawda funkcja ma spełniać [math]f\left( A\right) \in A[/math], czyli przypisana wartość [math]f\left( A\right)[/math] zbiorowi [math]A[/math] ma być elementem tego zbioru, ale ciężko powiedzieć którym, nie jest to jawnie powiedziane niestety. Ale korzystając z aksjomatu wyboru można wykazać, że taka funkcja istnieje (choć ciężko ją opisać wzorem jawnym).

Twierdzenia dotyczące porządków

Kolejne równoważne aksjomatowi wyboru twierdzenie to twierdzenie o maksymalnym łańcuchu:

W każdym zbiorze uporządkowanym [math]\left( X, \le\right)[/math] istnieje maksymalny łańcuch pod względem inkluzji.

Czyli w zbiorze uporządkowanym zawsze możemy znaleźć maksymalny łańcuch. Niestety, to o wiele trudniejszy problem niż jego brzmienie, ze względu na bogactwo zbiorów uporządkowanych, ich złożoność i możliwą nieskończoność. Jednak takie zadziwiające twierdzenie jest prawdziwe przy założeniu aksjomatu wyboru ( jest mu równoważne).

Poniższe twierdzenie jest równoważne twierdzeniu o maksymalnym łańcuchu, (a więc również aksjomatowi wyboru):

W każdym zbiorze uporządkowanym każdy łańcuch jest podzbiorem pewnego większego łańcucha maksymalnego.

To twierdzenie mówi, że jeśli mamy zbiór uporządkowany [math]\left( X, \le \right)[/math] oraz łańcuch [math]A \subset X[/math], to możemy dobrać do tego łańcucha większy łańcuch pod względem inkluzji, maksymalny.

Dowód jednego wynikania jest bardzo prosty( tego w tył akurat):

Załóżmy przytoczone twierdzenie. Pokazujemy twierdzenie o maksymalnym łańcuchu. Weźmy dowolny zbiór uporządkowany. Pokażemy że istnieje w nim łańcuch maksymalny pod względem inkluzji. Najpierw znajdźmy jeden łańcuch- zawsze możemy znaleźć łańcuch pusty. A więc mamy jeden łańcuch, i ponieważ do tego łańcucha możemy dobrać większy łańcuch pod względem inkluzji maksymalny (na mocy zakładanego twierdzenia), no to mamy łańcuch maksymalny, co należało pokazać.[math]\square[/math]

Dowód wynikania w drugą stronę jest znacznie trudniejszy, więc go podamy później.

Kolejne równoważne aksjomatowi wyboru twierdzenie, to słynny Lemat Zorna:

Jeśli w zbiorze uporządkowanym [math]\left( X, \le \right)[/math] każdy łańcuch ma ograniczenie górne, to istnieje w [math]\left( X, \le \right)[/math] element maksymalny.

Dzięki temu twierdzeniu możemy uzyskać element maksymalny zbioru uporządkowanego. Łatwo pokazać, że Lemat Zorna jest równoważny twierdzeniu o maksymalnym łańcuchu.

Aby pokazać lemat Zorna, weźmy dowolny zbiór uporządkowany [math]\left( X, \le \right)[/math] taki, że każdy łańcuch jest ograniczony od góry. Pokażemy, że istnieje w [math]\left( X, \le \right)[/math] element maksymalny. Na mocy twierdzenia o maksymalnym łańcuchu znajdujemy maksymalny łańcuch pod względem inkluzji, nazwijmy go [math]A[/math]. Łańcuch ten ( jak każdy) posiada ograniczenie górne (nazwijmy je [math]a[/math]), które jest porównywalne z każdym elementem [math]A[/math], więc ponieważ [math]A[/math] jest maksymalnym łańcuchem to musi [math]a\in A[/math], a więc jest elementem [math]A[/math] i jest większe (słabo) od każdego elementu [math]A[/math] , zatem jest elementem największym [math]A[/math], i ten element największy [math]a[/math] w [math]A[/math], jest równocześnie elementem maksymalnym w całym [math]\left( X, \le \right)[/math]. Gdyby tak nie było, to istniałby element [math]a\lt b[/math]. Ponieważ element [math]b[/math] jest większy od największego elementu [math]A[/math], to [math]b\not\in A[/math]. Zatem [math]A\cup \left\{ b\right\}[/math] jest łańcuchem (co łatwo sprawdzić) istotnie większym od [math]A[/math] pod względem inkluzji, co przeczy maksymalności [math]A[/math]. Uzyskana sprzeczność kończy dowód. [math]\square[/math]

Jako przykład zastosowania Lematu Zorna udowodnimy twierdzenie o maksymalnym antyłańcuchu:

W każdym zbiorze uporządkowanym [math]\left( X, \le \right)[/math] istnieje maksymalny antyłańcuch pod względem inkluzji.

Czyli w zbiorze uporządkowanym możemy również zawsze znaleźć maksymalny antyłańcuch.

Dowód:

Ustalmy dowolny zbiór uporządkowany [math]\left( X, \le \right).[/math] Rozważmy rodzinę wszystkich antyłańcuchów:

[math]\mathbb{B}=\left\{ A\subset X\Bigl| \ A \hbox{ jest antyłańcuchem w } \left( X, \le \right)\right\}[/math]

i uporządkujmy ją inkluzją. Wykażemy, że każdy łańcuch w [math]\left( \mathbb{B}, \subset \right)[/math] ma ograniczenie górne.

Ustalmy w tym celu dowolny łańcuch [math]\mathbb{A}.[/math] Jako ograniczenie górne kładziemy [math]\bigcup\mathbb{A}[/math], wpierw jednak musimy zapewnić, że [math]\bigcup\mathbb{A} \in \mathbb{B}[/math]( ograniczenie górne musi być elementem zbioru uporządkowanego). Suma rodziny [math]\mathbb{A}[/math]- rodziny antyłańcuchów, podzbiorów [math]X[/math] będzie podzbiorem [math]X[/math]. Aby wykazać, że [math]\bigcup\mathbb{A}[/math] jest antyłańcuchem, weźmy dowolne dwa różne elementy [math]x,y\in\bigcup\mathbb{A}[/math]. Wtedy [math]x\in C[/math] dla pewnego zbioru [math]C\in\mathbb{A}[/math], oraz [math]y\in D[/math] dla pewnego zbioru [math]D\in\mathbb{A}[/math]. Ponieważ [math]\mathbb{A}[/math] jest łańcuchem pod względem inkluzji, to [math]C\subset D[/math] lub [math]D\subset C[/math]. Jeśli [math]C\subset D[/math], to [math]x,y\in D[/math]. Podobnie, w przeciwnym wypadku, jeśli [math]D\subset C[/math] to [math]x,y\in C[/math]. Czyli [math]x,y[/math] są w [math]D[/math] lub [math]x,y[/math] są w [math]C[/math]. Ponieważ [math]C,D\in\mathbb{A}[/math], zbiory [math]C,D[/math] są antyłańcuchami, więc ponieważ [math]x,y[/math] są różnymi elementami takiego antyłańcucha, wnioskujemy, że elementy [math]x,y[/math] są nieporównywalne. Pokazaliśmy, że dowolne dwa różne elementy [math]\bigcup\mathbb{A}[/math] są nieporównywalne, czyli [math]\bigcup\mathbb{A}[/math] jest antyłańcuchem, i należy do [math]\mathbb{B}[/math]. Ponieważ [math]\bigcup\mathbb{A}[/math] jest nadzbiorem każdego zbioru rodziny [math]\mathbb{A}[/math], czyli [math]\bigcup\mathbb{A}[/math] jest większa pod względem inkluzji od każdego zbioru [math]C\in\mathbb{A}[/math], stąd [math]\bigcup\mathbb{A}[/math] jest ograniczeniem górnym dla [math]\mathbb{A}[/math], tego łańcucha. Z dowolności wyboru zbioru [math]\mathbb{A}[/math] każdy łańcuch w [math]\left( \mathbb{B}, \subset \right)[/math] ma ograniczenie górne.

Stosując lemat Zorna wnioskujemy, że w zbiorze [math]\left( \mathbb{B}, \subset \right)[/math] jest element maksymalny. Jest to poszukiwany maksymalny antyłańcuch pod względem inkluzji.[math]\square[/math]

W sposób analogiczny (a nawet prostszy) można udowodnić przy pomocy Lematu Zorna dowieść twierdzenie o maksymalnym łańcuchu.

Twierdzenie Zermelo

Kolejne równoważne aksjomatowi wyboru twierdzenie to twierdzenie Zermelo. Mówi ono, że każdy zbiór da się dobrze uporządkować.

Twierdzenie Zermelo: