If you believe Banach and Tarski, you can take a sphere, cut it into a handful of pieces, move them around, and put them back together into two complete spheres of the same size. 1
The accountants and engineers may be a bit angry about magically doubling a sphere…
but the proof that you can double a sphere does almost nothing questionable.
In fact, the most questionable thing we have to do is… to choose.
Yup! It turns out that making choices is more controversial than it seems it should be.2 In fact, the Axiom of Choice is perhaps the most discussed and most controversial axiom in all of mathematics.3
To convince you that choosing is hard, let’s look at simple example, picking a number between 0 and 1. Go ahead, pick one!
Like the girl in the red dress, you probably picked a rational number, i.e. a fraction. There’s nothing wrong with that, but, remember, that there really aren’t that many rational numbers.4 So, let’s try to pick a random irrational number between 0 and 1.
There are lots of choices possible, like or or , but that’s not really a random irrational number. They’re all very special ones that we can write down using a fancy formula, rather than a completely random choice.
So, how could we choose a random number?
Recall that an irrational number can be thought of as a infinite decimal, that neither repeats nor ends. So, to pick an irrational number at random, we could just pick digits randomly, one at a time.
Great! Now, you’ve picked a truly random irrational number!
But tell me, what number did you pick?
See the problem?
Choosing one digit, or even a million, is (in theory) not very hard. There are digits, you pick one. No problem.
But if you have to make an infinite number of choices… Well, it’s easy to say that you should make infinitely many choices, but can you really do it? If you can’t tell me the number you picked, did you really pick a number?
That is the controversy about the axiom of choice.
So, what does the axiom of choice actually say?
The axiom of choice says that, for any collection of (nonempty) sets, you can choose one thing out of each set.
For instance, if we were picking an infinite decimal, like before, our collection of sets would be a bunch of copies of the set of digits 0 to 9, one set of them for each of the infinitely many digits we need to pick. The axiom of choice says that we can pick one digit from each set of digits in order to pick an infinite decimal number. It doesn’t say how to pick those digits, or what digits you pick, just that you can pick them, somehow.
(To be clear, the axiom of choice doesn’t talk about making random choices, just a choice at all. So, in the exact case of picking digits that we just used, the axiom of choice simply says that there is some infinite decimal we can pick, not that it’s a random one. It’s perfectly valid for the axiom of choice to choose, say, all zero’s, and end up with the number 0.)
So why is this axiom so controversial?
The first is that you can’t actually get your hands on the object(s) the axiom of choice chose.
Axioms usually represent a basic definition, or a base truth, or something that is “obviously” true. For instance, one of the other basic axioms (of set theory) is that no matter which (counting) number you pick, there’s always a bigger one.5 That seems pretty obvious.
But, with the axiom of choice… Well, just like you couldn’t tell me which number you picked by picking each digit randomly, the axiom of choice simply says you can make a choice, not which one to make, or what the choice is.
If you can’t tell me what number you picked, did you pick it?
How is it “obvious” that you can make such a choice?
This is the argument of the constructivists. In their view, everything needs to be explicit. A choice only makes sense if you can tell me what you picked, or, at least, a way to make a unique choice. The axiom of choice fails this standard, and so should be avoided.
The other objection is that the axiom of choice leads to a number of “obviously false” results.
The most famous of these, we’ve already talked about, the Banach-Tarski paradox. In short, it says that you can take a sphere, cut it into a few pieces, move them around, and rearrange them into two spheres of the exact same size as the original! A bit of black magic, indeed.
The problem is that the axiom of choice is also instrumental in proving key, foundational, “obvious” results as well!
For instance, nothing is more obvious than if you have two bags of rice, one has more grains of rice than the other, or maybe the same amount of rice.
But without the axiom of choice, you can’t say the same thing about sets!
For finite sets, of course, this is not a problem. A set with 42 things in it is bigger than one with 27 things. But for infinite sets, it’s not always clear how to compare them.
Like we talked about way back in The size of infinity, the way to compare sets is line up the things inside them with each other. If we had two sets, say A and B, and each thing in A had a corresponding thing in B, then clearly B is at least as big as A.
The problem is that you can come up with complicated sets A and B where it’s not obvious how to line up things in A with things in B. In fact, without the axiom of choice, you can show it’s sometimes impossible to compare the size of the two sets. And it’s not even that you just don’t know which is bigger. It’s worse than that. The sets both have sizes, but you can’t even compare their sizes.
It turns out that the axiom of choice is equivalent to saying that you can always compare sizes of sets. In other words, either you accept the axiom of choice, or else you can’t always compare sizes. You can’t get one without the either.
There are a lot of other theorems that are equivalent to the axiom of choice. There’s a whole section of the Wikipedia page listing some of the equivalent results, some more intuitive, some less.
To quote Jerry Bona, “The Axiom of Choice is obviously true; the Well Ordering Principle is obviously false; and who can tell about Zorn’s Lemma?” The joke is that all of them are actually equivalent.
So, all of this leads to two very important questions.
First, you can’t “disprove” an axiom, since they’re base assumptions. But, can you prove that the axiom of choice is not consistent?
A consistent set of axioms is a set of assumptions that can’t prove contradictions. For instance, if you could use your axioms to prove that 0=1, that would mean your axioms were not consistent.
If you could show the axiom of choice caused inconsistencies, all the accountants in the world would feel more relieved, since then we could throw out the axiom of choice, along with its impossible consequences, like the Banach-Tarski paradox.
Okay, so we can’t throw out the axiom of choice because of inconsistencies, no matter how much the Bananch-Tarski paradox assaults our sensibilities.
But maybe we can do the opposite. The second question about the axiom of choice is whether we can prove it true using only the other axioms. In other words, do we need to assume the axiom of choice at all, or do we get it for free?
Here, again, we get an interesting answer. In 1963, Cohen showed that it’s impossible to prove the axiom of choice from the other standard axioms.
So, where does that leave us, intrepid explorers of mathematics?
As a (non-obvious) consequence, Cohen’s proof means we are free to either assume that the axiom of choice is true, or, in fact, that the axiom of choice is false! Either way is fine for math.
How do mathematicians deal with the controversy?
Originally, mathematicians were resistant to the axiom of choice. One well known story is about Tarski (of Banach-Tarski fame). He used the axiom of choice to prove a result about the sizes of infinite sets.7 He submitted the paper to a journal. In response, two editors rejected his paper.
Their argument? Well, Fréchet wrote that using one well-known truth to prove another well-known truth is not a new result. Meanwhile, Lebesgue wrote that using one false statement to prove another is of no interest.8
Nowadays, however, most mathematicians accept the axiom of choice without too many reservations. It’s simply too useful in proving too many foundational results in many fields. It’s consistent, so there doesn’t seem to be any reason to not use it, despite the occasional paradox it causes.9
Thanks for sticking with me! Those of you who came from the recent video by 3Blue1Brown may not have realized, but I haven’t posted recently. I’d planned on being a professor since high school, but a few months ago, I decided I was going to change careers. Learning as much computer science as I could and searching for a job and moving and so on took a lot of time and mental effort, which lead to not many (any?) blog posts.
However, we’ve now settled down in Albuquerque, NM, where I just started a job as a software developer for a small company making scientific software. New posts should now continue to come out about once a month. Yay! More awesome math!
(Also, if you haven’t checked out 3Blue1Brown before, you totally should. He’s pretty awesome too.)
- We started talking about this result in Double for Nothing: the Banach-Tarski Paradox, though we started talking about the basic ideas back in How Long is Infinity?. ↩
- Mathematical choice, like we’re talking about, is separate from the question of free will in philosophy. Though, on that front, I personally think it’s foolish to believe in anything other than free will. If we don’t have free will, it doesn’t matter what you believe, because either way, your actions are determined. If we do have free will, it’s clearly important to believe you have it, so that you can make better choices, and have the ability to change. So, in either case, believing you have free will is the correct choice. ↩
- The only competitor is the parallel postulate of Euclid. ↩
- In How Long is Infinity? we showed that, in fact, 0% of the numbers between 0 and 1 are rational, at least talking in terms of length. In the much earlier The size of infinity and A bigger infinity, we talked about one of the most mind-blowing results in mathematics, that the infinite size of all numbers between 0 and 1 is a larger infinity than the infinite size of all the rational numbers. ↩
- I’m referring to the axiom of infinity in Zermelo-Fraenkel set theory, the standard set theory I’m basing everything off of. The statement is more technical and complicated, but it’s there to establish there are infinitely many things. ↩
- This doesn’t contradict Gödel’s incompleteness theorem, which says that you cannot use a set of axioms to prove their own consistency. This result says that assuming the standard axioms of set theory are consistent, then adding the axiom of choice doesn’t add any inconsistencies. It’s still possible that the standard axioms are inconsistent themselves. ↩
- The theorem said that any infinite set has the same size (cardinality) as the “two-dimensional” version, the Cartesian product . For example, the line has the same cardinality as the plane . ↩
- This story was recounted by Jan Mycielski in Notices of the AMS vol. 53 no. 2 page 209. ↩
- Those that reject the axiom of choice, usually do it on philosophical grounds. Again, the axiom of choice simply says you can make a choice, not what that choice is. And if you can’t get your hands on it, did you really make a choice? Constructivists reject anything you cannot explicitly construct. Of course, they also reject the “Law of excluded middle,” which says that every statement is either true, or its negation is true, on which half of logical thought is built. ↩