| |
| |
| |
Introduction · Illustration · First Pass · Second Pass · Number Crunching
The trickery lies in the words "You" and "pieces". For a start, the pieces aren't like apple wedges -- they aren't solid volumes. Instead they are like ten interlacing sea urchins, each with an infinite number of infinitely thin spines.
The other tricky word is "You". Obviously there is no Williams-Sonoma contraption expensive enough to let you prepare apples in the manner just described. In fact, the case of the actual Paradox is worse, because neither you nor any mathematician can specify the infinite sets of points you would like to separate. The best you can do is to prove that "there must exist" sets of points with the desired weird properties. [In the lingo, the proof of the Banach-Tarski paradox relies on the Axiom of Choice. Somebody has proved that if you reject the Axiom of Choice, you can't construct the Paradox.]
So, now that I've admitted up front how the Paradox isn't quite as mind-blowing as sometimes advertised, let's state it precisely -- I think you'll still find it remarkable enough to want to be convinced that it's true. Define a globe of radius r to be the set of points in three-dimensional space whose distance from the origin is greater than zero, but less than or equal to r. Thus a globe is just a ball minus its center point, which would cause us headaches if we left it in.
The Banach-Tarski Paradox. Any globe has eight pairwise-disjoint subsets ("pieces") A1, A2, A3, A4, B1, B2, B3, B4, such that the A subsets could be rotated ("moved around") and superposed to make an exact copy of the original globe, and same with the B subpieces.
| A globe is a ball with its central point removed. |
| | |
| We spatter its surface with eight colors. Each color covers an infinity of infinitely small, evenly distributed points, but our pictures must (misleadingly) show them as finite. |
| | |
| Colors on the surface sink straight down along radial lines to the (missing) center. |
| | |
| Imagine the eight differently-colored parts of the globe to have been separated. Each is like a sea urchin with infinitely many, infinitely thin spines. |
    |
    | | |
| Give each one a slight turn -- but do not bend or stretch any of them! You can now re-juxtapose just the reddish pieces to make an exact copy of the original globe. Same with the bluish pieces. The volume of the original globe has been doubled. |
 
|
So much for our rough sketch of the Paradox. Before we prove it, some preliminaries:
[glass globe]Okay, there's this hollow glass globe bolted to the floor. Etched lightly into it are poles, an equator, a prime meridian, countries, rivers -- in short, all the features of the Earth normally seen on globes. Its z-axis goes through the poles; its x-axis goes through the intersections of its equator and prime meridian, and its y-axis is the line perpendicular to the other axes.
Inside the glass globe is a very slightly smaller opaque globe. It sits there without any rod stuck through it, so it can roll on any axis. Moreover, magnets glued just under its surface let you turn it from outside the glass shell.
[concentric globes]Position the inner globe so that its poles, equator, and prime meridian line up with the outer globe's. We'll call this its "home position". Make a wax-pencil mark at London on the glass globe -- this will be right above London on the inner globe too. Now the game is to rotate the inner globe one of four ways:
(Note: I'm writing "70.5" to stand for "the angle whose cosine is exactly one-third"; this number is chosen to make the number-crunching details at the end of the proof come out right.)
You can make as many rotations as you want. After each one, make a wax-pencil mark on the glass where the inner globe's London ends up. For example, you can turn the inner globe clockwise 70.5 degrees (a C rotation) so that its London moves under the glass Toronto. Then you can turn the inner London down 70.5 degrees (a D rotation) to the glass Brasilia. So Toronto, Brasilia, and any other place you move London to via the rotations C, A, U, and D gets a wax-pencil mark.
[mark glass globe wherever inner London lands]London's country is defined as all points that could be so marked. In general, a country is a group of points on the outer globe between any two of which you can "move" using these C, A, U, and D rotations.
Furthermore, we define the journey from London to such a point as the sequence of rotations that we used to put the inner-globe-London beneath it. For example, the journey from London to Toronto was C, and we write Toronto = C(London). The journey from London to Brasilia was CD, and we write Brasilia = CD(London). [Mathematicians please note that I'm applying rotations reading left-to-right; we normally apply composed functions right-to-left.]
The only other rule about valid journeys is that they can't include pointless back-and-forth stretches, like up-down-up-down-up-down. You must cancel out all occurrences of "UD", "DU", "AC", and "CA" until there are none left. This helps ensure that differently-spelled journeys take you to different points -- "CACACA(London)" and "DUDUDUDU(London)" would be the same point as "London", so we disallow them both; similarly, we reject "DUDUUCCA(London)" in favor of "UC(London)". This is pretty crucial, so make sure you get it.
So the points comprising London's country can be named "London", "C(London)", "DDCUAAADCC(London)", etc. We will examine these assertions later, but for now please accept that:
The next step is to pick a capital, a single representative point, from each country. [In real mathematese, we pick a "representative" from each "orbit" or "equivalence class".] We'll pick London as the capital of its country, since that's where we started. But suppose that some journey (CDAUUAUUADDCC?) moves inner-globe-London, from the home position, to the point beneath outer-globe-Timbuktu. Then we could pick Timbuktu as the capital; we would just have to rename all the points in the country using journeys from Timbuktu instead of London.
It turns out, sadly, that there is no simple way to specify capitals from all the countries. My first inclination was to say "pick the point from each country that's closest to the north pole", but this only works for the country that actually contains the north pole. All the other countries have an infinity of points packed densely around the pole; whichever point you pick, there are an infinity of closer ones. (It's the same reason that trying to find "the fraction closest to zero" doesn't work.)
It's at this point that we make the leap of faith and say, okay, we can't specify capital points from each of the different countries, but there must exist a set containing exactly one point from each. [This step is known as invoking the Axiom of Choice to get a "choice set".]
Now we have divided up the globe into an infinity of different countries (sets of points that can be moved onto each other using authorized rotations), and picked a representative "capital" point from each. Now a given point P on the globe will be in the same country as one capital, which we can call X. So some journey J, perhaps AUUUCDDCCUA, moves X onto P -- in fact, only one such J does this, although we must still prove that. So P = J(X). Color P according to this rule:
Example: What color is Camden, New Jersey? Well, first we appeal to our "choice set" to provide us the capital of Camden's country. Say it turns out to be Lagos, Nigeria. Then we just have to figure out what journey takes Lagos to Camden. (There will be only one.) Suppose DDDAAADDDCDA is it. Then Camden is Aqua, because the journey from its capital ends with an anti-clockwise turn.
Every point on the globe is one of these four colors, since the journey from its capital must have one of the endings listed. Now follow a point P, of whatever color, as you rotate the inner globe 70.5 degrees clockwise from its home position. What color point is it mapped onto? Well, the new point's journey must end in a C, so it's colored crimson, right? It seems that turning any point clockwise takes us to a crimson point:
This is almost true. The only exceptions occur when the original P was aqua, i.e. the journey from its capital ended in A.
If P = DDAA(X), then an extra clockwise rotation would take it to DDAAC(X), except that the final anti-clockwise and clockwise rotations cancel each other out. The point it moves to should be rewritten DDA(X), and therefore colored aqua.
The crazy thing is that, since any non-aqua point can be moved clockwise onto a crimson point, the opposite anti-clockwise twist moves the crimson points as a whole onto all the non-aqua points. To repeat: You can take the crimson points, rotate them anti-clockwise 70.5 degrees, and cover everything on the surface except the aqua points. In the solid case, you can take the crimson sea urchin, give it a twist, and cover all the points previously covered by the crimson, ultramarine, and daffodil sea urchins. Nuts, eh?
It's pretty much the same with the daffodil points, those whose journeys end in D. What happens when you rotate them up? Well, you add a U twist, undoing the ultimate "down" twist on the journey from their capitals, leaving all points with any ending except U. (The penultimate turn of a daffodil point cannot have been U, or else it would have ended UD, up-down -- illegal.) So the daffodil points (or sea urchin) can be rotated to cover all points previously covered by the daffodil, crimson, and aqua points (sea urchins).
The crimson and daffodil regions can be rotated, each in a different direction, to cover the whole globe -- indeed they're more than sufficient, since the originally crimson and daffodil points themselves get covered twice. The same argument works for the aqua and ultramarine regions. That's the end of our first pass at the proof.
Now to address the parts of the proof that were missing or wrong. A while back I made the following claims about "countries", where a country is the set of points you can get to from one specified point using the authorized rotations C, A, U, and D.
(4) was never actually used in the proof, so I'm comfortable leaving it unargued.
(1) is obvious if you're familiar with the notion of countability: Each country's points can be enumerated X, C(X), A(X), U(X), D(X), CC(X), CA(X), and so on, and are thus at-most-countable; a countable union of at-most-countable sets is itself countable; and since the points on the globe are uncountable, there must be an uncountable infinity of countries. If that made no sense to you, I highly recommend that you find an exposition of countability and Cantor's diagonal argument. It's not hard and it's utterly fascinating.
(2) and (3) are where things get messy. (2) would follow directly from (3): If each different journey C, A, U, D, CC, CU, CD, AA, AU, AD ... took you to a different point, then there would be an infinite number of points to get to from one starting point. The problem is that (3) is false.
(3) is false because there are some points from which two distinct journeys will take you to the same place. For example, there is some point d such that A(d) = CUCD(d). And if d is a capital, we don't know how to color A(d) ... or is it CUCD(d)? It could be either aqua or daffodil. We will call A(d) an annoying point.
To see that annoying points exist, consider the north pole and south pole. From its home position, give the inner globe a C or A turn, defined as a spin around the z-axis (the "real" axis of the outer glass globe). The poles don't move at all. So C(north pole) = north pole, and the north pole is annoying, and same for the south pole.
In fact, every journey fixes two annoying points, since any journey is equivalent to a single rotation (not, in general, 70.5 degrees) around some axis (not, in general, either the z-axis of C and A or the x-axis of U and D). Think about it: You move the inner globe inside the glass shell through a journey J, which is jerky sequence of C, A, U, and D rotations. The globe ends up in some weird alignment. You could now, however, ignoring the C, A, U, D restriction, just spin it back to the home position in one smooth motion. This "smooth motion" is a rotation around some weird axis; call it W. W is a line through the center of the globes. It passes through the glass globe at two poles, which we can call w1 and w2.
When we spin the globe around W, from the home position back to the end-position of journey J, the points w1 and w2 are fixed, because they are the poles. That means journey J itself, however widely it may cause w1 and w2 to travel over its whole duration, ultimately takes them back where they began. Since J(w1) = w1 and J(w2) = w2, w1 and w2 are annoying points.
The first step in patching things up is to prove that a weaker version of (3) is true. Specifically, we prove that every distinct journey, despite leaving two annoying points fixed, corresponds to a distinct rotation. This is where our choice of 70.5 degrees and axes for C, A, D, and U come in -- we chose them so that this number-crunching subproof would work out well. It's actually not all that interesting, so I'll put it off (again). Either skip to the end and read it, or accept for the moment that it's true.
The next step is not very elegant: just color all the annoying points black. Formally, an annoying point is any point that is fixed (moved onto itself) by some non-empty journey.
There are plenty of non-black points, since the black points are countable, whereas there are uncountably many points on the globe.
No black point is in the same country as a non-black point. How do we know that? Well, if we suppose (wink wink) that B and W are black and non-black compatriots, respectively, then some journey J takes B onto W:
W = J(B).
And B, by virtue of being black, is taken onto itself by some non-empty journey K:
B = K(B).
Now let J' be the inverse journey of J, which takes W to B:
B = J'(W).
Seeing all that, consider where you get when, starting at W, you take the journeys J', K, and J. First J' takes you to B. K takes you right back to B. Then J takes you to W. In other words, the journey J'KJ takes W onto W, so W is an annoying point, contradicting our assertion that it was non-black.
If we throw out all the annoying black points, our proof works, but it's a weaker version: it duplicates a globe-minus-annoying-points, not a whole globe. [In fact, this weaker version is called the Hausdorff Paradox.] Think about this fact for a minute: Our proof failed because it did not really specify a unique color for each point, some being accessible via multiple distinct journeys from their capitals. By throwing out such annoying points, we manage to salvage the uniqueness we need. The proof works because:
Some contrivance is needed to "fill in" the black points, which we now provide.
Let annoying0 be a synonym for "annoying". Let L be some axis of the globe whose poles are not annoying0. Choose a number θ (theta) such that spinning the globe through θ degrees about L, any integral number of times, never takes an annoying0 point onto an annoying0 point. There must be such an angle, because the set of angles for which some number of L-rotations would take an annoying0 point to an annoying0 point are countable.
Define an annoying1 point to be one reached by turning an annoying0 point around L through θ degrees. No annoying1 point is annoying0, otherwise it would contradict our choices of L and θ. Annoying2 points are reached by giving the annoying0 points two spins of θ degrees around L, and similarly for annoying3, annoying4, and so on without end. Let the annoying* points be those that are annoying(n) for some number n. Again by the choice of L and θ, no point can be both annoying(m) and annoying(n) if m <> n.
The point of this contrivance is that we can take all the annoying* points we've already covered, and spin them onto the "larger" set of all annoying* points. The spin in question is negative θ degrees around L. In other words: we first do our restricted proof with the non-annoying0 points, spinning two pieces to cover all the non-annoying0 points; then we take the annoying*-but-not-annoying0 points so covered and spin them "back" one stop, so each annoying3 point is moved onto an annoying2 point, each annoying4921 point is moved onto an annoying4920 point, and -- most significantly -- each annoying1 point is moved onto an annoying0 point. In this way all the points of the globe are covered.
Formally, we amend our coloring and rotation scheme as follows.
I. Color all annoying0 points black.
II. If P is non-annoying0 (whether annoying* or not) in the country with capital X, and P = J(X), use our old coloring scheme, keeping in mind that its color may be overwritten by rule III. Note that this rule does uniquely specify a color, since it now applies only to non-annoying points:
III. Darken any non-annoying0 point that would be moved, by an undoing of the final rotation in the journey from its capital, to an annoying* point. In other words, color P:
Rule III is also well-defined.
Now we show how to rotate just the crimson, daffodil, dark crimson, and dark daffodil point-sets so that they cover the entire globe. This time, unless I am embarrassingly mistaken, the proof will actually work.
First spin the crimson and dark crimson point-sets anti-clockwise through 70.5 degrees. This covers any non-annoying0 point whose journey did not end in A; that is, any point that wasn't black, aqua, or dark aqua. Furthermore, any such point is covered with dark crimson if and only if it is annoying*.
Then spin the daffodil and dark daffodil point-sets up through 70.5 degrees. This covers any non-annoying0 point whose journey did not end in U; that is, any point that wasn't black, ultramarine, or dark ultramarine. Again, any such point is covered with dark ultramarine if and only if it is annoying*.
We've spun the crimson and daffodil points so they cover all but the annoying* points. And we've spun the dark crimson and dark daffodil points so they cover all the annoying*-but-not-annoying0 points. All that's left are annoying0 points. To cover them, spin the dark crimson and dark daffodil points again, this time through negative θ degrees around the line L. This moves each annoying(n+1) point onto the corresponding annoying(n) point, for n >= 0. Thus all the annoying* points are now covered by dark crimson or dark daffodil points. We're done. The entire surface of the globe has been covered by rotating four of the nine differently-colored point-sets, and the same can be done with the other four (non-black) point-sets.
Whereas the rest of this presentation is merely based on The Banach-Tarski Paradox by Stan Wagon, the following proof that every journey corresponds to a different rotation is more or less plagiarized from it. It's the only part of the proof that requires number-crunching. I considered rephrasing it in a way that would not require a reader to know any matrix algebra, but decided that this part of the proof would be neither interesting nor truly comprehensible to anyone who didn't already have a fairly strong math background.
In case this is not obvious, let me state that the subtle and beautiful ideas of the proof are all above; what follows is just one of many possible contrivances you could use to prove that each distinct journey corresponds to a different rotation.
First, we express the rotations C, A, U, and D as matrices (remembering that "70.5 degrees" has been short for arccos(1/3)):
| C = |
|
1/3 |
-2 2/3
|
0 |
|
A = |
|
1/3 |
22/3
|
0 |
|
|
|
22/3
|
1/3 | 0 |
-22/3
|
1/3 | 0 | |||||||
| 0 | 0 | 1 | 0 | 0 | 1 |
| U = |
|
1 | 0 | 0 |
|
D = |
|
1 | 0 | 0 |
|
|
| 0 | 1/3 |
-22/3
|
0 | 1/3 |
22/3
|
|||||||
| 0 |
22/3
|
1/3 | 0 |
-22/3
|
1/3 |
Note that A and C are mutually inverse matrices, as are U and D.
If a journey is a string of these four letters with any pairs AC, CA, UD, and UD cancelled out, we want to show that distinct journeys yield different rotation matrices when the above definitions are plugged in and multiplied out. If J and K were distinct journeys amounting to the same rotation, then JK', where K' is the inverse journey of K, would be equal to the identity matrix. So if we can show that no non-empty journey equals the identity matrix, we can show that all distinct J and K are different rotations.
We further narrow our task by noting that, if there were a non-empty journey J equal to the identity matrix, then AJC and CJA would, after expanding "J" and cancelling, also be journeys equal to the identity matrix. Moreover if J starts with C than CJA starts (after cancelling) with C, and if J starts with A, D, or U, then AJC starts (after cancelling) with A. From the existence of a non-empty journey J equal to the identity matrix, we see that there must be another such journey that starts with A or C. So if we can show that second can't exist, the first can't either.
To get a contradiction, assume J is a journey of the second sort. We show that J(1,0,0) has the
form (a,b2,c)/3^k where a,b,c and k are integers and b is not divisible by
3. This implies that w(1,0,0) <> (1,0,0), which is the required contradiction.
The claim is proved by induction on the length of J. If J has length one, then J = A or
J = C and J(1,0,0) = (1,±22,0)/3).
Suppose then that J = J'C, J'A, J'U, or J'D, where J'(1,0,0) =
(a',b'2,c')/3^k-1. Then straightforward multiplication of the appropriate
matrix times the vector gives you J(1,0,0) = (a,b2,c)/3^k, where
We need only to show now that b never becomes divisible by 3, so that the y-coordinate of J(1,0,0) is never 0, as it would have to be if J were the identity matrix.
In the case of the one-letter journeys, C(1,0,0) = (1,22,0)/3 , so b=2; and A(1,0,0) = (1,-22,0)/3 , so b=-2.
In all other cases we need to prove, J has at least two "letters"; we break up these cases as follows:
2,c'')/3^k''.
Case 1: b = b' ± 2c', where c' = 3c'' and hence is divisible by 3; so if b' is not divisible by 3, neither is b;
Case 2: b = b' ± 2a', where a' = 3a'' and hence is divisible by 3; so if b' is not divisible by 3, neither is b;
In each of the remaining cases, b = 2b' - 9b'', so if b' is not divisible by 3, neither is b:
Case 3: b = b' + 2a' = b' + 2(a'' - 4b'') = b' + 2a'' - 8b'' = 2b' - 9b'';
Case 4: b = b' - 2a' = b' - 2(a'' + 4b'') = b' - 2a'' - 8b'' = 2b' - 9b'';
Case 5: b = b' - 2c' = b' - 2(c'' + 4b'') = b' - 2c'' - 8b'' = 2b' - 9b'';
Case 6: b = b' + 2c' = b' + 2(c'' - 4b'') = b' + 2c'' - 8b'' = 2b' - 9b''
This completes all the cases, so b is never divisible by 3.