Back to Search Start Over

Taking out LK parts from a proof in Peano arithmetic

Authors :
Tsuyoshi Yukami
Source :
Journal of Symbolic Logic. 51:682-700
Publication Year :
1986
Publisher :
Cambridge University Press (CUP), 1986.

Abstract

Let PA be Peano arithmetic with function symbols′, + and ·. The length of a proof P, denoted by lh(P), is the maximum length of threads of P (for the term ‘thread’, see [T, p. 14]). For a formula A and a natural number m, PA ⊢mA denotes the fact that there is a proof in PA of A whose length is less than or equal to m. PA ⊢ A denotes the fact that there is a proof in PA of A.G. Kreisel conjectured that the following proposition holds.“Let m be a natural number and A(a) be a formula. If for each natural number n, then PA ⊢ ∀xA(x)”.Let PA1 be the corresponding system with + and · replaced by ternary predicates and axioms saying that these predicates represent functions. Parikh [P] proved the following proposition which is obtained from Kreisel's conjecture by replacing PA by PA1.Proposition. Let A(a) be a formula in PA1and m be a natural number. Assume thatfor each natural number n. Then PA1 ⊢ ∀xA(x).The reason why Parikh's method succeeds is the fact that the only function symbol ′ in PA1 is unary. So his method fails for PA.To solve this conjecture for PA, we must make syntactical investigation into proofs in PA of formulas of the form A() with length ≤ m. Even if lengths of proofs are less than or equal to m, depths of occurrences of bound variables in induction axiom schemata or equality axiom schemata in proofs are not always bounded.

Details

ISSN :
19435886 and 00224812
Volume :
51
Database :
OpenAIRE
Journal :
Journal of Symbolic Logic
Accession number :
edsair.doi...........218c50a885e5e015c81ce4089bc978e1
Full Text :
https://doi.org/10.2307/2274022