# [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)
is:

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

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
```