Main Index Foundation of mathematics Set theory
  Subject Index
comment on the page

Axiom of Choice

An axiom of fundamental importance in set theory.

A choice function on a family typeset structure of sets is a function typeset structure with domain typeset structure such that typeset structure for each non-empty set typeset structure. If typeset structure is finite, the existence of a choice function is an easy consequence of the basic principles of set formations and rules of logic. If typeset structure is infinite this not longer the case and the existence of a choice function must be postulated as a separate axiom:

Axiom of Choice: On any family of non-empty sets there exists at least one choice function.

Axiom of choice can be formulated also without using the choice function. One such formulation is: Any product of non-empty sets is non-empty.

The father of the set theory Cantor used the axiom of choice but he did not see the necessity to single it out. The first person who explicitly observed that this axiom is used as an argument was Peano in connection with his theorem on the existence of solutions to a system of differential equations in 1890.  

In 1902 Beppo Levi  [1] stated the axiom of choice for the first time in proving: 1

Theorem 1: The union of a disjoint set typeset structure non-empty sets has cardinal number greater than or equal to typeset structure.

However, Levi was never ready to admit this axiom in general [2] , part 4.7. The first who formally introduce the axiom was E.Zermelo when he proved:

Zermelo’s well-ordering theorem: Every set can be well-ordered.

From this reason the axiom is also called Zermelo’s axiom of choice.  

The history of this result is as follows: In 1900 Hilbert had stated at the International Congress of Mathematicians as the so-called 1st Hilbert’s problem the Cantor’s problem of the cardinal number of the continuum. In this connection Hilbert also mentioned the question whether continuum can be well-ordered. Cantor opinion was that this was true, and gave several, unfortunately, faulty proofs. At the 2nd Congress in Heidelberg in 1904 Jules König gave a plenary lecture  in which he proved that continuum cannot be well-ordered. The next day Zermelo found an error in the proof. In the same year Zermelo published  [3]  a proof that every set can be well-ordered, using the axiom of choice.  In 1908 he published a second proof  [4] , also based on the axiom of choice.

The proofs which depend on the axiom of choice are regarded as non-constructive,  because  it is not possible to “concretize”  the used choice function. This highly non-constructive character of proofs depending on axiom of choice and many paradoxical results which can be derived from it, was the reason for a considerable criticism.  For instance,  É. Borel commented this by: any argument where one supposes an arbitrary choice a non-denumerably infinite number of times is outside the domain of mathematics.

Despite this axiom of choice is remarkably equivalent with many important statements, more than 200 of the equivalents are recorded in  [5] . For instance, in Zermelo-Fraenkel set theory (without the axiom of choice), Zorn’s lemma, the trichotomy law, and the well ordering principle (proved by  É. Borel) are equivalent to the axiom of choice.

Note that for certain infinite sets it is also possible to avoid the axiom of choice. For example, for the set of positive integers. The problems with the choice function can be overcomed due to the fact that every non-empty set of natural numbers has the least element (that is the set of positive integers is well-ordered) , and so we can simply take the least element of  a set. Similarly any time when is possible to specify an explicit choice, we can avoid the use of the axiom of choice.

In 1938, K. Gödel established the consistency of the axiom of choice with the axioms of von Neumann-Bernays-Gödel set theory  and of Zermelo-Fraenkel set theory, that is that it cannot be disproved using the other axioms of set theory.This together with its indispensability in many proofs led to its acceptance by the majority of mathematicians. Moreover,  in 1963 Cohen unexpectedly proved that the axiom of choice is also independent of Zermelo-Fraenkel set theory. In other words, the axiom of choice is logically independent of the other axioms of Zermelo-Fraenkel set theory. Consequently, assuming the axiom of choice, or its negation, cannot  lead to a contradiction that could not be obtained without that assumption.

In contexts sensitive to the axiom of choice, it is custom to write "ZF" for the Zermelo-Fraenkel axiom system without the axiom of choice, and "ZFC" when the axiom of choice is included.

Notes

1 It is not known whether or not this result implies the axiom of choice. In 1984 P.E.Howard proved that Theorem 1 implies that every well-ordered collection of non-empty sets has a choice function.

References

[1]  Levi, B. (1902). Intorno alla teoria degli aggregati. Instituto Lombardo di Scienze e Lettere. Rendiconti, ser. 2, 35, 863-868.

[2]  Moore, G. H. (1982). Zermelo’s axiom of choice. Its origins, development and influence. . New York - Heidelberg - Berlin: Studies in the History of Mathematics and Physical Sciences, 8. Springer Verlag.

[3]  Zermelo, E. (1904). Neuer Beweis für die Möglichkeit einer Wohlordnung. (German). Math. Ann. 65, 107-128.

[4]  Zermelo, E. (1908). Beweis, daß jede Menge wohlgeordnet werden kann. (German). Math. Ann. 59, 514-516.

[5]  Rubin, H., & Rubin, J. E. (1985). Equivalents of the axiom of choice. 2nd ed.. Amsterdam - New York - Oxford: North-Holland.

Cite this web-page as:

Štefan Porubský: Axiom of Choice.

Page created  .