Skip to main content

Proof pearl: de bruijn terms really do work


Michael Norrish and René Vestergaard




Placing our result in a web of related mechanised results, we give a direct proof that the de Bruijn λ-calculus (à la Huet, Nipkow and Shankar) is isomorphic to an α-quotiented λ-calculus. In order to establish the link, we introduce an “index-carrying” abstraction mechanism over de Bruijn terms, and consider it alongside a simplified substitution mechanism. Relating the new notions to those of the α-quotiented and the proper de Bruijn formalisms draws on techniques from the theory of nominal sets.

BibTeX Entry

    author           = {Norrish, Michael and Vestergaard, Ren\'e},
    editor           = {{Klaus Schneider and Jens Brandt}},
    month            = sep,
    series           = {Lecture Notes in Computer Science},
    year             = {2007},
    keywords         = {lambda-calculus theorem-proving},
    address          = {Kaiserslautern},
    title            = {Proof Pearl: de Bruijn Terms Really Do Work},
    pages            = {207--222},
    volume           = {4732},
    booktitle        = {International Conference on Theorem Proving in Higher Order Logics},
    paperurl         = {},
    publisher        = {Springer}