More Thoughts on the Axiom of Choice

I got a lot of good, interesting comments on my recent post on the axiom of choice (both on the post itself, and in this very good Hacker News thread). I wanted to answer some common questions and share the most interesting thing I learned.

Can’t we just pick at random?

A lot of people asked why we can’t just avoid the whole problem of the axiom of choice by picking set elements randomly. Because obviously we can just make a bunch of random choices, right? If there’s no limit to what the choices have to look like then there’s no problem.

If you believe that, then you believe the axiom of choice. “We can pick some element from each set, without being fussy about which one we get” is just what the axiom of choice says. And that’s fine. A lot of people believe the axiom of choice! But it’s not an alternative to the axiom of choice; it is the axiom of choice.

The fact that this “just pick at random” idea seems so facially compelling, or “obvious”, is a big part of why many mathematicians want to accept the axiom of choice. It just seems like we should be able to make a bunch of choices at once, if we’re not picky about which choices we make. It’s only when they are shown the really bizarre implications of getting to make those choices that most people start questioning whether the axiom makes sense.

Why do we want to believe the axiom of choice?

Another recurring question asked why we should want to believe the axiom of choice. It has a lot of bizarre consequences. In the last post I argued that those consequences aren’t as troubling as they seem, but they’re still weird. Why can’t we just dumpster the axiom of choice and avoid all of them?

One reason is the intuitive plausibility of the “just pick at random” idea. The goal of an axiomatic system is to formalize our list of “basic moves we should be able to make”. The ZF axioms include things like the axiom of extensionality, which says that two sets are equal if they have the same elements, and the axiom of pairing, which says that if \(A\) and \(B\) are sets then we can talk about the set \( {A,B } \). These aren’t weird exotic ideas. They’re just things we should be able to do with collections of things. They’re part of the intuition that the word “set” is trying to formalize.

You could see the axiom of choice as something like this—something in our basic, intuitive understanding of what a “set” is, that pre-exists formal definitions. It’s pretty easy to convince people that “choose an element from each set” is a reasonable thing to be able to do. The only problem is that it leads to absurd results like Banach-Tarski or the solution to the Infinite Hats puzzle. But if we satisfy ourselves that those absurdities aren’t a real problem, we return to “this seems like a thing we should be able to do”.

But really, why do we want to believe the axiom of choice?

On the other hand, that’s not a very strong reason to really care about the axiom of choice. At best, that leaves us at “why shouldn’t we, it doesn’t hurt anything”, which could just as easily be “why should we, it doesn’t help?” We care about the axiom of choice, and put up with the peripheral weirdness, because it lets us prove a variety of other results we care about. These include:

• Every Hilbert space has an orthonormal basis (so we can put coordinates on function spaces);
• Every field has an algebraic closure (very important in number theory—in my research I often wanted to talk about “the algebraic closure” of some large field, and that implicitly relies on the axiom of choice);
• The union of countably many countable sets is countable;
• The Hahn-Banach theorem (lets us extend linear functionals and guarantees that dual spaces are “interesting”);
• Gödel’s completeness theorem for first-order logic;
• The Baire category theorem, which I don’t even want to try to summarize but which shows up constantly in functional analysis.

All of these results are really useful in their respective fields, and we need the axiom of choice to prove them. And that’s a true “need”: these are all provable from ZFC but not from ZF.

These statements aren’t equivalent to the axiom of choice. If we wanted, we could take the above list as a list of new axioms to attach to ZF, and then we wouldn’t be stuck with choice. But that is a really strange and ad-hoc list of foundational axioms. It feels much better to take the one axiom—the axiom of choice, which is reasonably foundational and sounds plausible enough on its own—and get all these consequences for free.

Shoenfield’s Theorem: You only need the axiom of choice for weird things

But the coolest thing I learned about after writing the last post is Shoenfield’s Absoluteness Theorem. The statement of this theorem is pretty dense and I don’t think I completely understand it, but it has really nice implications for the axiom of choice.

In the last post I said that the axiom of choice just doesn’t cause problems as long as we’re not getting too far away from finite sets. This applies even to half the results in the previous section.

• We need the axiom of choice to show that every field has an algebraic closure, but not to show that the rationals do.
• We need the axiom of choice to show that every Hilbert space has an orthonormal basis, but not to show that Fourier theory gives an orthonormal basis for \(L^2([-\pi,\pi])\).
• We need the axiom of choice to prove the Baire Category Theorem for every complete metric space, but not to prove it for the real numbers or the real function space \(L^2(\mathbb{R}^n)\).

Shoenfield’s theorem helps tell us exactly when the axiom of choice is actually going to matter.

In the last post we talked about models of the ZF axioms, which are collections of sets that obey all the rules. Given a model, Kurt Gödel defined something called the constructible universe, which is a sort of smaller model, contained in the original model, which can be built up explicitly from smaller pieces. The constructible universe usually doesn’t contain everything in the original model, but it will in some sense contain all the simple explicitly describable things in the original model.

But the constructible universe has some extra nice properties. One is that the constructible universe will always satisfy the axiom of choice, even if the original model did not!¹ Specifically, since we construct the universe in a specific order, everything we’ve constructed can be well-ordered, which implies the axiom of choice. So any theorem that relies on the axiom of choice is automatically true as long as we’re only talking about sets in the constructible universe.

Shoenfield’s theorem extends that result even further. If you have a sufficiently simple question (for a precise definition of sufficiently simple), then the original model and the constructible universe must give the same answer. Since the axiom of choice always holds in the constructible universe, the answers to these simple questions can’t depend on whether you accept the axiom of choice or not.

What does that mean? Any simple-enough result that you can prove with the axiom of choice, you can also prove without it. That includes everything about Peano arithmetic and basic number theory, and also everything about the correctness of explicit computable algorithms. It also includes \(P = NP\) and the Riemann Hypothesis, and a number of other major unsolved problems.

There are questions that the axiom of choice really does matter for. But Gödel and Shoenfield’s results show that they have to be pretty far removed from anything finite or concretely constructible. So in practice, we can use the axiom of choice as a tool to make our work simpler, knowing that it won’t screw up anything practical that really matters.

Do you have other questions about the axiom of choice? Another cool fact I don’t know about? Or some other math topic you’d like me to explain? Tweet me @ProfJayDaigle or leave a comment below.