The primitive proof theory of the lambda-calculus
René Vestergaard · 2003
We consider formal provability with structural induction and related proof principles in the λ-calculus seen as a (functional) programming language, i.e., presented with first-order abstract syntax over one-sorted variable names. Structural induction is the principal primitive proof principle of that particular syntactic framework and it is, indeed, near-ubiquitously employed in informal proofs in the wider programming-language theory community. In spite of substantial efforts in the theorem-proving community, these informal proofs have unfortunately been neither formalised nor considered formalisable so far. This impasse must naturally raise uncomfortable questions about the formal validity of the proof principles. The highlights of the results we establish formally by structural means are the relative renaming freeness of β-residual theory, decidability of αequivalence, β-confluence, η-confluence, βη-confluence, β residual completion (aka strong weakly-finite β-development), residual β-confluence, η-overβ postponement, and notably β-standardisation. Interestingly, our uniform proof methodology, which has relevance beyond the λ-calculus, properly contains pen-and-paper proof practices in a precise sense except for the cases of α-decidability and β-standardisation where the known proofs fail in instructive ways. Our notion of residual completion, furthermore, presents a simplified treatment of residual theory compared to established practice, be it for strong finite development or for Huet’s Prism theorem/Levy’s Cube lemma. Overall, our approach makes precise what is the full algebraic proof burden of the considered results and our proofs, in fact, appear to be the first complete developments in the literature. Our results are relevant for researchers in programming language theory, rewriting, proof theory, and mechanised theorem proving/automated reasoning.