Banach–Tarski paradox

Cayley graph of F₂, showing decomposition into the sets S(a) and aS(a⁻¹). Traversing a horizontal edge of the graph in the rightward direction represents left multiplication of an element of F₂ by a; traversing a vertical edge of the graph in the upward direction represents left multiplication of an element of F₂ by b. Elements of the set S(a) are green dots; elements of the set aS(a⁻¹) are blue dots or red dots with blue border. Red dots with blue border are elements of S(a⁻¹), which is a subset of aS(a⁻¹).

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 set of all non-forbidden 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 concatenate them on the left with a.

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).[11]

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 rotations are taken about the same axis, the resulting group is the abelian circle group and does not have the property required in step 1.

An alternate arithmetic proof of the existence of free groups in some special orthogonal groups using integral quaternions leads to paradoxical decompositions of the rotation group.[12]

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 is a rotation in H which moves the first point into the second. (Note that the orbit of a point is a dense set in S².) The axiom of choice can be used to pick exactly one point from every orbit; collect these points into a set M. The action of H on a given orbit is free and transitive and so each orbit can be identified with H. In other words, every point in S² can be reached in exactly one way by applying the proper rotation from H to the proper element from M. Because of this, the paradoxical decomposition of H yields a paradoxical decomposition of S² into four pieces A₁, A₂, A₃, A₄ as follows:

${\displaystyle A_{1}=S(a)M\cup M\cup B}$

${\displaystyle A_{2}=S(a^{-1})M\setminus B}$

${\displaystyle \displaystyle A_{3}=S(b)M}$

${\displaystyle \displaystyle A_{4}=S(b^{-1})M}$

where we define

${\displaystyle S(a)M=\{s(x)|s\in S(a),x\in M\}}$

and likewise for the other sets, and where we define

${\displaystyle B=a^{-1}M\cup a^{-2}M\cup \dots }$

(The five "paradoxical" parts of F₂ were not used directly, as they would leave M as an extra piece after doubling, owing to the presence of the singleton {e}!)

The (majority of the) sphere has now been divided into four sets (each one dense on the sphere), and when two of these are rotated, the result is double of what was had before:

${\displaystyle aA_{2}=A_{2}\cup A_{3}\cup A_{4}}$

${\displaystyle bA_{4}=A_{1}\cup A_{2}\cup A_{4}}$

Finally, connect every point on S² with a half-open segment to the origin; the paradoxical decomposition of S² then yields a paradoxical decomposition of the solid unit ball minus the point at the ball's center. (This center point needs a bit more care; see below.)

N.B. 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 like the case of the point at the center of the ball, it is possible to patch the proof to account for them all. (See below.)

In Step 3, the sphere was partitioned into orbits of our group H. To streamline the proof, the discussion of points that are fixed by some rotation was omitted; 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 of S² (other than the null rotation) has exactly 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 as 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(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 SO(3).

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.

• 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.[15] 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.[16]
• 2011: Laczkovich's paper[17] left open the possibility if 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,[18] 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[19] and Jan Mycielski[20] 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[21] 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.[22][23] Tomkowicz[24] 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 [25] constructed a paradoxical decomposition of the hyperbolic plane H² that uses Borel sets. The paradox depends on the existence of a properly discontinuous subgroup of the group of isometries of H². Similar paradox is obtained by Grzegorz Tomkowicz [26] 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 [27] 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.