[FOM] Status of AC

joeshipman@aol.com joeshipman at aol.com
Thu Mar 2 14:15:57 EST 2006


Friedman:

>Every Pi^1_4 sentence provable in ZFC is provable in ZF.

Solovay:

>If a Sigma^1_3 sentence follows from V=L it is a theorem of ZFC. This 
is best possible since "Every real
>is constructible" is Pi^1_3.


How do you show that choice is eliminable from proofs of Pi^1_4 
sentences? And how much of an expansion in proof length is involved in 
the elimination procedure?

It is remarkable how useful Choice is, considering how much of 
mathematics can be coded into sentences of type Pi^1_4 or lower. There 
are plenty of theorems which cannot be coded into second-order 
arithmetic at all; but can anyone identify a well-known theorem or open 
problem which CAN be coded into second-order arithmetic but not into a 
Pi^1_4 sentence?

Harvey's example is VERY far from what I would call a "well-known 
theorem". I would hazard a guess that the Sigma^1_4 sentence he 
describes (which is provable in ZFC but not in ZF) cannot actually be 
formalized in second-order-arithmetic in fewer than 10,000 symbols (I'm 
talking about the length of the sentence, not of its proof!).

-- JS


More information about the FOM mailing list