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.) \diamond

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 {\Bbb R}^3 that is both translation and rotation invariant, which can measure every subset of {\Bbb R}^3, 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 {\Bbb R} or unit disk in {\Bbb R}^2 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 {\Bbb R} (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 G = (G,\cdot) be a group acting on a space X, and let A, B be subsets of X.

  1. We say that A, B are finitely G-equidecomposable if there exist finite partitions A = \bigcup_{i=1}^n A_i and B = \bigcup_{i=1}^n B_i and group elements g_1,\ldots,g_n \in G such that B_i = g_i A_i for all 1 \leq i \leq n.
  2. We say that A, B are countably G-equidecomposable if there exist countable partitions A = \bigcup_{i=1}^\infty A_i and B = \bigcup_{i=1}^\infty B_i and group elements g_1, g_2, \ldots \in G such that B_i = g_i A_i for all i.
  3. 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.
  4. 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 G = (G,+) 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 {\Bbb R} acts on itself by translation, then {}[0,2] is finitely {\Bbb R}-equidecomposable  with {}[10,11) \cup [21,22], and {}{\Bbb R} is finitely {\Bbb R}-equidecomposable with (-\infty,-10] \cup (10,+\infty). \diamond

Example 2. If G acts transitively on X, then any two finite subsets of X are finitely G-equidecomposable iff they have the same cardinality, and any two countably infinite sets of X are countably G-equidecomposable.  In particular, any countably infinite subset of X is countably G-paradoxical. \diamond

Exercise 1. Show that finite G-equidecomposability and countable G-equidecomposability are both equivalence relations. \diamond

Exercise 2. (Banach-Schroder-Bernstein theorem)  Let G act on X, and let A, B be subsets of X.

  1. 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.)
  2. 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.)
  3. Show that claims 1 and 2 hold when “finitely” is replaced by “countably”. \diamond

Exercise 3. Show that if G acts on X, A is a subset of X which is finitely (resp. countably) G-paradoxical, and x \in X, then the recurrence set \{ g \in G: gx \in A \} is also finitely (resp. countably) G-paradoxical (where G acts on itself by translation). \diamond

Let us first establish countable equidecomposability paradoxes in the reals.

Proposition 1. Let {\Bbb R} act on itself by translations.  Then {}[0,1] and {\Bbb R} are countably {\Bbb R}-equidecomposable.

Proof. By Exercise 2, it will suffice to show that some set contained in {}[0,1] is countably {\Bbb R}-equidecomposable with {\Bbb R}.  Consider the space {\Bbb R}/{\Bbb Q} of all cosets x+{\Bbb Q} of the rationals.  By the axiom of choice, we can express each such coset as x+{\Bbb Q} for some x \in [0,1/2], thus we can partition {\Bbb R} = \bigcup_{x \in E} x + {\Bbb Q} for some E \subset [0,1/2]. By Example 2, {\Bbb Q} \cap [0,1/2] is countably {\Bbb Q}-equidecomposable with {\Bbb Q}, which implies that \bigcup_{x \in E} x + ({\Bbb Q} \cap [0,1/2]) is countably {\Bbb R}-equidecomposable with \bigcup_{x \in E} x + {\Bbb Q}.  Since latter set is {\Bbb R} and the former set is contained in [0,1], the claim follows. \Box

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 {\Bbb R} containing an interval is {\Bbb R}-equidecomposable with {\Bbb R}.  In particular, we have

Corollary 1. Any subset of {\Bbb R} containing an interval is countably {\Bbb R}-paradoxical.

In particular, we see that any countably additive translation-invariant measure that measures every subset of {\Bbb R}, 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 {\Bbb R}.

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

Now we consider the integers.

Proposition 3. Let the integers {\Bbb Z} act on themselves by translation.  Then {\Bbb Z} is not finitely {\Bbb Z}-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 {\Bbb Z} into two sets A and B, which are in turn partitioned into finitely many pieces A = \bigcup_{i=1}^n A_i and B = \bigcup_{j=1}^m B_j, such that {\Bbb Z} can be partitioned as {\Bbb Z} = \bigcup_{i=1}^n A_i + a_i and {\Bbb Z} = \bigcup_{j=1}^m B_j + b_j for some integers a_1, \ldots,a_n,b_1,\ldots,b_m.

Now let N be a large integer (much larger than n,m,a_1,\ldots,a_n,b_1,\ldots,b_m).  We truncate {\Bbb Z} to the interval {}[-N,N] := \{-N,\ldots,N\}.  Clearly

A \cap [-N,N] = \bigcup_{i=1}^n A_i \cap [-N,N].  (1)

and

{}[-N,N] = \bigcup_{i=1}^n (A_i + a_i) \cap [-N,N].  (2)

From (2) we see that the set \bigcup_{i=1}^n (A_i \cap [-N,N]) + a_i differs from {}[-N,N] by only O(1) elements, where the bound in the O(1) expression can depend on n,a_1,\ldots,a_n 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

|[-N,N]| \leq |A \cap [-N,N]| + O(1). (3)

Similarly with A replaced by B.  Summing, we obtain

2 |[-N,N]| \leq |[-N,N]| + O(1), (4)

but this is absurd for N sufficiently large, and the claim follows.  \Box

Exercise 4. Use the above argument to show that in fact no infinite subset of {\Bbb Z} is finitely {\Bbb Z}-paradoxical; combining this with Example 2, we see that the only finitely {\Bbb Z}-paradoxical set of integers is the empty set. \diamond

The above argument can be generalised to an important class of groups:

Definition 2. (Amenability)  Let G = (G,\cdot) be a discrete, at most countable, group.  A Følner sequence is a sequence F_1, F_2, F_3, \ldots of finite subsets of G with \bigcup_{N=1}^\infty F_N = G with the property that \lim_{N \to \infty} \frac{|g F_N \Delta F_N|}{|F_N|} = 0 for all g \in G, where \Delta 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 G = (G,+).

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

Example 3. The sequence {}[-N,N] for N=1,2,3,\ldots is a Følner sequence for the integers {\Bbb Z}, which are hence an amenable group. \diamond

Exercise 5. Show that any abelian discrete group that is at most countable, is amenable. \diamond

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

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 p \in {\beta } {\Bbb N} and a Følner sequence (F_n)_{n=1}^\infty and defining \mu(A) := \lim_{n \to p} |A \cap F_n|/|F_n| for all A \in G. \diamond

The reals {\Bbb R} = ({\Bbb R},+) (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. \diamond

From this, we see that {\Bbb R} is not finitely {\Bbb R}-paradoxical.  But we can in fact say much more:

Proposition 4. Let A be a non-empty subset of {\Bbb R}.  Then A is not finitely {\Bbb R}-paradoxical.

Proof. Suppose for contradiction that we can partition A into two sets A = A_1 \cup A_2 which are both finitely {\Bbb R}-equidecomposable with A.  This gives us two maps f_1: A \to A_1, f_2: A \to A_2 which are piecewise given by a finite number of translations; thus there exists a finite set g_1,\ldots,g_d \in {\Bbb R} such that f_i(x) \in x + \{g_1,\ldots,g_d\} for all x \in A and i=1,2.

For any integer N \geq 1, consider the 2^N composition maps f_{i_1} \circ \ldots \circ f_{i_N}: A \to A for i_1,\ldots,i_N \in \{1,2\}.  From the disjointness of A_1,A_2 and an easy induction we see that the ranges of all these maps are disjoint, and so for any x \in A the 2^N quantities f_{i_1} \circ \ldots \circ f_{i_N}(x) are distinct.  On the other hand, we have

f_{i_1} \circ \ldots \circ f_{i_N}(x) \in x + \{g_1,\ldots,g_d\} + \ldots + \{g_1,\ldots,g_d\}. (5)

Simple combinatorics (relying primarily on the abelian nature of ({\Bbb R},+) shows that the number of values on the RHS of (5) is at most N^d.  But for sufficiently large N, we have 2^N > N^d, giving the desired contradiction. \Box

Let us call a group G supramenable if every non-empty subset of G is not finitely G-paradoxical; thus {\Bbb R} 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 G = (G,\cdot) has subexponential growth if for any finite subset S of G, we have \lim_{n \to \infty} |S^n|^{1/n} = 1, where S^n = S \cdot \ldots \cdot S is the set of n-fold products of elements of S.  Show that every group of subexponential growth is supramenable. \diamond

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

Exercise 10. Show that if two finite unions of intervals in {\Bbb R} are finitely {\Bbb R}-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.) \diamond

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

– Two-dimensional equidecomposability –

Now we turn to equidecomposability on the plane {\Bbb R}^2.  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 G = {\Bbb R}^2.  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 {\Bbb R}^2-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 {\Bbb R}^2-paradoxical.

Now suppose we allow both translations and rotations, thus G is now the group SO(2) \ltimes {\Bbb R}^2 of (orientation-preserving) isometries x \mapsto e^{i\theta} x + v for v \in {\Bbb R}^2 and \theta \in {\Bbb R}/2\pi {\Bbb Z}, where e^{i\theta} denotes the anti-clockwise rotation by \theta 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 g, h \in G such that all the words involving g and h (but not g^{-1} or h^{-1}) 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.  \Box

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

Lemma 3. The group G = SO(2) \ltimes {\Bbb R}^2 contains a free semigroup on two generators.

Proof. It is convenient to identify {\Bbb R}^2 with the complex plane {\Bbb C}.  We set g to be the rotation g x := \omega x for some transcendental phase \omega = e^{2\pi i \theta} be such that \omega := e^{2\pi i \theta} is transcendental (such a phase must exist, since the set of algebraic complex numbers is countable), and let h be the translation hx := x+1.  Observe that g and h act on the set A of polynomials in \omega with non-negative integer coefficients, and that gA and hA are disjoint.  The claim now follows from Lemma 2.  \Box

Combining Lemma 1 and Lemma 3 to create a countable, finitely paradoxical subset of SO(2) \ltimes {\Bbb R}^2, and then letting that set act on a generic point in the plane (noting that each group element in SO(2) \ltimes {\Bbb R}^2 has at most one fixed point), we obtain

Corollary 2. (Sierpinski-Mazurkiewicz paradox) There exist non-empty finitely SO(2) \ltimes {\Bbb R}^2-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 0 \to H \to G \to K \to 0 of discrete, at most countable, groups, and suppose one has a choice function \phi: K \to G 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 (A_n)_{n=1}^\infty and (B_n)_{n=1}^\infty be Følner sequences for H and K respectively.   Let f: {\Bbb N} \to {\Bbb N} be a rapidly growing function, and let (F_n)_{n=1}^\infty be the set F_n := \bigcup_{x \in B_n} \phi(x) \cdot A_{f(n)}.  One easily verifies that this is a Følner sequence for G if f is sufficiently rapidly growing.   (Strictly speaking, these F_n do not necessarily cover G, but this can  be achieved by right-translating the F_n suitably.  This can be done without choice because an at most countable set is always well-ordered.)   \Box

Exercise 11. Show that any finitely generated solvable group is amenable. More generally, show that any discrete, at most countable, solvable group is amenable. \diamond

Exercise 12. Show that any finitely generated subgroup of SO(2) \ltimes {\Bbb R}^2 is amenable.  (Hint: use the short exact sequence 0 \to {\Bbb R}^2 \to SO(2) \ltimes {\Bbb R}^2 \to SO(2) \to 0, which shows that SO(2) \ltimes {\Bbb R}^2 is solvable (in fact it is metabelian)).  Conclude that {\Bbb R}^2 is not finitely SO(2) \ltimes {\Bbb R}^2-paradoxical. \diamond

Finally, we show a result of Banach.

Proposition 5. The unit disk D in {\Bbb R}^2 is not finitely SO(2) \ltimes {\Bbb R}^2-paradoxical.

Proof. If the claim failed, then D would be finitely SO(2) \ltimes {\Bbb R}^2-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 SO(2) \ltimes {\Bbb R}^2 generated by a finite number of rotations x \mapsto e^{i\theta_j} x for j=1,\ldots,J and translations x \mapsto x +v_k for k=1,\ldots,K such that D and D \cup (D+v) are finitely G-equidecomposable.  Indeed, we may assume that the rigid motions that move pieces of D to pieces of D \cup (D+v) are of the form x \mapsto e^{i\theta_j} x + v_k for some 1 \leq j \leq J, 1 \leq k \leq K, thus

D \cup (D+v) = \bigcup_{j=1}^J \sum_{k=1}^K e^{i\theta_j} D_{j,k} + v_k (6)

for some partition D = \bigcup_{j=1}^J \sum_{k=1}^K D_{j,k} of the disk.

By amenability of the rotation group SO(2), one can find a finite set \Phi \subset SO(2) of rotations such that e^{i\theta_j} \Phi differs from \Phi by at most 0.01 |\Phi| elements for all 1 \leq j \leq J.  Let N be a large integer, and let \Gamma_N \subset {\Bbb R}^2 be the set of all linear combinations of e^{i\theta} v_k for \theta \in \Phi and 1 \leq k \leq K with coefficients in \{-N,\ldots,N\}.  Observe that \Gamma_N 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

|D \cap \Gamma_{N+10}| \leq 1.01 |D \cap \Gamma_N|.  (7)

On the other hand, from (6) and the rotation-invariance of the disk we have

2 |D \cap \Gamma_N| = 2 |e^{i\theta}(D) \cap \Gamma_N|

\leq |e^{i\theta}(D \cup (D+v)) \cap \Gamma_{N+5}|

\leq \sum_{j=1}^J \sum_{k=1}^K |e^{i(\theta+\theta_j)} D_{j,k} \cap \Gamma_{N+10}| (8)

for all \theta \in \Phi.  Averaging this over all \theta \in \Phi we conclude

2 |D \cap \Gamma_N| \leq 1.01 |D \cap \Gamma_{N+10}|, (9)

contradicting (7). \Box

Remark 4. Banach in fact showed the slightly stronger statement that any two finite unions of polygons of differing area were not finitely SO(2) \times {\Bbb R}^2-equidecomposable.   (The converse is also true, and is known as the Bolyai-Gerwien theorem.) \diamond

Exercise 13. Show that all the claims in this section continue to hold if we replace SO(2) \ltimes {\Bbb R}^2 by the slightly larger group \hbox{Isom}({\Bbb R}^2) = O(2) \ltimes {\Bbb R}^2 of isometries (not necessarily orientation-preserving. \diamond

Remark 5. As a consequence of Remark 4, the unit square is not SO(2) \ltimes {\Bbb R}^2-paradoxical.  However, it is SL(2) \ltimes {\Bbb R}^2-paradoxical; this is known as the von Neumann paradox. \diamond

– Three-dimensional equidecomposability –

We now turn to the three-dimensional setting. The new feature here is that the group SO(3) \times {\Bbb R}^3 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 F_2 on two generators is finitely F_2-paradoxical.

Proof. Let a, b be the two generators of F_2.  We can partition F_2 = \{1\} \cup W_a \cup W_b \cup W_{a^{-1}} \cup W_{b^{-1}}, where W_c is the collection of reduced words of F_2 that begin with c.  From the identities

W_{a^{-1}} = a^{-1} \cdot (F_2 \backslash W_a); \quad W_{b^{-1}} = b^{-1} \cdot (F_2 \backslash W_b) (8)

we see that F_2 is finitely F_2-equidecomposable with both W_a \cup W_{a^{-1}} and W_b \cup W_{b^{-1}}, and the claim now follows from Exercise 2. \Box

Corollary 3. Suppose that F_2 acts freely on a space X (i.e. gx \neq x whenever x \in X and g \in F_2 is not the identity).  Then X is finitely F_2-paradoxical.

Proof. Using the axiom of choice, we can partition X as X = \bigcup_{x \in \Gamma} F_2 x for some subset \Gamma of X.  The claim now follows from Lemma 5. \Box

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 A_+, A_-, B_+, B_- of X, whose union is not all of X, and elements a, b \in G, such that

a (X \backslash A_-) \subset A_+; \quad a^{-1} (X \backslash A_+) \subset A_-;

b(X \backslash B_-) \subset B_+; \quad b^{-1}(X \backslash B_+) \subset B_-. (9)

Then a, b generate a free group. (If drawn correctly, a diagram of the inclusions (9) resembles a game of doubles ping-pong of A_+, A_- versus B_+, B_-, hence the name.) \Box

Proposition 6. SO(3) contains a copy of the free group on two generators.

Proof. It suffices to find a space X that two elements of SO(3) 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

a = \begin{pmatrix} 3/5 & 4/5 & 0 \\ -4/5 & 3/5 & 0 \\ 0 & 0 & 1 \end{pmatrix}; \quad b = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 3/5 & -4/5 \\ 0 & 4/5 & 3/5 \end{pmatrix} (10)

and

A_\pm :=  5^{{\Bbb Z}} \cdot \{ \begin{pmatrix} x \\y \\ z \end{pmatrix}: x,y,z \in {\Bbb Z}, x=\pm 3y \hbox{ mod } 5, z = 0 \hbox{ mod } 5 \}

B_\pm :=  5^{{\Bbb Z}} \cdot \{ \begin{pmatrix} x \\y \\ z \end{pmatrix}: x,y,z \in {\Bbb Z}, z=\pm 3y \hbox{ mod } 5, x = 0 \hbox{ mod } 5 \} (11)

X := A_- \cup A_+ \cup B_- \cup B_+ \cup \{ \begin{pmatrix} 0 & 1 & 0 \end{pmatrix} \},

where 5^{{\Bbb Z}} 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. \Box

Remark 6. This is a special case of the Tits alternative. \diamond

Corollary 4. (Hausdorff paradox)  There exists a countable subset E of the sphere S^2 such that S^2 \backslash E is finitely SO(3)-paradoxical, where SO(3) of course acts on S^2 by rotations.

Proof. Let F_2 \subset SO(3) be a copy of the free group on two generators, as given by Proposition 6.  Each rotation in F_2 fixes exactly two points on the sphere.  Let E be the union of all these points; this is countable since F_2 is countable.  The action of F_2 on SO(3) \backslash E is free, and the claim now follows from Corollary 3. \Box

Corollary 5. (Banach-Tarski paradox on the sphere) S^2 is finitely SO(3)-paradoxical.

Proof. (Sketch) Iterating the Hausdorff paradox, we see that S^2 \backslash E is finitely SO(3)-equidecomposable to four copies of S^2 \backslash E, which can easily be used to cover two copies of S^2 (with some room to spare), by randomly rotating each of the copies.  The claim now follows from Exercise 2.  \Box

Exercise 15. (Banach-Tarski paradox on {\Bbb R}^3) Show that the unit ball in {\Bbb R}^3 is finitely SO(3) \ltimes {\Bbb R}^3-paradoxical. \diamond

Exercise 16. Extend these three-dimensional paradoxes to higher dimensions. \diamond