Explained: Gödel’s theorem and the Banach-Tarski Paradox
I want to share the following explanations that I came across recently and which I enjoyed very much. I can’t tell and don’t suspect that they come close to an understanding of the original concepts but that they are so easy to grasp that it is worth the time if you don’t already studied the extended formal versions of those concepts. In other words, by reading the following explanations your grasp of the matter will be less wrong than before but not necessarily correct.
World’s shortest explanation of Gödel’s theorem
by Raymond Smullyan, ’5000 BC and Other Philosophical Fantasies’ via Mark Dominus (ask me for the PDF of the book)
We have some sort of machine that prints out statements in some sort of language. It needn’t be a statement-printing machine exactly; it could be some sort of technique for taking statements and deciding if they are true. But let’s think of it as a machine that prints out statements.
In particular, some of the statements that the machine might (or might not) print look like these:
P*x (which means that the machine will print x) NP*x (which means that the machine will never print x) PR*x (which means that the machine will print xx) NPR*x (which means that the machine will never print xx) For example, NPR*FOO means that the machine will never print FOOFOO. NP*FOOFOO means the same thing. So far, so good.
Now, let’s consider the statement NPR*NPR*. This statement asserts that the machine will never print NPR*NPR*.
Either the machine prints NPR*NPR*, or it never prints NPR*NPR*.
If the machine prints NPR*NPR*, it has printed a false statement. But if the machine never prints NPR*NPR*, then NPR*NPR* is a true statement that the machine never prints.
So either the machine sometimes prints false statements, or there are true statements that it never prints.
So any machine that prints only true statements must fail to print some true statements.
Or conversely, any machine that prints every possible true statement must print some false statements too.
Mark Dominus further writes,
The proof of Gödel’s theorem shows that there are statements of pure arithmetic that essentially express NPR*NPR*; the trick is to find some way to express NPR*NPR* as a statement about arithmetic, and most of the technical details (and cleverness!) of Gödel’s theorem are concerned with this trick. But once the trick is done, the argument can be applied to any machine or other method for producing statements about arithmetic.
The conclusion then translates directly: any machine or method that produces statements about arithmetic either sometimes produces false statements, or else there are true statements about arithmetic that it never produces. Because if it produces something like NPR*NPR* then it is wrong, but if it fails to produce NPR*NPR*, then that is a true statement that it has failed to produce.
So any machine or other method that produces only true statements about arithmetic must fail to produce some true statements.
The Banach-Tarski Paradox
by MarkCC
Suppose you have a sphere. You can take that sphere, and slice it into a finite number of pieces. Then you can take those pieces, and re-assemble them so that, without any gaps, you now have two spheres of the exact same size as the original.
[...]
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.
[...] math doesn’t have to follow conservation of mass [...]. A sphere doesn’t have a mass. It’s just an uncountably infinite set of points with a particular collection of topological relationship and geometric relationships.
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.
How can both of these be true? Either the transformations always preserve volume or they don’t.
Roughly speaking the problem is that mathematicians cannot come up with a meaningful definition of volume that applies to all sets of points (when I say cannot, I mean literally impossible, not just that they tried really hard then gave up). Instead, we have a definition that applies to a very large collection of sets of points, but not all of them.
Sets from that collection have a well defined volume, and any transformation which always leaves this unchanged is called volume preserving.
Sets from outside it, which the sets in the Banach Tarski paradox are, don’t have a defined volume at all, and thus can interact with volume-preserving transformations in all sorts of weird ways.
I like this explanation put together by students and faculty at the University of Copenhagen.
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:
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.
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.
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.
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 paradoxical decomposition of F2 only gives a decomposition for a dense subset of the sphere, because you have to throw away the (countably many) fixed points of all the rotations involved to make the correspondence between F2 and the orbits of various points. To go the rest of the way and you need to use something other than rotations about the origin, ie something more than just the action of F2. But it’s certainly fair to say that Banach-Tarski works because of the structure of F2.
To go the rest of the way you still only use rotations, just not the rotations in F2.
The way I always did it was to use rotations about some fixed line that doesn’t go through 0.
We seem to be talking about different things, I’m talking about doubling the surface of the sphere. You’re talking about how to get the center once you’ve doubled the surface.
Ahh yes, you’re right.
Indeed. I worked from memory, and forgot about this complication. Edited the text to cite your comment.
I seem to recall reading about a way to divide the interval [0, 1] in subsets, translating some of them, and getting [0, 2] (involving the Vitali set or something like that), but maybe my memory fails me.
Whfg pbafvqre gur onyy nf orvat znqr hc ol enqvv. Or am I missing something?
This is possible if you use infinitely many subsets. With an uncountably infinite number of pieces it is true by definition, with a countably infinite number of pieces it can be proven using the Vitali set, and with a finite number of pieces it is not true.
What Oscar_Cunningham said, but basically, no, you are not.
I was expecting something harder given that you called it “a nice exercise”, so I pretty much assumed that mine was not the right solution...
Okay. In the original formulation of the paradox, the task is to cut a ball into pieces, and assemble two balls from the pieces. If I am not mistaken, you have solved a slightly easier task: cut a ball into pieces, and covered two balls with the pieces (with overlaps). A part of the “nice exercise” is to bridge this gap.
Jurer qbrf gur prager tb?
Jvgu gur abegu cbyr (be nal bgure neovgenel qverpgvba). Vf gurer nal ceboyrz jvgu gung V pnaabg frr?
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.
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.
Depends if you only want to show that set theory is incomplete, you don’t need Gödel numbering and you can more-or-less turn Smullyan’s explanation into a complete proof in a straightforward manner.
Ok, I agree that this is an important point.
You’re right, I hadn’t thought about that.
You don’t need omega-consistency, just consistency. Gödel originally proved it for omega-consistent theories, but five years later Rosser published a rather pleasing little trick that strengthens the result to just consistent theories.
You get real understanding when you study the actual proof. For that, the best book I know is Smullyan’s Goedel’s Incompleteness Theorems. For an informal argument that can be understood by someone who doesn’t know what a formal system is, I think this one is quite good.
I haven’t really looked into Gödel’s theorem yet (got books though......in the queue) but Gödel numbering itself seems to be relatively simple. The Diagonal lemma seems to be much more difficult, or at least I am missing a lot of required background knowledge. I stopped reading the Wiki entry on it and suspended it until I am going to dive into logic and especially provability logic.
It depends on what you mean by “simple”. The Diagonal Lemma is extremely easy to state and prove (by which I mean that the proof itself has very few steps), but the proof looks like magic. That is to say, the standard proof doesn’t really reveal how the Lemma was discovered in the first place.
Gödel Numbering, on the other hand, isn’t too difficult to understand, but actually proving the Incompleteness Theorems (or whatever) usually requires pages and pages of boring, combinatorial proofs that one’s Numbering works the way one wants it to. Conceptually, however, Gödel Numbering was a massive leap forward. As I understand it, before Gödel’s paper in 1931, no one had really realized that such techniques were possible (germs of the idea go back at least to Leibniz, though), nor that one could in fact use such a technique to make metatheoretical claims about one’s object-level theory in the language of that theory itself (so that the theory could, in a sense, “prove things about itself”), nor what the implications of this would be.
Another thing to note is that Gödel’s numbering technique inspired Alan Turing’s work in 1936, and arguably was an absolutely necessary conceptual breakthrough for the invention of computers.
Oh, and I wouldn’t recommend studying provability logic until you have already mastered a sufficient amount of Mathematical Logic, by which I mean that you have gained understanding equivalent to what you would ideally gain taking an advanced undergraduate Mathematics course or Philosophy course on the subject (assuming the Philosophy course was sufficiently technical/rigorous).
I know. But I thought it would be better than nothing. Such informal explanations also help to overcome the widespread belief that you need to be a genius to approach those problems.
Fair point, but I think the aforementioned danger of misunderstanding is more harmful than learned helplessness with respect to math is. I’d rather people not know the theorem than misunderstand it and use said misunderstanding to wreak epistemic violence.
A list of habitually abused scientific concepts in popular culture?
Godel’s incompleteness theorem
Schroedinger’s cat
many worlds
anything quantum really
most things about evolution
Add your own!
Scientifically, I suggest most of psychology and psychiatry (I’m looking at you, Law & Order: SVU). In a similar vein is programming/hacking (e.g. 24, any crime drama).
In popular culture? What misunderstandings of it have you seen?
Hmm, not popular culture. Certainly arguing with people purveying nonsense as a form of the argument “you can’t be certain therefore I might be right.”
Cryptography. Like, all of it.
But they do so in the wrong way, but conveying a second misconception that these problems can be easily understood without bothering actually study much maths.
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.
I would say that the entire value and interest of the Banach Tarski paradox lies in the fact that you are restricted to seemingly volume preserving transformations, thus proving that volume cannot be meaningfully defined on all sets of points in space. This is not an obvious fact, and in fact we can come up with definitions of volume that work on very large collections of sets of points in space. Without that you just get some very basic set theory, which is a lot less interesting and surprising than Banach Tarski. I wish the author had only claimed to be explaining basic set theory, instead of explaining Banach Tarski, in which case it would have been quite a good explanation.
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.
IAWYC. I’m pretty sure there are gaps in Banach-Tarski’s division of the sphere. The sets are rotated as wholes but they don’t look closed or open.
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:
You are correct. As several commenters have already pointed out, the provided explanation of the Banach-Tarski paradox is just bad.
I really like David Morgan-Mar’s explanation of the Banach-Tarski theorem.
So do I