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,

Purchased from American Mathematical Society for the exclusive use of nofirst nolast (email unknown) Copyright 2013 American Mathematical Society. Duplication prohibited. Please report unauthorized use to cust-serv@ams.org. Thank You! Your purchase supports the AMS' mission, programs, and services for the mathematical community.