The Setting
The item concerns typing over an increasing sequence of finite contexts, with free variables numbered by the stages at which they enter. Let be a pure type specification, where is an axiom relation on and is a product-rule relation on .✦ Terms are variables , sorts , applications , annotated abstractions , and dependent products .✦ The displayed binder names are notation; variables use de Bruijn indices, with zero referring to the nearest enclosing binder, and finite contexts are ordered newest first.
A renaming acts on a term by , replacing free indices according to and fixing sorts.✦ Below a binder its lift fixes zero and sends to . Write for the set of terms over . A simultaneous substitution acts by ; its lift fixes the bound variable and sends to with all free indices increased by one.✦ Both operations act recursively on applications, annotations, and binder bodies. For terms and over , the single substitution sends zero to and to ✦; instantiation is .✦
Full one-step beta reduction contracts to and is closed under every term constructor, including annotations and binder bodies.✦ Beta convertibility on terms over is the least equivalence relation containing full one-step beta reduction.✦ A beta normal form over is a term with no one-step reduct.✦ A term over is weakly normalizing, written , when reaches a normal form in finitely many steps, possibly zero✦; it is strongly normalizing, written , when no infinite beta reduction begins at .✦
Typing is the pure type system judgement generated by the axiom, variable, weakening, product, abstraction, application, and conversion rules of .✦ Product formation uses the triples in , abstraction requires a sorted product type, and conversion requires a sorted target type. A valid context for is a finite context obtained from the empty context by extensions with for some .✦ Context lookup gives the declared type as viewed in the full context; writing for the renaming , its defining clauses are (1). (1)✦
Towers and Their Judgements
A saturated context tower for is a sequence of valid contexts with , each extending its predecessor by one type having a sort there, such that every type sorted at a stage occurs as a new declaration at arbitrarily late stages.✦ The reversal in (2) translates their free levels into the indices of a context of length . (2)✦
Tower typing is typing of both and at some finite stage after reversal, as in (3).✦ A tower-typed substitution for in is an assignment satisfying the declared types of all variables of ; this is written , as in (4).✦ (3)✦ (4)✦
The Claim
Theorem 1. Suppose that is at most countable and fix an axiom . There is a sequence of contexts , with one context at each stage . The constructed saturated tower is given by (5). (5)✦ For a term and a sort with , and any lower bound , the construction satisfies (6). (6)✦
Let now be any saturated context tower for . For a type with and a lower bound , there is a variable as in (7). (7)✦ Given judgements and , a common stage exists as in (8). (8)✦ For a finite valid context , there is a variable-valued typed substitution as in (9). (9)✦
For every term over and every , reversal satisfies (10). (10)✦ Every renaming preserves strong normalization of a term , as in (11). (11)✦ For any renaming such that is strongly normalizing, (12) holds. (12)✦
In the paper, the result reads: if is at most countable and the variable names form a countably infinite set, there is a possibly empty countable sequence of named declarations, with a judgement over meaning one over some finite initial segment, such that every finite initial segment is valid and an infinite set of names is disjoint from all declared names; whenever a finite initial segment satisfies , infinitely many later declarations have the form with distinct names ; every finite valid context embeds by an injective renaming of its declared variables as a subsequence of a finite initial segment, and such an embedding sends to over a finite initial segment containing the embedded context; for every finite initial segment with and every finite set of names, a larger finite initial segment ends in a declaration with and ; finitely many judgements over hold over a common finite initial segment; and the injective renamings of the embedding clause preserve and reflect weak and strong normalization.
What Is Checked
The axiom and product-rule relations of are arbitrary, without functionality or uniqueness of sort witnesses. The tower judgements in (3) and (4) concern terms and their expected types under the finite-context typing relation.
(13)