scientific article; zbMATH DE number 432705

From MaRDI portal
Publication:3138832





Whereas much recent work about polymorphism has been to show that it is proof-theoretically powerful, the intention of the author is, in contrast, to construct systems with enough polymorphism to be useful but weak enough proof-theoretically to be tractable. An earlier paper of his [Part I, in Proc. Workshop, Berkeley/CA 1989, Publ. Math. Sci. Res. Inst. 21, 95-127 (1992; Zbl 0754.03018)] focused on the systems \(QL_ 1(\Lambda)\), \(QL_ 1(\lambda)\), \(PL_ 1(\Lambda)\), and \(PL_ 1(\lambda)\), where \(\Lambda\) represents explicit typing, \(\lambda\) implicit typing, \(Q\) quantificational logic, and \(P\) quantifier-free or propositional logic; all of these systems were shown to have the same provably computable functions as Peano Arithmetic. The same paper also included a discussion of the systems \(QL_ 0(\Lambda)\), \(QL_ 0(\lambda)\), \(PL_ 0(\Lambda)\), and \(PL_ 0(\lambda)\), shown to have the same provable functions as primitive recursive arithmetic. The current paper presents the systems \(QL(F_ 0\)-\(IR)\) and \(PL(F_ 0\)- \(IR)\), which are variants of \(QL_ 0(\lambda)\) and \(PL_ 0(\lambda)\) respectively in which the induction axiom for \(\mathbb{N}\) is replaced by the Function-Induction Rule \(t0\):\(T\); \(x\in \mathbb{N}\land tx\):\(T\to tx'\):\(T\) yield \(t: \mathbb{N}\to T\). These systems are shown here also to have the same proof-theoretic strength as primitive recursive arithmetic. In addition, the utility of \(QL(F_ 0\)-\(IR)\) is shown by having some important constructions carried out in it. For the entire collection see [Zbl 0772.00018].











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3138832)