[FOM] question about the complexity of a sentence

[Robert Solovay]

The sentence SPHERE has precisely the complexity Pi^1_4. There are two
points to verify:

1) There is a Pi^1_4 sentence, Phi, which is provably equivalent to
SPHERE in ZFC.

The sentence Phi will have the form (forall z) S(z). Here z encodes a
putative Banach-Tarski decomposition of the solid unit ball in R^3.
S(z) asserts that z does not, in fact, encode a Banach-Tarski
decomposition.

(I am assuming that the word sphere in the proposition in question
refers to the solid ball in R^3. The discussion would be similar if
the phrase "sphere" referred to the surface of this ball. I believe
that if the dimension is <= 2, the analogue of SPHERE is simply a
theorem of ZFC.)

The encoding goes as follows. Unpack z into a countable sequence of
reals <z_i: i in omega> in the usual way. Let n = z_0(0). Interpret
z_1, ..., z_n as codes for Sigma^1_2 sets A_1, ..., A_n. Interpret
z_{n+1}, .., z_{2n} as codes for elements of the group of isometries
of R^3, sigma_1, ..., sigma_n.

This data gives a Banach-Tarski counterexample if:

     1) A_1 \cup .... \cup A_n is equal to the unit ball with center
the origin and radius 1.

     2) Let B_i = sigma_i[A_i]. Then B_1 \cup ... \cup B_n has union
equal to the union of the two solid balls of radius 1  with centers
(0,0,0) and (2,2,2).

We have to see "z does not encode a Banach-Tarski counterexample" is
Sigma^1_3. Equivalently, one has to see "z does code a B-T
counterexample" is Pi^1_3.

The treatment of the two clauses is entirely analogous. We discuss 1):
What gives the complexity is saying: "For every real x, if x is in the
solid ball, then for some k, x is in A_k. This is Pi^1_3. The other
conditions are easily seen to be Pi^1_2.

The other point we need to establish is that for no Sigma^1_4 sentence
Psi does ZFC prove that Psi is equivalent to SPHERE.

Obviously we need some soundness assumption on ZFC to establish this.
(If ZFC is inconsistent, it proves everythig including the equivalence
whose proof we are trying to block.)

I will prove this claim under the assumption that ZFC has a countable
transitive model (and give the proof in the metatheory ZFC). In the
usual way, our assumption can be weakend to just Con(ZF) and the
metatheory can be weakened to primitive recursive arithmetic.

So assume, towards a contradiction, that (for some fixed Sigma^1_4
sentence Psi) ZFC proves the equivalence of Psi and SPHERE.

Let M be a countable transitive model of ZFC, By standard arguments,
we can choose M so that it is a model of Martin's Axiom + "not CH".

Under these assumptions, M also satisfies the following:

(a) The union of aleph_1 sets of Lebesgue measure zerois Lebesgue
measurable (and again has measure zero).

(b) Every Sigma^1_2 (boldface) set of reals is Lebesgue measurable.

(c) SPHERE

    (a) is definitely in my joint paper with Martin on Martin's Axiom
(entitled "Internal Cohen Extensions). (b) follows easily from (a). I
don't recall whether or not it appears in our paper. (c), of course,
follows immediately from (b).

Let Psi have the form (exists z) S(z) where S is Pi^1_3. Our
assumptions imply that for some real z_0 of M, S(z_0) holds in M. Let
N be L[z_0] as computed in M. It follows immediately from Shoenfield
absoluteness that S(z_0) holds in N. Hence Psi holds in N.

But N models ZFC, and by assumption ZFC proves Psi equivalent to
SPHERE. So N models SPHERE.

To get our sought for contradiction we just invoke the following Lemma.

Lemma: Assume that V = L[z] for some real z. Then SPHERE is false.

I close this posting with some comments on the proof of this lemma.

The proof is quite analogous to the proof of the result of Godel that if
V = L then there is a Delta^1_2 non Lebesgue measurable set.

(a) One follows the usual proof of the Banach-Tarski theorem. (I
personally found the treatment of the proof in Francis Edward Su's
minor thesis quite useful and I will refer to it in what follows. It's
available on the web at http://www.math.hmc.edu/~su/papers.html).

No doubt Wagon's book on Banach-Tarski is an equally good reference.
(Indeed Su cites Wagon as his source.)

(b) A standard tool in Banach-Tarski theory is that
G-equidecomposability is an equivalence relation. (Cf. definition 2 of
Su, loc. cit.) We need the slight refinement where we require the
pieces in the decomposition all to be boldface Delta^1_2. This revised
notion of equidecomposability (where the group G is taken to be the
group of isometries of R^3) is easily seen to be an equivalence
relation by the same proof as before.

(c) The only other point (as in the Godel proof mentioned) is to make
choices using the canonical well-ordering of the reals of L[z]. If we
do this, then the paradoxical decomposition of the sphere constructed
by the usual Banach-Tarski proof is easily checked to consist of
(boldface) Delta^1_2 sets. Hence SPHERE fails in the model L[z].

--Bob Solovay











On Sun, Jun 20, 2010 at 8:39 PM, Rupert McCallum
<Rupert.McCallum at acu.edu.au> wrote:
> In his thesis "The Search for New Axioms" Peter Koellner asserts that the following statement
>
> SPHERE. One cannot take a sphere apart into finitely many boldface Sigma^1_2 pieces, and rearrange them using rigid motons to form a sphere twice the size of the original
>
> is a Sigma^1_3 sentence. I am having trouble seeing this. Can anyone explain to me why it is so?
>
> Dr Rupert McCallum
> Lecturer in Mathematics
> (02) 9701 4050
>
>
> _______________________________________________
> FOM mailing list
> FOM at cs.nyu.edu
> http://www.cs.nyu.edu/mailman/listinfo/fom
>