×

Some lambda calculus and type theory formalized. (English) Zbl 0940.03019

Summary: We survey a substantial body of knowledge about lambda calculus and Pure Type Systems, formally developed in a constructive type theory using the LEGO proof system. On lambda calculus, we work up to an abstract, simplified proof of standardization for beta reduction that does not mention redex positions or residuals. Then we outline the metatheory of Pure Type Systems, leading to the strengthening lemma. One novelty is our use of named variables for the formalization. Along the way we point out what we feel has been learned about general issues of formalizing mathematics, emphasizing the search for formal definitions that are convenient for formal proof and convincingly represent the intended informal concepts.

MSC:

03B40 Combinatory logic and lambda calculus
03B35 Mechanization of proofs and logical operations
68T15 Theorem proving (deduction, resolution, etc.) (MSC2010)

Software:

LEGO; Automath; Coq
PDFBibTeX XMLCite
Full Text: DOI