Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 
 

 

Some results on the length of proofs


Author: R. J. Parikh
Journal: Trans. Amer. Math. Soc. 177 (1973), 29-36
MSC: Primary 02D99
DOI: https://doi.org/10.1090/S0002-9947-1973-0432416-X
MathSciNet review: 0432416
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Given a theory T, let $ \vdash _T^kA$ mean ``A has a proof in T of at most k lines". We consider a formulation $ P{A^\ast}$ of Peano arithmetic with full induction but addition and multiplication being ternary relations. We show that $ { \vdash ^k}A$ is decidable for $ P{A^\ast}$ and hence $ P{A^\ast}$ is closed under a weak $ \omega $-rule. An analogue of Gödel's theorem on the length of proofs is an easy corollary.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC: 02D99

Retrieve articles in all journals with MSC: 02D99


Additional Information

DOI: https://doi.org/10.1090/S0002-9947-1973-0432416-X
Keywords: Peano arithmetic, length of proofs, Presburger arithmetic
Article copyright: © Copyright 1973 American Mathematical Society

American Mathematical Society