[FOM] Eliminability of AC

[Francois G. Dorais]

James Hirschorn wrote:
> 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. 

Yes. Another neat example is the original proof (using MA) of the 
Baumgartner-Hajnal Partition Theorem vs Galvin's later combinatorial proof.

I believe there may be a general speedup theorem here, but I am not 
aware of any general result of this kind. Again, I would really like to 
know more about this (especially for Shoenfield absoluteness).

>> 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"?

These are CH examples, if I'm not mistaken, which is much simpler than 
V=L as a hypothesis. Formally, any proof of an arithmetical statement 
that makes significant use of V=L has the initial hurdle of decoding the 
statement of V=L. So there is a constant lower bound on the length of a 
V=L proof. It is definitely possible that such an example exists, but I 
suspect that human knowledge has not leaped that far yet...

I still claim that there is no known arithmetical statement whose "easy 
proof" uses a morass (or some other significant chunk of V=L). An 
example of that would be very interesting to see.

-- 
François G. Dorais
Department of Mathematics
Cornell University