Banach–Tarski paradox

From Wikipedia, the free encyclopedia

The Banach–Tarski "paradox": A ball can be decomposed and reassembled into two balls the same size as the original.

First stated by Stefan Banach and Alfred Tarski in 1924, the Banach-Tarski paradox or Hausdorff-Banach-Tarski paradox is the famous "doubling the ball" paradox, which states that by using the axiom of choice it is possible to take a solid ball in 3-dimensional space, cut it up into finitely many (non-measurable) pieces and, moving them using only rotations and translations, reassemble the pieces into two balls of the same radius as the original. Banach and Tarski intended this proof to be evidence in favor of rejecting the axiom of choice, but the nature of the proof is such that most mathematicians take it to mean that the axiom of choice merely results in bizarre and unintuitive consequences. Actually, as explained below, the fact that an isometry (and renaming of elements) can transform one quarter of a set into three quarters of this set plus one point is the heart of the counterintuitive aspect of the theorem.

[edit] Formal treatment

Let A and B be two subsets of Euclidean space. We call them equi-decomposable if they can be represented as finite unions of disjoint subsets and such that, for any i, the subset A_i is congruent to B_i. Then, the paradox can be reformulated as follows:

The ball is equi-decomposable with two copies of itself.

For the ball, five pieces are sufficient to do this; it cannot be done with fewer than five. There is an even stronger version of the paradox:

Any two bounded subsets of 3-dimensional Euclidean space with non-empty interior are equi-decomposable.

In other words, a marble could be cut up into finitely many pieces and reassembled into a planet, or a telephone could be transformed into a water lily. These transformations are not possible with real objects made of a finite number of atoms and bounded volumes, but it is possible with their geometric shapes. The Banach–Tarski paradox is made somewhat less bizarre by pointing out that there is always a function that can map one-to-one the points in one shape to another. For example, two balls can be transformed bijectively to a similarly infinite subset of itself (such as one ball). Likewise, we can make one ball into a larger or smaller ball by simply multiplying the radius of each point in the ball, using spherical coordinates, by a constant. However, such transformations in general are non-isometric or involve an uncountably infinite number of pieces. The surprising consequence of the Banach-Tarski paradox is that it can be done with only rotation and translation (isometric mapping) of a finite number of pieces.

What makes the paradox possible is that the pieces are infinitely convoluted. Technically, they are not measurable, and so they do not have "reasonable" boundaries or a "volume" in the ordinary sense. It is impossible to carry out such a disassembly physically because disassembly "with a knife" can create only measurable sets. This pure existence statement in mathematics points out that there are many more sets than just the measurable sets familiar to most people.

The paradox also holds in all dimensions higher than three. It does not hold for subsets of the Euclidean plane. (The statement above does not apply to a two-dimensional subset of three-dimensional space, since such a subset would have empty interior.) Still, there are some paradoxical decompositions in the plane: a disc can be cut into finitely many pieces and reassembled to form a solid square of equal area; see Tarski's circle-squaring problem.

The paradox shows that it is impossible to define "volume" on all bounded subsets of Euclidean space such that equi-decomposable sets will have equal volume.

The proof is based on the earlier work of Felix Hausdorff, who found a closely related paradox 10 years earlier; in fact, the Banach–Tarski paradox is a simple corollary of the technique developed by Hausdorff.

It has recently been shown that the pieces can be chosen in such a way that they can be moved continuously into place without running into one another.^[1]

[edit] A sketch of the proof

Essentially, the paradoxical decomposition of the ball is achieved in four steps:

1. Find a paradoxical decomposition of the free group in two generators.
2. Find a group of rotations in 3-d space isomorphic to the free group in two generators.
3. Use the paradoxical decomposition of that group and the axiom of choice to produce a paradoxical decomposition of the hollow unit sphere.
4. Extend this decomposition of the sphere to a decomposition of the solid unit ball.

We now discuss each of these steps in more detail.

Step 1. The free group with two generators a and b consists of all finite strings that can be formed from the four symbols a, a^-1, b and b^-1 such that no a appears directly next to an a^-1 and no b appears directly next to a b^-1. Two such strings can be concatenated and converted into a string of this type by repeatedly replacing the "forbidden" substrings with the empty string. For instance: abab^-1a^-1 concatenated with abab^-1a yields abab^-1a^-1abab^-1a, which gets reduced to abaab^-1a. One can check that the set of those strings with this operation forms a group with neutral element the empty string e. We will call this group F₂.

The sets S(a^-1) and aS(a^-1) in the Cayley graph of F₂

The group F₂ can be "paradoxically decomposed" as follows: let S(a) be the set of all strings that start with a and define S(a^-1), S(b) and S(b^-1) similarly. Clearly,

but also

, and

.

The notation aS(a^-1) means take all the strings in S(a^-1) and concatenate them on the left with a.

Make sure that you understand this last line, because it is at the core of the proof. Now look at this: we cut our group F₂ into four pieces (Forget about e for now, it doesn't pose a problem), then "shift" some of them by multiplying with a or b, then "reassemble" two of them to make F₂ and reassemble the other two to make another copy of F₂. That's exactly what we want to do to the ball.

Step 2. In order to find a group of rotations of 3D space that behaves just like (or "isomorphic to") the group F₂, we take two orthogonal axes, e.g. the x and z axes, and let A be a rotation of some irrational multiple of π, take arccos(1/3), about the first, x axis, and B be a rotation of some irrational multiple of π, take arccos(1/3), about the second, y axis. (This step cannot be performed in two dimensions since it involves rotations in three dimensions.) It is somewhat messy but not too difficult to show that these two rotations behave just like the elements a and b in our group F₂. We'll skip it, leaving the exercise to the reader. The new group of rotations generated by A and B will be called H. Of course, we now also have a paradoxical decomposition of H.

Step 3. The unit sphere S² is partitioned into orbits by the action of our group H: two points belong to the same orbit if and only if there's a rotation in H which moves the first point into the second. We can use the axiom of choice to pick exactly one point from every orbit; collect these points into a set M. Now (almost) every point in S² can be reached in exactly one way by applying the proper rotation from H to the proper element from M, and because of this, the paradoxical decomposition of H then yields a paradoxical decomposition of S².

Step 4. Finally, connect every point on S² with a ray to the origin; the paradoxical decomposition of S² then yields a paradoxical decomposition of the solid unit ball minus the center. (The center of the ball needs a bit more care, but we omit this part in the sketch.)

NB. This sketch glosses over some details. One has to be careful about the set of points on the sphere which happen to lie on the axis of some rotation in H. However, there are only countably many such points, and it is possible to patch them up (see below). The same applies to the center of the ball.

Some details, fleshed out. In Step 3, we partitioned the sphere into orbits of our group H. To streamline the proof, we omitted the discussion of points that are fixed by some rotation; since the paradoxical decomposition of F₂ relies on shifting certain subsets, the fact that some points are fixed might cause some trouble. Since any rotation excluding the identity of S² has two fixed points, and since H, which is isomorphic to F₂, is countable, there are countably many points of S² that are fixed by some rotation in H, denote this set of fixed points D. Step 3 proves that S²-D admits a paradoxical decomposition. What remains to be shown is the

Claim. S²-D is equidecomposable with S². Proof. Let λ be some line through the origin that does not intersect any point in D--this is possible since D is countable. Let J be the set of angles, α, such that for some natural number n, and some P in D, r(α)P is also in D, where r is a rotation about λ of nα. Then J is countable so there exists angle θ not in J. Let ρ be the rotation about λ by θ, then ρ acts on D with no fixed points, i.e. ρⁿ(D) is disjoint from D, and for natural m<n, ρⁿ(D) is disjoint from ρ^m(D). Let E be the disjoint union of ρⁿ(D) over n=0,1,2,... Then S² = E ∪ (S² - E) ~ ρ(E) ∪ (S² - E) = (E - D) ∪ (S² - E) = S² - D, where ~ denotes 'is equidecomposable to'.

For step 4, it has already been shown that the ball minus a point admits a paradoxical decomposition; it remains to be shown that the ball minus a point is equidecomposable with the ball. Consider a sphere within the ball, of radius r = half the radius of the ball, whose center is r from the center of the ball, denote this sphere S₁₇. Then S₁₇ minus a point is equidecomposable with S₁₇, by the Claim, since one point is most definitely countable. Note that this involves the rotation about a point other than the origin, so the Banach-Tarski paradox involves isometries of Euclidean 3-space rather than just SO(3).

[edit] Further reading

• "Sur la décomposition des ensembles de points en parties respectivement congruentes", Fundamenta Mathematicae, 6, (1924), 244-277, Banach and Tarski's original paper (in French).
• Layman's Guide to the Banach–Tarski Paradox (from Kuro5hin)
• Francis E. Su, "The Banach–Tarski Paradox"
• S. Wagon, The Banach–Tarski Paradox, Cambridge University Press, 1986.
• L. Wapner, The Pea and the Sun: A Mathematical Paradox, A.K. Peters, 2005

[edit] References

1. ^ Wilson, Trevor M. (Sept. 2005). "A continuous movement version of the Banach–Tarski paradox: A solution to De Groot's problem". Journal of Symbolic Logic 70: 946–952.