Proof Theory reference needed

Thread View: sci.logic

2 messages

[T] Back to Threads [V] Tree View [G] Group Articles

2 total messages Started by Jan Johannsen Wed, 27 Jan 1993 10:10

#625

Author: Jan Johannsen
Date: Wed, 27 Jan 1993 10:10

26 lines
1660 bytes

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

---
--------------------------------------------------------------------------------
"[Die Mathematik] steht ja "uber allem. Die Werke von Abel oder Kronecker sind
 heute genauso gut wie vor vierhundert Jahren, und so wird es immer sein.
 Es entstehen wohl neue Wege, doch die alten f"uhren weiter. Sie schliessen
 sich nicht. Dort ... dort ist die Ewigkeit. Nur die Mathematik hat keine
 Angst vor ihr."
                   Stanislaw Lem, "Transfer"
--------------------------------------------------------------------------------
               Jan Johannsen, Universit"at Erlangen, IMMD 1 
                Martensstrasse 3, D-8520 Erlangen, Germany   
                          Tel.:  49-9131-857688                         
               Email:  johannsen@informatik.uni-erlangen.de  
--------------------------------------------------------------------------------

Re: Proof Theory reference needed

#634

Author: W.Jose Castrellon G.
Date: Thu, 28 Jan 1993 04:50

23 lines
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.

Thread Navigation

This is a paginated view of messages in the thread with full content displayed inline.

Messages are displayed in chronological order, with the original post highlighted in green.

Use pagination controls to navigate through all messages in large threads.

Back to All Threads