home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / sci / logic / 2657 < prev    next >
Encoding:
Text File  |  1993-01-28  |  1.5 KB  |  36 lines
  1. Newsgroups: sci.logic
  2. Path: sparky!uunet!charon.amdahl.com!pacbell.com!ames!sun-barr!cs.utexas.edu!zaphod.mps.ohio-state.edu!magnus.acs.ohio-state.edu!wjcastre
  3. From: wjcastre@magnus.acs.ohio-state.edu (W.Jose Castrellon G.)
  4. Subject: Re: Proof Theory reference needed
  5. Message-ID: <1993Jan28.045042.10630@magnus.acs.ohio-state.edu>
  6. Sender: news@magnus.acs.ohio-state.edu
  7. Nntp-Posting-Host: top.magnus.acs.ohio-state.edu
  8. Organization: The Ohio State University,Math.Dept.(studnt)
  9. References: <1k5n2rEINNruv@uni-erlangen.de>
  10. Date: Thu, 28 Jan 1993 04:50:42 GMT
  11. Lines: 23
  12.  
  13. In article <1k5n2rEINNruv@uni-erlangen.de> 
  14. jnjohann@immd1.informatik.uni-erlangen.de (Jan Johannsen) writes:
  15.  
  16. >
  17. >The following seems to be a folklore result in Proof Theory:
  18. >
  19. >Let PA be (first-order) Peano Arithmetic, and let G be the set of all
  20. >Pi_1-sentences  true in the standard model N. 
  21. >Then PA and PA + G have the same set of provably recursive functions.
  22. >
  23. >Could someone please give me a hint where to find a proof of this
  24. >fact ?
  25. >
  26. >Thanks    Jan
  27. >
  28.  
  29. You might want to try the book by Joram Hirschfeld and William Wheeler
  30. on theory of models and arithmetic in the Springer series; even if the proof
  31. is not there, chances are you'll find the section on aritmetic is quite 
  32. interesting; the whole book contains many applications. [both were students 
  33. under Abraham Robinson...].
  34. Also, it might be in the De Millo & Lipton paper, where they prove the  
  35. independence of the P<NP conjecture from certain axiomatic systems.
  36.