Multi-Page Printing

48 1. Logic and foundations E described above, one would almost surely get that E has measure 1, as each random number is almost certain to lie in a different coset of Q!. 1.12.4. The Banach-Tarski paradox. We now turn to the Banach-Tarski paradox. The usual formulation of this paradox involves a partition of the unit ball into pieces that can be rearranged (after rotations and transla- tions) to form two copies of the ball. To avoid some minor technicalities, we will work instead on the unit sphere S2 with an explicit countable set Σ removed, and establish the following version of the paradox: Proposition 1.12.6 (Banach-Tarski paradox, reduced version). There ex- ists a countable subset Σ of S2 and partition of S2\Σ into four disjoint pieces E1 ∪ E2 ∪ E3 ∪ E4, such that E1 and E2 can be rotated to cover S2\Σ, and E3 and E4 can also be rotated to cover S2\Σ. Of course, from the rotation-invariant nature of Lebesgue measure on the sphere, such a partition can only occur if at least one of E1,E2,E3,E4 are not Lebesgue measurable. We return briefly to set theory and give the standard proof of this propo- sition. The first step is to locate two rotations a,b in the orthogonal group SO(3) which generate the free group a,b . This can be done explicitly for instance, one can take a := ⎛ ⎝−4/5 3/5 4/5 0 3/5 0⎠ 0 0 1 ⎞ b := ⎛ ⎝0 1 0 0 3/5 −4/5⎠ 0 4/5 3/5 ⎞ . See [Ta2010, §2.2] for a verification (using the ping-pong lemma) that a,b do indeed generate the free group. Each rotation in a,b has two fixed antipodal points in S2 we let Σ be the union of all these points. Then the group a,b acts freely on the remainder S2\Σ. Using the axiom of choice, we can then build a (non-measurable) subset E of S2\Σ which consists of a single point from each orbit of a,b . For each i = 1,2,3,4, we then define Ei to be the set of all points of the form wx, where x ∈ E and w ∈ a,b is a word such that • w is the identity, or begins with a (if i = 1) • w begins with a−1 (if i = 2) • w begins with b (if i = 3) • w begins with b−1 (if i = 4). It is then clear that E1,E2,E3,E4 partition S2\Σ, while a−1E1 ∪ aE2 and b−1E3 ∪ bE4 both cover S2\Σ, as claimed. Now let us interpret this example using oracles. The free group a,b is countably enumerable, and so with a countable amount of time and memory,