The Banach–Tarski paradox is a theorem in set-theoretic geometry that states the following: Given a solid ball in three-dimensional space, there exists a decomposition of the ball into a finite number of disjoint subsets that can be put back together in a different way to yield two identical copies of the original ball. Indeed, the reassembly process involves only moving the pieces around and rotating them, without changing their original shape. The pieces themselves are not "solids" in the traditional sense, but infinite scatterings of points. The reconstruction can work with as few as five pieces.
An alternative form of the theorem states that given any two "reasonable" solid objects (such as a small ball and a huge ball), the cut pieces of either can be reassembled into the other. This is often stated informally as "a pea can be chopped up and reassembled into the Sun" and called the "pea and the Sun paradox".
The theorem is a veridical paradox: it contradicts basic geometric intuition, but is not false or self-contradictory. "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 impossible, since all these operations ought, intuitively speaking, to preserve the volume. The intuition that such operations preserve volume is not mathematically absurd and is even included in the formal definition of volume. But this is not applicable here because in this case it is impossible to define the volumes of the considered subsets. Reassembling them produces a set whose volume is defined, but happens to be different from the volume at the start.
Unlike most theorems in geometry, the mathematical proof of this result depends on the choice of axioms for set theory in a critical way. It can be proven using the axiom of choice, which allows for the construction of non-measurable sets, i.e., collections of points that do not have a volume in the ordinary sense, and whose construction requires an uncountable number of choices.Wagon, Corollary 13.3
It was shown in 2005 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.
As proved independently by Leroy and Simpson, the Banach–Tarski paradox does not violate volumes if one works with locales rather than topological spaces. In this abstract setting, it is possible to have subspaces without points but still nonempty. The parts of the paradoxical decomposition do intersect in the sense of locales, so much that some of these intersections should be given a positive mass. Allowing for this hidden mass to be taken into account, the theory of locales permits all subsets (and even all sublocales) of the Euclidean space to be satisfactorily measured.
Banach and Tarski publication In a paper published in 1924, Stefan Banach and Alfred Tarski gave a construction of such a paradoxical decomposition, based on earlier work by Giuseppe Vitali concerning the unit interval and on the paradoxical decompositions of the sphere by Felix Hausdorff, and discussed a number of related questions about 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 and of a Euclidean space in at least three dimensions, both of which have a nonempty interior, there are partitions of and into a finite number of disjoint subsets, , (for some integer k), such that for each (integer) between and , the sets and are congruent.
Now let be the original ball and be the union of two translated copies of the original ball. Then the proposition means that the original ball can be divided into a certain number of pieces and then rotated and translated in such a way that the result is the whole set , which contains two copies of .
The strong form of the Banach–Tarski paradox 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 dimensions 1 and 2 on the one hand, and 3 and higher on the other hand, is due to the richer structure of the group of Euclidean motions in 3 dimensions. For the group is solvable, but for it contains a free group with two generators. John von Neumann studied the properties of the group of equivalences that make a paradoxical decomposition possible, and introduced the notion of amenable groups. He also found a form of the paradox in the plane that uses area-preserving affine transformations in place of the usual congruences.
Tarski proved that amenable groups are precisely those for which no paradoxical decompositions exist. Since only free subgroups are needed in the Banach–Tarski paradox, this led to the long-standing von Neumann conjecture, which was disproved in 1980.
Formal treatment The Banach–Tarski paradox states that a ball in the ordinary Euclidean space can be doubled using only the operations of partitioning into subsets, replacing a set with a congruent set, and reassembling. 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 a paradoxical set. Suppose that is a group acting on a set . In the most important special case, is an -dimensional Euclidean space (for integral n), and consists of all isometries of , i.e. the transformations of into itself that preserve the distances, usually denoted . Two geometric figures that can be transformed into each other are called congruent, and this terminology will be extended to the general -action. Two subsets and of are called -equidecomposable, or equidecomposable with respect to , if and can be partitioned into the same finite number of respectively -congruent pieces. This defines an equivalence relation among all subsets of . Formally, if there exist non-empty sets , such that
and there exist elements such that
then it can be said that and are -equidecomposable using pieces. If a set has two disjoint subsets and such that and , as well as and , are -equidecomposable, then 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, there is a sharp result in this case, due to Raphael M. Robinson: This article, based on an analysis of the Hausdorff paradox, settled a question put forth by von Neumann in 1929: 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 the Bernstein–Schroeder theorem due to Banach that implies that if is equidecomposable with a subset of and is equidecomposable with a subset of , then and are equidecomposable.
The Banach–Tarski paradox can be put in context 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 , then all sets with non-empty interior become congruent. Likewise, one ball can be made into a larger or smaller ball by stretching, or in other words, by applying similarity transformations. Hence, if the group is large enough, -equidecomposable sets may be found whose "sizes" vary. Moreover, since a countable set can be made into two copies of itself, one might expect that using countably many pieces could somehow 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 end up doubling the ball's volume. 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, nonexistence 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 divide a certain set (essentially, the surface of a unit sphere) into four parts, then rotate one of them to become itself plus two of the other parts. This follows rather easily from a -paradoxical decomposition of , the free group with two generators. Banach's and Tarski's proof relied on an analogous fact Hausdorff discovered some years earlier: the surface of a unit sphere in space is a disjoint union of three sets and a countable set such that, on the one hand, are pairwise congruent, and on the other hand, is congruent with the union of and . This is often called the Hausdorff paradox.
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 a 1923 paper by Banach as the precursors to their work. Vitali's and Hausdorff's constructions depend on Zermelo's axiom of choice ("AC"), 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:
(The role this axiom plays in our reasoning seems to us to deserve attention)
They point out that while the second result fully agrees with geometric intuition, its proof uses AC in an even more substantial way than the proof of the paradox. Thus Banach and Tarski imply that AC should not be rejected solely because it produces a paradoxical decomposition, for such an argument also undermines proofs of geometrically intuitive statements.
But in 1949, A. P. Morse showed that the statement about Euclidean polygons can be proved in ZF set theory and thus does not require the axiom of choice. In 1964, Paul Cohen proved that the axiom of choice is independent from ZF—that is, choice cannot be proved from ZF. A weaker version of an axiom of choice is the axiom of dependent choice, DC, and it has been shown that DC is sufficient for proving the Banach–Tarski paradox, that is,
The Banach–Tarski paradox is not a theorem of ZF, nor of ZF+DC, assuming their consistency.Wagon, Corollary 13.3
Much of mathematics uses AC. As Stan Wagon points out at the end of his monograph, the Banach–Tarski paradox has been more significant for its role in pure mathematics than for foundational questions: it motivated a fruitful new direction for research, the amenability of groups, which has nothing to do with the foundational questions.
In 1991, using then-recent results by Matthew Foreman and Friedrich Wehrung, Janusz Pawlikowski proved that the Banach–Tarski paradox follows from ZF plus the Hahn–Banach theorem. The Hahn–Banach theorem does not rely on the full axiom of choice but can be proved using a weaker version of AC called the ultrafilter lemma.
A sketch of the proof