A Simple Proof of Parsons' Theorem

Notre Dame Journal of Formal Logic 46 (1):83-91 (2005)
  Copy   BIBTEX

Abstract

Let be the fragment of elementary Peano arithmetic in which induction is restricted to -formulas. More than three decades ago, Parsons showed that the provably total functions of are exactly the primitive recursive functions. In this paper, we observe that Parsons' result is a consequence of Herbrand's theorem concerning the -consequences of universal theories. We give a self-contained proof requiring only basic knowledge of mathematical logic

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 90,616

External links

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

Through your library

Analytics

Added to PP
2010-08-24

Downloads
21 (#630,965)

6 months
2 (#668,348)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Citations of this work

Finitary Set Theory.Laurence Kirby - 2009 - Notre Dame Journal of Formal Logic 50 (3):227-244.
Elementary Proof of Strong Normalization for Atomic F.Fernando Ferreira & Gilda Ferreira - 2016 - Bulletin of the Section of Logic 45 (1):1-15.
Harrington’s conservation theorem redone.Fernando Ferreira & Gilda Ferreira - 2008 - Archive for Mathematical Logic 47 (2):91-100.

Add more citations

References found in this work

Finitism.W. W. Tait - 1981 - Journal of Philosophy 78 (9):524-546.
Fragments of arithmetic.Wilfried Sieg - 1985 - Annals of Pure and Applied Logic 28 (1):33-71.
Bounded arithmetic and the polynomial hierarchy.Jan Krajíček, Pavel Pudlák & Gaisi Takeuti - 1991 - Annals of Pure and Applied Logic 52 (1-2):143-153.
On n-quantifier induction.Charles Parsons - 1972 - Journal of Symbolic Logic 37 (3):466-482.
On 퐧-Quantifier Induction.Charles Parsons - 1972 - Journal of Symbolic Logic 37 (3):466 - 482.

View all 9 references / Add more references