Article View: sci.logic
Article #625Proof Theory reference needed
From: Jan Johannsen
Date: Wed, 27 Jan 1993 10:10
Date: Wed, 27 Jan 1993 10:10
26 lines
1660 bytes
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
--------------------------------------------------------------------------------
Technical Details
Message-ID:
<1k5n2rEINNruv@uni-erlangen.de>Path:
arc1-ca.pugleaf.net!sparky!uunet!math.fu-berlin.de!fauern!uni-erlangen.de!immd1.informatik.uni-erlangen.de!jnjohannShow Full Headers
Complete Article Headers
Path: arc1-ca.pugleaf.net!sparky!uunet!math.fu-berlin.de!fauern!uni-erlangen.de!immd1.informatik.uni-erlangen.de!jnjohann From: jnjohann@immd1.informatik.uni-erlangen.de (Jan Johannsen) Newsgroups: sci.logic Subject: Proof Theory reference needed Date: Wed, 27 Jan 1993 10:10:35 GMT Organization: CSD., University of Erlangen Message-ID: <1k5n2rEINNruv@uni-erlangen.de> NNTP-Posting-Host: faui1k.informatik.uni-erlangen.de Lines: 26