×

Elementary descent recursion and proof theory. (English) Zbl 0821.03027

As the authors say in the introduction, much of the results of this paper will look familiar to proof theorists. They include basic properties of functions and functionals defined by transfinite recursion, connection of Grzegorczyk and Hardy hierarchies and ordinal estimates for provably recursive functions and well-orderings of the systems with some forms of mathematical and transfinite induction. The emphasis is on detailed and careful proofs, and some refinements, like construction of a primitive recursive cut-elimination operator, are sacrificed.
Reviewer: G.Mints (Stanford)

MSC:

03F03 Proof theory in general (including proof-theoretic semantics)
03F30 First-order arithmetic and fragments
03F15 Recursive ordinals and ordinal notations
03D20 Recursive functions and relations, subrecursive hierarchies
Full Text: DOI

References:

[1] Hardy, G. H., A theorem concerning the infinite cardinal numbers, Quart. J. Math., 35, 87-94 (1904) · JFM 34.0077.02
[2] Mints, G., Finite investigations of infinite derivations, J. Soviet Math., 10, 548-596 (1978) · Zbl 0399.03044
[3] Monk, J. D., Mathematical Logic, (Graduate Texts in Mathematics, Vol. 37 (1976), Springer: Springer Berlin) · Zbl 0354.02002
[4] Parsons, C., On \(n\)-quantifier induction, J. Symbolic Logic, 37, 466-482 (1972) · Zbl 0264.02027
[5] Rose, H. E., Subrecursion: functions and hierarchies, (Oxford Logic Guides, Vol. 9 (1984), Oxford University Press: Oxford University Press Oxford) · Zbl 0539.03018
[6] Schütte, K., Proof Theory (1977), Springer: Springer Berlin · Zbl 0367.02012
[7] Smith, R. L., The consistency of some finite forms of the Higman and Kruskal theories, (Harrington, L. A.; etal., Harvey Friedman’s Research on the Foundations of Mathematics (1985), North-Holland: North-Holland Amsterdam)
[8] Tait, W. W., Normal derivability in classical logic, (Barwise, J., The Syntax and Semantics of Infinity Languages. The Syntax and Semantics of Infinity Languages, Lecture Notes in Math., 72 (1968), Springer: Springer Berlin), 204-236 · Zbl 0206.00502
[9] Takeuti, G., Proof theory (1975), North-Holland: North-Holland Amsterdam · Zbl 0354.02027
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.