Maybe-Mathematical Musings

Math, Teaching, Literature, and Life

July 28, 2021

Other Writing

Subscribe via RSS

Twitter: @ProfJayDaigle

Support my writing at Ko-Fi

Recent Posts:

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:

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.

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!1 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.

  1. This is how Gödel proved that the axiom of choice must be consistent with the ZF axioms: the constructible universe gives us a model of ZF that also satisfies the axiom of choice. ↵Return to Post

Tags: math teaching models set theory axiom of choice philosophy of math