The Setting
Substitution in a dependent typing judgement acts on the subject and its expected type. The assignment to each variable must respect the substitution into its own type.
A pure type specification consists of a collection of sorts , an arbitrary axiom relation , and an arbitrary product-rule relation .β¦ Terms over are generated by variables for natural numbers , sort constants , application , annotated abstraction , and dependent product .β¦ Variable names at binders are source notation; occurrences use de Bruijn indices, with zero denoting the nearest binder. Contexts are finite lists in newest-first order, with denoting extension of by .
The renaming of a term by a map is the term obtained by replacing by , fixing sorts, and acting recursively on applications and binder domains.β¦ Under a binder its action uses the lifted renaming and . Write for the renaming that increases every free index by one.
A simultaneous substitution is an assignment of terms to natural-number indices; its action is the capture-avoiding operation in (1), where the lifted assignment is given by and . (1)β¦
The single-variable substitution associated with a term is the assignment in (2); bound-variable instantiation is .β¦ (2)β¦
One-step reduction is the least relation containing and closed under reduction in either application position, in abstraction annotations and bodies, and in product domains and codomains.β¦ The relation of convertibility is the smallest equivalence relation containing .β¦
The typing judgement is the least relation generated by the pure type system rules.β¦ Axioms give for . From , the variable rule gives ; weakening sends to under the same condition. Product formation uses and to give when . Abstraction gives when and the product has a sort in . Application gives from and . Conversion gives from when and for some sort .
A valid context is a newest-first list obtained from the empty context by adjoining to a valid whenever for some sort .β¦ Context lookup is the relation between a context, an index, and its type generated by (3). (3)β¦
A typed simultaneous substitution is an assignment of terms to indices satisfying the typing condition (4) for every context lookup. (4)β¦
The Claim
Theorem 1. Let , let be a valid context, and let be a typed simultaneous substitution. Then (5)β¦ For a term with , the single-variable substitution satisfies (6)β¦
In the paper, the result reads: in named-variable notation, let and let be valid, and suppose that for ; then gives ; in particular, for a context , and give .
What Is Checked
The claims (5) and (6) are stated over arbitrary pure type specifications, indexed terms in newest-first contexts, and the typed assignments of (4), with validity of the target context required for (5).