The Setting
Thinning in a dependent context concerns the variables in a term and in its expected type. Fix a pure type specification , where is a collection of sorts, is an arbitrary axiom relation, and is an arbitrary product-rule relation.β¦ The collection of terms over is generated by (1). (1)β¦ The binder names in (1) are notation for reading terms; variables are de Bruijn indices, with zero referring to the nearest binder. Contexts are finite lists in newest-first order, and denotes extension of by .
A variable renaming acts on a term by replacing its free indices according to ; write the result as .β¦ For a variable renaming , the lifted renaming is the map in (2) used beneath a binder, and denotes the successor map. (2)β¦ Renaming fixes sorts, distributes over application, and acts on annotated abstractions and dependent products by (3). (3)
A simultaneous substitution is an assignment of terms to indices. The action of a simultaneous substitution on a term is the term obtained by replacing by , fixing sorts, and distributing over application. The lifted substitution of a simultaneous substitution is an assignment of terms to indices satisfying and . Under either binder, substitution by acts on the domain with and on the body with . For terms and , bound variable instantiation is the term obtained by the substitution in (4), using the single-variable substitution . (4)
One-step reduction on is the least relation containing (5) and closed under reduction in either part of an application, in every abstraction annotation and body, and in every product domain and codomain. (5)β¦ Beta convertibility on is the smallest equivalence relation containing .β¦
The typing judgement is the least relation satisfying the rules in (6); all displayed sort letters range over . (6)β¦
A valid context is a finite newest-first list obtained from the empty context by extending a valid context with a type for which for some sort .β¦
Context variable lookup is the relation generated by (7), expressing a declarationβs type at its position in the full context. (7)β¦
The Claim
Theorem 1. Let , let be a valid context, and let be a renaming such that whenever . Then (8)β¦
Let , and suppose that and for sorts . Then (9)β¦
In the paper, the result reads: if and is a valid context containing the named declarations of unchanged and in their original order, then .
What Is Checked
The renaming statement (8) ranges over arbitrary pure type specifications, a valid target context, and typed images of every source context lookup in (7). The insertion statement (9) concerns two types sortable over the same older context and a judgement under one of them. Both assertions use the typing relation (6), including dependent products and conversion for the full reduction in (5).