Banach–Tarski paradox

The Banach–Tarski paradox is a theorem in set-theoretic geometry, which 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, which can then 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. However, 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.^[1]

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 one 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 to be impossible, since all these operations ought, intuitively speaking, to preserve the volume. The intuition that such operations preserve volumes is not mathematically absurd and it is even included in the formal definition of volumes. However, this is not applicable here because in this case it is impossible to define the volumes of the considered subsets. Reassembling them reproduces a set that has a volume, which happens to be different from the volume at the start.

Unlike most theorems in geometry, the

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.[3]

As proved independently by Leroy^[4] and Simpson,^[5] 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 point but still nonempty. The parts of the paradoxical decomposition do intersect a lot 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.

In a paper published in 1924,^[6] 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 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 nonempty interior, there are partitions of A and B into a finite number of disjoint subsets, ${\displaystyle A=A_{1}\cup \cdots \cup A_{k}}$, ${\displaystyle B=B_{1}\cup \cdots \cup B_{k}}$ (for some integer k), such that for each (integer) i between 1 and k, the sets A_i and B_i are congruent.

Now let A be the original ball and B be the union of two translated copies of the original ball. Then the proposition means that the original ball A can be divided into a certain number of pieces and then be rotated and translated in such a way that the result is the whole set B, which contains two copies of A.

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

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.

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

among all subsets of X. Formally, if there exist non-empty sets ${\displaystyle A_{1},\dots ,A_{k}}$, ${\displaystyle B_{1},\dots ,B_{k}}$ such that

${\displaystyle A=\bigcup _{i=1}^{k}A_{i},\quad B=\bigcup _{i=1}^{k}B_{i},}$

${\displaystyle \quad A_{i}\cap A_{j}=B_{i}\cap B_{j}=\emptyset \quad {\text{for all }}1\leq i<j\leq k,}$

and there exist elements ${\displaystyle g_{i}\in G}$ such that

${\displaystyle g_{i}(A_{i})=B_{i}{\text{ for all }}1\leq i\leq k,}$

then it can be said 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, there is a

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

Banach and Tarski explicitly acknowledge

The Banach–Tarski paradox is not a theorem of ZF, nor of ZF+DC, assuming their consistency.[10]

Large amounts of mathematics use 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

Here a proof is sketched which is similar but not identical to that given by Banach and Tarski. 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.

These steps are discussed in more detail below.

The free group with two generators a and b consists of all finite strings that can be formed from the four symbols a, a⁻¹, b and b⁻¹ such that no a appears directly next to an a⁻¹ and no b appears directly next to a b⁻¹. 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⁻¹a⁻¹ concatenated with abab⁻¹a yields abab⁻¹a⁻¹abab⁻¹a, which contains the substring a⁻¹a, and so gets reduced to abab⁻¹bab⁻¹a, which contains the substring b⁻¹b, which gets reduced to abaab⁻¹a. One can check that the set of those strings with this operation forms a group with identity element the empty string e. This group may be called F₂.

The group ${\displaystyle F_{2}}$ can be "paradoxically decomposed" as follows: Let S(a) be the subset of ${\displaystyle F_{2}}$ consisting of all strings that start with a, and define S(a⁻¹), S(b) and S(b⁻¹) similarly. Clearly,

${\displaystyle F_{2}=\{e\}\cup S(a)\cup S(a^{-1})\cup S(b)\cup S(b^{-1})}$

but also

${\displaystyle F_{2}=aS(a^{-1})\cup S(a),}$

and

${\displaystyle F_{2}=bS(b^{-1})\cup S(b),}$

where the notation aS(a⁻¹) means take all the strings in S(a⁻¹) and

This is at the core of the proof. For example, there may be a string ${\displaystyle aa^{-1}b}$ in the set ${\displaystyle aS(a^{-1})}$ which, because of the rule that ${\displaystyle a}$ must not appear next to ${\displaystyle a^{-1}}$, reduces to the string ${\displaystyle b}$. Similarly, ${\displaystyle aS(a^{-1})}$ contains all the strings that start with ${\displaystyle a^{-1}}$ (for example, the string ${\displaystyle aa^{-1}a^{-1}}$ which reduces to ${\displaystyle a^{-1}}$). In this way, ${\displaystyle aS(a^{-1})}$ contains all the strings that start with ${\displaystyle b}$, ${\displaystyle b^{-1}}$ and ${\displaystyle a^{-1}}$, as well as the empty string ${\displaystyle e}$.

Group F₂ has been cut into four pieces (plus the singleton {e}), then two of them "shifted" by multiplying with a or b, then "reassembled" as two pieces to make one copy of ${\displaystyle F_{2}}$ and the other two to make another copy of ${\displaystyle F_{2}}$. That is exactly what is intended to do to the ball.

In order to find a free group of rotations of 3D space, i.e. that behaves just like (or "is isomorphic to") the free group F₂, two orthogonal axes are taken (e.g. the x and z axes). Then, A is taken to be a rotation of ${\textstyle \theta =\arccos \left({\frac {1}{3}}\right)}$ about the x axis, and B to be a rotation of ${\displaystyle \theta }$ about the z axis (there are many other suitable pairs of irrational multiples of π that could be used here as well).^[13]

The group of rotations generated by A and B will be called H. Let ${\displaystyle \omega }$ be an element of H that starts with a positive rotation about the z axis, that is, an element of the form ${\displaystyle \omega =\ldots b^{k_{3}}a^{k_{2}}b^{k_{1}}}$ with ${\displaystyle k_{1}>0,\ k_{2},k_{3},\ldots ,k_{n}\neq 0,\ n\geq 1}$. It can be shown by induction that ${\displaystyle \omega }$ maps the point ${\displaystyle (1,0,0)}$ to ${\textstyle \left({\frac {k}{3^{N}}},{\frac {l{\sqrt {2}}}{3^{N}}},{\frac {m}{3^{N}}}\right)}$, for some ${\displaystyle k,l,m\in \mathbb {Z} ,N\in \mathbb {N} }$. Analyzing ${\displaystyle k,l}$ and ${\displaystyle m}$ modulo 3, one can show that ${\displaystyle l\neq 0}$. The same argument repeated (by symmetry of the problem) is valid when ${\displaystyle \omega }$ starts with a negative rotation about the z axis, or a rotation about the x axis. This shows that if ${\displaystyle \omega }$ is given by a non-trivial word in A and B, then ${\displaystyle \omega \neq e}$. Therefore, the group H is a free group, isomorphic to F₂.

The two rotations behave just like the elements a and b in the group F₂: there is now a paradoxical decomposition of H.

This step cannot be performed in two dimensions since it involves rotations in three dimensions. If two nontrivial rotations are taken about the same axis, the resulting group is either ${\displaystyle \mathbb {Z} }$ (if the ratio between the two angles is rational) or the free abelian group over two elements; either way, it does not have the property required in step 1.

An alternative arithmetic proof of the existence of free groups in some special orthogonal groups using integral quaternions leads to paradoxical decompositions of the

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(nα)P is also in D, where r(nα) is a rotation about λ of nα. Then J is countable. So there exists an angle θ not in J. Let ρ be the rotation about λ by θ. Then ρ acts on S² with no fixed points in D, 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 circle within the ball, containing the point at the center of the ball. Using an argument like that used to prove the Claim, one can see that the full circle is equidecomposable with the circle minus the point at the ball's center. (Basically, a countable set of points on the circle can be rotated to give itself plus one more point.) 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

Use is made of the fact that if A ~ B and B ~ C, then A ~ C. The decomposition of A into C can be done using number of pieces equal to the product of the numbers needed for taking A into B and for taking B into C.

The proof sketched above requires 2 × 4 × 2 + 8 = 24 pieces - a factor of 2 to remove fixed points, a factor 4 from step 1, a factor 2 to recreate fixed points, and 8 for the center point of the second ball. But in step 1 when moving {e} and all strings of the form aⁿ into S(a⁻¹), do this to all orbits except one. Move {e} of this last orbit to the center point of the second ball. This brings the total down to 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.

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 n ≥ 3 and k ≥ 1, 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

, one can further prove that the sphere Sⁿ⁻¹ can be partitioned into as many pieces as there are real numbers (that is, ${\displaystyle 2^{\aleph _{0}}}$ pieces), so that each piece is equidecomposable with two pieces to Sⁿ⁻¹ using rotations. These results then extend to the unit ball deprived of the origin. A 2010 article by Valeriy Churkin gives a new proof of the continuous version of the Banach–Tarski paradox.

In the

As von Neumann notes:[16]

"Infolgedessen gibt es bereits in der Ebene kein nichtnegatives additives Maß (wo das Einheitsquadrat das Maß 1 hat), das gegenüber allen Abbildungen von A₂ invariant wäre."

"In accordance with this, already in the plane there is no non-negative additive measure (for which the unit square has a measure of 1), which is invariant with respect to all transformations belonging to A₂ [the group of area-preserving affine transformations]."

To explain further, the question of whether a finitely additive measure (that is preserved under certain transformations) exists or not depends on what transformations are allowed. The Banach measure of sets in the plane, which is preserved by translations and rotations, is not preserved by non-isometric transformations even when they do preserve the area of polygons. The points of the plane (other than the origin) can be divided into two dense sets which may be called A and B. If the A points of a given polygon are transformed by a certain area-preserving transformation and the B points by another, both sets can become subsets of the A points in two new polygons. The new polygons have the same area as the old polygon, but the two transformed sets cannot have the same measure as before (since they contain only part of the A points), and therefore there is no measure that "works".

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.

• 2000: 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.^[17] 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 neighborhood 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.
• 2003: It had been known for a long time that the full plane was paradoxical with respect to SA₂, and that the minimal number of pieces would equal four provided that there exists a locally commutative free subgroup of SA₂. In 2003 Kenzi Satô constructed such a subgroup, confirming that four pieces suffice.^[18]
• 2011: Laczkovich's paper^[19] left open the possibility that there exists a free group F of piecewise linear transformations acting on the punctured disk D \ {(0,0)} without fixed points. Grzegorz Tomkowicz constructed such a group,^[20] showing that the system of congruences A ≈ B ≈ C ≈ B U C can be realized by means of F and D \ {(0,0)}.
• 2017: It has been known for a long time that there exists in the hyperbolic plane H² a set E that is a third, a fourth and ... and a ${\displaystyle 2^{\aleph _{0}}}$-th part of H². The requirement was satisfied by orientation-preserving isometries of H². Analogous results were obtained by
  John Frank Adams^[21] and Jan Mycielski^[22]
  who showed that the unit sphere S² contains a set E that is a half, a third, a fourth and ... and a ${\displaystyle 2^{\aleph _{0}}}$-th part of S². Grzegorz Tomkowicz[23] showed that Adams and Mycielski construction can be generalized to obtain a set E of H² with the same properties as in S².
• 2017: Von Neumann's paradox concerns the Euclidean plane, but there are also other classical spaces where the paradoxes are possible. For example, one can ask if there is a Banach–Tarski paradox in the hyperbolic plane H². This was shown by Jan Mycielski and Grzegorz Tomkowicz.^[24][25] Tomkowicz^[26] proved also that most of the classical paradoxes are an easy consequence of a graph theoretical result and the fact that the groups in question are rich enough.
• 2018: In 1984, Jan Mycielski and Stan Wagon
  properly discontinuous subgroup of the group of isometries of H². A similar paradox was obtained in 2018 by Grzegorz Tomkowicz,^[28]
  who constructed a free properly discontinuous subgroup G of the affine group SA(3,Z). The existence of such a group implies the existence of a subset E of Z³ such that for any finite F of Z³ there exists an element g of G such that ${\displaystyle g(E)=E\triangle F}$, where ${\displaystyle E\,\triangle \,F}$ denotes the symmetric difference of E and F.
• 2019: Banach–Tarski paradox uses finitely many pieces in the duplication. In the case of countably many pieces, any two sets with non-empty interiors are equidecomposable using translations. But allowing only Lebesgue measurable pieces one obtains: If A and B are subsets of Rⁿ with non-empty interiors, then they have equal Lebesgue measures if and only if they are countably equidecomposable using Lebesgue measurable pieces. Jan Mycielski and Grzegorz Tomkowicz [29] extended this result to finite dimensional Lie groups and second countable locally compact topological groups that are totally disconnected or have countably many connected components.
• 2024: Robert Samuel Simon and Grzegorz Tomkowicz ^[30] introduced a colouring rule of points in a Cantor space that links paradoxical decompositions with optimisation. This allows one to find an application of paradoxical decompositions in economics.
• 2024: Grzegorz Tomkowicz ^[31] proved that in the case of non-supramenable connected Lie groups G acting continuously and transitively on a metric space, bounded G paradoxical sets are generic.

• Hausdorff paradox – Paradox in mathematics
• Nikodym set
• Paradoxes of set theory
• Tarski's circle-squaring problem – Problem of cutting and reassembling a disk into a square
• Von Neumann paradox – Geometric theorem