I did my undergraduate project on the question of finitely-additive, isometry-invariant measures that extend the Lebesgue Measure and which are defined on all possible bounded subsets of R^n.
And yes, that's relevant. There is (perhaps surprisingly) such a measure on R,and there is such a measure on R^2, but the Banach-Tarski "paradox" shows that there is no such measure on R^3 (and therefore trivially, R^n for n>3).
For contrast, we'd usually like to have a measure that's countably additive, but there is a simple construction (albeit using the axiom of choice) that shows such an object is impossible.
This has, by the way, been submitted and discussed several times in the past. In case you're interested in reading other descriptions, and previous discussions, you can find some of them here:
Wikipedia says you can collapse two balls into one, so doesn't that mean you can cut your ball in half, mold the halves into balls, and then merge those two half-volume balls into one half-volume ball? And if you can do that, can't you get to an infinitely small ball?
norvig's comment didn't exist when I started mine, but by the time I'd typed all my comment in, norvig's had appeared. I toyed with the idea of deleting the riddle from mine, but have decided to leave it.
I'm a bit confused here. The site is "Hacker News", however I'm seeing more and more wikipedia articles posted here which are not news at all. I think Banach-Tarski paradox is a fascinating thing, and when I first heard about it (years ago) it blew my mind, but posting wikipedia articles with neat, but old facts is not exactly the news.
It's new for some. It doesn't have to be newly created content, as long as it gets people interested (which usually means that for many it is new). At least it is an unwritten rule.
With a site experiencing even the smallest exponential growth, this definition of "interesting" will cause most I the material posted to recur on a fixed schedule as the number of people who haven't seen it yet drifts above some threshold. This condition is only excaserbated by existing users leaving (which will of course happen on some other predictable curve). On Hacker News, many of us feel this schedule I currently "three months".
As I understand it, the Banach-Tarski construction depends on the axiom of choice. And Banach-Tarski violates my intuitions so thoroughly that I think I might prefer to dispense with the axiom of choice than accept B-T.
If you do give up the axiom of choice, is there a lot of cool/useful math that you'd also have to give up?
Does it bother you that by dividing all the integers into odd and even numbers, I can end up with two infinite sets, each of the same size as the original set?
While the Banach-Tarski violates your intuitions, it is probably because it is more about how there are "multiple copies" of the real numbers in the real numbers, than anything resembling a real cut.
Not to nitpick or assume you we're saying this, but doesn't the cardinality of the evens and odds equalling the cardinality of the integers hold even without the axiom of choice?
Yes, the argument is more complicated, and does require the axiom of choice.
However, to me the "basic principle" is a similar argument. The important thing (for me) was to understand this is an argument about slicing up infinities in an "Infinite comb" type way, rather than anything resembling a "cut".
Hilbert's basis theorem is the big one, and the reason the axiom was invented. But you can get very far without it - you just have to be very careful about it, because the operation of choosing an arbitrary representative of each of many sets is so natural it can be hard to realize you've used the axiom.
Your third example is often cited as an unintuitive result, so I wouldn't mind getting rid of it. The first and second are easy enough to consider collateral damage, which we already have plenty of in basic math. But the fourth one is harder to give up. What would it look like without the axiom?
The axiom of choice makes everything simpler. Which helps a lot when we're talking about things like infinite dimensional vector spaces.
That said, it is a theorem that absolutely no theorem of number theory can possibly depend on the axiom of choice. So absolutely no "real" consequence can come from accepting or not the axiom of choice.
mathematicians like it, but physicists and computer scientists seem to be able to get by without it (based on answers i've received asking the same q in the past).
Very interesting read. I've been thinking about it for a while, and although the explanation in the article makes sense to me, I wonder if the following is equivalent:
Consider a spherical surface S. We can construct a mapping from the point of S to the points in a finite and limited subset of R^2 (say, the square [0, 1] X [0, 1]). One way to do that is to map each point of "latitude" ρ and "longitude" θ (in degrees), to the point ((ρ+90)/180, θ/360).
Now, let's consider the rectangle [0, .5] x [0, 1]. There is obviously a 1:1 mapping from this to the original square (just halve or double one of the coordinates to change from one to the other). In an intuitive sense, there are "as many" points in half the square as in the whole square, a bit like there are as many natural numbers as there are even numbers. (This is one definition of infinite set, if I remember correctly).
Now this means that we can remap all the points from half the square to a complete sphere, and the points from the other half square to a "new" complete sphere, in fact mapping points from the original sphere S to two new identical spheres.
Is this reasoning correct, or am I missing anything (probably something obvious...)?
i'm not a mathematician either, but i think the mistake you're making is in neglecting the difference between "subset A of the sphere has as many points as the entire sphere" and "here's a way to cut a sphere into subsets, and reassemble the subsets into two spheres". intuitively, your mapping scheme involves stretching, shearing and discontinuous transforms on the subsets before you get two spheres out of it - it is pretty obvious from the mathematics of infinite sets that you can always do this, so there's no real "paradox" involved.
Once I understood this, I find it is a bit a cheat (as you might expect). The 'cuts' are not cuts in any real-world sense.
Hopefully you are happy with the idea that there are as many integers as there are both even integers or odd integers. Therefore in some sense I can "cut" the integers into two equally sized sets. This paradox does something very similar on the real numbers, making use of the form of the real numbers to avoid the "doubling" effect I got when cutting the integers.
It doesn't do it on the real numbers at all, it does it on a subset of rotations in R^3.
You're right that these aren't "pieces" in the intuitive visual sense. That's why Feynman ridiculed the result, because in the initial description given to him he assumed physical pieces, not pairwise disjoint sets.
But it is a way in to understanding the way things work. It helps to have simpler situations that exhibit aspects of the whole thing.
I remember being told about the library that has all finite books that can possibly be written. Every finite string of characters appears as a book. Obviously there are infinitely many, but we won't worry too much about that.
Now we find that someone, overnight, stole all the books except for those that start with the letter "q". We're annoyed at first, but then someone suggests we just erase the initial "q" from all the remaining books.
So we do that, and lo and behold! We have the full collection again! We even now have an extra book, one that's completely blank!
It's not a paradox, but it is the way infinite things can work, and it shows how 1/26 of a collection can be the same as the whole collection. This is related to how the B-T "paradox" works, but it's very much over-simplified.
Even so, it's a useful place to get people starting to think about things in the right way.
I watched that, constantly wondering when it would become interesting. Or funny. Or clever. Or anything other than a waste of time.
It didn't.
Added in edit: Fascinating - Someone down-voted this comment. Here I was thinking it would be helpful that people who trust my opinion will know not to waste their time, and people who don't know me can use this comment to see if their taste in these things matches mine. But no, someone just thinks it's of negative value. Interesting. I'm always learning new things about the HN community.
Your comment is a little harsh, but totally accurate. I saw all the video and I want my 3:42 minutes back!
(Note: I remember that one of my comments initially got two or three downvotes in spite of having only accurate relevant facts (not opinions), I got a little worried but it bounce and finally that comment got like 12 points. Don't worry, be happy!)
The drawing on the page is confusing. It depicts the "pieces" as contiguous solid chunks--but in order to reassemble the sphere into two, don't you have to pick sets which are more like general predicates on the points of R^3? Those don't look like puzzle pieces.
It's like depicting the irrational numbers by coloring everything on a number line between pi and e blue.
Is it possible to do the cut-up-and-reassembly trick with a finite number of sets where the membership is computable? If so the "Banach-Tarski Algorithm" for the special case of duplicating the sphere might be helpful for understanding.
No, you can't do it with computable sets, because if you could then there'd be a proof that doesn't need the Axiom of Choice, but Banach-Tarski can fail without the Axiom of Choice. (For instance, without AC it can happen that all subsets of R^n are Lebesgue measurable, and then Banach-Tarski is impossible.)
[EDITED to add: er, actually in order to prove that "without AC it can happen that all subsets of R^n are Lebesgue measurable" you need there to be an inaccessible cardinal. If you don't know what that means, ignore it. I'm mentioning it just to avoid leaving a false statement in the record.]
The theorem explains US fiscal cliff reasons: there are infinite number of cents between $0 and $1. If we have infinite number of cents - we can buy infinite number of things!
Now you know the whole story.
A: Banach-Tarski Banach-Tarski.
I did my undergraduate project on the question of finitely-additive, isometry-invariant measures that extend the Lebesgue Measure and which are defined on all possible bounded subsets of R^n.
And yes, that's relevant. There is (perhaps surprisingly) such a measure on R,and there is such a measure on R^2, but the Banach-Tarski "paradox" shows that there is no such measure on R^3 (and therefore trivially, R^n for n>3).
For contrast, we'd usually like to have a measure that's countably additive, but there is a simple construction (albeit using the axiom of choice) that shows such an object is impossible.
This has, by the way, been submitted and discussed several times in the past. In case you're interested in reading other descriptions, and previous discussions, you can find some of them here:
http://www.hnsearch.com/search#request/all&q=banach+tars...