Thursday, April 21, 2011

What did Banach's Wife think of the Banach-Tarski Paradox?

I recently read and reviewed The Pea and The Sun by Leonard Wapner, which is about the Banach-Tarski Paradox. Recall that the Banach-Tarski Paradox is actually a theorem (not a paradox) that says you can take apart a ball of volume 1 into a finite number of pieces (some of the pieces will be VERY funky) and reassemble to get a ball of volume 2. By repeating this process you can take a pea and get a ball the size of the sun. (My review is here).

When I told my wife this theorem (she has a Masters in Comp Sci and knows some math) she said Math is Broken!!!. She later wondered why mathematicians didn't just toss out The Axiom of Choice (for uncountable sets) since it leads to such an obviously false theorem.

By coincidence, Leonard Wapner had just emailed me to thank me for my review (and to agree that MacArthur Park is the worst song ever written, see this article on my website). SO I put the question to him- why didn't mathematicians just toss out AC since it leads to BT? What follows is an edited version of our back and fourth emails.

BILL: I told my wife the Banach-Tarski Paradox and she wonders why mathematicians didn't just IMMEDIATELY toss out the Axiom of choice for uncountable sets since BT is so obviously false.

LEONARD: I do not believe BT is obviously false. I believe it to be true, based on the axioms of set theory, including AC. Your wife is claiming there are no real world manifestations of the phenomenon. She is not alone with this feeling. Personally, I am highly skeptical of there being any real world models of the BT result. (Those given in the book were clearly labeled as speculations at best.

But, I also believe we can't rule out the possibility, based on mathematical and physical discoveries, to date. BT does not contradict any theorem or axiom. And, it's no more counterintuitive than some Baby BTs (mini version of BT that proceeded it that are also counter-intuitive) and some physical phenomena (relativity, quantum mechanics, etc.)

BILL: By the time BT was proven AC was embedded into the math culture. Many things had already been build on it. Is that why Math folks didn't just toss it out? Would anything important be lost if we tossed uncountable AC out?

LEONARD: I believe it wasn't tossed out because there was no mathematical justification (in the way of a mathematical contradiction) to do so. If AC were to produce a mathematical contradiction, then, being a questionable axiom, it might be tossed. But, there is no mathematical contradiction and I think most mathematicians accept AC. In any case, it would be even more counterintuitive for some to drop it than accept the BT result. AC allows for surprises, but no mathematical contradictions.

I suspect that there are useful theorems, relying on AC, which would be lost if AC were to be tossed. I can't give a specific example now, but I do know that there have been proofs relying on AC which have encouraged others to prove those same theorems without AC. BT, in its usual form, requires AC. Some variations of it do not.

BILL: BT is obv false in the real world. Is this enough of a reason to toss it out (my wife things so).

LEONARD: Coincidentally, my wife asks me the exact same question. And, this is precisely what intrigues me about BT and other paradoxes. As I write above, I prefer to say it is "apparently" false in the real world, rather than obviously false. I can't rule out that which I've not seen simply because I've not seen it.

27 comments:

  1. I assume by "real" world y'all are referring to the "physical" world?

    ReplyDelete
  2. I dislike this hijacking of the words "true" and "false".

    I think he means "consistent" (with ZFC).

    Then you can say it is consistent but false.

    ReplyDelete
  3. I agree with LW: It is not clear that BT contradicts anything in the physical world, since (perhaps) it is not physically possible to implement the required cuts.

    ReplyDelete
  4. As a confection, Rudy Rucker's transfinite novel White Light contains one of the few fictional treatments of the Banach-Tarski Paradox:

    -----------
    "Look, Nick, we can patent the [hyper-matter duplication] process. It's going to be awhile before anyone thinks of using the Banach-Tarski decomposition anyway!"
    -----------

    A related quote (to my mind, anyway!) is from Michael Spivak's Calculus on Manifolds:

    -----------
    "There are good reasons why theorems should all be easy and the definitions hard ... Definitions serve a twofold purpose: they are rigorous replacements for vague notions, and machinery for elegant proofs. ... Stokes' Theorem shares three important attributes with many fully evolved major theorems: (1) It is trivial. (2) It is trivial because the terms appearing in it have been properly defined. (3) It has significant consequences."
    -----------

    Here the point is that (very broadly speaking) those mathematical disciplines (like integers, formal logic, complexity theory, and quantum mechanics) that are founded upon definitions that are simple and easy to learn (like Peano-style counting, axioms and inferences, the complexity class P, and Hilbert space) necessarily are associated to theorems that are intrinsically hard (like the Riemann Hypothesis, Godel Incompleteness, P versus NP, and the complexity-theoretic status of quantum computation).

    In short, from a Spivakian point-of-view, hard theorems like Banach-Tarski are the price we pay for embracing the simple axioms of the point-set theory.

    In striking contrast---according to a natural reading of Spivak's essay anyway---mathematical disciplines like differential geometry and category theory are associated to definitions that are abstract and subtle (hence painful to learn) but whose theorems are trivial in the sense of Grothendieck's celebrated "rising sea":

    -----------
    "The sea [of mathematical reasoning] advances insensibly in silence, nothing seems to happen, nothing moves, the water is so far off you hardly hear it. . . yet it finally surrounds the resistant substance."
    -----------

    We thus appreciate that there is an eminently practical reason for systems engineers to embrace geometric approaches to both classical and quantum mechanics: the practical objective is to "trivialize"—in Spivak's precise and pragmatic sense of the word "trivial"—the analysis of system dynamics in a broad class of practical STEM enterprises.

    For this reason, my sympathies as a systems engineer are very substantially aligned with the instincts of GASARCH's wife ... whenever simple axioms force us to grapple with very hard theorems, it may make solid practical sense to embrace harder axioms, with a view toward finding simpler theorems, that have broader utility in practical applications.

    ReplyDelete
  5. you say back and fourth emails, but there are actually 6 emails !!

    ReplyDelete
  6. Some mainstream mathematician decide not to use axiom of choice. Compare the discussion here:

    http://mathoverflow.net/questions/34843/what-is-realistic-mathematics

    ReplyDelete
  7. "I suspect that there are useful theorems, relying on AC, which would be lost if AC were to be tossed. I can't give a specific example now,"

    Here's an example: Every vector space has a basis. Believe it or not, this is equivalent to full AC. Proven by Andreas Blass in 1984.

    ReplyDelete
  8. With BT the pieces are not physically realizable -- they aren't measurable.

    There are plenty of mainstream mathematical tools that use choice. E.g. Tychonoff's Theorem or the Hahn-Banach Theorem.

    ReplyDelete
  9. I don't understand why one would even think about discarding AC just because of this.

    On the one hand, the Banach-Tarsky paradox is not obviously false, it's just counterintuive, but it does not say anything about the physical world anyway and is certainly not contradicted by it. You're slicing the sphere into parts that have no volume and assembling them. It's "only" very surprising, but just that. (By the way, there are also similar-looking surprising statements that can be proved without AC anyway).

    On the other hand, AC is obviously true: if you have a family of non-empty sets, the fact that each
    set is non-empty means that there is at least one element in each; so for each set just pick one
    element, doesn't matter which. One may complain that there may not be a way to define which particular subset was selected, but that's irrelevant to the question of *existence* of some point in the cartesian product. You can only toss AC if you artificially restrict what you mean by "exist". Nowhere in (mainstream) mathematics is the inability to construct a explicit example a hidrance to the existence of the example, and I don't see why an exception should be made for this.
    (By the way, the fact that the sets may be large doesn't make it any harder to pick one element from each; it is just hard to *specify* the particular ones you picked).

    ReplyDelete
  10. How about to consider the possibility that R^3 is not the right space for modelling physical balls?

    ReplyDelete
  11. I like the answer from Anonymous@3:23pm. Keep Choice, and beware of using R^3 to model physical objects.

    For example, I'd guess that modeling physical objects using a fine-grained, discrete grid would avoid this paradox.

    The real reason to avoid AC is that proofs without AC feel more satisfying. However, a proof using AC is immeasurably better than no proof at all.

    ReplyDelete
  12. First read about this in http://www.amazon.com/Mathematics-Loss-Certainty-Galaxy-Books/dp/0195030850 -- lots of fun!

    ReplyDelete
  13. It's funny but I've always had the exact opposite problem from your wife, and maybe from most people on first hearing the "paradox". The Banach-Tarski Paradox just always struck me as obviously true. There's uncountably many points. You can put those in two piles with an uncountable number in each pile. You can make each pile into a sphere. So? What's paradoxical?

    No, no, people say. You can't disassemble one sphere into two spheres, you disassemble one sphere into four funky pieces and if you do it just right it only takes two funky pieces to reassemble a sphere and you won't have anything left over.

    So then (for me) everything hinges on what the heck assembly and disassembly means and that leads to rigid motions and how you rigidly move piles of points that don't seem to be all connected in the way that I think of rigid points as being connected. Way too much work and thinking to still be naively amazed at the end.

    No, no, people say, just think about the simple concepts, you've got one sphere and you can get two spheres. Yeah, yeah, I can do that all day long, isn't that just the old there are just as many hotel rooms with even numbers in the infinite hotel as there are hotel rooms altogether. No, no, you've missed the point, this is something different, it doesn't follow so easily.

    First time I was ever amazed was when I finally saw a proof a couple years ago which was easier than i had guessed considering nobody ever talks about the proof.

    Oh well. Got anything else amazing to show me?

    ReplyDelete
  14. Bill, this feels like one of your homework questions; "prove that if an object that can't exist is created, then a pea can become the sun".

    ReplyDelete
  15. There is nice book which I don't remember its name unfortunately which collects a number of interesting results in three chapter. The first chapter is paradoxes that arise from accepting AC if true, the second chapter is paradoxes that arise from accepting AC is false, and the third chapter is about paradoxes that arise ... well, I will not tell you so you will go and find the book, but you can guess what third chapter is about.

    ReplyDelete
  16. I have two questions:

    can you create a countable number of balls with the same volume as the original?

    can you create an uncountable number of balls with the same ball as the original?

    ReplyDelete
  17. Micki: "Oh well. Got anything else amazing to show me?"

    Sure. If you really believe your own argument, then you should be quite surprised to hear that Banach-Tarski's 2D analog is false.

    ReplyDelete
  18. I would be more inclined to believe that the physical universe is discrete than that the AC is "false".

    The mathematical universe is a weird place.

    ReplyDelete
  19. The fundamental misunderstanding with objections to AC based on physical intuition is to think that 4-dimensional space-time has anything to do with R4. In fact, I would argue, that rather than being isomorphic with the continuum, it is much more likely that the physical universe is finite and discrete, and hence entirely countable. AC gives us a rich mathematical universe, and Banach-Tarski can be seen as a spectacular demonstration of the immense denseness of the the Continuum.

    Halfdan Faber

    ReplyDelete
  20. gasarch, u are married ? this is new .... and wonderful news. who would have guessed.

    ReplyDelete
  21. Doesn't the law of excluded third in propositional logic depend on AC? At least the common proof does, maybe something a bit weaker than AC is sufficient.

    ReplyDelete
  22. Other comments have implicitly mentioned this, but to me (biased as a set theorist tends to be) the Banach-Tarski paradox is more a paradox about our idea of measure. The Lebesgue measure is the culprit -- it's just a "bad" measure in that there are non-measurable sets. But this is not so surprising since we start with our intuition of volume and do some non-trivial mathematics to get the Lebesgue measure.

    This point of view leads down a different road since on further investigation the reals are the culprit since they do not allow for a better measure; and then there are so many things "wrong" with the reals...

    ReplyDelete
  23. This discussion overplays the role of AC in achieiving Banach-Tarski paradoxes. In 1994, Dougherty and Foreman showed that there are "paradoxical" unit ball decompositions which have the property of Baire. Similar "paradoxes" can be acheived constructively using only open sets and without appealing to the Axiom of Choice.

    ReplyDelete
  24. I told my wife about the Banach-Tarski paradox, and she said that this showed AC was obviously ridiculous and must be discarded.

    Then I told her that (not AC) implied that an infinite Chinese menu, with infinitely many columns and infinitely many choices in column, could be empty.
    (As I phrased it, infinity to the infinity power could be equal to zero). She said that this showed that (not AC) was obviously ridiculous and must be discarded.

    ReplyDelete
  25. How about give up Choice, and give up R (and uncountability) at the same time (restricting us to some definition of "definable reals")?

    ReplyDelete
  26. I see no need to take a position as to whether AC is "true" or "false". Set theory is not the real world -- it is only a formal system which, hopefully, models some aspects of the real world.
    In the corner of the math world that I inhabit, it is not normal to rely on AC to prove theorems, and in presenting any theorem whose proof depended on AC, I would certainly note that fact when stating the theorem.

    By the way, the proof of BT is not that esoteric. I can recommend the book "The Banach-Tarski Paradox" by Stan Wagon. In one short chapter which took me less than an hour to read, he sketched a proof that I found totally convincing.

    ReplyDelete
  27. I am not sure whether I should be surprised about this theorem or not, because that it is possible to find an onto mapping from an infinite set to two other infinite sets is commonplace in mathematics.
    One can make an example even from denumerable sets:
    A: a1, a2, a3, ...
    B: b1, b2, b3, ...
    C: c1, c2, c3, ...

    Mapping M, maps a(2i) to b(i) and a(2i - 1) to c(i).

    ReplyDelete