[FOM] Eliminability of AC

James Hirschorn James.Hirschorn at univie.ac.at
Mon Mar 31 22:56:38 EDT 2008

joeshipman at aol.com wrote:
> > Can anyone provide examples, particularly
> > arithmetical ones, of theorems outside of logic and set theory which
> > were first proven (or are most easily proven) by showing they follow
> > from V=L and then applying Absoluteness?

On Wednesday 26 March 2008 20:34, Francois G. Dorais replied:
> I'm not aware of any speedup associated with Shoenfield absoluteness. 
> If there is, I would really like to know.

A basic example for absoluteness (but not exactly Schoenfield's absoluteness) 

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 

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

I should think this is much shorter than Luzin's original proof (in 1923, I 
believe) of the above corollary. 

(This obviously does not answer Joe's query, but is rather in the intersection 
of real analysis and descriptive set theory.)

> In any case, I'm pretty sure that you won't find any known arithmetical
> theorem whose "easy proof" requires, e.g., using a morass and Shoenfield
> absoluteness.

I suspect you are mistaken, although I don't have an arithmetical 
counterexample off hand. For the example given in this thread on p-adic 
fields, perhaps the original proof is also the "easy proof"?

James Hirschorn

More information about the FOM mailing list