The axiom of choice (AC) seems harmless enough. It says that given a family of non empty sets, there is a choice function that assigns to each set an element of that set.

AC is practically indispensable for doing modern mathematics. It is an existential axiom that implies the existence of all kinds of objects. But it gives no guidance on how to find examples of these objects. So in what sense do they exist?

A voting scheme

Don’t buy a single vote more than necessary.
– Douglas William Jerrold

Voting is in the news today as are various voting schemes. However when it comes to voting a proposal up or down, there’s only one simple criterion: majority rule. If the voters are v0, v1, v2, … vn-1 then the proposal is accepted if at least n/2+1 are in favour.

But what if there are infinitely many voters v0, v1, v2, … ? What does it mean for there to be a majority in favour? AC implies that there exists an infinitary voting scheme (this is not obvious) but supplies not a hint about how it could work.

One possibility is to pass the proposal if infinitely many voters voted Aye, but it’s possible that at the same time infinitely many voted Nay.

A vote is an infinite sequence (e..g.) Aye, Nay, Nay, Aye,… and a voting scheme is a function which assigns either Aye or Nay to each vote. A majority is a set of voters such that any motion for which they all vote Aye, passes.

Then we require the following properties to hold:

Given any set of voters, either it or its complement is a majority, but not both
If everyone switches their vote, the result switches
The result of adding any number of voters to a majority is a majority
The result of removing a single voter from a majority is still a majority.
The intersection of two majorities is a majority

There are a number of consequences of these properties we can immediately derive. Let’s call the complement of a majority a minority.

A motion passes iff the set of those who voted Aye is a majority and fails if it is a minority
The set of all voters is a majority and the empty set is a minority
Any finite set is a minority
Any cofinite set is a majority
If the vote is unanimous, the result follows the vote
The union of two minorities is a minority

Sounds simple? Well don’t try to invent a particular voting scheme because you won’t succeed. Any scheme that can be defined concretely will fail at least one of these properties. In fact it’s been shown that it’s consistent with the axioms of set theory and a weak form of the axiom of choice that there is no voting scheme.

Here is a simple argument against the existence of a voting scheme. Let E be the even numbers and O the odds. Either E or O is a majority, say E. But how is O smaller than E?They are isomorphic,

Nevertheless full AC says a voting scheme exists. The question is, exists in what sense?

Non measurable set

You’ve probably heard of the Banach-Tarski result. AC implies that it is possible to divide a unit sphere into five pieces then reassemble them into two unit spheres (using only translations and rotations, that should preserve volume). This is like proving that 1=1+1 except that four of the pieces can’t be assigned volumes: they are non measurable sets.

AC implies the existence of non measurable sets – e.g. solids that don’t have a volume – but don’t ask to see an example of one. Any set you can describe precisely will be measurable – for example, any Borel set. Analysis texts devote a lot of space to proving that the results of various operations, like countable union, preserve measurability.

These texts could be greatly simplified if they just assumed that all sets are measurable. Of course if they also assumed AC they’d be in trouble but you can do most of analysis with weaker forms of choice, like countable choice, that don’t imply the existence of non measurable sets.

An indeterminate game

You’re all familiar with finite discrete games like checkers and chess. Simplifying a bit, they have the following properties:

Players I and II alternate, I moving first, until the game ends
On each move the mover has a finite choice of moves
On each move the mover plays a natural number
Each player knows the sequence of moves up to the current position
If the last move produces a winning position, the mover wins
If the last move produces a losing position, the mover loses
If the last move produces neither, the game ties

It’s actually quite tricky to make this precise, and I’ll skip the details. The crucial concept is that of a strategy, which is simply a function which given the moves so far, returns the next move for the player concerned. A winning strategy is one that always eventually puts its user in a winning position.

Zermelo showed more than a century ago that if a game always ends, then either one player has a winning strategy, or both have a tying strategy.

But we can also define infinite games. In fact it’s simpler. Given any subset G of the Baire space (set of sequences of natural numbers):

Players I and II alternate, I moving first.
On each move each player plays a natural number
If the resulting infinite sequence a0,b0,a1,b1,a2,b2, … is in G, II wins, otherwise I wins.

A winning strategy for II is a function which takes a0,b0,…an and yields bn. A strategy for I takes a0,b0,…an,bn and yields an+1.

Since there are no ties we might expect that one of the players has a winning strategy (in which case the game is said to be determinate). Not so fast.

AC implies the existence of a nondeterminate game. An example? Don’t look for one, for the usual reasons. Any game you can define will be determinate. In particular, if G is a Borel set, then G is determinate.

There are a number of weaker versions of AC that can be proved directly in ZF. Suppose, for example, that each choice set has exactly two reals. Then choose the smallest! More generally the same idea works if each choice set has a finite set of reals.

A well ordering of the reals

But what if a choice set has an infinite number of reals? Say, all those greater than 0? There is no smallest.

However we could use another ordering of the reals, in which any subset has a least element. This is called a well-ordering. Then any family of sets of reals would have a choice function.

The natural numbers are well ordered (by arithmetic ordering), so every family of nonempty sets of natural numbers has a choice function,

Is there a well-ordering of the reals? AC implies there is, but don’t try to find an example. No ordering you can define will be a well-ordering, otherwise you could prove AC from ZF, which has been shown to be impossible (if ZF is consistent so is ZF+¬AC)

Yet another mathematical object that does not exist in any practical sense.

An infinitesimal

One important application of AC is to prove the compactness property of first order logic. This says that if every finite subset of a set of first order formulas is consistent (has an interpretation), the whole set has an interpretation (this is nontrivial because different finite subsets my have different interpretations).

One application is to prove the possible existence of infinitesimals. An infinitesimal is a number that is greater than 0 but less than 1/n for every natural number n.

For a long time calculus was based on infinitesimals. The derivative f’ of a function f was ‘defined’ as (f(x+𝛆)-f(x))/𝛆. Engineers still think in terms of infinitesimals dx and dy.

In the 1800s infinitesimals were declared inconsistent and abolished, replaced by the 𝛆-𝛅 formalism.

However in the 1960s Abraham Robinson pointed out that compactness implies the existent of an extension of the reals with infinitesimals. If we take all true first order properties of the reals (such as x+y=y+x or log(xy) = log(x) + log(y) and add the formulas

𝛆<1
𝛆<1/2
𝛆<1/3
𝛆<1/4
…

Then every finite subset is consistent. Hence, by compactness, the whole set is consistent. Robinson called the resulting structure the hyperreals and it’s a model of the first order theory of the reals, with infinitesimals.

The only snag is, what is 𝛆, the infinitesimal whose existence is guaranteed by compactness? Don’t ask, because there is no hope of defining it. If 𝛆 works so does 𝛆/2, or 𝛆**2, or √𝛆. There is no infinitesimal distinguished in the same sense that i and -i are distinguished in the complex numbers. So the hyperreals have infinitesimals but don’t try to choose a particular one.

Degrees of Existence

One thing is clear, existence is not a straight forward binary property. It’s a spectrum. On one end there’s the existence of integers like 42 and recursively defined functions like factorial. On the other end is the voting scheme, which seems like pure vapourware.

AC by itself implies only vapourware. However these zombie-like objects like the voting scheme are necessary for the smooth functioning of the mathematical universe. Without them the universe is chaotically irregular.

The universe with AC is like an all-conquering army with straight ranks but ranks filled in part with zombies. Their presence fills us with discomfort but without them we’re lost.