Degrees of Relative Provability

Notre Dame Journal of Formal Logic 53 (4):479-489 (2012)
  Copy   BIBTEX

Abstract

There are many classical connections between the proof-theoretic strength of systems of arithmetic and the provable totality of recursive functions. In this paper we study the provability strength of the totality of recursive functions by investigating the degree structure induced by the relative provability order of recursive algorithms. We prove several results about this proof-theoretic degree structure using recursion-theoretic techniques such as diagonalization and the Recursion Theorem

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 91,069

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Accessible recursive functions.Stanley S. Wainer - 1999 - Bulletin of Symbolic Logic 5 (3):367-388.
Recursive analysis.R. L. Goodstein - 1961 - Mineola, N.Y.: Dover Publications.
Weak Presentations of Computable Fields.Carl G. Jockusch & Alexandra Shlapentokh - 1995 - Journal of Symbolic Logic 60 (1):199 - 208.
Degrees joining to 0'. [REVIEW]David B. Posner & Robert W. Robinson - 1981 - Journal of Symbolic Logic 46 (4):714 - 722.
Generalized weak presentations.Alexandra Shlapentokh - 2002 - Journal of Symbolic Logic 67 (2):787-819.
Some restrictions on simple fixed points of the integers.G. L. McColm - 1989 - Journal of Symbolic Logic 54 (4):1324-1345.
On first-order theories with provability operator.Sergei Artëmov & Franco Montagna - 1994 - Journal of Symbolic Logic 59 (4):1139-1153.

Analytics

Added to PP
2012-11-09

Downloads
38 (#372,920)

6 months
1 (#1,087,801)

Historical graph of downloads
How can I increase my downloads?

References found in this work

A jump operator on honest subrecursive degrees.Lars Kristiansen - 1998 - Archive for Mathematical Logic 37 (2):105-125.
An Introduction to Proof Theory.Samuel R. Buss - 2000 - Bulletin of Symbolic Logic 6 (4):464-465.
Subsystems of Set Theory and Second-Order Number Theory.Wolfram Pohlers - 2000 - Bulletin of Symbolic Logic 6 (4):467-469.

View all 7 references / Add more references