Aksjomat wyboru

Aksjomat wyboru, pewnik wyboru, AC (od ang. axiom of choice) – aksjomat teorii mnogości gwarantujący istnienie zbioru zawierającego dokładnie po jednym elemencie z każdego zbioru należącego do danej rodziny niepustych zbiorów rozłącznych^[1]. Postulowany zbiór jest nazywany selektorem^{[potrzebny przypis]}.

Aksjomat AC jest niezależny od powszechnie przyjmowanych aksjomatów Zermela-Fraenkla (ZF). Teorie mnogości oparte na aksjomatach ZF oraz aksjomat AC oznacza się zwykle skrótem ZFC. Można również rozważać teorie mnogości oparte na ZF, w których przyjęto negację AC.

Większość matematyków uznaje i stosuje AC, jednak w dowodach twierdzeń zazwyczaj wyraźnie zaznacza się, gdy zakłada się AC. Dowody te nazywa się nieefektywnymi; zwykle są one także niekonstruktywne, gdy mówią jedynie o istnieniu danego obiektu, jednak nie wskazują go (nie podają konstrukcji; por. intuicjonizm).

W przypadku rodzin zbiorów skończonych aksjomat wyboru jest trywialny (tzn. wynika z innych aksjomatów). W przypadku rodzin zbiorów nieskończonych aksjomat AC również wydaje się intuicyjny, jednak jego konsekwencje bywają zaskakujące. Na przykład Stefan Banach i Alfred Tarski korzystając z AC udowodnili twierdzenie o paradoksalnym rozkładzie kuli (kulę z trójwymiarowej przestrzeni euklidesowej można rozłożyć na sześć części, a następnie z tych części można złożyć, korzystając wyłącznie z obrotów i przesunięć, dwie kule identyczne jak kula wyjściowa).

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

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

${\displaystyle \forall _{\mathcal {S}}{\Big \{}{\big [}\forall _{X\in \,{\mathcal {S}}}X\neq \varnothing {\big ]}\!\land \!{\big [}\forall _{X,Y\in \,{\mathcal {S}}}\,(X\neq Y\Rightarrow X\cap Y=\varnothing ){\big ]}}$${\displaystyle \Rightarrow \exists _{V}\forall _{X\in \,{\mathcal {S}}}\,\exists _{x}{\big (}X\cap V=\{x\}{\big )}{\Big \}}}$

Czasami alternatywnie używa się równoważnej postaci aksjomatu wyboru:^[2]

Dla każdej rodziny ${\displaystyle {\mathcal {S}}}$ zbiorów niepustych istnieje jej funkcja wyboru, to znaczy funkcja ${\displaystyle f:{\mathcal {S}}\to \bigcup {\mathcal {S}}}$ spełniająca dla każdego ${\displaystyle A\in {\mathcal {S}}}$ warunek ${\displaystyle f(A)\in A}$

${\displaystyle \forall _{\mathcal {S}}\left[\varnothing \notin {\mathcal {S}}\Rightarrow \exists _{f:{\mathcal {S}}\to \bigcup {\mathcal {S}}}\ \forall _{A\in {\mathcal {S}}}f(A)\in A\right]}$

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

• twierdzenie Tarskiego: Iloczyn kartezjański dowolnej rodziny zbiorów niepustych jest niepusty.
  Elementami iloczynu kartezjańskiego rodziny niepustych zbiorów ${\displaystyle {\mathcal {S}}=\{S_{i}\colon i\in I\}}$ są wszystkie funkcje ${\displaystyle f\colon I\to \bigcup S_{i}}$ spełniające warunek ${\displaystyle f(i)\in S_{i}}$ dla każdego ${\displaystyle i\in I,}$ gdzie ${\displaystyle I}$ jest ustalonym zbiorem indeksów. Teza twierdzenia Tarskiego brzmi: istnieje chociaż jedna taka funkcja ${\displaystyle f.}$
• twierdzenie Hessenberga: Każdy zbiór nieskończony jest równoliczny ze swoim kwadratem kartezjańskim, tj. ${\displaystyle |A|=|A\times A|.}$
• prawo trychotomii: Dla dowolnych zbiorów ${\displaystyle A,B}$ zachodzi ${\displaystyle |A|=|B|}$ albo ${\displaystyle |A|>|B|,}$ albo ${\displaystyle |A|<|B|.}$
• twierdzenie Königa: Jeśli dla dowolnych liczb kardynalnych ${\displaystyle {\mathfrak {m}}_{i},{\mathfrak {n}}_{i}}$ spełniona jest nierówność ${\displaystyle {\mathfrak {m}}_{i}<{\mathfrak {n}}_{i},}$ to ${\displaystyle \sum {\mathfrak {m}}_{i}<\prod {\mathfrak {n}}_{i},}$ gdzie ${\displaystyle i}$ przebiega zbiór indeksów ${\displaystyle I.}$
• lemat Teichmüllera-Tukeya: Niech ${\displaystyle W}$ będzie własnością skończonego typu, mogącą przysługiwać podzbiorom pewnego zbioru ${\displaystyle A;}$ każdy podzbiór tego zbioru mający wspomnianą własność jest zawarty w maksymalnym (ze względu na zawieranie) podzbiorze ${\displaystyle A}$ mającym własność ${\displaystyle W.}$
• twierdzenie Zermela: 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.

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 (SP od ang. selection principle)

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

• Aksjomat wyboru dla zbiorów dających się dobrze uporządkować (ACWO, od ang. axiom of choice for well orderable sets)

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

• Aksjomat wyboru dla zbiorów skończonych (ACF, od ang. axiom of choice for finite sets)

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

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

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

• Przeliczalny aksjomat wyboru (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 (OP, od ang. ordering principle)

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

• Aksjomat podziału^[a] (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^[b] (PDC, od ang. principle of dependent choices, albo DC)

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

• Twierdzenie o ideale pierwszym^[c] (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

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, na przykład:

• analiza matematyczna – równoważność definicji ciągłości funkcji według Cauchy’ego i Heinego^[d]
• 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^[e]
• analiza funkcjonalna – twierdzenie Hahna-Banacha^[f] oraz twierdzenie Krejna-Milmana^[g]
• topologia – twierdzenie Tichonowa: produkt przestrzeni zwartych jest zwarty^[h].

• aksjomat determinacji

• 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. DOI: 10.1007/978-94-015-8988-8_4. Brak numerów stron w książce
• Thomas Jech: The Axiom of Choice. Amsterdam: North Holland, 1973. Brak numerów stron w książce

Polskojęzyczne

• Roman Duda, Kłopotliwy aksjomat wyboru, Centrum Kopernika Badań Interdyscyplinarnych – Uniwersytet Jagielloński, kanał „Copernicus” na YouTube, 3 sierpnia 2016 [dostęp 2021-05-23].
• MariuszM. Skałba MariuszM., Pierwszy stopień do raju, „Delta”, sierpień 2022, ISSN 0137-3005 [dostęp 2023-12-10] .

Anglojęzyczne

• Eric W.E.W. Weisstein Eric W.E.W., Axiom of Choice, [w:] MathWorld, Wolfram Research  (ang.). [dostęp 2023-06-01].
• John L.J.L. Bell John L.J.L., Axiom of Choice, Edward N.E.N. Zalta, Stanford Encyclopedia of Philosophy, 18 marca 2015 [dostęp 2017-12-30] [zarchiwizowane z adresu 2017-12-21]  (ang.).
• Axiom of choice (ang.), Routledge Encyclopedia of Philosophy, rep.routledge.com [dostęp 2023-05-08].
• How the Axiom of Choice Gives Sizeless Sets, kanał PBS Infinite Series na YouTube, 14 września 2017 [dostęp 2024-08-23].