Article View: sci.logic
Article #634Re: Proof Theory reference needed
From: W.Jose Castrellon G.
Date: Thu, 28 Jan 1993 04:50
Date: Thu, 28 Jan 1993 04:50
23 lines
1534 bytes
1534 bytes
In article <1k5n2rEINNruv@uni-erlangen.de> jnjohann@immd1.informatik.uni-erlangen.de (Jan Johannsen) writes: > >The following seems to be a folklore result in Proof Theory: > >Let PA be (first-order) Peano Arithmetic, and let G be the set of all >Pi_1-sentences true in the standard model N. >Then PA and PA + G have the same set of provably recursive functions. > >Could someone please give me a hint where to find a proof of this >fact ? > >Thanks Jan > You might want to try the book by Joram Hirschfeld and William Wheeler on theory of models and arithmetic in the Springer series; even if the proof is not there, chances are you'll find the section on aritmetic is quite interesting; the whole book contains many applications. [both were students under Abraham Robinson...]. Also, it might be in the De Millo & Lipton paper, where they prove the independence of the P<NP conjecture from certain axiomatic systems.
Technical Details
Message-ID:
<1993Jan28.045042.10630@magnus.acs.ohio-state.edu>Path:
arc1-ca.pugleaf.net!sparky!uunet!charon.amdahl.com!pacbell.com!ames!sun-barr!cs.utexas.edu!zaphod.mps.ohio-state.edu!magnus.acs.ohio-state.edu!wjcastreReferences:
<1k5n2rEINNruv@uni-erlangen.de>Show Full Headers
Complete Article Headers
Newsgroups: sci.logic Path: arc1-ca.pugleaf.net!sparky!uunet!charon.amdahl.com!pacbell.com!ames!sun-barr!cs.utexas.edu!zaphod.mps.ohio-state.edu!magnus.acs.ohio-state.edu!wjcastre From: wjcastre@magnus.acs.ohio-state.edu (W.Jose Castrellon G.) Subject: Re: Proof Theory reference needed Message-ID: <1993Jan28.045042.10630@magnus.acs.ohio-state.edu> Sender: news@magnus.acs.ohio-state.edu Nntp-Posting-Host: top.magnus.acs.ohio-state.edu Organization: The Ohio State University,Math.Dept.(studnt) References: <1k5n2rEINNruv@uni-erlangen.de> Date: Thu, 28 Jan 1993 04:50:42 GMT Lines: 23