Aksjomat wyboru – Wikipedia, wolna encyklopedia

Z Wikipedii, wolnej encyklopedii

Spis treści

1 Definicja
2 Równoważniki
3 Słabsze formy
4 Bibliografia
5 Przypisy

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).

[edytuj] 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.$

[edytuj] 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^[1];
analiza funkcjonalna – twierdzenie Hahna-Banacha^[2] oraz twierdzenie Kreina-Milmana^[3];
topologia – twierdzenie Tichonowa: produkt przestrzeni zwartych jest zwarty^[4].

[edytuj] 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^[5]
(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^[6]
(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^[7]
(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

[edytuj] 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.

Przypisy

↑ Do udowodnienia wystarcza jedna ze słabszych wersji aksjomatu wyboru.
↑ Wymaga jedynie BPI.
↑ Do dowodu wystarcza słabsza wersja aksjomatu wyboru; wraz z BPI twierdzenie pociąga AC.
↑ Produktowane przestrzenie nie muszą być Hausdorffa; jeśli są, to do dowodu wystarczy wtedy BPI.
↑ Aksjomat ten jest bardzo słaby: na przykład nie można przy jego założeniu udowodnić, że każdy nieskończony zbiór da się podzielić na nieskończenie wiele nieskończonych rozłącznych zbiorów.
↑ Już podstawowe twierdzenia w analizie i teorii miary potrzebują założenia PDC albo przynajmniej CC (np. aby udowodnić, że zbiór liczb rzeczywistych nie jest sumą przeliczalnej rodziny zbiorów miary zero). Istnienie zbiorów niemierzalnych nie wynika z aksjomatów ZF + PDC, czyli układ ZF + PDC + „każdy podzbiór prostej rzeczywistej jest mierzalny” jest niesprzeczny.
↑ Ten aksjomat wystarczy, aby udowodnić np. twierdzenie o zwartości, twierdzenie Hahna-Banacha, istnienie zbiorów niemierzalnych, czy twierdzenie Tichonowa dla przestrzeni Hausdorffa.

Poznaj przeszłość Warszawy