[FOM] Sigma-1 Completeness
Robert M. Solovay
solovay at Math.Berkeley.EDU
Sat Aug 4 04:23:46 EDT 2007
Richard,
There seems no trouble proving the strong form of Sigma_1
completeness in IDelta_0 + Exp. (I interpet Sigma_0 as being given by a
limited formula and not by a primitive recursive one.)
The question as to whether one can prove Sigma_1 completeness in
IDelta_0 + Omega_1 seems difficult. Even expressing truth of Delta_0
formulas by a formula in the Polytime hierarchy seems unlikely since one
suspects PSpace is not in this hierarchy. [Of course proving this
suspicion involves settling open problems in computer science that seem as
difficult as the P =? NP question.] I see no way to **prove** that Sigma_1
completeness [however this is reasonably made precise] can not be carried
out in IDelta_0 + Omega_1.
--Bob Solovay
On Fri, 3 Aug 2007, Richard Heck wrote:
>
> Q, and even PA, is \Sigma_1 complete. My question concerns what theories
> know about their own \Sigma_1 completeness. We can distinguish two
> versions of this question:
> (i) A theory T might be able to show, for EACH \Sigma_1 sentence A,
> that, if A, then T proves A.
> (ii) A theory T might be able to show that, for EVERY \Sigma_1 sentence
> A, if A, then T proves A.
> What is the weakest theory T with each property---if such there is?
>
> I'm sure this is well-known to many of you, but I can't seem to find the
> answer. I'm guessing that maybe the answer to (ii) is I\Sigma_1.
>
> Richard
>
> --
> ==================================================================
> Richard G Heck, Jr
> Professor of Philosophy
> Brown University
> http://frege.brown.edu/heck/
> ==================================================================
> Get my public key from http://sks.keyserver.penguin.de
> Hash: 0x1DE91F1E66FFBDEC
> Learn how to sign your email using Thunderbird and GnuPG at:
> http://dudu.dyn.2-h.org/nist/gpg-enigmail-howto
>
> _______________________________________________
> FOM mailing list
> FOM at cs.nyu.edu
> http://www.cs.nyu.edu/mailman/listinfo/fom
>
More information about the FOM
mailing list