The Setting
The scoping question concerns free indices in the subject and expected type and the sorting requirements on the context’s declarations.
A pure type specification consists of a set of sorts, an axiom relation , and a product-rule relation .✦ The set of terms is generated by (1), with and : (1)✦ The abstraction has domain annotation , and is a dependent product. These are de Bruijn terms: index denotes the newest variable, and a context is a finite list of terms written newest first, with adjoining to . The corresponding named binder forms are and .
For a natural number , a term is scoped at when every free index is less than , with the binder clauses specified in (2): (2)✦
Substitution and Typing
A variable renaming acts on terms by replacing indices. Its action , its lift under a binder, and the shift are specified in (3): (3)✦ A simultaneous substitution replaces each variable by its image, with action and binder lift given by (4): (4)✦ Both operations fix sorts. They act componentwise on applications and binder annotations, using their lifted actions on binder bodies.
For terms , the bound-variable instantiation is the term obtained by applying the single-variable substitution of (5) to : (5) One-step reduction is the compatible closure of the contraction (6), including reduction in every annotation and binder body: (6)✦ The relation of convertibility is the equivalence relation generated by one-step reduction.✦
For terms and sorts , typing is the least judgment generated by the rules in (7), where is the empty context: (7)✦
A valid context for is a finite context obtained from the empty context by adjoining types that have a sort in the preceding context, as in (8): (8)✦
The Claim
Theorem 1. Suppose for the specification . Then (9) and (10) hold, where is the length of the context: (9)✦ (10)✦
In the paper, the result reads: if in named notation, then is valid and , and the sorting judgment of each declaration of in its preceding prefix occurs as a subderivation of the given derivation, with denoting free variables and the variables declared in .
What Is Checked
The assertions are stated over arbitrary pure type specifications and the typing judgments generated by (7) on de Bruijn terms in finite contexts. Equality of terms is decidable whenever equality of the sorts is decidable.