Explained: Gödel's theorem and the Banach-Tarski Paradox

The explanation of Banach-Tarski misses the point, which is that by using only volume-preserving transformations (no stretching) on subsets of the sphere, you can rearrange it into two spheres of the same size, provided you use the axiom of choice to define the subsets (which turn out to be immeasurable and escape the volume-preserving property of the transformations.) Here is a good explanation.

This Banach-Tarski explanation is nice at a very beginner level, but worse than useless above that. Here is a very important related fact: The Banach-Tarski paradox is simply NOT TRUE on the line and the plane. You can not do such a rearrangement with a circle to get two circles of the same size.

The difference between 2D and 3D that causes this change is very interesting. The isomorphism group has a much more complex structure in 3D. In particular, the group of 3D rotations contains a free group. This means that there exist 3D rotations a and b and their respective inverses A and B such that a list of successively applied such rotations is the identity if and only if it is the identity for formal reasons. (For example, aaBbAA is the identity for formal reasons.) How does this lead to the paradox? There are two main ideas involved:

1. This free subgroup has a paradoxical behavior. (We now treat it as a subset of the unit sphere.) The elements of this set are defined by rotations such as AbAbABaAABBaBbb. This set can be divided into four disjoint subsets depending on their first letter. These four subsets are isomorphic to each other, but each is also isomorphic to their union.

2. We can use the axiom of choice to pick representative elements from the cosets of our free group. (Basically, to get a maximal subset of the sphere such that the above free rotations never move one element into another.) Such a set will behave very similarly to a single element of the free group, but it has the advantage that its rotated versions together give the whole sphere, not just a sparse subset of it.

3. These were the main ideas. EDIT: One minor idea that I originally forgot is nicely explained by earthwormchuck163 in a reply to this comment. The complication is that rotations have fixed points, and the relief is that there are only countably many of them.

4. One very minor idea is that if you have a paradox for the sphere using rotations, you can get a paradox for the ball. This is a nice exercise.

The Banach-Tarski one is not an explanation; it's an analogy that makes a non-mathematician feel they've read an explanation. This phenomenon is dangerous in math for the same reason it's dangerous in quantum mechanics.

(In fact, it's the same thing that bugged me when I was sitting through Christmas Mass out of respect for my parents; the priest was making surface analogies about the love of God, and the congregation felt that they were hearing explanations of theology or even evidence for the existence of God's love. Is there a name for this phenomenon?)

Smullyan's intuitive example of quining and Goedel was good, though.

World's shortest explanation of Gödel's theorem

I'd read this explanation from Smullyan before I read about the theorem in more detail, and I don't think Smullyan's explanation conveys real understanding. It doesn't talk about Gödel numbering, which is the real ingenuity behind the proof, and it doesn't talk about omega-inconsistency. At best, it gives you a glimpse of the logic involved and gives you the ability to think up more cute examples that also serve as incomplete explanations. At worst, it might give you a fundamental misunderstanding of the theorem that may cause you to think and say extremely stupid things.

I like these. They are both perfectly correct, and clearly express important and surprising ideas.

They give you an understanding of parts of Gödel's theorem and the Banach-Tarski theorem, but not the whole thing. Mark Dominus' caveat does a good job of indicating the gap between Raymond Smullyan's explanation and Gödel's theorem. There's also a gap between MarkCC's explanation and the Banach-Tarski theorem.

MarkCC puts the natural numbers into one-to-one correspondence with two copies of the natural numbers. Similarly, the points in a ball can be put in one-to-one correspondence with the points in two balls, although it's not immediately obvious. It's easier to see how to put the ball in one-to-one correspondence with a ball of twice the diameter: Just expand the ball. But even knowing this, one might assume that you can't increase the volume of the ball without stretching it somehow. The Banach-Tarski theorem (which requires a lengthier explanation) indicates a way to do just that.

Godel's theorem seems well explained. The Banach-Tarski thing seems like a BS non-explanation:

It starts by asserting an incorrect theorem about spheres, then tries to prove by analogy to something that is totally different and breaks two of the restrictions that were put on the sphere (finite number of pieces, no gaps).

Therefore God.

Pardon my ignorance, but I wasn't aware that the "strange" results dealing with infinite sets of various cardinality were related to the "strange" results related to accepting the axiom of choice. Is this a limitation of my mathematics education, or are the infinite set "paradoxical" results independent of the axiom-of-choice sphere cutting "paradoxical" results?

To really push my understanding of the terminology, I thought that definitions of equivalent size for infinite sets based on one-to-one and onto correspondence did not require reference to the axiom of choice.

Alternatively, I'm not understanding the implications I'm supposed to get from:

How about this? Take the set of all natural numbers. Divide it into two sets: the set of even naturals, and the set of odd naturals. Now you have two infinite sets, the set {0, 2, 4, 6, 8, ...}, and the set {1, 3, 5, 7, 9, ...}. The size of both of those sets is the ω - which is also the size of the original set you started with. Now take the set of even numbers, and map it so that for any given value i, f(i) = i/2. Now you've got a copy of the set of natural numbers. Take the set of odd naturals, and map them with g(i) = (i-1)/2. Now you've got a second copy of the set of natural numbers. So you've created two identical copies of the set of natural numbers out of the original set of natural numbers.

I really like David Morgan-Mar's explanation of the Banach-Tarski theorem.