The Axiom of Choice

TLDR - I prefer the Axiom of Dependent Choice to the full Axiom of Choice.

Background: The Need for an Axiomatic System

It was the turn of the 20th century and mathematicians had a problem: the math that they had been using just didn't add up. It was only in the 1800s that calculus and related fields got their footing with the modern, rigorous definition of limits. By the turn of the 20th century, a lot of math was still done without rigorous foundations, and this included the quickly-growing field of set theory. In 1901, Bertrand Russell discovered a flaw in set theory that led to a revolution in every corner of mathematics.

Prior to Bertrand's result, most mathematicians used "naive set theory" in which sets could be any "collection" of things. In particular, sets could contain other sets, and could even contain themselves. Russell's Paradox is as follows: if $S$ is the set of all sets which contain themselves, then does $S$ contain itself?

If $S$ does contain itself, then by definition $S$ is not in $S$. If $S$ does not contain itself, then by definition $S$ is in $S$. This is a contradiction. Something is wrong. Russell's "naive set theory" doesn't work.

Even in the 1800s, some mathematicians saw set theory as a possible foundation for all of mathematics. But Russell's result and other paradoxes showed that set theory, as it stood in 1900, couldn't stand as the foundation of anything. Eventually, mathematicians adopted a set of rules called ZFC that cleverly avoids problems like Russell's Paradox by restricting what sets are possible. In ZFC, sets can still contain other sets, but can not contain themselves.

Today, ZFC is more or less the de facto foundation of all mathematics.

The Axiom of Choice

ZFC stands for "Zermelo-Frankel Set Theory plus the Axiom of Choice". ZFC is defined by 9 axioms (depending on who is counting). The first 8 axioms together form Zermelo-Frankel Set Theory (ZF), and the 9th axiom is called the Axiom of Choice. The Axiom of Choice is the most controversial inclusion to ZFC, and I personally do not like to use it.

Axiom (Axiom of Choice): Given any set $\mathcal{S}$ of non-empty sets, there exists a choice function $f$ on $\mathcal{S}$ such that $f(A) \in A$ for all $A \in \mathcal{S}$.

I think of this as: "Given any collection $\mathcal{S}$ of non-empty sets, it is possible to simultaneously choose one element of each set." There are a ton of equivalent formulations of the axiom of choice, most famously the Well-Ordering Theorem and Zorn's Lemma.

Even I have to admit that this is a pretty intuitive axiom. On the other hand, I find naive set theory to be intuitive as well, and look where that kind of thinking got 19th century mathematicians. Digging deeper, I find I mistrust the Axiom of Choice because it is not constructive: it states that a choice function exists, but doesn't provide a method for finding that choice function. To some people, I know, this may be no big deal, but it rubs me the wrong way. Results that require this axiom tend not to be "constructive".

Proponents of the Axiom of Choice might point out that there are a lot of really beautiful theorems that form the backbone of modern math, and require the Axiom of Choice. One of the most popular of these is the following:

Theorem: Every vector space has a basis.

This theorem makes it really easy to visualize and manipulate vector spaces, but there is no "algorithm" or "procedure" to find said basis. This theorem implies that the real numbers have a basis over the rational numbers, but it is impossible to write down any such basis, or write down an exact description of such a basis.

Opponents to the Axiom of Choice often point to controversial results that arise from assuming the Axiom of Choice. Two oft-used examples are:

Theorem (Well-Ordering Theorem): Every set can be given a well-ordering.

Theorem (Banach-Tarski Paradox): The 3-dimensional ball $D^3$ can be decomposed into a finite number of subsets. These subsets can be split into two groups. Each group of subsets can be reassembled into a copy of $D^3$ by rotations and translations.

I find the well-ordering theorem to be completely unintuitive because I can't imagine any well-ordering on an uncountable set. However, there exist well-ordered uncountable sets in ZF, so I can't really fault the Axiom of Choice for this. As for the Banach-Tarski paradox, I don't find this strange - after all, one copy of $D^3$ and two copies of $D^3$ have the same cardinality, so why shouldn't you be able to transform one into the other? My main problem with the Axiom of Choice is that it is non-constructive, and I like to do constructive mathematics.

The Axiom of Dependent Choice

You really do lose a lot of math when you ignore the Axiom of Choice completely. In particular, the Axiom of Choice can be used to prove the existence of sequences, and sequences are the backbone of real analysis. Without any Choice, it's not possible to prove that a function between metric spaces that preserves convergent sequences is continuous. See this math.stackexchange.com question for more on real analysis without the Axiom of Choice.

In order to deal with sequences, I like to use the more refined Axiom of Dependent Choice (DC).

Axiom (Axiom of Dependent Choice): Given any countable collection $\mathcal{S} = (A_1, A_2, \dots)$ of sets, and any compatibility relations $R_{i,i+1} \subset A_i \times A_{i+1}$, there exists a sequence $(a_1, a_2, \dots)$ such that $a_i \in A_i$ and $(a_i, a_{i+1}) \in R_{i, i+1}$.

The Axiom of Choice states that you can simultaneously choose one element from each of any number of sets. The Axiom of Dependent Choice, however, only states that you can choose these elements iteratively, one after the other. The Axiom of Dependent Choice is more constructive, and I find it more reasonable.

In the end, it doesn't really matter. Through black magic set theory, Kurt Gödel proved in 1938 that if ZF is self-consistent if and only if ZFC is self-consistent. So, assuming the Axiom of Choice can not result in any paradoxes. In this blog, I do assume the Axiom of Choice where it is necessary. But I always mention when the Axiom of Choice is used.