Abstract

The Curry-Howard correspondence equates propositions with types and derivations with lambda-terms. The lambda-calculus does not immediately provide terms to correspond to incomplete derivations—- derivations containing “holes”. Solutions include lambda-lifting; I will show how a suitable notion of typed nominal term can also represent incomplete terms and give a nice Curry-Howard correspondence which very precisely matches what we do when we fill in a proof on a piece of paper. The typing system is quite sophisticated, corresponding with first-order logic.

• Types correspond with first-order logic predicates.
• Terms correspond with incomplete proofs.
• Level 1 variables (atoms) correspond with assumptions; types of the variables correspond with predicates assumed.
• Level 2 variables (unknowns) correspond with unknown parts of the derivation.
• A notion of beta-reduction for level 1 variables corresponds with proof-normalisation.
• Instantiation of level 2 variables corresponds with filling in more of the derivation.

Full details are in my conference paper with Mulligan and more information, including slides of the talk (before the talk, if I’m really efficient) can be found on my homepage.