{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,13]],"date-time":"2026-03-13T19:27:53Z","timestamp":1773430073691,"version":"3.50.1"},"reference-count":17,"publisher":"Cambridge University Press (CUP)","issue":"3","license":[{"start":{"date-parts":[[2014,3,12]],"date-time":"2014-03-12T00:00:00Z","timestamp":1394582400000},"content-version":"unspecified","delay-in-days":7132,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[1994,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>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\u00f6del's claim that there is superrecursive (in fact, unbounded) proof speedup of (<jats:italic>i<\/jats:italic> + l)st-order arithmetic over <jats:italic>i<\/jats:italic>th-order arithmetic, where arithmetic is formalized in Hilbert-style calculi with + and \u2022 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.<\/jats:p><jats:p>Our first proof of G\u00f6del'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.<\/jats:p>","DOI":"10.2307\/2275906","type":"journal-article","created":{"date-parts":[[2006,5,6]],"date-time":"2006-05-06T22:52:43Z","timestamp":1146955963000},"page":"737-756","source":"Crossref","is-referenced-by-count":25,"title":["On G\u00f6del's theorems on lengths of proofs I: Number of lines and speedup for arithmetics"],"prefix":"10.1017","volume":"59","author":[{"given":"Samuel R.","family":"Buss","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S0022481200019496_ref006","first-page":"23\u201324","volume-title":"Ergebnisse eines Mathematischen Kolloquiums","author":"G\u00f6del","year":"1936"},{"key":"S0022481200019496_ref011","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1973-0432416-X"},{"key":"S0022481200019496_ref003","first-page":"366\u2013367","article-title":"Abbreviating proofs by adding new axioms","volume":"77","author":"Ehrenfeucht","year":"1971","journal-title":"Bulletin of the American Mathematical Societyg"},{"key":"S0022481200019496_ref001","unstructured":"Buss S. R. , On G\u00f6dels theorems on lengths of proofs II: Lower bounds for recognizing k symbolprovability, in preparation."},{"key":"S0022481200019496_ref017","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(87)90066-2"},{"key":"S0022481200019496_ref004","volume-title":"A mathematical introduction to logic","author":"Enderton","year":"1972"},{"key":"S0022481200019496_ref008","first-page":"69\u201384","article-title":"The number of proof lines and the size of proofs in first-order logic","volume":"27","author":"Kraj\u00ed\u010dekand","year":"1988","journal-title":"Archive for Mathematical Logic"},{"key":"S0022481200019496_ref009","doi-asserted-by":"publisher","DOI":"10.4064\/fm-42-1-101-110"},{"key":"S0022481200019496_ref002","unstructured":"Buss S. R. , Bounded arithmetic, Bibliopolis, Naples, 1986: revision of Ph.D. Thesis, Princeton University, Princeton, New Jersey, 1985."},{"key":"S0022481200019496_ref012","first-page":"394\u2013397","volume-title":"Kurt G\u00f6del, Collected Works, volume 1","author":"Parikh","year":"1986"},{"key":"S0022481200019496_ref005","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(91)90015-E"},{"key":"S0022481200019496_ref013","first-page":"165\u2013196","volume-title":"Logic Colloquium \u201884","author":"Pudl\u00e1k","year":"1986"},{"key":"S0022481200019496_ref015","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1981-0597664-7"},{"key":"S0022481200019496_ref007","first-page":"153\u2013178","article-title":"On the number of steps in proofs","volume":"41","author":"Kraj\u00ed\u010dek","year":"1989","journal-title":"Annals of Pure and Applied Logic"},{"key":"S0022481200019496_ref010","volume-title":"Sentences undecidable in formalized arithmetic: an exposition of the theory of Kurt G\u00f6del","author":"Mostowski","year":"1952"},{"key":"S0022481200019496_ref016","volume-title":"Proof theory","author":"Takeuti","year":"1987"},{"key":"S0022481200019496_ref014","first-page":"309\u2013331","volume-title":"Logic and Combinatorics, Contemporary Mathematics","volume":"65","author":"Pudl\u00e1k","year":"1987"}],"container-title":["Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200019496","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,15]],"date-time":"2019-05-15T03:16:05Z","timestamp":1557890165000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200019496\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994,9]]},"references-count":17,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1994,9]]}},"alternative-id":["S0022481200019496"],"URL":"https:\/\/doi.org\/10.2307\/2275906","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[1994,9]]}}}