Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
As I'm sure many of you do, I read the XKCD webcomic regularly. The most recent one involves a joke about the Axiom of Choice, which I didn't get.
I went to Wikipedia to see what the Axiom of Choice is, but as often happens with things like this, the Wikipedia entry is not in plain, simple, understandable language. Can someone give me a nice simple explanation of what this axiom is, and perhaps explain the XKCD joke as well?
The joke is really about the Banach-Tarski theorem, which says that you can cut up a sphere into a finite number of pieces which when reassembled give you two spheres of the same size as the original sphere. This theorem is extremely counterintuitive since we seem to be doubling volume without adding any material or stretching the material that we have.
The theorem makes use of the Axiom of Choice (AC), which says that if you have a collection of sets then there is a way to select one element from each set. It has been proved that AC cannot be derived from the rest of set theory but must be introduced as an additional axiom. Since AC can be used to derive counterintuitive results such as the Banach-Tarski theorem, some mathematicians are very careful to specify when their arguments depend on AC.
Here is a formal statement of AC. Suppose we have a set $W$ and a rule associating a nonempty set $S_w$ to each $w \in W$. Then AC says that there is a function $$f:W \to \bigcup_{w \in W} S_w$$ such that for all $w \in W$ $$f(w) \in S_w$$
It might be a good idea to say something about the connection between the axiom of choice and the Banach-Tarski paradox. The reason the Banach-Tarski paradox is counterintuitive is that we expect that if you split up a sphere into finitely many pieces, the total "mass" of all the pieces is still the same - so you shouldn't be able to put those pieces together again into something of twice the total "mass." The reason this reasoning doesn't apply is that the pieces in question don't have mass at all! This is not the same as saying that they have zero mass. It's something much more terrifying: the notion of "mass" (which to a mathematician generally means something precise called measure) can't be defined for these pieces (in a way that still preserves all the reasonable properties we want of our notion of mass).
What does this have to do with the axiom of choice? Well, it turns out that the axiom of choice is one way we can construct these bizarre pieces (non-measurable sets). Without the axiom of choice, it's not possible to prove that such pieces exist. With the axiom of choice, we can construct things like the Vitali set and like the pieces that occur in the Banach-Tarski paradox because AC greatly increases our ability to write down weird sets.
Given a set $S$, to say that $S$ is not empty is to say that $\exists x(x\in S)$ (in English: there exists some $x$ such that $x$ is an element of $S$). First-order logic has an inference rule which allows us to move from $\exists x(x\in S)$ to some [new] constant symbol $s$ such that $s\in S$.
This process, called existential instantiation, allows us to move from "the set is not empty" to "here is an element of the set". And this is, in effect, means that we [or rather the inference rule] chose some arbitrary element from $S$.
Suppose now that you have $S_0,S_1$ and neither is empty, then you apply the process twice, and you have two elements of $S_0$ and $S_1$ respectively.1 But what happens if we are given some indexed family $S_n$ for $n\in\Bbb N$ and the information that neither of the $S_n$ is empty?
We cannot use existential instantiation infinitely many times. Remember that mathematics, formally, is always on its way to prove something. Proofs are finite in nature, so you can only apply the inference rule for finitely many of these $S_n$'s.
And to solve this we use the notion of a "choice function". If we had a function $f$ such that $f(n)\in S_n$ for all $n\in\Bbb N$, then we wouldn't need to apply any existential instantiation on the $S_n$'s, since $f(n)$ would already be some fixed element of $S_n$. And the axiom of choice asserts that such $f$ exists, in the broadest way possible, namely if we are given any indexed family of non-empty sets (regardless to the index set), then it has a choice function.
Now we can apply existential instantiation to the set of choice functions, which we have proved to be non-empty using the axiom of choice, and obtain the wanted function.
In simple words, if so, the axiom of choice says that given any family of non-empty sets $S_i$ for $i\in I$, there exists a function such that $f(i)\in S_i$ for all $i\in I$.
But of course, this doesn't quite explain the joke in that last panel. For this we need to talk about...
The axiom of choice is extremely useful, and it seems extremely natural as well. If we are given non-empty sets, then there is a way to choose an element from each set. But the consequences of the axiom of choice can be counterintuitive at first.
One of them, called the Banach-Tarski paradox, states that given a ball in $\Bbb R^3$, we can partition it into five parts, move these parts around without stretching or skewing them, and then reconstruct two balls each one exactly the same as the original ball.
This is truly mind boggling, and a lot of people object to the axiom of choice on the ground that this process shouldn't be possible. But those people often mistake mathematical balls to actual physical balls (or vice versa) and a non-constructive mathematical process with what we can do by hand [or robot] in real life.
The XKCD that you link is playing exactly on that. The character in the last panel has cut through the pumpkin several times, and suddenly there were two pumpkins. Just like in the Banach-Tarski paradox. And the "narrator" character points out that they shouldn't have used the axiom of choice to carve out a pumpkin.
Footnotes.
The annotation to http://www.irregularwebcomic.net/2339.html has an explanation of the Banach-Tarski paradox in easy to read language. It does ignore some of the technical details, but it covers most of the idea of the construction nicely.
You have some boxes, at least one. There may be only one box, seven boxes, or infinitely many boxes.
In each and every box, there are some items, at least one. There may be arbitrarily many items.
Question: Can you pick, at least in principle, exactly one item from each box, without necessarily describing the details or rules of how you select them?
The axiom of choice says that the answer to this question is affirmative.
It might seem quite innocuous, but it turns out that the axiom of choice has groundbreaking consequences in virtually all subfields of mathematics. Some of these consequences are fundamental results, others are mind-boggling paradoxes. The long list includes:
Jyotirmoy writes that:
[To prove the Banach-Tarski theorem] requires the Axiom of Choice.
This statement needs some qualification. A bit of background: the standard collection of set-theoretic axioms is called ZFC, where "C" stands for the axiom of choice. Deleting the axiom of choice yields a smaller collection of axioms called ZF. Here's the key point: when someone says: "So-and-so theorem requires the axiom of choice" what they're usually meaning is "so-and-so theorem does not follow from the ZF axioms alone."
This applies here. Explicitly:
So, in the presence of the ZF axioms, there's really a range of axioms between the axiom of choice and nothing; somewhere in amongst that tumult is the Banach-Tarski theorem, and it is neither right at the top (read: equivalent to the axiom of choice) nor right at the bottom (read: equivalent to the empty condition.)
Here is another equivalent of the axiom of choice which I believe has not yet been discussed. Given a surjective function $f: A \rightarrow B$, there exists a function $g: B \rightarrow A$ such that $f \circ g = Id_{B}$. The idea is the following:
(1) Let $A,B \neq \emptyset$.
(2) Then given that $\forall x \in B \ \exists y \in A \ (f(y) = x)$, by the surjectivity of $f$, we can have a function $g$ such that $g(x) = y$ or $\exists z (g(x) = z \in y)$ and ignore any elements of $A$ that are left-over after choosing these $y$'s.
(3) This allows us to show that $f \circ g$ is an identity function with respect to elements of $B$.
"[i]f you have a collection of sets then there is a way to select one element from each set." What does "a way" mean? That there is an algorithm that can select such an element? Obviously, there is a non-algorithmic way to do so -- just go to each set and pick out an element from it. That cannot be what AOC means. But if we mean by "function," just a laundry list that associates one thing with another, that is what it comes to.
