And He took the five loaves and the two fish, and looking up to heaven, He blessed and broke and gave the loaves to the disciples; and the disciples gave to the multitudes. So they all ate and were filled, and they took up twelve baskets full of the fragments that remained. – Matthew 14.

The logician Willard Quine defined a paradox as an “absurd” statement backed up by an argument.

The famous result of Banach and Tarski definitely counts as a paradox by this definition. They proved that it is possible to take a unit sphere (a ball with radius 1), divide it into five pieces, then by rotations and translations reassemble it into two unit spheres.

Huh?

This would seem to be impossible, based on our experience of the physical world. What happened to conservation of volume? The original sphere had volume 4π/3, the five parts should have total volume 4π/3, but the two spheres have  total volume 8π/3. Something doesn’t add up.

That’s literally true. Four of the pieces are so bizarre they don’t have a volume (technically, they are non measurable sets). Therefore you can’t add their volumes.

Axiom of Choice

I’ve said before that a paradox can often be understood as a proof by contradiction of one of the (often implicit) assumptions. One of the assumptions here is the additivity of volume. But the other is the Axiom of Choice.

The Axiom of Choice (AC) seems harmless at first. It says that if you have a collection of nonempty sets, there is a single function (a “choice function”) that assigns to each set an element of that set.

This seems reasonable and in line with our experience. If you have a bunch of bags each with some candies in them, there is certainly no problem collecting one from each bag (a child can do it and will only be too happy to oblige). Even if the candies in each bag are  identical.

Trouble happens when the number of candy bags is uncountably infinite. Why should there be a uniform way of making this infinite number of choices?

Nonmeasurable sets

This trouble takes many forms. The Banach Tarski paradox is just one. AC also (obviously) implies that there are sets that don’t have a volume (or area, or length).

The supposed existence of nonmeasurable sets seriously complicates analysis. (Analysis is, roughly speaking, generalized calculus.) Analysis textbooks are full of results which state that such-and-such a procedure always generates a measurable set. If students ask to see an example of one of these mysterious objects that don’t have a volume (or area, or length), the instructor is in trouble. AC tells you that such sets exist, but says nothing about any particular one of them. It’s non constructive.

In fact it can be shown that almost any set that is in any sense definable (say, by logical formulas) is measurable. For example, all Borel sets are measurable. If authors simply assumed that all sets are measurable, the average text would shrink to a fraction of its size. And they wouldn’t get into trouble – it is not possible, without AC, to prove the existence of a non measurable set.

Determinacy

More trouble arises when we deal with infinite games. Finite games of perfect information (no hidden cards) are well understood. If ties are impossible, then one player ‘owns’ the game – has a winning strategy. (A strategy is basically a complete playbook which tells you what to do in each situation.) Zermelo, the Z in ZF, first proved this. This is called determinacy.

When we move to infinite games (in which the players alternate forever) AC causes trouble. As you can guess, AC implies the existence of nondeterminate games, in which every strategy for player I is beaten by some strategy for player II, and vice versa. Strange. Needless to say, I can’t give you a concrete example of a nondeterminate game. Once again, you can prove that almost any particular game that you can specify is determinate.

Infinite voting systems

My final example of a  counterintuitive consequence of AC is the ultrafilter theorem. To avoid nerdy formulas, I’ll describe it in terms of voting.

Let’s say we have a finite group of voters

P₁, P₂, P₃, … , P_n

and they each vote Aye or Nay on a resolution. When do the Ayes have it? Obviously, when they have a majority (let’s count ties as the Nays having it). No problem.

When there are infinitely many voters, however, it is not so obvious what to do. A vote can be thought of as an infinite sequence of Ayes and Nays, e.g.

Aye, Nay, Nay, Aye, Nay, Aye, Aye, Nay, …

What constitutes a “majority” of an  infinite set of voters? You could give it to the Ayes if there are infinitely many of them, but it is also possible that at the same time there are infinitely many Nays, in which case the Nays have grounds for complaint.

It’s useful to make a list of the properties such a voting system should have.

• If the vote is unanimous, then the result should be the same, whether Aye or Nay
• No ties: either the Ayes have it (have a majority), or the Nays do
• If a vote is held and one person changes their vote, the outcome is unaffected.
• If a vote is held and the Ayes have it, and then any number of voters switch from Nay to Aye, the Ayes still have it
• the union of two minorities is a minority, and the intersection of two majorities is a majority

Sounds doable, but how?

We already saw that making all infinite sets majorities won’t work, because their complements may be infinite. In the same way we can’t say minorities are all finite. We can’t choose one or even finitely many people as the deciders, because individual votes don’t count.

Hmmm.

Well, don’t try to solve this because you won’t succeed. It can be shown, again, that there is no concrete (definable) scheme that works. In particular, even if we use Turing machines that can perform an infinite sequence of steps in a  finite amount of time (this makes mathematical sense), there is no voting program.

And yet the Axiom of Choice tells us that there is a voting method (not obvious). But don’t ask what it is, it’s a rabbit that AC pulls out of its hat.

The nature of existence

What to do about this?

We can retain AC and just live with the absurd Banach-Tarski  result, with sets without volume (or area or length), with games that have no winner, and infinite voting.

But in what sense does, say, there exist a voting method? AC tells us we are free to imagine that there exists a voting method. Gödel showed that AC is consistent with ZF (assuming, as everyone believes, that ZF is consistent). That means we won’t get into trouble if we use it. But many of its consequences are unsettling.

AC means, for example, that you can say “I know that there is a voting method that works” but not “I know a voting method that works”. Of course this situation happens in  real life. But in real life there’s the possibility of resolving the situation. If you know there is a wolf in the woods, you can go into the woods and find it. No use going looking for the voting method because you’ll never find it.

Other choices

Can we do without AC? To a point, yes. There are weaker forms that don’t have unsettling consequences. One is Countable Choice (CC), that says that given an (infinite) sequence

S₁, S₂, S₃, …

of sets there is a sequence

x₁, x₂, x₃, …

with each x_i an element of  S_i. (There is a slightly more powerful version, called Dependent Choice (DC), where each set of choices depends on the set of choices made previously).

CC or DC is enough to  do most practical mathematics, including most analysis. However it is not enough for important foundational theorems. For example, DC is not enough to prove the completeness theorem for first order logic. (Which says that every formula is either provable or has a counterexample.) For completeness, you need a voting method.

Another possibility is the Axiom of Determinacy (AD) which says that every game has a winner. It has some nice consequences, for example, it implies that every set of real numbers is measurable.

But it also implies that ZF is consistent. This sounds nice, too, but is actually a disaster. It means that we can’t prove the consistency of AD with ZF (assuming the consistency of ZF). In fact it is not known whether ZF+AD is consistent. Not safe for work!

AC, I can’t quit you

What to do? I’m afraid I don’t have the answer. AC causes trouble but it also makes life a lot simpler. For example, it implies that any two orders of infinity are comparable. Without AC, cardinal arithmetic is chaos. Set theorists have tried to come up with a weaker version of the Axiom of Determinacy but so far nothing persuasive has appeared.

In the end, it’s an engineering decision. If we choose AC, we have a well ordered mathematical universe with very nice features but also some bizarre objects with properties that contradict our real life experiences. A kind of Disneyland but with monsters. If we reject AC, we have a chaotic, complex universe in which the normal rules don’t apply. A kind of slum with broken windows, collapsing stairways, and cracked foundations. A “disaster” as Horst Herrlich put it.

And there doesn’t seem to be a middle ground. DC fixes some of the cracks and makes a large part of the slum (e.g. analysis) habitable, but doesn’t make it a theme park.

One possibility is to treat AC as a powerful drug and take it only when necessary. Theorems should come with consumer labels saying what went into them. So if you see a box on the shelf of “Banach and Tarski’s Miracle Duplicator! Feed Multitudes!”, it will say on the back of the box “Contains AC”.