On gödel's theorems on lengths of proofs I: Number of lines and speedup for arithmetics

Journal of Symbolic Logic 59 (3):737-756 (1994)
  Copy   BIBTEX

Abstract

This paper discusses lower bounds for proof length, especially as measured by number of steps (inferences). We give the first publicly known proof of Gödel's claim that there is superrecursive (in fact. unbounded) proof speedup of (i + 1)st-order arithmetic over ith-order arithmetic, where arithmetic is formalized in Hilbert-style calculi with + and · as function symbols or with the language of PRA. The same results are established for any weakly schematic formalization of higher-order logic: this allows all tautologies as axioms and allows all generalizations of axioms as axioms. Our first proof of Gödel's claim is based on self-referential sentences: we give a second proof that avoids the use of self-reference based loosely on a method of Statman

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 76,400

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

Analytics

Added to PP
2009-01-28

Downloads
60 (#200,004)

6 months
1 (#452,962)

Historical graph of downloads
How can I increase my downloads?

References found in this work

Proof Theory.Gaisi Takeuti - 1990 - Studia Logica 49 (1):160-161.
On the scheme of induction for bounded arithmetic formulas.A. J. Wilkie & J. B. Paris - 1987 - Annals of Pure and Applied Logic 35 (C):261-302.
On me number of steps in proofs.Jan Krajíèek - 1989 - Annals of Pure and Applied Logic 41 (2):153-178.
Sentences Undecidable in Formalized Arithmetic: An Exposition of the Theory of Kurt Gödel.A. Mostowski - 1953 - British Journal for the Philosophy of Science 3 (12):364-374.

View all 7 references / Add more references