Axiom of choice

The axiom of choice is an axiom of the Zermelo-Fraenkel set theory . It was first formulated by Ernst Zermelo in 1904. The axiom of choice says that for every set of non-empty sets there is a selection function , that is, a function that assigns an element to each of these non-empty sets and thus “selects” it. For finite sets one can deduce this without this axiom, so the axiom of choice is only interesting for infinite sets.

The axiom of choice

Let be a set of non-empty sets. Then a selection function for is called , if each element of assigns an element of , that is, has the domain and the following applies: ${\displaystyle A}$ ${\displaystyle F}$ ${\displaystyle A}$ ${\displaystyle F}$ ${\displaystyle X}$ ${\displaystyle A}$ ${\displaystyle X}$ ${\displaystyle F}$ ${\displaystyle A}$

${\displaystyle \forall X\in A:F(X)\in X.}$

${\displaystyle F}$So choose from each set in exactly one item. ${\displaystyle X}$ ${\displaystyle A}$

The axiom of choice then reads: For every set of non-empty sets there is a selection function.

Example: Be . The on through ${\displaystyle A=\{\{0,2\},\{1,2,5,7\},\{4\}\}}$ ${\displaystyle A}$

${\displaystyle F(\{0,2\})=2;\quad F(\{1,2,5,7\})=2;\quad F(\{4\})=4}$

defined function is a selection function for . ${\displaystyle F}$ ${\displaystyle A}$

Alternative formulations

• The power set of any set without the empty set has a selection function (Zermelo 1904).
• Let be a set of pairwise disjoint non-empty sets . Then there is a set that has exactly one element in common with everyone ( Zermelo 1907 , ZF ). ${\displaystyle A}$ ${\displaystyle X_{i}}$ ${\displaystyle C}$ ${\displaystyle X_{i}}$
• Be an arbitrary index set and a family of non-empty sets , then there exists a function with domain that any one element of associates: . ${\displaystyle I}$ ${\displaystyle (A_{i})_{i\in I}}$ ${\displaystyle A_{i}}$ ${\displaystyle F}$ ${\displaystyle I}$ ${\displaystyle i\in I}$ ${\displaystyle A_{i}}$ ${\displaystyle F(i)\in A_{i}}$

Remarks

The axiom of choice postulates the existence of a choice function. But you still have no method how to construct one. In this case one speaks of a weak statement of existence .

A selection function also exists without the axiom of selection for the following cases:

• For a finite set of non-empty sets it is trivial to give a selection function: One chooses any particular element from each set, which is possible without any problems. One does not need the axiom of choice for this. A formal proof would use induction on the size of the finite set. ${\displaystyle A=\{A_{1},\ldots ,A_{n}\}}$
• For sets of non-empty subsets of the natural numbers , it is also possible without any problems: The smallest element is selected from each subset. Similarly, one can specify an explicit selection function (without using the axiom of choice) for a set of closed subsets of the real numbers by choosing the (if possible positive) element with the smallest absolute value from each set.
• A selection function can even be defined for sets of intervals of real numbers: the center point is selected from each interval.

The following examples illustrate which cases the axiom of choice is relevant for:

• One can not prove the existence of a selection function for a general countable set of two-element sets in ZF (not ZFC, i.e. without the axiom of choice).
• The same is true for the existence of a selection function for the set of all non-empty subsets of the real numbers.

There are, however, attenuations of the axiom of choice which do not imply this, but for cases like the two examples show the existence, e.g. for the first case the countable axiom of choice (CC, for countable choice , also denoted by AC _ω or ACN), which says that a selection function exists if the set family is countable, or the axiom of dependent choice (DC, for dependent choice ).

Kurt Gödel showed in 1938 that the axiom of choice within the framework of the Zermelo-Fraenkel set theory does not result in a contradiction if one assumes the consistency of all other axioms. In 1963, however, Paul Cohen showed that even negating the axiom of choice does not lead to a contradiction. Both assumptions are therefore acceptable from a formalistic point of view. The axiom of choice follows, as Waclaw Sierpinski proved in 1947, from the generalized continuum hypothesis .

The axiom of choice is accepted by the vast majority of mathematicians. In many branches of mathematics, including newer ones such as nonstandard analysis , it leads to particularly aesthetic results. The Constructivist mathematics , however, a mathematics branch, which deliberately avoids the axiom of choice. In addition, there are other mathematicians, including many close to theoretical physics, who also do not use the axiom of choice, especially because of counterintuitive consequences such as the Banach-Tarski paradox . This leads to the question of whether theorems for whose proof the axiom of choice is usually used, such as Hahn-Banach's theorem, can be weakened in such a way that they can be proven without the axiom of choice, but still cover all important applications.

Sentences equivalent to the axiom of choice

Assuming the ZF axioms, there are a number of important theorems that are equivalent to the axiom of choice. The most important of these are the lemma of Zorn and the well-order theorem . Zermelo introduced the axiom of choice to formalize the proof of the well-order theorem. The names Lemma and Theorem come from the fact that these formulations do not appear as immediately understandable as the axiom of choice itself.

• Set theory
  • Well -ordered theorem : Any amount can be well-ordered.
  • If there is an infinite amount, then and have the same cardinality . ${\displaystyle \,A}$ ${\displaystyle \,A}$ ${\displaystyle A\times A}$
  • Trichotomy : Two sets either have the same cardinality or one of the two sets has a smaller cardinality than the other. The equivalence was proven by Friedrich Hartogs in 1915.
  • The Cartesian product of a non-empty family of non-empty sets is not empty.
  • König's theorem : Put simply, the sum of a sequence of cardinal numbers is really smaller than the product of a sequence of larger cardinal numbers.
  • Every surjective function has a right inverse .
  • Lemma von Teichmüller-Tukey : A non-empty set of finite character has a maximum element with respect to the set inclusion.
• Order theory
  • Zorn's Lemma : Every non-empty semi-ordered set in which every chain (i.e. every totally ordered subset) has an upper bound contains at least one maximal element.
  • Hausdorff's maximal chain theorem : In an ordered set, every chain can be expanded to a maximal chain.
  • Hausdorff's maximal chain theorem (weakened): In an ordered set there is at least one maximal chain.
• algebra
  • Every generating system of a vector space contains a basis of . ${\displaystyle V}$ ${\displaystyle V}$
  • Every vector space has a basis.
  • Every ring with a single element that is not the zero ring has a maximum ideal .
• Graph theory
  • Every (infinite) undirected, connected graph has a spanning tree .
• topology
  • Tychonoff's theorem : The product of compact spaces is itself compact. (However, this statement is only equivalent to the axiom of choice if the Hausdorff property is not required for compactness .)
  • In the product topology: The conclusion of a product by subsets is equal to the product of the subsets.
  • The product of whole uniform spaces is complete.

literature

• Thomas Jech : The Axiom of Choice . North Holland, 1973, ISBN 0-7204-2275-2 .
• Ernst Zermelo : Proof that a lot can be well organized . In: Mathematische Annalen 59, 1904, pp. 514-516.
• Ernst Zermelo: New proof of the possibility of a well-ordered system . In: Mathematische Annalen 65, 1908, pp. 107–128.
• Horst Herrlich: Axiom of Choice. Springer Lecture Notes in Mathematics 1876, Springer Verlag, Berlin / Heidelberg 2006, ISBN 3-540-30989-6 .
• Paul Howard, Jean E. Rubin: Consequences of the Axiom of Choice. American Mathematical Society, 1998, ISBN 0-8218-0977-6 .
• Per Martin-Löf : 100 years of Zermelo's axiom of choice: what was the problem with it? (PDF file; 257 kB)

Web links

• Overview of implications of the axiom of choice and their relationships based on the work of Howard and Rubin (last updated in 2002, interactive online version ).

Individual evidence

1. ^ Kurt Gödel: The consistency of the axiom of choice and of the generalized continuum-hypothesis . In: Proceedings of the US National Academy of Sciences . tape 24 , 1938, pp. 556-557 ( online [PDF]).
2. ^ Paul Cohen: Set Theory and the Continuum Hypothesis . Benjamin, New York 1963.
3. ^ See Leonard Gillman: Two classical surprises concerning the axiom of choice and the continuum hypothesis. American Mathematical Monthly, Volume 109, 2002, p. 544, pdf
4. ↑ See Gillman, loc. cit.
5. ^ Andreas Blass, Axiomatic set theory. In: Contemporary Mathematics. Volume 31, 1984 Chapter: Existence of bases implies the axiom of choice. Pp. 31–33, online (English) pdf