The Setting
Fix a pure type specification , with arbitrary axiom relation and product-rule relation .β¦ Its term set consists of variables, sort constants, applications , annotated abstractions , and dependent products .β¦ Named bound variables denote de Bruijn terms, with index zero referring to the nearest binder. Contexts are listed newest first.
Full one-step reduction contracts to and permits reduction in every subterm, including annotations and binder bodies.β¦ Here is capture-avoiding substitution for the bound variable.β¦ Beta convertibility is the least equivalence relation containing .β¦ The typing judgement uses for sort axioms and for product formation, together with the variable, weakening, abstraction, application, and conversion rules; conversion requires the new expected type to have a sort.
A normal term is a term with no one-step reduct.β¦ A term is weakly normalizing if some finite reduction reaches a normal term, and strongly normalizing, written , if no infinite reduction starts at .β¦ Write for its chosen normal form when one exists, with a fixed fallback otherwise.β¦ A valid context is a context obtained from the empty context by adjoining declarations with for some , where is the context preceding each declaration.β¦ A legal term in is a term that occurs as either the subject or the expected type of a typing judgement in .β¦ System weak normalization means that every legal term in every valid context is weakly normalizing.β¦
A saturated context tower is a sequence of valid contexts of length , each extended by one declaration whose type has a sort in the preceding context. Every type available at a stage is declared afresh at arbitrarily late stages. Free variables retain their declaration levels across the tower. The tower typing judgement holds when at some stage, with both the subject and expected type expressed in that prefixβs variables.β¦
Candidate Conditions
For a term , the set of typed strongly normalizing terms at is (1): (1) For a finite argument list , write for left-associated iterated application, with .β¦ Argument list reduction changes exactly one component by one beta step.β¦ A strongly normalizing argument list is a finite argument list that admits no infinite sequence of argument list reduction steps, written .β¦
A tested stack at is a finite argument list generated by the clauses in (2); denotes adjoining at the front of the list: (2) The ground set consists of the tower-typed terms that pass every tested stack, as specified in (3): (3)β¦
A term set is head expansion closed at when it contains whenever this term has tower type , the annotation , body , and argument are strongly normalizing, the argument list is strongly normalizing, and .β¦
Definition 1. The family of normalization candidates at consists of the term sets with the bounds and head expansion closure in (4): (4)β¦
The bounded intersection of a family of term sets is their intersection restricted to , as in (5).β¦ The bottom set is the bounded intersection of all normalization candidates at , as in (6).β¦ (5)β¦ (6)β¦
For a product and an argument , put . Given an argument set and a family of term sets for each , the indexed product test is the set of terms in (7): (7)β¦
The Claim
Theorem 1. Fix a term , and let be any family of candidates. Then (8), (9), and (10) hold: (8)β¦ (9)β¦ (10)β¦ Assume that is system weakly normalizing. Let , and for each let be any family of candidates. The indexed product test satisfies (11): (11)β¦
In the paper, the result reads: the inclusion-ordered family is a complete lattice with largest element and least element , and for an actual product , any , and any families indexed by sets for , the set is a candidate at .
What Is Checked
The statements concern term sets in a saturated context tower of an arbitrary pure type specification, with system weak normalization required for the indexed product test.