Axiom of Choice: Introduction

“The Axiom of Choice is necessary to select a set from an infinite number of pairs of socks, but not an infinite number of pairs of shoes.” — Bertrand Russell, Introduction to mathematical philosophy

“Tarski told me the following story. He tried to publish his theorem [the equivalence between the Axiom of Choice and the statement ‘every infinite set A has the same cardinality as AxA’] in the Comptes Rendus Acad. Sci. Paris but Fréchet and Lebesgue refused to present it. Fréchet wrote that an implication between two well known propositions is not a new result. Lebesgue wrote that an implication between two false propositions is of no interest. And Tarski said that after this misadventure he never again tried to publish in the Comptes Rendus.”

  • Jan Mycielski, A System of Axioms of Set Theory for the Rationalists

Obligatory Introduction

The Axiom of Choice, the most controversial axiom of the 20th Century.

The axiom states that a certain kind of function, called a `choice’ function, always exists. It is called a choice function, because, given a collection of non-empty sets, the function ‘chooses’ a single element from each of the sets. It is a powerful and useful axiom, asserting the existence of useful mathematical structures (such as bases for vector spaces of arbitrary dimension, and ultraproducts). It is a generally accepted axiom, and is in wide use by mathematicians. In fact, according to Elliott Mendelson in Introduction to Mathematical Logic (1964) “The status of the Axiom of Choice has become less controversial in recent years. To most mathematicians it seems quite plausible and it has so many important applications in practically all branches of mathematics that not to accept it would seem to be a wilful hobbling of the practicing mathematician. ”

Neverless, being an axiom, it cannot be proven and must instead be assumed. In particular, it is an axiom of set theory and it is not provable from the other axioms (the Zermelo-Fraenkel axioms of Set Theory). In fact many mathematicians, in particular constructive mathematicians, reject the axiom, stating that it does not capture a ‘real’ or ‘physical’ property, but is instead just a mathematical oddity, an artefact of the mathematics used to approximate reality, rather than reality itself. In the words of the LessWrong community: the constructive mathematicians would claim it is a statement about the map, and not the territory.

Historically, the axiom has experienced much controversy. Before it was shown to be independent of the other axioms, it was believed either to follow from them (i.e., be ‘True’) or lead to a contradiction (i.e., be ‘False’). Its independence from the other axioms was, in fact, a very surprising result at the time.