The Strangeness of Choice: the Banach-Tarski Paradox

Today, I'm going to try to show you an example of why the axiom makes so many people so uncomfortable. When you get down to the blood and guts of what it means, it implies some *very* strange things. What I'm going to do today is tell you about one of those: the Banach-Tarski paradox, in which you can create two spheres of size S out of one sphere of size S cutting the single sphere into pieces, and then gluing those pieces back together. Volume from nowhere, and your spheres for free!

As I said in the post on the axiom of choice, it was very controversial at first: controversial enough that many people made attempts to disprove it. The most famous of those attempts was developed by two mathematicians: Stefan Banach and Alfred Tarski, based on the work of Hausdorff. They produced a result which goes beyond unintuitive and into the realm of downright strange. Their result is now known as the Banach-Tarski paradox (although strictly speaking, it isn't a paradox), and while it failed as a disproof of the axiom of choice, it's now commonly used as the example of why the axiom of choice is weird.

What the BT paradox says is that it's possible to take a sphere, cut it into a small
finite number of pieces, and to reassemble those pieces into two spheres the same size as the original. This involves *no* stretching or deformation of the pieces at all: just translation, and rotation. There are *no* gaps in the two spheres. No copying of pieces. No clever tricks *at all* in how you glue the pieces together to form new spheres - and yet the volume doubles. You've gotten 2 spheres from one.

How does it work? Of course there's a trick to it. Banach and Tarski *thought* that the trick should serve as a disproof of the axiom of choice - so it's not a simple trick.

The trick, such as it is, involves the *shape* of the pieces. The shapes consist of *unmeasurable* sets of points: intuitively, their shapes are so complex that you can't describe them accurately even using a countably infinite number of points. So it's not something that you can actually do with a model of a sphere: these "shapes" have no measurable volume (in the sense that their volume and surface area isn't definable), and their edges aren't finite.

But there's a formulation of a constraint in terms of sets where the axiom of choice says that these sets *exist*, even if we can't find them.

The proof of it goes way beyond what I want to write here. The basic idea of it is that there's a geometric notion of equidecomposablility: two objects A and B are equidecomposable if and only if they can be broken into sets A=∪i=1,nai and B=∪b=1,jbj where there's a one to one mapping between the ai and bj such that ai maps to bj if and only if ai is geometrically congruent with bj.

Through some nifty trickery with group theory and the AC, you can then show that two spheres are equidecomposable with a single sphere *minus* the center point; and then separately show that the sphere minus the missing point is equidecomposable with the sphere. The whole thing works off of choice by choosing elements from the powerset of points in the sphere: using choice, you can infer the existence of bizarre
nonconstructable sets that happen to meet the requirements.

If the idea of creating phantom volume out of nowhere through the axiom of choice doesn't make it clear to you why people are bothered by it, then I don't know what will.

Tags

More like this

I did that with a bagel!

Really. I cut it in half and spread about a pound of cream cheese on each half.

I could only eat HALF the bagel! It was like eating the whole thing. I doubled it by cutting it in half. I had no idea I was a math genius.

http://golem.ph.utexas.edu/category/2007/06/quantization_and_cohomology…

"... Of course the axiom of choice does fail in the category of topological spaces, or smooth spaces. This is very much linked to how bundles work! So, Toby noticed that while the axiom of choice fails in these categories, it still holds 'locally' for certain 'nice surjections' p:EâB, of the sort we study in bundle theory."

"In other words, while bundles don't usually have global sections, they always have local sections! So, in the category of smooth spaces, the axiom of choice only holds 'locally'!..."

/scratching my head..
Can i cut this paradox in half and glue it back together.. but correctly this time?

By Ryan Dickie (not verified) on 04 Jun 2007 #permalink

A friend of mine found an interesting anagram of "BANACH TARSKI".

It's "BANACH TARSKI BANACH TARSKI"...

By Ashley Y. (not verified) on 04 Jun 2007 #permalink

Very clever. I'm trying that anagram on my maths lecturer.

By ferfuracious (not verified) on 04 Jun 2007 #permalink

Volume from nowhere, and your spheres for free!

'We gotta move these unmeasurable sets?'

Hmm. Think the original was better, sadly.

By Anonymous (not verified) on 05 Jun 2007 #permalink

I've always thought that there's somewhat less to Banach-Tarski than meets the eye. There is an interesting and important point if you're interested in measure theory: that AC leads to the conclusion there are sets for which the notion of 'volume' of cannot be defined in a consistent fashion.

Is that something like the Cantor set being 1-1 equivalent to the interval [0,1] despite being measure 0 in size?

That's weird, too, but no one ever called it a paradox.

It's worth noting that Banach-Tarski can be viewed in a good light -- the existence of such paradoxical decompositions on a space corresponds (by a theorem of, who else, Tarski) with the existence of a nice (additive, isometry-invariant, measure zero on the null sets) measure that assigns measure 1 to the whole space.

Mark!

I'd be happy if you would write some words about the opposite. I mean, there are a number of statements that seem to be trivial, but unprovable without AC.

Wikipedia says that AC is eqivalent to the statement that every vector space has a basis. Also it says that AC is equivalent with that the Cartesian product of any nonempty family of nonempty sets is nonempty.

As far as my limited vision allows me to see, both AC and the lack of AC leads to outrageous consquences.

By krisztian pinter (not verified) on 05 Jun 2007 #permalink

If the idea of creating phantom volume out of nowhere through the axiom of choice doesn't make it clear to you why people are bothered by it, then I don't know what will.

Yes, but they are probably the same persons that are bothered by axiom sets that allow infinities to exist, even if we can't find them.

krisztian,

Mark and commenters discussed consequences and equivalent statements rather thoroughly here.

Btw, Wikipedia may be slightly off on the power of the existence of vector basis. Commenter Zeno claims on the above thread that "existence of a basis in every vector space is a popular consequence of AC, but in ZF it is strictly weaker than AC, not equivalent".

outrageous consquences

FWIW, my personal take on AC is like infinities and other idealizations that work well, it is easier or even necessary to work with them to get the most out of the math. So I can allow myself to not be bothered, but rather pleased, with outrageous consequences.

By Torbjörn Lars… (not verified) on 05 Jun 2007 #permalink

Or science fiction:
The technical basis for a bigifying machine?

Using Heisenberg decouplers to reduce a contained mass of neutronium to a purely probabilistic state which can be continuously manipulated (unlike traditional quantized matter)? I thought you'd never ask!

By undebigulator (not verified) on 05 Jun 2007 #permalink

>Or science fiction

Rudy Rucker used it in "White Light". Which is finally back in print.

I'd recommend it to anybody that likes this blog...it's about a mathematician who astrally projects to the outskirts of Heaven, and finds that he's got access to some of the lower-order infinities while he's there. (He can count from 1 to Aleph-null by speaking the numbers faster and faster, so that each takes half the time of the one before it.) It's got a rudimentary plot, but it's really more of a "Flatland"-style exploration of the mathematics.

By chaos_engineer (not verified) on 05 Jun 2007 #permalink

Is that something like the Cantor set being 1-1 equivalent to the interval [0,1] despite being measure 0 in size?

Not really. Certainly there is a function f which maps the Cantor set onto the interval; I believe one can even choose f to be continuous. However, it isn't geometrically nice at all; it plays merry hell with distances and lengths. It's kind of weird, in the way infinities are always kind of weird, but it's not really contrary to intuition (inasmuch as there is any sort of intuition on the subject).

The functions which rearrange the sets in Banach-Tarski are all rigid motions, which means they preserve distances, lengths, and volumes. You'd think that we could assign every subset of R^3 a volume which was compatible with our usual notions (which assigned the unit cube the volume 1, for example) and which behaved nicely under unions and intersections and such. However, if we could do that, then the volumes of the sets before and after rearrangement would be the same, and that clearly isn't so; Banach and Tarski took a set with positive volume and doubled that volume.

The fact that we can't assign every subset of R^3 (or R, for that matter) a volume in a sensible way was once seen by some as a good reason to believe that AC was false, especially since we start and finish with perfectly sensible sets. (Maybe this is still considered evidence against AC; I'm not familiar with the "anti-Choice" viewpoint). Hence "paradox".

By Chad Groft (not verified) on 05 Jun 2007 #permalink

I've never seen what's so great about the B-T paradox. You start with the unit ball in R3. The real line (and thus R3) doesn't correspond with anything existent in real life when you really get down to it, so the 'revelation' that you can do things with R3 that you can't do with actual volumes seems pretty obvious. I mean, just the fact that there's a mapping from [0,1] to [0,2] would seem to imply that there's absolutely nothing rigid about 'volumes' in R (I blindly assume that the mapping doesn't use AC ^_^).

The only weird parts are some of the details, like that only 5 pieces are needed (and the 5th is only necessary to hold the center point, and may in fact be composed of *only* the center point), and that you can rearrange it all with perfectly rigid motions without the pieces intersecting each other. Those are just interesting curiousities, though, I would think.

By Xanthir, FCD (not verified) on 05 Jun 2007 #permalink

Hey, I was told you have a PhD in computer programming ...what's this got to do with computer programming?!

By truth machine (not verified) on 05 Jun 2007 #permalink

"Hey, I was told you have a PhD in computer programming ...what's this got to do with computer programming?!"

CAN you get a PHD in programming, didn't know that...computer science? informatics?

Anyhow math and CS have an intimate if occasionally ambivalent relationship.

By Anonymous (not verified) on 06 Jun 2007 #permalink

Is this how you make a Tardis?

Mark (and/or others),

I was thinking about this last night and I'd like to ask a meta-question.

When a proof provides a "nonsensical" answer, how do you determine whether there is a problem with the steps, or that the issue under discussion is "just weird"?

Suppose two mathematicians are sitting down at lunch and the conversation goes:

Prof. A:
a) Start with simple statement.
b) Apply axioms to get other following statements.
c) End with a statement that is non-sensical.

Prof. B:
d1) Hmm, application of one or more of the axioms was done wrongly.
or
d2) Hmm, these axioms behave strangely. Cool!

Is distinction of these two responses simply based on preponderance of evidence?

I was thinking of the classic proofs of "1=0", where the appropriate response is d1 because "dividing both sides of an equation by 0" is not a valid application of algebra (or some other similar mistake.)

But it appears that the same script applies to BT and the response has been d2, that axiom of choice does, in fact, behave strangely.

Do people believe BT is valid because enough folks of enough reputation have looked at it over enough time to believe that there isn't a mistake of application of axioms involved?

Just curious,
-Richard

To the best of my understanding, it works like this:

If the math in question is modeling a physical phenomena, we can simply compare test the 'weird' results and see if anything turns up. If the tests disagree with the math, then we know the model is flawed and can start correcting it. If it agrees, then reality proves itself to be, once again, stranger than we imagined. ^_^

If we're just talking about pure math, then it's much more complex. The real question, then, is "Is this a useful result?" If something leads to contradiction, we can throw it out immediately. If it's just weird, then it might still be useful. I think we pretty much just judge it based on that.

For example, admitting in a rule that allowed division by zero allows a contradiction. Even if it didn't, though (and I believe there are algebras where division by zero is well-defined and acceptable), it's not useful to be able to divide by zero. The consequences of those axioms leads to even further strangeness and just starts generally messing things up. Thus, we don't generally allow it in.

AC, on the other hand, brings us a rich bounty of useful results. You get the occasional weird thing, but most can overlook those, or don't think they're weird at all (as I said earlier, I don't see what's paradoxical about B-T at all). So, unless someone can come up with an alternate treatment that brings us all the goodness of AC with none of the weirdness, we'll keep using it.

By Xanthir, FCD (not verified) on 07 Jun 2007 #permalink

Richard, it's a question of what "nonsensical" means. There are two very different types of statements, both of which could be called nonsensical.

One is statements that are counterintuitive. The BT paradox is such a statement. Achieving a result like that elicits a response of type d2.

The other is statements that are contradictory. They go against something we already know to be true. 0=1 is such a statement. These garner response d1.

Of course, people make mistakes. There are instances of people thinking something was contradictory, when in fact it was simply counterintuitive. Similarly, there are instances of people not recognizing when they had something contradictory.

By Antendren (not verified) on 07 Jun 2007 #permalink

Thanks Xanthir & Antendren.

Counterintuitive != contradictory. That makes it clearer for me.

-Richard

Maybe we could put this process to some use pratically by reversing the paradox.

We have got all this nasty nuclear wast gunk lying about and we need to do something about it - right?

So we set up our iksra chanab factory ( so called because it reverses the paradox) and we solidify the waste and make big spheres with it - see where I am going with this?

Then we deconstruct the spheres in pairs using our iksra chanab machine and reconstruct these parts of two spheres each of size s into only one sphere of size s. And hey presto we have reduced our waste problem. Of course a further refinement of the machine is to do this process recursively. (Patent pending)

Of course a further refinement of the machine is to do this process recursively.

I will do you one better - I am currently patenting self-assembling iksrat chanab machines. I expect the prototype to disappear within a Planck volume any day now. It will be the basis for the ultimate planckite technology.

Could we cooperate on a gold making factory to finance though, to finance operations? I have trouble with the corresponding inverted banach tarski factory. It is a paradox, really.

By Torbjörn Lars… (not verified) on 11 Jun 2007 #permalink

I agree with Xanthir, that it is hard to see what is so paradoxical (if anything) about this sphere decomposition (if anyone knows, please let me know too). Apart from that, I'm just enjoying so much talk about sets.

"CAN you get a PHD in programming, didn't know that...computer science? informatics?

Anyhow math and CS have an intimate if occasionally ambivalent relationship."

It was a joke -- on William Dembski. MarkCC gets it, even if you don't.

By truth machine (not verified) on 13 Jun 2007 #permalink

By the way, there is a much simpler form of Banach-Tarski which, while less counter intuitive, contains the essence of the proof.

Theorem: It is possible to take a circle, cut it into a countably infinite number of pieces, and rearrange them to make two circles of the same radius as the original circle.

Proof: Choose an irrational number alpha. Define an equivalence relation on the circle where two points are equivalent if they differ by an integer multiple of alpha*2 pi. Now (here comes the Axiom of Choice) in each equivalence class, choose one element. Call the set of chosen elements S. The circle is the disjoint union of S_k:=S+k*(alpha 2 pi), as k runs through the integers. Then we can take the pieces ... S_{-4}, S_{-2}, S_{0}, S_{2}, S_{4} ... and rotate them to form a new circle, turning S_{2k} into the position previously occupied by S_k. Similarly, we can take the pieces S_{-3}, S_{-1}, S_{1}, S_{3}, ... and glue them together to form a second circle. QED

In this proof, we used the rotations of the circle. The actual BT theorem uses the rotations of the sphere, which form a noncommumative group. That noncommutativity gives you enough room to get down to a finite number of pieces, while making the details much more complicated, but the ideas are the same.

If you want to read the details, a good source is Francis Su's Exposition

By David Speyer (not verified) on 27 Jun 2007 #permalink