Aksjomat wyboru

Aksjomat wyboru (ozn. AC od ang. Axiom of Choice) – jeden z aksjomatów teorii mnogości mówiący o możliwości skonstruowania zbioru (nazywanego selektorem) zawierającego dokładnie po jednym elemencie z każdego zbioru należącego do rodziny niepustych zbiorów rozłącznych .

Powszechnie przyjmowane aksjomaty Zermelo-Fraenkela (ZF) teorii mnogości rozszerzone o AC oznacza się zwykle skrótem ZFC. Aksjomat ten jest niezależny ZF – można również rozważać modele teorii mnogości oparte na ZF, w których przyjęto negację AC. Z tego powodu choć większość matematyków uznaje i stosuje aksjomat wyboru, to w dowodach twierdzeń go wykorzystujących przyjęło się jednak zaznaczać ten fakt – dowody te nazywa się nieefektywnymi; zwykle są one także niekonstruktywne , gdyż mówią często jedynie o istnieniu danego obiektu, jednak nie wskazują go (nie podają konstrukcji; por. intuicjonizm ).

W przypadku ograniczenia się do skończonych rodzin zbiorów aksjomat wyboru jest trywialny (wynika z innych aksjomatów); zastosowany dla nieskończonych rodzin zbiorów również wydaje się intuicyjny, lecz jego konsekwencje bywają zaskakujące, np. Stefan Banach i Alfred Tarski korzystając z AC udowodnili twierdzenie o paradoksalnym rozkładzie kuli (mówiące o możliwości rozkładu kuli w trójwymiarowej przestrzeni euklidesowej na sześć części, z których można złożyć, korzystając wyłącznie z obrotów i przesunięć , dwie kule o średnicy równej średnicy kuli wyjściowej).

Definicja

Aksjomat wyboru podawany jest zwykle w następującej postaci:

Dla każdej rodziny $\scriptstyle \mathcal U$ niepustych zbiorów rozłącznych istnieje zbiór $\scriptstyle V$ (tzw. selektor), do którego należy dokładnie po jednym elemencie z każdego ze zbiorów należących do rodziny $\scriptstyle \mathcal U,$

$\forall_{\mathcal U} \Big(\big(\forall_{X \in \mathcal{U}} X \ne \varnothing\big) \and \big(\forall_{X, Z \in \mathcal U} (X \ne Z \Rightarrow X \cap Z = \varnothing)\big) \Rightarrow \exists_V \forall_{X \in \mathcal U} \exists_z \big(X \cap V = \{z\}\big)\Big).$

Przykładem innego sformułowania aksjomatu wyboru jest twierdzenie Tarskiego:

iloczyn kartezjański dowolnej liczby niepustych zbiorów jest niepusty.

Elementami iloczynu kartezjańskiego $\scriptstyle \prod A_i$ są wszystkie funkcje $\scriptstyle f\colon I \to \bigcup A_i$ spełniające warunek $\scriptstyle f(i) \in A_i$ dla każdego $\scriptstyle i \in I,$ gdzie $\scriptstyle I$ jest ustalonym zbiorem indeksów . Aksjomat wyboru postuluje wtedy, iż

jeśli $\scriptstyle \mathcal A = \{A_i\colon i \in I\}$ jest rodziną niepustych zbiorów, to istnieje taka funkcja $\scriptstyle f,$ nazywana funkcją wyboru dla $\scriptstyle \mathcal A,$ dla której $\scriptstyle f(i) \in A_i$ dla każdego $\scriptstyle i \in I.$

Równoważniki

Wśród ważnych twierdzeń równoważnych aksjomatowi wyboru można wymienić następujące wyniki teorii mnogości:

• Twierdzenie Hessenberga : Każdy zbiór nieskończony jest równoliczny ze swoim kwadratem kartezjańskim , tj. $\scriptstyle |A| = |A \times A|.$
• Prawo trychotomii : Dla dowolnych zbiorów $\scriptstyle A, B$ zachodzi $\scriptstyle |A| = |B|$ albo $\scriptstyle |A| > |B|,$ albo $\scriptstyle |A| < |B|.$
• Twierdzenie Tarskiego : Produkt dowolnej rodziny zbiorów niepustych jest niepusty.
• Twierdzenie Königa : Jeśli dla dowolnych liczb kardynalnych $\scriptstyle \mathfrak m_i, \mathfrak n_i$ spełniona jest nierówność $\scriptstyle \mathfrak m_i < \mathfrak n_i,$ to $\scriptstyle \sum \mathfrak m_i < \prod \mathfrak n_i,$ gdzie $\scriptstyle i$ przebiega zbiór indeksów $\scriptstyle I.$
• Lemat Teichmüllera-Tukeya : Niech $\scriptstyle W$ będzie własnością skończonego charakteru, mogącą przysługiwać podzbiorom pewnego zbioru $\scriptstyle A;$ każdy podzbiór tego zbioru mający wspomnianą własność jest zawarty w maksymalnym (ze względu na zawieranie) podzbiorze $\scriptstyle A$ mającym własność $\scriptstyle W.$
• Twierdzenie Zermelo : każdy zbiór można dobrze uporządkować .
• Lemat Kuratowskiego-Zorna : w dowolnym niepustym zbiorze częściowo uporządkowanym , w którym każdy podzbiór liniowo uporządkowany ma ograniczenie górne , istnieje (co najmniej jeden) element maksymalny ;
• Twierdzenie Hausdorffa o łańcuchu maksymalnym : każdy niepusty zbiór częściowo uporządkowany zawiera maksymalny (w sensie zawierania) podzbiór liniowo uporządkowany.

Aksjomat wyboru (często w postaci lematu Kuratowskiego-Zorna) pojawia się w dowodach różnych wyników spoza teorii mnogości, choć często potrzebna jest jedynie jego słabsza wersja (zob. Słabsze formy aksjomatu wyboru), np.

• teoria pierścieni – twierdzenie Krulla : każdy pierścień z jedynką ma ideał maksymalny (każdy ideał zawarty jest w pewnym ideale maksymalnym );
• algebra liniowa – twierdzenie Hamela : każda przestrzeń liniowa ma bazę (Hamela);
• algebra uniwersalna – twierdzenie Steiniza : każde ciało ma domknięcie algebraiczne ;
• analiza funkcjonalna – twierdzenie Hahna-Banacha oraz twierdzenie Kreina-Milmana ;
• topologia – twierdzenie Tichonowa : produkt przestrzeni zwartych jest zwarty.

Słabsze formy

Czasami matematycy asekurując się przed paradoksalnymi następstwami zakładania aksjomatu wyboru ograniczają się do jego słabszych, nierównoważnych wersji. W wielu zastosowaniach są one wystarczające i, nierzadko, wygodniejsze. Część z nich jest podobna do samego aksjomatu wyboru: niektóre ograniczają tylko rozważane rodziny niepustych zbiorów, np. do skończonych (ACF), inne zakładają z kolei, że funkcja wyboru wybiera podzbiór każdego danego niepustego zbioru zamiast elementu.

• Zasada wyboru
  (skr. SP od ang. Selection Principle)

  Dla każdego zbioru $\scriptstyle X$ istnieje funkcja przyporządkowująca każdemu, co najmniej dwuelementowemu podzbiorowi zbioru $\scriptstyle X$ pewien niepusty, właściwy podzbiór zbioru $\scriptstyle X.$

• Aksjomat wyboru dla zbiorów dających się dobrze uporządkować
  (skr. ACWO od ang. Axiom of Choice for Well Orderable sets)

  Dla każdego zbioru $\scriptstyle X$ istnieje funkcja przyporządkowująca dokładnie jeden element $\scriptstyle x \in X$ każdemu niepustemu podzbiorowi zbioru $\scriptstyle X$ dającemu się dobrze uporządkować.

• Aksjomat wyboru dla zbiorów skończonych
  (skr. ACF od ang. Axiom of Choice for Finite sets)

  Dla każdego zbioru $\scriptstyle X$ istnieje funkcja przyporządkowująca dokładnie jeden element $x\in X$ każdemu niepustemu, skończonemu podzbiorowi zbioru $\scriptstyle X.$

• Aksjomat wyboru dla zbiorów n-elementowych
  (skr. C_n od ang. axiom of Choice for finite sets of n elements)

  Dla każdego zbioru $\scriptstyle X$ istnieje funkcja wybierająca po jednym elemencie z każdego $\scriptstyle n$-elementowego podzbioru zbioru $\scriptstyle X.$

• Przeliczalny aksjomat wyboru
  (skr. CAC od ang. Countable Axiom of Choice albo AC_ω)

  Dla każdej przeliczalnej rodziny zbiorów istnieje funkcja wyboru.

Inne wersje wynikają z aksjomatu wyboru, ale mają całkowicie od niego odmienną postać:

• Aksjomat liniowego uporządkowania
  (skr. OP od ang. Ordering Principle)

  Każdy zbiór da się uporządkować liniowo .

• Aksjomat podziału
  (skr. PP od ang. Partition Principle)

  Każdy zbiór nieskończony da się podzielić na dwa nieskończone, rozłączne zbiory.

• Zasada wyborów zależnych
  (skr. PDC albo DC od ang. Principle of Dependent Choices)

  Jeśli $\scriptstyle R \subseteq X \times X$ jest taką relacją na niepustym zbiorze $\scriptstyle X,$ że dla dowolnego $\scriptstyle x$ istnieje $\scriptstyle y$ spełniający $\scriptstyle x R y,$ to istnieje ciąg $\scriptstyle (x_n) \subseteq X,$ dla którego $\scriptstyle x_i R x_{i+1}$ dla $\scriptstyle i \in \mathbb N.$

• Twierdzenie o ideale pierwszym
  (skr. BPI od ang. Boolean Prime Ideal theorem)

  Na każdej algebrze Boole'a istnieje ultrafiltr .

Prawdziwe są następujące ciągi implikacji:

AC ⇒ PDC ⇒ CAC

AC ⇒ SP ⇒ OP ⇒ ACF ⇒ ∀n C_n ⇒ C_m ⇒ PP

AC ⇒ BPI ⇒ OP

AC ⇒ ACWO ⇒ ACF

Bibliografia

• Omar De La Cruz, Carlos Augusto Di Prisco: Weak forms of the axiom of choice and partitions of infinite sets. Dordrecht: Kluwer Acad. Publ., 1998. 
• Thomas Jech: The Axiom of Choice. Amsterdam: North Holland, 1973.