The Axiom of Choice

The Axiom of Choice

In the previous articles, we saw how paradoxes forced restrictions on the formation of classes and propositional functions. Russell’s Theory of Types sought to prevent an expression from referring to a totality of which it was itself a member. The problem that will concern us now is different. It does not arise from a contradiction, but from a question about mathematical existence: can we assert that an object exists even when we have no rule that allows us to construct or determine it?

This question lies at the origin of one of the most debated principles in modern mathematics: the Axiom of Choice. At first sight, its statement seems entirely innocent. If we have several nonempty sets, we should be able to choose one element from each of them. However, when the collection of sets is infinite and no criterion specifies which element to choose, that apparent obviousness becomes an additional mathematical assumption.

Choosing an element

Suppose that we have three nonempty sets:

$$A=\{1,2\}\qquad B=\{5,7\}\qquad C=\{11,13\}$$

There seems to be no difficulty in choosing one element from each. We may select, for example, \(1\) from \(A\), \(5\) from \(B\), and \(11\) from \(C\). The result can be represented by a function \(f\):

$$f(A)=1\qquad f(B)=5\qquad f(C)=11$$

The function \(f\) assigns one of its elements to each set. This is what we call a choice function. The condition it must satisfy is very simple:

$$f(X)\in X$$

When the family contains a finite number of sets, we can make the choices one after another. No new mathematical principle is required: it is enough to repeat finitely many times the statement that every nonempty set has at least one element.

A rule for choosing

No special problem arises when we have a rule that determines which element should be chosen. If all the sets consist of natural numbers, we could always select the least element:

$$f(X)=\min(X)$$

The rule defines the function by itself. We do not merely assert that a choice exists; we specify how to make it.

A traditional example helps illustrate the difference. Imagine an infinite collection of pairs of shoes. We can choose the left shoe from each pair because the property “being the left shoe” provides a common rule. By contrast, if we have an infinite collection of pairs of socks that are indistinguishable with respect to the relevant properties, we know that each pair contains two objects, but we have no uniform criterion for choosing one of them.

The Axiom of Choice does not provide such a rule. It simply states that some simultaneous choice exists, even if we do not know how to describe or compute it.

Simultaneous choice

Let \(\mathcal{A}\) be a family of nonempty sets. The Axiom of Choice states that there exists a function \(f\), defined on all the members of \(\mathcal{A}\), that selects one element from each set:

$$\left[\forall A\in\mathcal{A}\,(A\neq\emptyset)\right]\rightarrow\exists f\left[\operatorname{dom}(f)=\mathcal{A}\land\forall A\in\mathcal{A}\,(f(A)\in A)\right]$$

The function \(f\) takes a set \(A\) from the family as its argument and returns one of its elements. The selected element need not have any special property. Nor is there claimed to be a unique choice function: different functions may select different elements.

From the function, we can form the collection of chosen elements:

$$C=\{f(A)\mid A\in\mathcal{A}\}$$

When the sets in \(\mathcal{A}\) are pairwise disjoint, \(C\) contains exactly one element from each of them:

$$\forall A\in\mathcal{A}\qquad |C\cap A|=1$$

This formulation in terms of a choice set is especially intuitive, although the general form of the axiom does not require the sets to be disjoint. If two sets share an element, a choice function may select that same element for both.

Finite and infinite choices

The difficulty does not lie in choosing a single element. By definition, every nonempty set contains at least one. Nor does it lie in making finitely many choices. The leap occurs when we seek to make infinitely many simultaneous choices without any common rule.

For each set \(A\in\mathcal{A}\), we may assert:

$$\exists x\,(x\in A)$$

But the Axiom of Choice allows us to pass from all those individual statements to the existence of a single function that gathers all the choices together:

$$\exists f\,\forall A\in\mathcal{A}\,(f(A)\in A)$$

The transition between the two expressions may seem small, but it is not merely a grammatical rearrangement. In the first, we assert separately that each set has some element. In the second, we postulate the existence of a new object—the function \(f\)—that contains all the choices at once.

Existence without definition

The controversial character of the axiom can be summarized as follows: it guarantees the existence of a function without providing a definition that allows us to identify it individually. We know that some choice function exists, but the axiom does not tell us which one.

This kind of reasoning is not unusual in classical mathematics. One can prove that an object exists without providing a procedure for constructing it. The Axiom of Choice, however, carries this idea into an especially vivid case: it gathers a potentially immense number of arbitrary decisions into a single mathematical object.

Before the Axiom of Choice

The principle did not suddenly appear in Zermelo’s work. During the nineteenth century, mathematicians had made implicit choices in numerous proofs. When they wrote “for each set, choose an element” or “take a representative from each class,” it was assumed that all those choices could be made simultaneously.

As long as the collections under consideration were finite, countable, or accompanied by some natural criterion, this assumption attracted little attention. The situation changed with Cantor’s Set Theory, which required mathematicians to work with increasingly general infinite totalities.

Well-ordering

One of the central questions in Cantorian theory was whether every set could be well-ordered. An order is a well-order when every nonempty subset has a least element.

If \(\preceq\) is an order on a set \(M\), the condition can be expressed as:

$$\forall B\subseteq M\left[B\neq\emptyset\rightarrow\exists b\in B\,\forall x\in B\,(b\preceq x)\right]$$

The natural numbers with their usual order are well-ordered. Every nonempty set of natural numbers contains a number smaller than all the others. For example, the subset of positive even numbers has \(2\) as its least element.

The usual order of the real numbers, by contrast, is not a well-order. The open interval \((0,1)\) has no least element: given any positive number in the interval, we can always find a smaller one.

Cantor maintained that every set could be given some well-order, even if that order differed from the usual one and even if we were unable to describe it explicitly. This claim was essential for extending the techniques developed for ordinal numbers to arbitrary sets.

The continuum

The question became especially striking in the case of the continuum. Was it possible to order all real numbers in such a way that every nonempty subset had a least element? The resulting order would have to be very different from the usual order of the number line.

It was not enough merely to assert that a well-order must exist. It had to be justified. Hilbert included this question among the great problems that mathematics in the new century was expected to solve.

Zermelo and the Well-Ordering Theorem

In 1904, Ernst Zermelo presented a proof that every set can be well-ordered. The decisive principle in his argument was precisely the possibility of simultaneously choosing one element from each nonempty set in a family.

Zermelo did not believe that he was introducing a practice alien to mathematics. In his view, mathematicians already used this procedure routinely, even though they had not isolated it as an independent principle. His contribution was to make it explicit and reveal the extraordinary strength of its consequences.

Choosing from the subsets

Let \(M\) be any set. Consider all its nonempty subsets. The Axiom of Choice allows us to postulate a function \(c\) that selects one element from each of them:

$$c:\mathcal{P}(M)\setminus\{\emptyset\}\longrightarrow M$$

$$c(A)\in A$$

The function \(c\) can choose an element of \(M\). It can then choose another from the set of remaining elements, followed by another from those not yet chosen, and so on.

The idea is not merely to repeat the process through stages numbered by the natural numbers. For an arbitrary infinite set, the procedure may continue through transfinite stages. Each new element occupies a position after all those previously selected. The order in which the elements appear ultimately provides a well-ordering of \(M\).

This is only the general intuition behind the proof. The complete argument must specify how all the stages are organized and how to prevent the process from stopping before the entire set has been traversed.

From well-ordering to choice

The connection also works in the opposite direction. Suppose every set can be well-ordered and \(\mathcal{A}\) is a family of nonempty sets. We can gather the elements of those sets together and assign a well-order to the resulting totality.

Each set \(A\in\mathcal{A}\) will then have a least element with respect to that order. We simply choose it:

$$f(A)=\min_{\preceq}(A)$$

In this way, we obtain a choice function. The Axiom of Choice proves the Well-Ordering Theorem, and the Well-Ordering Theorem, in turn, recovers a choice function. The two principles express the same mathematical strength from different perspectives.

The controversy of 1904

Zermelo’s proof provoked one of the greatest mathematical controversies of the early twentieth century. The unease did not arise solely from the conclusion. Many mathematicians already suspected that every set should be capable of being well-ordered. What was truly controversial was the kind of existence invoked to justify it.

The choice function was not defined by any specific formula. Nor was there a procedure for calculating which element it should select from each set. Zermelo asserted its existence all at once, even when the family required an uncountable number of choices.

Borel, Baire, and Lebesgue

The French analysts Émile Borel, René Baire, and Henri Lebesgue received the principle with deep reservations. Their own research depended on ideas from Set Theory, but they distrusted arguments asserting the existence of objects that could neither be defined nor constructed.

Borel was willing to accept finite choices and even certain countable sequences of choices. What he rejected was the leap to an uncountable number of completely arbitrary decisions. For him, a purported choice that could not be described by a law lay outside legitimate mathematical practice.

Lebesgue formulated the problem especially directly: can the existence of a mathematical object be proved without defining it? From a constructive perspective, to assert that something exists is to provide conditions that determine it effectively or, at the very least, characterize it uniquely.

Baire adopted an even more restrictive position. He denied that merely having a set automatically entitled us to regard the totality of all its subsets, together with a choice made across all of them, as already given.

Hadamard and mathematical existence

Jacques Hadamard defended the opposite position. He accepted that a proof could establish the existence of an object without providing an individual description of it. For Hadamard, identifying mathematical existence with our psychological or practical ability to construct an object imposed a restriction foreign to the nature of mathematics.

The debate thus opposed two conceptions. According to the first, a mathematical object exists when we can define or construct it. According to the second, a proof can guarantee its existence even if it supplies no method for exhibiting it.

The Axiom of Choice became a privileged point of reference in this dispute. Its statement sharply separated two ideas that had often previously been conflated: proving that a choice exists and showing how that choice is made.

Poincaré and the vicious circle

Criticism of the Axiom of Choice also became entangled with another problem discussed in the previous article: impredicative definitions. Poincaré did not direct all his objections at choice itself, but at certain totalities used in Zermelo’s first proof.

At one point in the argument, it was necessary to consider the totality of certain sets defined through the procedure itself. For Poincaré, the definition involved a vicious circle: the object being defined could belong to the totality used to define it.

It is therefore important to distinguish two different criticisms. One questioned whether the existence of a choice function could be asserted without defining it. The other questioned the use of impredicative totalities in the specific proof. One could accept the Axiom of Choice while rejecting Zermelo’s proof, or accept the proof as conditionally correct while rejecting the axiom itself.

A controversy without paradox

Unlike the unrestricted Principle of Comprehension, the Axiom of Choice does not immediately lead to a contradiction such as Russell’s Paradox. The objection is not that choosing an element from each set produces an antinomy.

The doubt concerns the meaning of mathematical existence. The axiom introduces a global function without specifying which one it is or giving a property that distinguishes it from all others. For its defenders, this is a legitimate existence proof. For its critics, it is merely verbal existence.

Zermelo’s response

Zermelo responded extensively to his critics. In 1908, he presented a new proof of the Well-Ordering Theorem inspired by Dedekind’s theory of chains. The new proof still depended on the Axiom of Choice, but it sought to present the process more clearly and avoid some of the objections directed at the 1904 argument.

Zermelo also maintained that banning all impredicative definitions would endanger procedures commonly used in Analysis. In his view, the critics imposed restrictions on Set Theory that they did not apply with equal severity to other established branches of mathematics.

The discussion nevertheless yielded a deeper lesson. It was no longer enough to use set-theoretic principles intuitively. It was necessary to specify precisely which sets could be admitted, which operations could be performed on them, and which existence principles should be accepted.

That same year, Zermelo presented an axiomatization of Set Theory. In it, the Axiom of Choice appeared as one of the system’s explicit principles. The aim was no longer to reduce the theory to an informal intuition of set, but to delimit it through a series of precise rules.

Conclusion

The Axiom of Choice appears to assert something elementary: from every nonempty set, we can choose an element. Its depth emerges when the choice must be made simultaneously across an infinite family and no rule determines the selected elements.

Zermelo transformed this assumption, previously used implicitly, into an explicit mathematical principle. With it, he proved that every set admits a well-ordering. But the proof opened a discussion that went beyond the original problem: is proving that an object exists sufficient, or must we be able to construct and define it?

The controversy showed that the foundational crisis was not limited to eliminating paradoxes. It was also necessary to decide which forms of existence and proof would be accepted by the new mathematics. Russell’s Theory of Types responded by restricting expressions capable of generating vicious circles. Zermelo would take a different path: explicitly formulating the principles that should govern the formation and behavior of sets.

In the next article, we will examine that proposal: the axioms with which Zermelo attempted to reconstruct Set Theory on a rigorous foundation.

Recommended reading

• Moore, G. H. (1982). Zermelo’s Axiom of Choice: Its Origins, Development, and Influence.
• Ferreirós, J. (2007). Labyrinth of Thought: A History of Set Theory and Its Role in Modern Mathematics.
• Torretti, R. (1998). Cantor’s Paradise: The Set-Theoretic Tradition in the Philosophy of Mathematics.
• Zermelo, E. (1904). Beweis, daß jede Menge wohlgeordnet werden kann.
• Zermelo, E. (1908). Neuer Beweis für die Möglichkeit einer Wohlordnung.