On the length of proofs in formal systems

DOI10.21099/tkbjm/1496158798zbMath0493.03034OpenAlexW2290178991MaRDI QIDQ1168322

Tohru Miyatake

Publication date: 1980

Published in: Tsukuba Journal of Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.21099/tkbjm/1496158798

zbMATH Keywords

Peano arithmeticPresburger arithmeticlength of proofGentzen methodfirst order formal system

Mathematics Subject Classification ID

First-order arithmetic and fragments (03F30) Complexity of proofs (03F20)

Related Items

VARIANTS OF KREISEL’S CONJECTURE ON A NEW NOTION OF PROVABILITY, The lengths of proofs: Kreisel's conjecture and Gödel's speed-up theorem, The Kreisel length-of-proof problem, The number of proof lines and the size of proofs in first order logic, A theorem on generalizations of proofs, On the number of steps in proofs, The undecidability of \(k\)-provability, \(k\)-provability in \(\mathrm{PA}\), Bounded arithmetic, proof complexity and two papers of Parikh