[FOM] Eliminability of AC

[James Hirschorn]

On Monday 31 March 2008 22:56, I wrote:
> Theorem. Every Delta-1-2 set of reals is Lebesgue measurable.
>
> Corollary. All analytic sets (i.e. Souslin sets, A-sets, Sigma-1-1) are
> measurable.
>
> Metamathematical proof (for those not already familiar). Suppose A = {x in
> R: phi(x,a)}, where phi is Delta-1-2, a in R and R denotes the real line.
> Let X be a G_delta set of reals whose equivalence class [X] in the measure
> algebra of Lebesgue measure is equal to ||phi(dot r,a)||, where dot r is a
> name for the random real. Then mu((A-X) U (X-A))=0, i.e. the set difference
> is null, proving that A is measurable.
>
> To see that the difference is null, supposing to the contrary that, say,
> B = A-X has positive outer measure, there exists a random real r in B over
> some countable elementary model M with a,A,X in M. Then N[r] |= phi(r,a) by
> the absoluteness of analytic (i.e. Sigma-1-1) relations between transitive
> models of enough of ZFC (note this differs slightly from Schoenfield's
> absoluteness), where N denotes the transitive collapse of M. This
> contradicts the fact that M |= R-X forces ~phi(dot r,a). Similarly, if r in
> X-A is random over N, then N[r] |= ~phi(r,a) by absoluteness, contradicting
> that X forces phi(dot r,a). QED
>
Bob Solovay pointed out that the above "Theorem" is false because of 
Godel's Delta-1-2 ordering of the reals in L. 

In the above proof I invoked Sigma-1-1 absoluteness with phi. Hence the proof 
only works for the Corollary, but not the "Theorem".

He also mentioned his result that all _provably_ Delta-1-2 sets are 
measurable. Even better: Let B denote the measure algebra above. 
Call a set A of reals _absolutely Delta-1-2 for V^B_ if there is a real 
parameter a and Sigma-1-2 predicates phi and psi such that 
(1) A = {x in R:phi(x,a)},
(2) phi and psi complement each other at a, in the forcing extension V^B.
    I.e. V^B |= phi(x,a) <-> ~psi(x,a) for all x in R. 
(Note that phi and psi also complement each other at a, in the ground model V, 
by Schoenfield's absoluteness.)

Theorem (Solovay). Every set of reals absolutely Delta-1-2 for V^B is 
measurable.

The above proof applies:

If phi(r,a) holds, then so does ~psi(r,a) because they are complements in V.
Hence N[r] |= ~psi(r,a), because Sigma-1-1 absoluteness generalizes to 
downwards Pi-1-2 absoluteness. Thus N[r] |= phi(r,a) 
because phi complements psi in N[r] by the elementarity of M.

And if ~phi(r,a) holds, then N[r] |= ~phi(r,a) by downwards Pi-1-2 
absoluteness. 

James Hirschorn