The Setting
Fix a pure type specification , where is a collection of sorts and and are arbitrary relations.β¦ Terms over are generated by variables, sort constants, application , annotated abstraction , and dependent product .β¦ The displayed names are source notation; bound variables use de Bruijn indices, with zero denoting the nearest binder.
Full one-step reduction is the relation generated by head contraction and closed under application and under every annotation and binder body of abstractions and products.β¦ Capture-avoiding simultaneous substitution replaces free indices by assigned terms, lifting the assignment beneath binders.β¦ Bound variable instantiation uses the single variable substitution sending zero to and each index to the variable of index .β¦ convertibility is the smallest equivalence relation containing .β¦
For a context of variable declarations and terms and , the typing judgement is the least relation generated by the axiom, variable, weakening, product, abstraction, application, and conversion rules.β¦ An axiom gives . Variable introduction declares , and weakening preserves existing judgements, when . A product has sort when its domain has sort , its codomain has sort in the extended context, and . Abstraction types the body at the codomain in the extended context and requires the corresponding product to have a sort. Application gives type when and . Conversion changes an expected type to a convertible type having some sort. A valid context is a finite newest-first list of variable declarations obtained from the empty context by extensions with for some .β¦
A normal term is a term having no one-step reduct.β¦ A weakly normalizing term is a term from which a finite sequence of reductions reaches a normal term;β¦ a strongly normalizing term , written , is a term from which no infinite sequence of reductions starts.β¦ A legal term in a context is a term occurring as either the subject or the expected type of a typing judgement.β¦ System weak normalization means that every legal term in every valid context is weakly normalizing.β¦ Write for the chosen full normal form when one exists, with a fixed arbitrary value otherwise.β¦
A saturated context tower is a family of valid contexts with , each extended to the next by a type having some sort. Its free names are fixed levels, numbered by the order in which declarations enter the tower. Variable renaming by acts on free indices; beneath a binder its lift fixes zero and sends to .β¦ For , the reversal is the renaming that sends to and leaves other indices unchanged.β¦ Writing for this renaming, tower typing is defined by (1). (1)β¦ Saturation requires that, whenever , every bound admits with .
Candidates and Tested Stacks
For a term , the top candidate is the set of strongly normalizing terms having type in , as in (2). (2)β¦ A tested stack at a term is a finite list generated by (3): the empty list is tested at every , and is tested at when and is tested at . (3)β¦ For a term and a finite list of terms, iterated application is the term obtained by applying the arguments in list order, associating to the left, and equals for the empty list.β¦ The ground candidate is the set of terms having type that remain strongly normalizing after every tested stack, as in (4). (4)β¦
The Claim
Theorem 1. For every term , (5)β¦ For every literal sort , (6)β¦ For a variable satisfying , (7)β¦ Suppose is weakly normalizing, , and . Then (8)β¦
What Is Checked
The assertions (5), (6), and (7) are stated over an arbitrary pure type specification and a saturated context tower; (8) additionally assumes system weak normalization. Equality of terms is decidable whenever equality of sorts is decidable.