Notational convention: In this post only, I will colour a statement red if it assumes the axiom of choice. (For the rest of the course, the axiom of choice will be implicitly assumed throughout.)
The famous Banach-Tarski paradox asserts that one can take the unit ball in three dimensions, divide it up into finitely many pieces, and then translate and rotate each piece so that their union is now two disjoint unit balls. As a consequence of this paradox, it is not possible to create a finitely additive measure on that is both translation and rotation invariant, which can measure every subset of , and which gives the unit ball a non-zero measure. This paradox helps explain why Lebesgue measure (which is countably additive and both translation and rotation invariant, and gives the unit ball a non-zero measure) cannot measure every set, instead being restricted to measuring sets that are Lebesgue measurable.
On the other hand, it is not possible to replicate the Banach-Tarski paradox in one or two dimensions; the unit interval in or unit disk in cannot be rearranged into two unit intervals or two unit disks using only finitely many pieces, translations, and rotations, and indeed there do exist non-trivial finitely additive measures on these spaces. However, it is possible to obtain a Banach-Tarski type paradox in one or two dimensions using countably many such pieces; this rules out the possibility of extending Lebesgue measure to a countably additive translation invariant measure on all subsets of (or any higher-dimensional space).
In these notes I would like to establish all of the above results, and tie them in with some important concepts and tools in modern group theory, most notably amenability and the ping-pong lemma. This material is not required for the rest of the course, but nevertheless has some independent interest.
– One-dimensional equidecomposability –
Before we study the three-dimensional situation, let us first review the simpler one-dimensional situation. To avoid having to say “X can be cut up into finitely many pieces, which can then be moved around to create Y” all the time, let us make a convenient definition:
Definition 1. (Equidecomposability) Let be a group acting on a space X, and let A, B be subsets of X.
- We say that A, B are finitely G-equidecomposable if there exist finite partitions and and group elements such that for all .
- We say that A, B are countably G-equidecomposable if there exist countable partitions and and group elements such that for all i.
- We say that A is finitely G-paradoxical if it can be partitioned into two subsets, each of which is finitely G-equidecomposable with A.
- We say that A is countably G-paradoxical if it can be partitioned into two subsets, each of which is countably G-equidecomposable with A.
One can of course make similar definitions when is an additive group rather than a multiplicative one.
Clearly, finite G-equidecomposability implies countable G-equidecomposability, but the converse is not true. Observe that any finitely (resp. countably) additive and G-invariant measure on X that measures every single subset of X, must give either a zero measure or an infinite measure to a finitely (resp. countably) G-paradoxical set. Thus, paradoxical sets provide significant obstructions to constructing additive measures that can measure all sets.
Example 1. If acts on itself by translation, then is finitely -equidecomposable with , and is finitely -equidecomposable with .
Example 2. If G acts transitively on X, then any two finite subsets of X are finitely -equidecomposable iff they have the same cardinality, and any two countably infinite sets of X are countably -equidecomposable. In particular, any countably infinite subset of X is countably G-paradoxical.
Exercise 1. Show that finite G-equidecomposability and countable G-equidecomposability are both equivalence relations.
Exercise 2. (Banach-Schroder-Bernstein theorem) Let G act on X, and let A, B be subsets of X.
- If A is finitely G-equidecomposable with a subset of B, and B is finitely G-equidecomposable with a subset of A, show that A and B are finitely G-equidecomposable with each other. (Hint: adapt the proof of the Schroder-Bernstein theorem.)
- If A is finitely G-equidecomposable with a superset of B, and B is finitely G-equidecomposable with a superset of A, show that A and B are finitely G-equidecomposable with each other. (Hint: use part 1.)
- Show that claims 1 and 2 hold when “finitely” is replaced by “countably”.
Exercise 3. Show that if G acts on X, A is a subset of X which is finitely (resp. countably) G-paradoxical, and , then the recurrence set is also finitely (resp. countably) G-paradoxical (where G acts on itself by translation).
Let us first establish countable equidecomposability paradoxes in the reals.
Proposition 1. Let act on itself by translations. Then and are countably -equidecomposable.
Proof. By Exercise 2, it will suffice to show that some set contained in is countably -equidecomposable with . Consider the space of all cosets of the rationals. By the axiom of choice, we can express each such coset as for some , thus we can partition for some . By Example 2, is countably -equidecomposable with , which implies that is countably -equidecomposable with . Since latter set is and the former set is contained in [0,1], the claim follows.
Of course, the same proposition holds if [0,1] is replaced by any other interval. As a quick consequence of this proposition and Exercise 2, we see that any subset of containing an interval is -equidecomposable with . In particular, we have
Corollary 1. Any subset of containing an interval is countably -paradoxical.
In particular, we see that any countably additive translation-invariant measure that measures every subset of , must assign a zero or infinite measure to any set containing an interval. In particular, it is not possible to extend Lebesgue measure to measure all subsets of .
We now turn from countably paradoxical sets to finitely paradoxical sets. Here, the situation is quite different: we can rule out many sets from being finitely paradoxical. The simplest example is that of a finite set:
Proposition 2. If G acts on X, and A is a non-empty finite subset of X, then A is not finitely (or countably) G-paradoxical.
Proof. One easily sees that any two sets that are finitely or countably G-equidecomposable must have the same cardinality. The claim follows.
Now we consider the integers.
Proposition 3. Let the integers act on themselves by translation. Then is not finitely -paradoxical.
Proof. The integers are of course infinite, and so Proposition 2 does not apply directly. However, the key point is that the integers can be efficiently truncated to be finite, and so we will be able to adapt the Proposition 2 argument in our case.
Let’s see how. Suppose for contradiction that we could partition into two sets A and B, which are in turn partitioned into finitely many pieces and , such that can be partitioned as and for some integers .
Now let N be a large integer (much larger than ). We truncate to the interval . Clearly
From (2) we see that the set differs from by only O(1) elements, where the bound in the O(1) expression can depend on but does not depend on N. (The point here is that [-N,N] is “almost” translation-invariant in some sense.) Comparing this with (1) we see that
Similarly with A replaced by B. Summing, we obtain
but this is absurd for N sufficiently large, and the claim follows.
Exercise 4. Use the above argument to show that in fact no infinite subset of is finitely -paradoxical; combining this with Example 2, we see that the only finitely -paradoxical set of integers is the empty set.
The above argument can be generalised to an important class of groups:
Definition 2. (Amenability) Let be a discrete, at most countable, group. A Følner sequence is a sequence of finite subsets of G with with the property that for all , where denotes symmetric difference. A discrete, at most countable, group G is amenable if it contains at least one Følner sequence. Of course, one can define the same concept for additive groups .
Remark 1. One can define amenability for uncountable groups by replacing the notion of a Følner sequence with a Følner net. Similarly, one can define amenability for locally compact Hausdorff groups equipped with a Haar measure by using that measure in place of cardinality in the above definition. However, we will not need these more general notions of amenability here. The notion of amenability was first introduced (though not by this name, or by this definition) by von Neumann, precisely in order to study these sorts of decomposition paradoxes.
Example 3. The sequence for is a Følner sequence for the integers , which are hence an amenable group.
Exercise 5. Show that any abelian discrete group that is at most countable, is amenable.
Exercise 6. Show that any amenable discrete group G that is at most countable is not finitely G-paradoxical, when acting on itself. Combined with Exercise 3, we see that if such a group G acts on a non-empty space X, then X is not finitely G-paradoxical.
Remark 2. Exercise 6 suggests that an amenable group G should be able to support a non-trivial finitely additive measure which is invariant under left-translations, and can measure all subsets of G. Indeed, one can even create a finitely additive probability measure, for instance by selecting a non-principal ultrafilter and a Følner sequence and defining for all .
The reals (which we will give the discrete topology!) are uncountable, and thus not amenable by the narrow definition of Definition 2. However, observe from Exercise 5 that any finitely generated subgroup of the reals is amenable (or equivalently, that the reals themselves with the discrete topology are amenable, using the Følner net generalisation of Definition 2). Also, we have the following easy observation:
Exercise 7. Let G act on X, and let A be a subset of X which is finitely G-paradoxical. Show that there exists a finitely generated subgroup H of G such that A is finitely H-paradoxical.
From this, we see that is not finitely -paradoxical. But we can in fact say much more:
Proposition 4. Let A be a non-empty subset of . Then A is not finitely -paradoxical.
Proof. Suppose for contradiction that we can partition A into two sets which are both finitely -equidecomposable with A. This gives us two maps , which are piecewise given by a finite number of translations; thus there exists a finite set such that for all and .
For any integer , consider the composition maps for . From the disjointness of and an easy induction we see that the ranges of all these maps are disjoint, and so for any the quantities are distinct. On the other hand, we have
Simple combinatorics (relying primarily on the abelian nature of shows that the number of values on the RHS of (5) is at most . But for sufficiently large N, we have , giving the desired contradiction.
Let us call a group G supramenable if every non-empty subset of G is not finitely G-paradoxical; thus is supramenable. From Exercise 3 we see that if a supramenable group acts on any space X, then the only finitely G-paradoxical subset of X is the empty set.
Exercise 8. We say that a group has subexponential growth if for any finite subset S of G, we have , where is the set of n-fold products of elements of S. Show that every group of subexponential growth is supramenable.
Exercise 9. Show that every abelian group has subexponential growth (and is thus supramenable. More generally, show that every nilpotent group has subexponential growth and is thus also supramenable.
Exercise 10. Show that if two finite unions of intervals in are finitely -equidecomposable, then they must have the same total length. (Hint: reduce to the case when both sets consist of a single interval. First show that the lengths of these intervals cannot differ by more than a factor of two, and then amplify this fact by iteration to conclude the result.)
Remark 3. We already saw that amenable groups G admit finitely additive translation-invariant probability measures that measure all subsets of G (Remark 2 can be extended to the uncountable case); in fact, this turns out to be an equivalent definition of amenability. It turns out that supramenable groups G enjoy a stronger property, namely that given any non-empty set A on G, there exists a finitely additive translation-invariant measure on G that assigns the measure 1 to A; this is basically a deep result of Tarski.
– Two-dimensional equidecomposability –
Now we turn to equidecomposability on the plane . The nature of equidecomposability depends on what group G of symmetries we wish to act on the plane.
Suppose first that we only allow ourselves to translate various sets in the planes, but not to rotate them; thus . As this group is abelian, it is supramenable by Exercise 9, and so any non-empty subset A of the plane will not be finitely -paradoxical; indeed, by Remark 3, there exists a finitely additive translation-invariant measure that gives A the measure 1. On the other hand, it is easy to adapt Corollary 1 to see that any subset of the plane containing a ball will be countably -paradoxical.
Now suppose we allow both translations and rotations, thus G is now the group of (orientation-preserving) isometries for and , where denotes the anti-clockwise rotation by around the origin. This group is no longer abelian, or even nilpotent, so Exercise 9 no longer applies. Indeed, it turns out that G is no longer supramenable. This is a consequence of the following three lemmas:
Lemma 1. Let G be a group which contains a free semigroup on two generators (in other words, there exist group elements such that all the words involving g and h (but not or ) are distinct). Then G contains a non-empty finitely G-paradoxical set. In other words, G is not supramenable.
Proof. Let S be the semigroup generated by g and h (i.e. the set of all words formed by g and h, including the empty word (i.e. group identity). Observe that gS and hS are disjoint subsets of S that are clearly G-equidecomposable with S. The claim then follows from Exercise 2.
Lemma 2. (Semigroup ping-pong lemma) Let G act on a space X, let g, h be elements of G, and suppose that there exists a non-empty subset A of X such that gA and hA are disjoint subsets of A. Then g, h generate a free semigroup.
Proof. As in the proof of Proposition 4, we see from induction that for two different words w, w’ generated by g, h, the sets wA and w’A are disjoint, and the claim follows.
Lemma 3. The group contains a free semigroup on two generators.
Proof. It is convenient to identify with the complex plane . We set g to be the rotation for some transcendental phase be such that is transcendental (such a phase must exist, since the set of algebraic complex numbers is countable), and let be the translation . Observe that g and h act on the set A of polynomials in with non-negative integer coefficients, and that gA and hA are disjoint. The claim now follows from Lemma 2.
Combining Lemma 1 and Lemma 3 to create a countable, finitely paradoxical subset of , and then letting that set act on a generic point in the plane (noting that each group element in has at most one fixed point), we obtain
Corollary 2. (Sierpinski-Mazurkiewicz paradox) There exist non-empty finitely -paradoxical subsets of the plane.
We have seen that the group of rigid motions is not supramenable. Nevertheless, it is still amenable, thanks to the following lemma:
Lemma 4. Suppose one has a short exact sequence of discrete, at most countable, groups, and suppose one has a choice function that inverts the projection of G to K (the existence of which is automatic, from the axiom of choice, or if G is finitely generated). If H and K are amenable, then so is G.
Proof. Let and be Følner sequences for H and K respectively. Let be a rapidly growing function, and let be the set . One easily verifies that this is a Følner sequence for G if f is sufficiently rapidly growing. (Strictly speaking, these do not necessarily cover G, but this can be achieved by right-translating the suitably. This can be done without choice because an at most countable set is always well-ordered.)
Exercise 11. Show that any finitely generated solvable group is amenable. More generally, show that any discrete, at most countable, solvable group is amenable.
Exercise 12. Show that any finitely generated subgroup of is amenable. (Hint: use the short exact sequence , which shows that is solvable (in fact it is metabelian)). Conclude that is not finitely -paradoxical.
Finally, we show a result of Banach.
Proposition 5. The unit disk D in is not finitely -paradoxical.
Proof. If the claim failed, then D would be finitely -equidecomposable with a disjoint union of two copies of D, say D and D+v for some vector v of length greater than 2. By Exercise 7, we can then find a subgroup G of generated by a finite number of rotations for and translations for such that D and are finitely G-equidecomposable. Indeed, we may assume that the rigid motions that move pieces of D to pieces of are of the form for some , thus
for some partition of the disk.
By amenability of the rotation group SO(2), one can find a finite set of rotations such that differs from by at most elements for all . Let N be a large integer, and let be the set of all linear combinations of for and with coefficients in . Observe that is a finite set whose cardinality grows at most polynomially in N. Thus, by the pigeonhole principle, one can find arbitrarily large N such that
On the other hand, from (6) and the rotation-invariance of the disk we have
for all . Averaging this over all we conclude
Remark 4. Banach in fact showed the slightly stronger statement that any two finite unions of polygons of differing area were not finitely -equidecomposable. (The converse is also true, and is known as the Bolyai-Gerwien theorem.)
Exercise 13. Show that all the claims in this section continue to hold if we replace by the slightly larger group of isometries (not necessarily orientation-preserving.
Remark 5. As a consequence of Remark 4, the unit square is not -paradoxical. However, it is -paradoxical; this is known as the von Neumann paradox.
– Three-dimensional equidecomposability –
We now turn to the three-dimensional setting. The new feature here is that the group of rigid motions is no longer abelian (as in one dimension) or solvable (as in two dimensions), but now contains a free group on two generators (not just a free semigroup, as per Lemma 3). The significance of this fact comes from
Lemma 5. The free group on two generators is finitely -paradoxical.
Proof. Let a, b be the two generators of . We can partition , where is the collection of reduced words of that begin with c. From the identities
we see that is finitely -equidecomposable with both and , and the claim now follows from Exercise 2.
Corollary 3. Suppose that acts freely on a space X (i.e. whenever and is not the identity). Then X is finitely -paradoxical.
Proof. Using the axiom of choice, we can partition X as for some subset of X. The claim now follows from Lemma 5.
Next, we embed the free group inside the rotation group SO(3) using the following useful lemma (cf. Lemma 2).
Exercise 14 (ping-pong lemma). Let G act on a set X. Suppose that there exist disjoint subsets of X, whose union is not all of X, and elements , such that
Then a, b generate a free group. (If drawn correctly, a diagram of the inclusions (9) resembles a game of doubles ping-pong of versus , hence the name.)
Proposition 6. contains a copy of the free group on two generators.
Proof. It suffices to find a space X that two elements of act on in a way that Exercise 14 applies. There are many such constructions. One is given (and motivated) in this blog post of David Speyer, based on passing from the reals to the 5-adics, where -1 is a square root and so SO(3) becomes isomorphic to PSL(2). At the end of the day, one takes
where denotes the integer powers of 5 (which act on column vectors in the obvious manner). The verification of the ping-pong inclusions (9) is a routine application of modular arithmetic.
Remark 6. This is a special case of the Tits alternative.
Corollary 4. (Hausdorff paradox) There exists a countable subset E of the sphere such that is finitely -paradoxical, where of course acts on by rotations.
Proof. Let be a copy of the free group on two generators, as given by Proposition 6. Each rotation in fixes exactly two points on the sphere. Let E be the union of all these points; this is countable since is countable. The action of on is free, and the claim now follows from Corollary 3.
Corollary 5. (Banach-Tarski paradox on the sphere) is finitely -paradoxical.
Proof. (Sketch) Iterating the Hausdorff paradox, we see that is finitely -equidecomposable to four copies of , which can easily be used to cover two copies of (with some room to spare), by randomly rotating each of the copies. The claim now follows from Exercise 2.
Exercise 15. (Banach-Tarski paradox on ) Show that the unit ball in is finitely -paradoxical.
Exercise 16. Extend these three-dimensional paradoxes to higher dimensions.