tag:blogger.com,1999:blog-3722233.post2459498477941171074..comments2024-03-27T19:58:17.387-05:00Comments on Computational Complexity: What did Banach's Wife think of the Banach-Tarski Paradox?Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger27125tag:blogger.com,1999:blog-3722233.post-11384013242924609672011-06-08T04:31:50.431-05:002011-06-08T04:31:50.431-05:00I am not sure whether I should be surprised about ...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. <br />One can make an example even from denumerable sets:<br />A: a1, a2, a3, ...<br />B: b1, b2, b3, ...<br />C: c1, c2, c3, ...<br /><br />Mapping M, maps a(2i) to b(i) and a(2i - 1) to c(i).Majdodinhttps://www.blogger.com/profile/06638299762577890471noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-87112664943643766762011-05-06T20:21:02.299-05:002011-05-06T20:21:02.299-05:00I see no need to take a position as to whether AC ...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.<br />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.<br /><br />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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-73111163628052460642011-04-28T21:00:39.466-05:002011-04-28T21:00:39.466-05:00How about give up Choice, and give up R (and uncou...How about give up Choice, and give up R (and uncountability) at the same time (restricting us to some definition of "definable reals")?Panhttps://www.blogger.com/profile/12086932411600314924noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-72678592550409775892011-04-26T10:37:19.557-05:002011-04-26T10:37:19.557-05:00I told my wife about the Banach-Tarski paradox, an...I told my wife about the Banach-Tarski paradox, and she said that this showed AC was obviously ridiculous and must be discarded.<br /><br />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.<br />(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.Davidhttps://www.blogger.com/profile/13818371550669837787noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-59288534145044430862011-04-25T22:51:19.844-05:002011-04-25T22:51:19.844-05:00This discussion overplays the role of AC in achiei...This discussion overplays the role of AC in achieiving Banach-Tarski paradoxes. In 1994, Dougherty and Foreman <a href="http://www.jstor.org/pss/2152721" rel="nofollow">showed</a> 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.Teutschhttps://www.blogger.com/profile/04848264673734802964noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-25177643866927453592011-04-23T11:11:00.063-05:002011-04-23T11:11:00.063-05:00Other comments have implicitly mentioned this, but...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.<br /><br />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...Peternoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-46526822524899518562011-04-23T07:33:48.332-05:002011-04-23T07:33:48.332-05:00Doesn't the law of excluded third in propositi...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.Ralf Muschallhttps://www.blogger.com/profile/04261178237250734174noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1229922700175876922011-04-23T05:53:45.362-05:002011-04-23T05:53:45.362-05:00gasarch, u are married ? this is new .... and wond...gasarch, u are married ? this is new .... and wonderful news. who would have guessed.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-47111957833740973922011-04-22T22:29:08.441-05:002011-04-22T22:29:08.441-05:00The fundamental misunderstanding with objections t...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. <br /><br />Halfdan FaberAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-44131224755257035082011-04-22T04:40:19.247-05:002011-04-22T04:40:19.247-05:00I would be more inclined to believe that the physi...I would be more inclined to believe that the physical universe is discrete than that the AC is "false".<br /><br />The mathematical universe is a weird place.Anonymoushttps://www.blogger.com/profile/09364120444779754928noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-77193208162750847752011-04-22T02:19:16.004-05:002011-04-22T02:19:16.004-05:00Micki: "Oh well. Got anything else amazing to...Micki: "Oh well. Got anything else amazing to show me?"<br /><br />Sure. If you really believe your own argument, then you should be quite surprised to hear that Banach-Tarski's 2D analog is false.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-68456285639339487002011-04-22T00:35:00.210-05:002011-04-22T00:35:00.210-05:00I have two questions:
can you create a countable ...I have two questions:<br /><br />can you create a countable number of balls with the same volume as the original?<br /><br />can you create an uncountable number of balls with the same ball as the original?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-444525915730457832011-04-21T20:11:58.755-05:002011-04-21T20:11:58.755-05:00There is nice book which I don't remember its ...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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-14645059949291335702011-04-21T18:46:01.694-05:002011-04-21T18:46:01.694-05:00Bill, this feels like one of your homework questio...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".Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-52851341174160735062011-04-21T18:20:28.761-05:002011-04-21T18:20:28.761-05:00It's funny but I've always had the exact o...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?<br /><br />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.<br /><br />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.<br /><br />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.<br /><br />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.<br /><br />Oh well. Got anything else amazing to show me?Mickihttps://www.blogger.com/profile/11592612022853202507noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-91671032525284325592011-04-21T16:52:19.956-05:002011-04-21T16:52:19.956-05:00First read about this in http://www.amazon.com/Mat...First read about this in http://www.amazon.com/Mathematics-Loss-Certainty-Galaxy-Books/dp/0195030850 -- lots of fun!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-3089313349322588662011-04-21T15:52:42.463-05:002011-04-21T15:52:42.463-05:00I like the answer from Anonymous@3:23pm. Keep Choi...I like the answer from Anonymous@3:23pm. Keep Choice, and beware of using R^3 to model physical objects.<br /><br />For example, I'd guess that modeling physical objects using a fine-grained, discrete grid would avoid this paradox.<br /><br />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.Lex Spoonhttps://www.blogger.com/profile/13859632965228608649noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-8450429097347725032011-04-21T15:23:52.913-05:002011-04-21T15:23:52.913-05:00How about to consider the possibility that R^3 is ...How about to consider the possibility that R^3 is not the right space for modelling physical balls?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-9391864515825890772011-04-21T14:04:58.124-05:002011-04-21T14:04:58.124-05:00I don't understand why one would even think ab...I don't understand why one would even think about discarding AC just because of this.<br /><br />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).<br /><br />On the other hand, AC is obviously true: if you have a family of non-empty sets, the fact that each<br />set is non-empty means that there is at least one element in each; so for each set just pick one<br />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.<br />(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).Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-87364284599203050932011-04-21T13:27:33.617-05:002011-04-21T13:27:33.617-05:00With BT the pieces are not physically realizable -...With BT the pieces are not physically realizable -- they aren't measurable.<br /><br />There are plenty of mainstream mathematical tools that use choice. E.g. Tychonoff's Theorem or the Hahn-Banach Theorem.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-35672017539974448482011-04-21T13:01:52.632-05:002011-04-21T13:01:52.632-05:00"I suspect that there are useful theorems, re..."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,"<br /><br />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.Xamuelhttp://www.xamuel.comnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-76274000310859150762011-04-21T10:59:35.975-05:002011-04-21T10:59:35.975-05:00Some mainstream mathematician decide not to use ax...Some mainstream mathematician decide not to use axiom of choice. Compare the discussion here:<br /><br />http://mathoverflow.net/questions/34843/what-is-realistic-mathematicsLukasz Grabowskihttps://www.blogger.com/profile/12330558387447969321noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-21645979667333387812011-04-21T10:55:20.779-05:002011-04-21T10:55:20.779-05:00you say back and fourth emails, but there are actu...you say back and fourth emails, but there are actually 6 emails !!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-54895386299748781262011-04-21T10:12:10.121-05:002011-04-21T10:12:10.121-05:00As a confection, Rudy Rucker's transfinite nov...As a confection, Rudy Rucker's transfinite novel <i>White Light</i> contains one of the few fictional treatments of the Banach-Tarski Paradox:<br /><br />-----------<br />"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!"<br />-----------<br /><br />A related quote (to my mind, anyway!) is from Michael Spivak's <i>Calculus on Manifolds</i>:<br /><br />-----------<br />"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."<br />-----------<br /><br />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).<br /><br />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.<br /><br />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":<br /><br />-----------<br />"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." <br />-----------<br /><br />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.<br /><br />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.John Sidleshttp://faculty.washington.edu/sidlesnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-32419083098971518802011-04-21T09:50:44.482-05:002011-04-21T09:50:44.482-05:00I agree with LW: It is not clear that BT contradic...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.Anonymousnoreply@blogger.com