Journal article:

    Samuel R. Buss.
    "On Gödel's theorems on lengths of proofs I: Number of lines and speedups for arithmetic."
    Journal of Symbolic Logic 39 (1994) 737-756.

    Download article: postscript or PDF

    Related talk

    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 $i$-th order arithmetic, where arithmetic is formalized in Hilbert-style calculi with $+$ and $\cdot$ 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's.

Back to Sam Buss's publications page.