The Setting
Typing generation asks which premises a typing judgement imposes on the outer constructor of its subject. The expected type may have been changed by conversion.
A pure type specification consists of a collection of sorts , an arbitrary axiom relation , and an arbitrary product-rule relation .✦ Terms over are variables, sort constants, applications , annotated abstractions , and dependent products .✦ The named binders are source notation; variables in the library use de Bruijn indices , with referring to the nearest binder. Contexts are finite lists in newest-first order, written when extended by a type , or in named notation.
For a term over and a map , the renamed term is the term obtained by replacing each free by .✦ It fixes sorts and acts recursively on term constructors, using the lifted map and under a binder. Write for renaming by successor. For a term over and an assignment of terms to indices, the substituted term is the term obtained by replacing by and fixing sorts.✦ It acts recursively, using and under a binder.
The single-variable substitution determined by a term over is the assignment of terms to indices given by and .✦ For terms and over , the bound-variable instance is the term given by , written with named binders.✦ For a context , context lookup is the relation between an index and its declared type viewed in the full context, defined by (1).✦ (1)
One-step reduction is the least relation containing (2) and closed under every term constructor, including reduction in abstraction annotations and bodies and in product domains and codomains.✦ (2) The convertibility relation is the smallest equivalence relation containing .✦
The typing judgement is the least relation closed under the axiom, variable, weakening, product, abstraction, application, and conversion rules.✦ An axiom gives . Whenever , the variable rule gives , and weakening takes to . When , , and , the product has type . When and for some sort , abstraction gives . When and , application gives . Given , , and for some sort , conversion gives .
The generation condition for terms in a context is a condition determined by the outer constructor of . For , it requires a type with and ; for , it requires a sort with and . For , it requires sorts satisfying (4); for , it requires a term and a sort satisfying (5); for , it requires terms satisfying (6).
The Claim
Theorem 1 (Typing generation). Let be a pure type specification and suppose . The generation condition holds as in (3): (3)✦ (4)✦ (5)✦ (6)✦
What Is Checked
The statements concern the typing relation on de Bruijn terms in newest-first contexts for arbitrary pure type specifications, with full convertibility between expected types. Equality of terms is decidable whenever equality of sorts is decidable.