Paradoxical decompositions

0 Paradoxical decompositions

There is a mathematical theorem which implies the following: An orange can be cut into finitely many pieces, and these pieces can be reassembled to yield two oranges of the same size as the original one. Admittedly, this sounds more like a version of the feeding of the five thousand than like rigorous mathematics. Nevertheless, it is a perfectly sound application of the Banach–Tarski paradox, whose strongest form is: Let A and B be any two bounded sets in three-dimensional space with non-empty interior. Then there is a partition of A into finitely many sets which can be reassembled to yield B. Applications much more bizarre than just making two oranges out of one come to mind immediately: A pea can be split into finitely many pieces which can be recombined to yield a lifesized statue of Stefan Banach (or a solid ball whose diameter is larger than the distance of the Earth from the sun). Can a theorem whose consequences so blatantly defy common sense be true? In fact, there is an element of faith to the Banach–Tarski paradox (so that it is not all that removed from the feeding of the five thousand). Its proof rests on two pillars: – the axiom of choice (and you can believe in that or leave it), and – the fact that the free group in two generators lacks a property called amenability. In fact, the Banach–Tarski paradox is just one instance of so-called paradoxical decompositions: Some set can be split up and then be recombined to yield two copies of itself. As we shall see in this chapter, paradoxical decompositions (or rather: their non-existence) are at the very heart of the notion of amenability.

0.1 The Banach–Tarski paradox We begin by making precise what we mean when we say that some set admits a paradoxical decomposition: Definition 0.1.1 Let G be a group which acts on a (non-empty) set X. Then E ⊂ X is called G-paradoxical if there are pairwise disjoint subsets A1 , . . . , An , B1 , . . . , Bm of E along Sn Sm with g1 , . . . , gn , h1 , . . . , hm ∈ G such that E = j=1 gj · Aj and E = j=1 hj · Bj . V. Runde: LNM 1774, pp. 1–15, 2002 c Springer-Verlag Berlin Heidelberg 2002


2

0 Paradoxical decompositions

Exercise 0.1.1 Let G be a group which acts on a set X, let H be a subgroup of G, and let E ⊂ X be H-paradoxical. Show that E is G-paradoxical.

We shall simply speak of paradoxical sets (instead of using the slightly lengthier adjective G-paradoxical) in the following two cases: – G acts on itself via multiplication from the left, and – X is a metric space, and G is the group of invertible isometries on X. Theorem 0.1.2 The free group in two generators is paradoxical. Proof Let a and b be two generators of F2 . For x ∈ {a, b, a−1 , b−1 }, let W (x) := {w ∈ F2 : w starts with x}. Then F2 = {eF2 } ∪ W (a) ∪ W (b) ∪ W (a−1 ) ∪ W (b−1 ), the union being disjoint. Now observe that, for any w ∈ F2 \ W (a), we have a−1 w ∈ W (a−1 ), so that w = a(a−1 w) ∈ aW (a−1 ). It follows that F2 = W (a) ∪ aW (a−1 ) and, similarly, F2 = W (b) ∪ bW (b−1 ). u t We shall now see that, given a paradoxical group G that acts on some set X, a mild demand on the group action forces X to G-paradoxical. This is the first time that we encounter the axiom of choice; we indicate the dependence on the axiom of choice by (AC).

Proposition 0.1.3 (AC) Let G be a paradoxical group which acts on X without non-trivial fixed points, i.e. if there are g ∈ G and x ∈ X such that g · x = x, then g = eG . Then X is G-paradoxical. Proof Let A1 , . . . , An , B1 , . . . , Bm ⊂ G and g1 , . . . , gn , h1 , . . . , hm be as in Definition 0.1.1. Choose a set M ⊂ X such that M contains exactly one element from every G-orbit. We S claim that {g · M : g ∈ G} is a disjoint partition of X. Certainly, g∈G g · M = X (since M contains one point from every G-orbit). Suppose now that there are g, h ∈ G and x, y ∈ M such that g · x = h · y. Then h−1 g · x = y, so that x, y ∈ M are in the same G-orbit and thus must be equal. Since G acts on X without non-trivial fixed points, this means h−1 g = eG . Let [ A∗j = {g · M : g ∈ Aj } (j = 1, . . . , n) and Bj∗ =

[

{g · M : g ∈ Bj }

(j = 1, . . . , m).

∗ Clearly, A∗1 , . . . , A∗n , B1∗ , . . . , Bm are pairwise disjoint subsets of X such that X = Sm ∗ ∗ Aj = j=1 hj · Bj . u t

Sn

j=1 gj

·

Exercise 0.1.2 Show where exactly in the proof of Proposition 0.1.3 the axiom of choice was invoked.

0.1 The Banach–Tarski paradox

3

So, suppose that F2 acts without non-trivial fixed points on some set X. Then Theorem 0.1.2 and Proposition 0.1.3 combined yield that X is F2 -paradoxical. Since — in view of the Banach–Tarski paradox — we want to show that certain subsets of R3 are paradoxical, we are thus faced with the problem of making F2 act on R3 as invertible isometries. For n ∈ N, we use the symbol O(n) to denote the real n × n-matrices A such that At A = AAt = En , where En is the identity matrix; O(n) is called the n-dimensional orthogonal group. The n-dimensional special orthogonal group SO(n) is the subgroup of O(n) consisting of those matrices A ∈ O(n) such that det A = 1. Theorem 0.1.4 There are rotations A and B about lines through the origin in R3 which generate a subgroup of SO(3) isomorphic to F2 . Proof Let A± =



√  ∓232 0  1 3 0 0 01

1 3  2√2 ± 3

and

B±



 1 0 0 √   1 = 0 ∓232  . √3 1 0 ±232 3

Let w be a reduced word in A, B, A−1 , and B −1 which is not the empty word . We claim that w cannot act as the identity on R3 . To see this, first note that we may assume without loss of generality that w ends in A± (otherwise, conjugate with A± ). We claim that     a 1 1  √    w · 0 = k b 2, 3 0 c where a, b, c ∈ Z with 3 6 |b and k is the length of w. This certainly establishes the claim that w does not act as the identity on R3 . We proceed by induction on k. Suppose first that k = 1, i.e. w = A± , so that     1 1 √    1 w ·  0  =  ±2 2  . 3 0 0 Let w = A± w0 or w = B ± w0 , where     1 a0 √ 1     w0 ·  0  = k−1  b0 2  3 0 c0 with a0 , b0 , c0 ∈ Z and 3 6 |b0 . It follows that     1 a 1  √    w · 0 = k b 2, 3 0 c where (

a = a0 ∓ 4b0 , b = b0 ± 2a0 , c = 3c0 , in case w = A± w0 ; 0 0 0 a = 3a , b = b ∓ 2c , c = c0 ± 4b0 , in case w = B ± w0 .

4

0 Paradoxical decompositions

It is clear from these identities that a, b, c ∈ Z. What remains to be shown is that 3 6 |b. Case 1: w = A± B ± v (where possibly v = ). Then b = b0 ∓ 2a0 with 3|a0 . Since 3 6 |b0 by assumption, it follows that 3 6 |b. Case 2: w = B ± A± v. Then b = b0 ∓ 2c0 with 3|c0 . Again, 3 6 |b0 , so that 3 6 |b. Case 3: w = A± A± v. By assumption,     a00 1 √ 1     v ·  0  = k−2  b00 2  3 0 c00 with a00 , b00 , c00 ∈ Z. It follows that b = b0 ± 2a0 = b ± 2(a00 ∓ 4b00 ) = b0 + b00 ± 2a00 − 9b00 = 2b0 − 9b00 , so that 3 6 |b. Case 4: w = B ± B ± v. This is treated like Case 3. u t Exercise 0.1.3 Show that SO(n), for each n ≥ 3, contains a subgroup isomorphic to F2 .

With F2 as a subgroup of SO(3) and Proposition 0.1.3 at hand, we can now prove the first classical result on paradoxical decompositions. As is customary, we write S 2 for the unit sphere in R3 : Theorem 0.1.5 (Hausdorff paradox; AC) There is a countable subset D of S 2 such that S 2 \ D is SO(3)-paradoxical. Proof Let A and B be as in the proof of Theorem 0.1.4. Then the subgroup G of SO(3) generated by A and B is isomorphic to F2 . Since A and B are rotations about lines through the origin, each w ∈ G \ {eG } has exactly two fixed points in S 2 . The set F := {x ∈ S 2 : x is a fixed point for some w ∈ G \ {eG }} S is thus countable, and so is D := {w · F : w ∈ G}. Clearly, G acts on S 2 \ D without non-trivial fixed points, so that, by Proposition 0.1.3, S 2 \ D is G-paradoxical. By Exercise 0.1.1, S 2 \ D is SO(3)-paradoxical. u t 2 As we shall see very soon, S itself is SO(3)-paradoxical. Definition 0.1.6 Let G be a group which acts on a set X, and let A and B be subsets of X. Then A and B are called G-equidecomposable if there are A1 , . . . , An ⊂ A, B1 , . . . , Bn ⊂ B and g1 , . . . , gn ∈ G such that: (i) A =

n [

j=1

Aj

and

B=

n [

Bj ;

j=1

(ii) Aj ∩ Ak = ∅ = Bj ∩ Bk (j, k ∈ {1, . . . , n}, j 6= k); (iii) gj · Aj = Bj (j = 1, . . . , n).

0.1 The Banach–Tarski paradox

5

If A and B are G-equidecomposable, we write A ∼G B. In case G is the group of invertible isometries of a metric space (or if G is obvious), we simply write A ∼ B. Exercise 0.1.4 Show that ∼G is an equivalence relation. Exercise 0.1.5 Let G be a group that acts on a set X, and let A, A1 , A2 , B, B1 , B2 ⊂ X. Show that the following hold: (i) If A ∼ B, then there is a bijection φ : A → B with C ∼ φ(C) for all C ⊂ A. (ii) If A1 ∩ A2 = ∅ = B1 ∩ B2 with A1 ∼ B1 and A2 ∼ B2 , then A1 ∪ A2 ∼ B1 ∪ B2 .

Proposition 0.1.7 Let D ⊂ S 2 be countable. Then S 2 and S 2 \ D are SO(3)-equidecomposable. Proof Let L be a line in R3 through the origin such that L ∩ D = ∅, and let W be the collection of all θ ∈ [0, 2π) with the follow property: There is x ∈ D such that ρ · x ∈ D as well, where — for some n ∈ N — ρ is the rotation about L by the angle nθ. It is clear from the definition that W is countable, so that there is θ ∈ [0, 2π) \ W . Let ρ be the rotation about L by the angle θ, then ρn · D ∩ D = ∅ for all n ∈ N. It follows that ρn · D ∩ ρm · D = ∅

(n, m ∈ N, n 6= m).

˜ = S∞ ρn · D. Then Let D n=0 ˜ ∪ (S 2 \ D) ˜ ∼ρ·D ˜ ∪ (S 2 \ D) ˜ = S 2 \ D, S2 = D which establishes the claim. u t The relevance of G-equidecomposability becomes apparent in the next proposition: Proposition 0.1.8 Let G be a group that acts on a set X, and let E and E 0 be subsets of X with E ∼G E 0 . Then, if E is G-paradoxical, so is E 0 . Proof Let A1 , . . . , An , B1 , . . . , Bm ⊂ E be as in in Definition 0.1.1, and let A :=

n [

Aj

and

j=1

B :=

n [

Bj ,

j=1

so that A ∼G E and B ∼G E. From Exercise 0.1.4, it follows that A ∼G E 0 and B ∼G E 0 . This implies that E 0 is also G-paradoxical. u t Exercise 0.1.6 Verify the last statement in the proof of Proposition 0.1.8.

Together, Theorem 0.1.5, Proposition 0.1.7, and Proposition 0.1.8 yield a stronger version of the Hausdorff paradox: Corollary 0.1.9 (AC) S 2 is SO(3)-paradoxical. We are also now in a position to prove a weak version of the Banach–Tarski paradox (which is already sufficient if all you want is to make two oranges out of one): Corollary 0.1.10 (Weak Banach–Tarski paradox; AC) Every closed ball in R3 is paradoxical.

6

0 Paradoxical decompositions

Proof It is sufficient to prove that the closed unit ball B1 [0, R3 ] is paradoxical. We first show that B1 [0, R3 ] \ {0} is paradoxical. Since S 2 is SO(3)-paradoxical by Corollary 0.1.9, there are A1 , . . . , An , B1 , . . . , Bm ⊂ S 2 ⊂ R3 and g1 , . . . , gn , h1 , . . . , hm ∈ SO(3) as in Definition 0.1.1. Let A∗j := {tx : t ∈ (0, 1], x ∈ Aj }

(j = 1, . . . , n)

Bj∗ := {tx : t ∈ (0, 1], x ∈ Bj }

(j = 1, . . . , m).

and

∗ Then, certainly, A∗1 , . . . , A∗n , B1∗ , . . . , Bm ⊂ B1 [0, 1; R3 ] \ {0} are pairwise disjoint and Sm Sn 3 ∗ B1 [0, R ] \ {0} = j=1 gj · Aj = j=1 hj · Bj∗ . It follows that B1 [0, R3 ] \ {0} is indeed paradoxical.
Let x = 0, 0, 21 ∈ B1 [0, R3 ] \ {0}. Let ρ be a rotation of infinite order about a line through x that misses the origin. Let D := {ρn · 0 : n ∈ N0 }. Clearly, ρ · D = D \ {0}. Then

B1 [0, R3 ] = D ∪ B1 [0, R3 ] \ D ∼ ρ · D ∪ B1 [0, R3 ] \ D = B1 [0, R3 ] \ {0}, so that B1 [0, R3 ] is paradoxical by Proposition 0.1.8. u t Exercise 0.1.7 Show that R3 is paradoxical.

Remark 0.1.11 A classical result by S. Mazur and S. Ulam ([M–U]) asserts that a surjective isometry between real Banach spaces is already linear if it maps the origin to the origin. It follows that any surjective isometry between Banach spaces is the composition of a surjective, R-linear isometry with a translation. For the invertible isometries on R3 , this means that every such isometry is the composition of an element of O(3) with a translation. To establish the Banach–Tarski paradox in its strongest form, we need another definition: Definition 0.1.12 Let G be a group that acts on the set X, and let A and B be subsets of X. We write A G B (or simply: A  B) if A and a subset of B are G-equidecomposable. Exercise 0.1.8 Show that G is a reflexive and transitive relation on the equivalence classes of P(X) with respect to ∼G .

The following is an analogue of the Cantor–Bernstein theorem for : Theorem 0.1.13 Let G be a group that acts on a set X, and let A and B be subsets of X such that A G B and B G A. Then A ∼G B. Proof Let B1 ⊂ B and A1 ⊂ A be such that A ∼ B1 and B ∼ A1 . Let φ : A → B1 and ψ : B → A1 be bijections as in Exercise 0.1.5(i). Let C0 := A \ A1 , and define Cn+1 := S∞ ψ(φ(Cn )). Let C := n=0 Cn . It follows that ψ −1 (A \ C) = B \ φ(C). By Exercise 0.1.5(i), this means that A \ C ∼ B \ φ(C). In a similar fashion, we see that C ∼ φ(C). It follows that A = (A \ C) ∪ C ∼ (B \ φ(C)) ∪ φ(C) = B by Exercise 0.1.5(ii). u t We can now prove the Banach–Tarski paradox:

0.2 Tarski’s theorem

7

Theorem 0.1.14 (Banach–Tarski paradox; AC) Let A and B be bounded subsets of R3 , each with non-empty interior. Then A ∼ B. Proof By symmetry and by Theorem 0.1.13, it is sufficient to prove that A  B. Since A is bounded, there is r > 0 such that A ⊂ Br [0, R3 ]. Let x be an interior point of B. Then there is  > 0 such that B [x, R3 ] ⊂ B. Since Br [0, R3 ] is compact, there are invertible isometries g1 , . . . , gn : R3 → R3 (in fact, translations will do) such that Br [0, R3 ] ⊂ g1 · B [x, R3 ] ∪ · · · ∪ gn · B [x, R3 ]. Choose isometries h1 , . . . , hn on R3 such that hj · B [x, R3 ] ∩ hk · B [x, R3 ] = ∅ for j 6= k Sn (again, translations will do). Let S := j=1 hj · B [x, R3 ]. It follows from the weak Banach– Tarski paradox Corollary 0.1.10, that S  B [x, R3 ] (Why?). Then A ⊂ Br [0, R3 ] ⊂ g1 · B [x, R3 ] ∪ · · · ∪ gn · B [x, R3 ]  S  B [x, R3 ] ⊂ B which establishes the claim. u t Exercise 0.1.9 Where exactly in the proof of Theorem 0.1.14 was the axiom of choice used?

0.2 Tarski’s theorem We have mentioned in the introduction of this chapter that one of the key ingredients for the proof of the Banach–Tarski paradox was that F2 lacks the property of amenability. We have not yet defined what amenability is, but we won’t spill any beans by already admitting that for a (discrete) group amenability is the same as not being paradoxical. Nevertheless, the formal definition of amenability, which will be given at the end of this section, looks quite different from Definition 0.1.1. The reason why these two notions are equivalent is the following deep theorem due to A. Tarski: Theorem 0.2.1 (Tarski’s theorem; AC) Let G be a group that acts on a set X, and let E be subset of X. Then there is a finitely additive, G-invariant set function µ : P(X) → [0, ∞] with µ(E) ∈ (0, ∞) if and only if E is not G-paradoxical. Exercise 0.2.1 Let G be a group that acts on a set X, and let E ⊂ X be G-paradoxical. If µ : P(X) → [0, ∞] is any finitely additive, G-invariant set function, show that µ(E) = 0 or µ(E) = ∞ (and thus prove the easy direction of Tarski’s theorem). Do you need the axiom of choice?

The proof of the difficult direction of Tarski’s theorem requires some preparation. We start with some notions from graph theory: A (undirected) graph is a triple (V, E, φ), where V and E are non-empty sets and φ is a map from E into the unordered pairs of elements of V . The elements of V are called vertices and the elements of E are called edges. If e ∈ E and v, w ∈ V with φ(e) = (v, w), we say that e joins v and w or that v and w are the endpoints of e; we shall also sometimes be sloppy and simply identify the edge e with its image under φ. A path in (V, E, φ) is a finite sequence (e1 , . . . , en ) of edges together with a finite sequence (v0 , . . . , vn ) of vertices where v0 is an endpoint of e1 , vn is an endpoint of en , and vj is an endpoint of ej for j = 1, . . . , n − 1. We say that v0 and vn are joined by the path. For formal reasons, we will also say that the empty path joins each vertex with itself.

8

0 Paradoxical decompositions

Definition 0.2.2 Let (V, E, φ) be a graph, and let k ∈ N. (i) If each vertex is the endpoint of exactly k edges, then (V, E, φ) is called k-regular . (ii) If V = X ∪ Y , where X and Y are disjoint, and each edge has one endpoint in X and one in Y , then (V, E, φ) is called bipartite. In what follows we shall simply speak of a bipartite graph (X, Y, E, φ) when we mean that (V, E, φ) is a bipartite graph with V , X and Y as in Definition 0.2.2(ii). Definition 0.2.3 Let (X, Y, E, φ) be a bipartite graph, and let A ⊂ X and B ⊂ Y . A perfect matching of A and B is a subset F of E such that (i) each element of A ∪ B is an endpoint of exactly one f ∈ F , and (ii) all endpoints of edges in F are in A ∪ B. Exercise 0.2.2 Let (X, Y, E, φ) be a bipartite graph which is k-regular for some k ∈ N, and suppose that |V | < ∞. (i) Show that |E| < ∞ and that |X| = |Y |. (ii) For any M ⊂ V , let N (M ) be the set of those vertices which are joined by an edge with a point of M . Show that |N (M )| ≥ |M |. (iii) Let A ⊂ X and B ⊂ Y be such that there is a perfect matching F of A and B with |F | maximal. Show that A = X. (Hint: Assume that there is x ∈ X \ A, and consider the set Z of those vertices z which are joined with x by a path (e1 , . . . , en ) such that the ej ’s lie alternately in F and E \ F . Use the maximality of |F | to show that Z ∩ Y ⊂ B. Then show that Z ∩ Y = N (Z ∩ X) and use (ii) to arrive at a contradiction.) (iv) (Marriage theorem) Conclude that there is a perfect matching of X and Y .

The reason why the assertion of Exercise 0.2.2(iv) carries the catchy name “marriage theorem” is the following application: If each girl in town finds exactly k boys attractive and each boy in town finds exactly k girls attractive, then it is possible to arrange marriages between them in such a way that, in each marriage, the partners find one another attractive. How comforting to know . . . We shall now prove K¨onig’s theorem, which is simply the marriage theorem without any finiteness requirements: Theorem 0.2.4 (K¨ onig’s theorem; AC) Let (X, Y, E, φ) be a bipartite graph which is k-regular for some k ∈ N. Then there is a perfect matching of X and Y . Proof Define an equivalence relation on V : Two vertices are equivalent if they can be joined by a path (remember that each vertex is joined with itself by the empty path). Each equivalence class with respect to this relation is again a k-regular, bipartite graph and has countably many vertices and edges (by k-regularity). If we can find a perfect matching for each such graph, we can put them together to form a matching for X and Y . We may thus suppose that X, Y and E are countably infinite, and that any two points in V can be joined by a path. Let {en : n ∈ N} be an enumeration of E. Consider the collection of all finite sequences in {0, 1}; if s and t are such sequences, we write s ≤ t if s is an initial segment of t. We call such a sequence s of length n good if there are finite sets V 0 ⊂ V and E 0 ⊂ E such that:

0.2 Tarski’s theorem

9

– V 0 contains all vertices that appear as endpoints of e1 , . . . , en ; – {e1 , . . . , en } ⊂ E 0 ; – (V 0 , E 0 , φ|E 0 ) is a k-regular, bipartite graph which has a perfect matching F 0 for V 0 ∩ X and V 0 ∩ Y such that, for j < n, ej ∈ F 0 if and only if sj = 1. From this definition, it is clear that if s ≤ t and if t is good, then so is s. If V 0 ⊂ V and E 0 ⊂ E are finite sets such that (V 0 , E 0 , φ|E 0 ) is a graph, then there are finite subsets V 00 ⊂ V and E 00 ⊂ E with V 0 ⊂ V 00 and E 0 ⊂ E 00 such that (V 00 , E 00 , φ|E 00 ) is a bipartite, k-regular graph. (How exactly is this accomplished?). By Exercise 0.2.2(iv), there is a perfect matching F 00 ⊂ E 00 for V 00 ∩ X and V 00 ∩ Y . Define a good sequence through ( 1, if ej ∈ F 00 , N → {0, 1}, j 7→ 0, else. It follows that each good sequence of length n has, for each m > n, a good extension of length m. We can thus inductively define an infinite sequence in {0, 1} such that each finite initial segment of s is good and has infinitely many good extensions. Let F := {en : sn = 1}. Then F is a perfect matching for X and Y . u t Exercise 0.2.3 Once again: Where exactly in the proof of Theorem 0.2.4 was the axiom of choice used?

K¨onig’s theorem was only the first step on the way to a proof of Tarki’s theorem. The next step is to associate, with each group action on some set, an object called the type semigroup of that action. In order to define the type semigroup of a given group action, we first have to enlarge that action: Definition 0.2.5 Let G be a group that acts on a set X. (i) Define X ∗ := X × N0 and G∗ := {(g, π) : g ∈ G, and π is a permutation of N0 }, and let G∗ act on X ∗ via (g, π) · (x, n) := (g · x, π(n))

((g, π) ∈ G∗ , (x, n) ∈ X ∗ ).

(ii) If A ⊂ X ∗ , then those n ∈ N0 such that there is an element of A whose second coordinate is n are called the levels of A. Exercise 0.2.4 Let G, X, G∗ , and X ∗ as in Definition 0.2.5. Show that, if E1 , E2 ⊂ X, then E1 ∼G E2 if and only if E1 × {n} ∼G∗ E2 × {m} for all n, m ∈ N0 .

Definition 0.2.6 Let G, X, G∗ , and X ∗ be as in Definition 0.2.5. (i) A set A ⊂ X ∗ is called bounded if it has only finitely many levels. (ii) If A ⊂ X ∗ is bounded, then the equivalence class of A with respect to ∼G∗ is called the type of A and is denoted by [A]. (iii) If E ⊂ X, we write [E] := [E × {0}].

10

0 Paradoxical decompositions

(iv) Let A, B ⊂ X ∗ be bounded, and let k ∈ N0 be such that B 0 := {(b, n + k) : (b, n) ∈ B} ∩ A = ∅. Define [A] + [B] := [A ∪ B 0 ]. (v) Let S := {[A] : A ⊂ X ∗ is bounded}. Then (S, +) is called the type semigroup of the action of G on X. We have just labeled (S, +) the type semigroup, thus implying that it is indeed a semigroup. This requires at least a little verification: Exercise 0.2.5 Let G be a group acting on a set X, and let (S, +) be the corresponding type semigroup. (i) Show that + is well defined. (ii) Show that (S, +) is a commutative semigroup with identity [∅].

If S is any commutative semigroup, define nα := α + · · · + α | {z }

(α ∈ S, n ∈ N).

n times

Also, we write α ≤ β for α, β ∈ S if there is γ ∈ S such that α + γ = β. Exercise 0.2.6 Let S be a commutative semigroup, and let α1 , α2 , β1 , β2 ∈ S be such that α1 ≤ β1 and α2 ≤ β2 . Show that α1 + α2 ≤ β1 + β2 . Exercise 0.2.7 Let G be a group acting of a set X, and let S be the corresponding type semigroup. Show that: (i) If α, β ∈ S are such that α ≤ β and β ≤ α, then α = β. (ii) A set E ⊂ X is G-paradoxical if and only if [E] = 2[E].

If S is the type semigroup of some group action, we have the following cancellation law: Theorem 0.2.7 (AC) Let S be the type semigroup of some group action, and let α, β ∈ S and n ∈ N be such that nα = nβ. Then α = β. Proof If nα = nβ, then there are two disjoint, bounded G∗ -equidecomposable sets E, E 0 ⊂ X ∗ with pairwise disjoint subsets A1 , . . . , An ⊂ E and B1 , . . . , Bn ⊂ E 0 such that – E = A1 ∪ · · · ∪ An and E 0 = B1 ∪ · · · ∪ Bn , and – [Aj ] = α and [Bj ] = β for j = 1, . . . , n. Let χ : E → E 0 and, for j = 1, . . . , n, let φj : A1 → Aj and ψj : B1 → Bj be bijective maps as in Exercise 0.1.5(i) (choose φ1 and ψ1 as the identity). For each a ∈ A1 and b ∈ B1 let a ¯ := {a, φ2 (a), . . . , φn (a)}

and

¯b := {b, φ2 (b), . . . , φn (b)}

Define a bipartite graph as follows: Let X := {¯ a : a ∈ A1 } and Y := {¯b : b ∈ B1 }. For each j = 1, . . . , n form an edge from a ¯ ∈ X to ¯b ∈ Y if χ(φj (a)) ∈ ¯b. This graph is n-regular

0.2 Tarski’s theorem

11

(Why?). Thus, by K¨onig’s theorem, it has a perfect matching F . For each a ¯ ∈ X, there is ¯b ∈ Y and a unique edge (¯ a, ¯b) ∈ F such that χ(φj (a)) = ψk (b) for some j, k ∈ {1, . . . , n}. For any j, k ∈ {1, . . . , n} define Cj,k := {a ∈ A1 : (¯ a, ¯b) ∈ F and χ(φj (a)) = ψk (b)} and Dj,k := {b ∈ B1 : (¯ a, ¯b) ∈ F and χ(φj (a)) = ψk (b)}. Then ψk−1 ◦ χ ◦ φj maps Cj,k bijectively onto Dj,k as in Exercise 0.1.5(i); in particular Cj,k ∼G∗ Dj,k . Since {Cj,k : j, k = 1, . . . , n} and {Dj,k : j, k = 1, . . . , n} are disjoint partitions of A1 and B1 , respectively, it follows from Exercise 0.1.5(ii) that A1 ∼G∗ B1 , i.e. α = β. u t For the proof of Tarski’s theorem, we will need the following corollary of the cancellation law: Corollary 0.2.8 (AC) Let S be the type semigroup of some group action, and let α ∈ S and n ∈ N be such that (n + 1)α ≤ nα. Then α = 2α. Proof From the hypothesis, we obtain 2α + nα = (n + 1)α + α ≤ nα + α = (n + 1)α ≤ nα. Repeating this argument, we obtain nα ≥ nα + nα = 2nα. Since, trivially, nα ≤ 2nα, we have nα = 2nα = n(2α) by Exercise 0.2.7(i). From Theorem 0.2.7, α = 2α follows. u t In order to complete the proof of Tarski’s theorem, we need one more theorem, for which, in turn, we need the following technical lemma: Lemma 0.2.9 Let S be a commutative semigroup, let S0 ⊂ S be finite, and let  ∈ S0 be such that (n + 1) 6≤ n for n ∈ N, and such that for each α ∈ S there is n ∈ N with α ≤ n. Then there is a function ν : S0 → [0, ∞] with the following properties: (i) ν() = 1; (ii) if α1 , . . . , αn , β1 , . . . , βm ∈ S0 are such that α1 + · · · + αn ≤ β1 + · · · + βm , then n X j=1

ν(αj ) ≤

m X

ν(βj ).

j=1

Proof We proceed by induction on the cardinality of |S0 |. If |S0 | = 1, then S0 = {}. In this case ν() := 1 satisfies (i). To verify (ii) let n, m ∈ N be such that n ≤ m, and assume that n ≥ m + 1. But then (m + 1) ≤ n ≤ m, which contradicts the hypotheses on . Suppose now that that there is α0 ∈ S0 \ {}. By the induction hypothesis, there is a function ν : S0 \ {α0 } → [0, ∞] satisfying (i) and (ii). Since, for any α ∈ S, there is n ∈ N such that α ≤ n, it follows from (ii) that ν attains only finite values. Extend ν to S0 by letting

12

0 Paradoxical decompositions

   p q 1 X  X  ν(α0 ) := inf ν(γj ) − ν(δj ) , r  j=1 j=1 where the infimum is taken over all r ∈ N and γ1 , . . . , γp , δ1 , . . . , δq ∈ S0 \ {α0 } satisfying δ1 + · · · + δq + rα0 ≤ γ1 + · · · + γp . It follows that this infimum is taken over a non-empty set (Why?), and that ν(α0 ) ≥ 0. It remains to be shown that the extended ν still satisfies (ii). Let α1 , . . . , αn , β1 , . . . , βm ∈ S0 \ {α0 } and s, t ∈ N0 be such that α1 + · · · αn + sα0 ≤ β1 + · · · + βm + tα0 .

(0.1)

If s = t = 0, the claim is clear from the induction hypothesis. Case 1: s = 0 and t > 0. We have to show that n X

ν(αj ) ≤ tν(α0 ) +

j=1

m X

ν(βj ).

j=1

i.e.   n m X 1 X ν(αp ) − ν(βj ) =: w. ν(α0 ) ≥ t j=1 j=1 Let r ∈ N and γ1 , . . . , γp , δ1 , . . . , δq ∈ S0 \ {α0 } satisfy δ1 + · · · + δq + rα0 ≤ γ1 + · · · + γp .

(0.2)

It is sufficient to show that 

p X

q X



1 ν(γj ) − ν(δj ) ≥ w. r j=1 j=1

(0.3)

From (0.1) — note that s = 0 — we obtain by multiplication with r and adding the same terms on both sides: rα1 + · · · + rαn + tδ1 + · · · + tδq ≤ rβ1 + · · · + rβm + rtα0 + tδ1 + · · · + tδq . Substituting (0.2) yields: rα1 + · · · + rαn + tδ1 + · · · + tδq ≤ rβ1 + · · · + rβm + tγ1 + · · · + tγp . Applying the induction hypothesis, we obtain r

n X

ν(αj ) + t

j=1

which implies (0.3). Case 2: Suppose that s > 0. It suffices to show that

q X j=1

ν(δj ) ≤ r

m X j=1

ν(βj ) + t

n X j=1

ν(γj ),

0.2 Tarski’s theorem

sν(α0 ) +

n X

ν(αj ) ≤ z1 + · · · + zt +

j=1

m X

13

ν(βj ),

j=1

where z1 , . . . , zt are any of the numbers whose infimum defines ν(α0 ). Without loss of generality, we may suppose that z1 = · · · = zt =: z (Why?). We thus must prove that sν(α0 ) +

n X

ν(αj ) ≤ tz +

j=1

m X

ν(βj ).

j=1

Multiplying (0.1) by r and adding the same terms on both sides yields: rα1 + · · · + rαn + rsα0 + tδ1 + · · · + tδq ≤ rβ1 + · · · + rβm + rtα0 + tδ1 + · · · + tδq . (0.4) Let γ1 , . . . , γp , δ1 , . . . , δq ∈ S0 \ {α0 } satisfy (0.2) with   p q X 1 X z= ν(γj ) − ν(δj ) . r j=1 j=1 Substituting (0.2) into (0.4) yields: rα1 + · · · + rαn + tδ1 + · · · + tδq + rsα0 ≤ rβ1 + · · · + rβm + tγ1 + · · · + tγp . From this inequality and from the definition of ν(α0 ), it follows that   p q n n m n X X X X X X s  ν(αj ) ≤ ν(αj ) + sν(α0 ) + r ν(βj ) + t ν(γj ) − r ν(αj ) − t ν(δj ) sr j=1 j=1 j=1 j=1 j=1 j=1 = tz +

m X

ν(βj ).

j=1

This finishes the proof. u t Theorem 0.2.10 (AC) Let (S, +) be a commutative semigroup with neutral element 0, and let  be an element of S. Then the following are equivalent: (i) (n + 1) 6≤ n for all n ∈ N. (ii) There is a semigroup homomorphism ν : (S, +) → ([0, ∞], +) such that ν() = 1. Proof The implication (ii) =⇒ (i) is easy (Work it out for yourself!). We shall thus focus on the proof of (i) =⇒ (ii). Without loss of generality suppose that, for each α ∈ S, there is n ∈ N such that α ≤ n (otherwise, first disregard those elements α lacking this property, and later define ν(α) := ∞ for all such α). For any finite subset S0 of S containing , let MS0 be the set of all κ : S → [0, ∞] such that – κ() = 1, and – κ(α + β) = κ(α) + κ(β) for α, β, α + β ∈ S0 .

14

0 Paradoxical decompositions

It follows from Lemma 0.2.9 that MS0 6= ∅ (Why?). Let [0, ∞]S be equipped with the product topology. Then it is compact by Tychonoff’s theorem. It is easily seen (but nevertheless check it yourself) that, for each finite subset S0 of S, the set MS0 is closed in [0, ∞]S . It is equally easily seen that the family {MS0 : S0 ⊂ S is finite} T has the finite intersection property. Hence, {MS0 : S0 ⊂ S is finite} contains at least one map ν : S → [0, ∞]. It is clear that ν() = 1, and if α, β ∈ S, then ν(α + β) = ν(α) + ν(β) because ν ∈ M{α,β,α+β} . u t Exercise 0.2.8 One last time: Where in the proof of Theorem 0.2.10 was the axiom of choice used?

We are finally able to complete the proof of Tarski’s theorem: Proof of (the difficult direction of ) Tarski’s theorem Let S be the type semigroup of the action of G on X. Suppose that E is not G-paradoxical. By Exercise 0.2.7(ii), this means that [E] 6= 2[E], and from Corollary 0.2.8 it follows that (n + 1)[E] 6≤ n[E] for all n ∈ N. Hence, Theorem 0.2.10 implies that there is an additive map ν : S → [0, ∞] such that ν([E]) = 1. Then µ : P(X) → [0, ∞],

A 7→ ν([A])

is the desired set function. u tIf X is any set, and µ : P(X) → [0, ∞] is a finitely additive set function with µ(X) < ∞, then we may define m ∈ `∞ (X)∗ through Z hφ, mi := φ(x) dµ(x) (φ ∈ `∞ (X)) X

(for a detailed exposition on integration with respect to not necessarily countably additive set functions, see [D–S, Chapter III]). The following is thus an easy consequence of Tarski’s theorem: Corollary 0.2.11 (AC) For a group G the following are equivalent: (i) G is not paradoxical. (ii) There is a finitely additive set function µ : P(G) → [0, ∞) such that µ(G) = 1 and µ(gE) = µ(E) for all g ∈ G and E ⊂ G. (iii) There is m ∈ `∞ (G)∗ with: (a) h1, mi = kmk = 1; (b) hδg ∗ φ, mi = hφ, mi (g ∈ G, φ ∈ `∞ (G)). Groups satisfying Corollary 0.2.11(iii) are called amenable . . .

0.3 Notes and comments As you might have guessed, the interest in paradoxical decompositions does not go as far back as to biblical times. Nevertheless, their origins can be traced back to the beginnings of modern measure theory.

0.3 Notes and comments

15

As we all know, n-dimensional Lebesgue measure λn is (a) σ-additive, (b) invariant under invertible isometries (Why?), and (c) normalized in the sense that a certain set, [0, 1]n say, is mapped to 1. As we all know as well, λn cannot be extended to all of P(Rn ) in such a way that (a), (b), and (c) remain valid. In [Hau], F. Hausdorff raised the question of whether there was a (a)’ finitely additive set function on P(Rn ) that still satisfied (b) and (c). With the help of his paradox, Hausdorff was able to answer this question in the negative for n ≥ 3. Interestingly, for n = 1, 2, there is a set function on all of P(Rn ) for which (a)’, (b), and (c) still hold ([Ban]). Further investigations in this direction led S. Banach and A. Tarski to the paradox that now carries their name ([B–T]). Tarski’s theorem first saw the light of day in [Tar]. Our exposition is based on [Wag], which is a monograph devoted entirely to paradoxical decompositions; another modern account of the Banach–Tarski paradox is [Stro]. Popular expositions of the Banach–Tarski paradox are [Fre] and [Run 2]. The article [Fre] attempts to be humorous and contains three pictures showing its author (i) with one orange, then (ii) cutting up the orange with a knife into finitely many pieces, and eventually (iii) with two oranges. Why is any attempt to implement the Banach–Tarski paradox using a knife bound to fail? Finally, if you had problems solving Exercise 0.2.2, look it up in [B–M] or [Pat 1].