The Banach–Tarski paradox is a theorem in set theoretic geometry which states that a solid ball in 3-dimensional space can be split into several non-overlapping pieces, which can then be put back together in a different way to yield two identical copies of the original ball. The pieces are infinite scatterings of points which require an uncountably infinite number of arbitrary choices to define explicitly, but the reassembly process involves only moving them around and rotating them, without changing the shape.

In a paper published in 1924, Stefan Banach and Alfred Tarski gave a construction of such a "paradoxical decomposition", based on earlier paradoxical decompositions of a unit interval and of a sphere due to Giuseppe Vitali and Felix Hausdorff, and discussed a number of related questions concerning decompositions of subsets of Euclidean spaces in various dimensions. They proved the following more general statement, the strong form of the Banach–Tarski paradox:

Given any two bounded subsets A and B of a Euclidean space in at least three dimensions, both of which have a non-empty interior, there are partitions of A and B into a finite number of disjoint subsets, A = A₁ ∪ ... ∪ A_k, B = B₁ ∪ ... ∪ B_k, such that for each i between 1 and k, the sets A_i and B_i are congruent.

This is false in dimensions one and two, but Banach and Tarski showed that an analogous statement remains true if countably many subsets are allowed. The difference between the dimensions 1 and 2 on the one hand, and three and higher, on the other hand, is due to the richer structure of the group Gn of the Euclidean motions in the higher dimensions, which is solvable for n =1, 2 and contains a free group with two generators for n ≥ 3. John von Neumann studied the properties of the group of equivalences that make a paradoxical decomposition possible, identifying the class of amenable groups, for which no paradoxical decompositions exist. He also found a form of the paradox in the plane which uses area-preserving affine transformations in place of the usual congruences.

The reason the Banach–Tarski theorem is called a paradox is because it contradicts basic geometric intuition. "Doubling the ball" by dividing it into parts and moving them around by rotations and translations, without any stretching, bending, or adding new points, seems to be impossible, since all these operations preserve the volume, but the volume is doubled in the end. According to the strong version of the theorem, the points inside a pea can be sorted into pieces, the pieces can be rotated and reassembled to cover all the points in the Sun.

What makes the paradox possible in set theory is the axiom of choice, which allows the construction of non measurable sets, collections of points that do not have a volume in the ordinary sense. Robert Solovay showed that the axiom of choice, or a weaker variant of it, is necessary for the construction of nonmeasurable sets by constructing a model of ZF set theory (without choice) in which every geometric subset has a well-defined Lebesgue measure.

The existence of nonmeasurable sets, such as those in the Banach–Tarski paradox, has been used as an argument against the axiom of choice, although most mathematicians accept that nonmeasurable sets exist.

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

Formal treatment

The Banach–Tarski paradox states that a ball in the ordinary Euclidean space can be doubled using only the operations of partioning into subsets, replacing a set with a congruent set, and reassembly. Its mathematical structure is greatly elucidated by emphasizing the role played by the group of Euclidean motions and introducing the notions of equidecomposable sets and paradoxical set. Suppose that G is a group acting on a set X. In the most important special case, X is an n-dimensional Euclidean space, and G consists of all isometries of X, i.e. the transformations of X into itself that preserve the distances. Two geometric figures that can be transformed into each other are called congruent, and this terminology will be extended to the general G-action. Two subsets A and B of X are called G-equidecomposable, or equidecomposable with respect to G, if A and B can be partitioned into the same finite number of respectively G-congruent pieces. It is easy to see that this defines an equivalence relation among all subsets of X. Formally, if

and there are elements g₁,...,g_k of G such that for each i between 1 and k, g_i (A_i ) = Bi , then we will say that A and B are G-equidecomposable using k pieces. If a set E has two disjoint subsets A and B such that A and E, as well as B and E, are G-equidecomposable then E is called paradoxical.

Using this terminology, the Banach–Tarski paradox can be reformulated as follows:

A three-dimensional Euclidean ball is equidecomposable with two copies of itself.

In fact, a sharp result (due to Raphael M. Robinson) is known in this case: doubling the ball can be accomplished with five pieces; and fewer than five pieces will not suffice.

The strong version of the paradox claims:

Any two bounded subsets of 3-dimensional Euclidean space with non-empty interiors are equidecomposable.

While apparently more general, this statement is derived in a simple way from the doubling of a ball by using a generalization of Bernstein–Schroeder theorem due to Banach that implies that if A is equidecomposable with a subset of B and B is equidecomposable with a subset of A, then A and B are equidecomposable.

The Banach–Tarski paradox is made somewhat less bizarre by pointing out that for two sets in the strong form of the paradox, there is always a bijective function that can map the points in one shape into the other in a one-to-one fashion. In the language of Georg Cantor's set theory, these two sets have equal cardinality. Thus, if one enlarges the group to allow arbitrary bijections of X then all sets with non-empty interior become congruent. Likewise, we can make one ball into a larger or smaller ball by stretching, in other words, by applying similarity transformations. Hence if the group G is large enough, we may find G-equidecomposable sets whose "size" varies. Moreover, since a countable set can be made into two copies of itself, one might expect that somehow, using countably many pieces could do the trick. On the other hand, in the Banach–Tarski paradox the number of pieces is finite and the allowed equivalences are Euclidean congruences, which preserve the volumes. Yet, somehow, they end up doubling the volume of the ball! While this is certainly surprising, some of the pieces used in the paradoxical decomposition are non-measurable sets, so the notion of volume (more precisely, Lebesgue measure) is not defined for them, and the partitioning cannot be accomplished in a practical way. In fact, the Banach–Tarski paradox demonstrates that it is impossible to find a finitely-additive measure (or a Banach measure) defined on all subsets of a Euclidean space of three (and greater) dimensions that is invariant with respect to Euclidean motions and takes the value one on a unit cube. In his later work, Tarski showed that, conversely, non-existence of paradoxical decompositions of this type implies the existence of a finitely-additive invariant measure.

The heart of the proof of the "doubling the ball" form of the paradox presented below is the remarkable fact that by a Euclidean isometry (and renaming of elements), one can transform one quarter of a certain set (essentially, the surface of a unit sphere) into three quarters of this set plus one point. This follows rather easily from a F₂-paradoxical decomposition of F₂, the free group with two generators. Banach and Tarski's proof relied on an analogous fact discovered by Hausdorff some years earlier: the surface of a unit sphere in space is a disjoint union of three sets B, C, D and a countable set E such that, on the one hand, B, C, D are pairwise congruent, and, on the other hand, B is congruent with the union of C and D. This is often called the Hausdorff paradox. By carefully analyzing the structure of this argument, Raphael M. Robinson proved in 1947 that the minimal number of pieces in a paradoxical decomposition of the ball is five, completely answering a question put forth by von Neumann in 1929.

Connection with earlier work and the role of the axiom of choice

Banach and Tarski explicitly acknowledge Giuseppe Vitali's 1905 construction of the set bearing his name, Hausdorff's paradox (1914), and an earlier (1923) paper of Banach as the precursors to their work. Vitali's and Hausdorff's constructions depend on Zermelo's axiom of choice, which is also crucial to the Banach–Tarski paper, both for proving their paradox and for the proof of another result:

Two Euclidean polygons, one of which strictly contains the other, are not equidecomposable.

They remark:

Le rôle que joue cet axiome dans nos raisonnements nous semble mériter l'attention

(The role this axiom plays in our reasoning seems, to us, to deserve attention)

and point out that while the second result fully agrees with our geometric intuition, its proof uses AC in even more substantial way than the proof of the paradox. Thus Banach and Tarski imply that AC should not be rejected simply because it produces a paradoxical decomposition. Indeed, such an argument would also reject some geometrically intuitive statements!

Ironically, in 1949 A.P.Morse showed that the statement about Euclidean polygons can be proved in ZF and thus does not require the axiom of choice. In 1964, Paul Cohen proved the equiconsistency of the axiom of choice with the rest of set theory, which implies that ZFC (ZF set theory with the axiom of choice) is consistent if and only if ZF set theory without choice is consistent. Later, Robert M. Solovay, using Cohen's technique of forcing, established that in the absence of choice, it is consistent to assign a Lebesgue measure to any subset in Rn, contradicting BT. Solovay's results extend to ZF supplemented by a weak form of AC called the axiom of dependent choice, DC. It follows that

Banach–Tarski paradox is not a theorem of ZF, nor of ZF+DC (Wagon, Corollary 13.3).

A majority of mathematicians presently accepts AC for pragmatic reasons. As Stan Wagon points out at the end of his monograph, the Banach–Tarski paradox is more significant for its role in pure mathematics than it is to foundational questions. As far the axiom of choice is concerned, BT plays the same role as the existence of non-measurable sets. But the Banach–Tarski paradox is more significant for the rest of mathematics because it motivated a fruitful new direction for research, amenability of groups, which has nothing to do with the foundational questions.

In 1991, using then-recent results by Matthew Foreman and Friedrich Wehrung,[2] Janusz Pawlikowski proved that the Banach-Tarski paradox follows from ZF plus the Hahn-Banach theorem.[3] The Hahn-Banach theorem doesn't rely on the full axiom of choice but can be proven using a weaker version of AC called the ultrafilter lemma. So Pawlikowski proved that the set theory needed to prove the Banach-Tarski paradox, while stronger than ZF, is weaker than full ZFC.

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 F2.

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.

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

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 F2 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, z axis. (This step cannot be performed in two dimensions since it involves rotations in three dimensions. If we take two rotations about same axis, the resulting group is commutative and doesn't have the property required in step 1.) 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²2 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 S² with no fixed points in D, i.e. ρn(D) is disjoint from D, and for natural m<n, ρn(D) is disjoint from ρm(D). Let E be the disjoint union of ρn(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 S17. Then S17 minus a point is equidecomposable with S17, by the Claim, since a one point set is 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).

Proof sketched above requires 2*4*2+8 = 24 pieces, 2 to remove fixed points, 4 from step 1, 2 to recreate fixed points and 8 for the center point of the second ball. In step 1 move {e} and all strings of symbol a only into S(a-1), do this to all orbits except one. Move {e} of the last orbit to the center of the second ball. This gives 16+1 pieces. With more algebra one can also decompose fixed orbits into 4 sets as in step 1. This gives 5 pieces and is the best possible.

Obtaining infinitely many balls from one

Using the Banach–Tarski paradox, it is possible to obtain k copies of a ball in the Euclidean n-space from one, for any integers and , i.e. a ball can be cut into k pieces so that each of them is equidecomposable to a ball of the same size as the original. Using the fact that the free group F₂ of rank 2 admits a free subgroup of countably infinite rank, a similar proof yields that the unit sphere S^{n − 1}1 can be partitioned into countably infinitely many pieces, each of which is equidecomposable (with two pieces) to the S^{n − 1}1 using rotations. By using analytic properties of the rotation group SO(n), which is a connected analytic Lie group, one can further prove that the sphere S^{n − 1} can be partitioned into as many pieces as there are real numbers (that is, pieces), so that each piece is equidecomposable with two pieces to S^{n − 1} using rotations. These results then extend to the unit ball deprived from the origin.

The von Neumann paradox in the Euclidean plane

In the Euclidean plane, two figures that are equidecomposable with respect to the group of Euclidean motions are necessarily of the same area, therefore, a paradoxical decomposition of a square or disk of Banach–Tarski type that uses only Euclidean congruences is impossible. A conceptual explanation of the distinction between the planar and higher-dimensional cases was given by John von Neumann: unlike the group SO(3) of rotations in three dimensions, the group G₂ of Euclidean motions of the plane is solvable, which implies the existence of an invariant finitely-additive measure on G₂ and R2 and rules out paradoxical decompositions of non-negligible sets. Von Neumann then posed the following question: can such a paradoxical decomposition be constructed if one allowed a larger group of equivalences?

It is clear that if one permits similarities, any two squares in the plane become equivalent even without further subdivision. This motivates restricting one's attention to the group SA₂ of area-preserving affine transformations. Since the area is preserved, any paradoxical decomposition of a square with respect to this group would be counterintuitive for the same reasons as the Banach–Tarski decomposition of a ball. In fact, the group SA₂ contains as a subgroup the special linear group SL(2,R), which in its turn contains the free group F₂ with two generators as a subgroup. This makes it plausible that the proof of Banach–Tarski paradox can be imitated in the plane. The main difficulty here lies in the fact that the unit square is not invariant under the action of the linear group SL(2,R), hence one cannot simply transfer a paradoxical decomposition from the group to the square, as in the third step of the above proof of the Banach–Tarski paradox. Moreover, the fixed points of the group present a lot of difficulties (for example, the origin is fixed under all linear transformations). Von Neumann's solution was to enlarge the group to SA₂ by including the translations, and he constructed a paradoxical decomposition of the unit square with respect to the enlarged group. Applying the Banach–Tarski method, the paradox for the square can be strengthened as follows:

Any two bounded subsets of the Euclidean plane with non-empty interiors are equidecomposable with respect to the area-preserving affine maps.

The class of groups isolated by von Neumann in the course of study of Banach–Tarski phenomenon turned out to be very important for many areas of mathematics: these are amenable groups, or groups with an invariant mean, and include all finite and all solvable groups. Generally speaking, paradoxical decompositions arise when the group used for equivalences in the definition of equidecomposability is not amenable.

Recent progress

* Von Neumann's paper left open the possibility of a paradoxical decomposition of the interior of the unit square with respect to the linear group SL(2,R) (Wagon, Question 7.4). In 2000, Miklós Laczkovich proved that such a decomposition exists.[4] More precisely, let A be the family of all bounded subsets of the plane with non-empty interior and at a positive distance from the origin, and B the family of all planar sets with the property that a union of finitely many translates under some elements of SL(2,R) contains a punctured neighbourhood of the origin. Then all sets in the family A are SL(2,R)-equidecomposable, and likewise for the sets in B. It follows that both families consist of paradoxical sets.

* It had been known for a long time that the full plane was paradoxical with respect to SA2, and that the minimal number of pieces would equal four provided that there exists a locally commutative free subgroup of SA2. In 2003 Kenzi Satô constructed such a subgroup, confirming that four pieces suffice.[5]

See also

* Tarski's circle-squaring problem

Notes

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

2. ^ M. Foreman and F. Wehrung, The Hahn-Banach theorem implies the existence of a non-Lebesgue measurable set, "Fundamenta Mathematicae" 138 (1991), p. 13-19.

3. ^ Pawlikowski, Janusz: The Hahn-Banach theorem implies the Banach-Tarski paradox. "Fundamenta Mathematicae" 138 (1991), s. 21-22.

4. ^ Paradoxical sets under SL2(R), Ann. Univ. Sci. Budapest. Eötvös Sect. Math. 42 (1999), 141–145.

5. ^ A locally commutative free group acting on the plane, Fundamenta Mathematica, 180 (2003), no. 1, 25–34.

References

* Stefan Banach and Alfred Tarski, Sur la décomposition des ensembles de points en parties respectivement congruentes, Fundamenta Mathematicae, 6, (1924), 244–277. Review at JFM

* Layman's Guide to the Banach–Tarski Paradox (from Kuro5hin)

* Karl Stromberg, The Banach-Tarski paradox, Amer. Math. Monthly 86 (1979), no. 3, 151–161.

* Francis E. Su, "The Banach–Tarski Paradox"

* John von Neumann, Zur allgemeinen Theorie des Masses, Fundamenta Mathematicae, 13 (1929), 73–116.

* S. Wagon, The Banach–Tarski Paradox, Cambridge University Press, 1986.

* L. Wapner, The Pea and the Sun: A Mathematical Paradox, A.K. Peters, 2005