scientific article; zbMATH DE number 432705
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].
- scientific article; zbMATH DE number 65743
- scientific article; zbMATH DE number 194511
- A finitary subsystem of the polymorphic -calculus
- On the proof theory of type two functionals based on primitive recursive operations
- Intrinsic reasoning about functional programs. II: Unipolar induction and primitive-recursion
- Formalizing non-termination of recursive programs
- Theories with self-application and computational complexity.
- Axioms for strict and lazy functional programs
- Intrinsic reasoning about functional programs. II: Unipolar induction and primitive-recursion
- A note on the \(\Pi_ 2^ 0\)-induction rule
- A flexible type system for the small Veblen ordinal
- A finitary subsystem of the polymorphic -calculus
- scientific article; zbMATH DE number 65743 (Why is no real title available?)
- Proof-theoretic notions for software maintenance
- Tiered arithmetics
- On the proof theory of type two functionals based on primitive recursive operations
- Explicit mathematics: power types and overloading
- scientific article; zbMATH DE number 6606377 (Why is no real title available?)
- Intrinsic reasoning about functional programs. I: First order theories
- Term rewriting theory for the primitive recursive functions
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)