The Setting
Typing a variable applied to arguments raises a uniqueness question when axiom and product relations admit several outputs.
A pure type specification is a triple consisting of a collection of sorts , an arbitrary axiom relation , and an arbitrary product-rule relation .β¦ A term over is an expression generated by (1), where ranges over variables and ranges over : (1)β¦ Variables use de Bruijn indices, with zero referring to the nearest enclosing binder; the binder names in (1) are named notation for these terms. A context is a finite list of declarations in newest-first order.
Renaming by a map is the operation on terms that replaces variable index by ; under a binder its lift fixes zero and sends to .β¦ A simultaneous substitution is an assignment of a term to each variable index that acts on terms by replacing index by ; under a binder its lift sends zero to variable zero and sends to with its free indices increased by one.β¦ Both operations leave sorts fixed and act recursively on applications, binder annotations and binder bodies. The single-variable substitution determined by a term is the simultaneous substitution that sends zero to and to variable .β¦ Bound-variable instantiation of a body by a term is the term obtained by applying the single-variable substitution determined by to , avoiding capture under binders.β¦
One-step reduction is the least relation containing the contraction in (2) and closed under reduction in either part of an application and in every annotation and body of an abstraction or dependent product: (2)β¦ The relation of convertibility is the smallest equivalence relation containing .β¦
Typing is the least relation generated by the rules in (3), written with fresh binder names; extending a context shifts free indices in the variable ruleβs expected type and in weakeningβs subject and expected type.β¦ (3)β¦
A neutral term is a term that is a variable or an application with a neutral function, as in (4); the argument ranges over arbitrary terms: (4)β¦ A normal form is a term with no outgoing one-step reduction, as specified by (5): (5)β¦
The Claim
Theorem 1. Let be a pure type specification and a context. Let be neutral, and suppose and . Then (6)β¦ For a neutral term with , there is a sort such that (7)β¦ Let be a normal form with . Then, for suitable sorts and terms, one of the following holds: (8)β¦
What Is Checked
The statements (6) and (7) concern neutral terms and their expected types in a common context over an arbitrary pure type specification, while (8) concerns a term in normal form together with a typing judgement for that term and its expected type. Equality of terms over is decidable whenever equality of sorts in is decidable.