The Setting
Fix a pure type specification , where is the set of sorts, with an arbitrary axiom relation and product-rule relation .β¦ Terms are generated by variables, sort constants, applications , annotated abstractions , and dependent products .β¦ A normal form sort profile records every sort that types a termβs chosen normal form.β¦
Full one-step reduction on terms is the closure, under all term constructors, of the contraction in (1); this includes reduction in annotations and binder bodies.β¦ The bound variable instantiation of a term is the term obtained by replacing the bound variable by , avoiding capture.β¦ (1) The relation of convertibility is the least equivalence relation containing .β¦ A normal term is a term with no one-step reduct.β¦ A weakly normalizing term is a term that reaches a normal term by finitely many steps.β¦ The chosen normal form is the unique normal form of when one exists, with a fixed fallback otherwise.β¦ A neutral term is a variable or an application whose function is neutral; its argument is unrestricted.β¦
A context is a finite sequence of declarations; extends it by the newest declaration. The typing judgement is generated by the axiom, variable and weakening rules, dependent product formation using , abstraction, application with bound variable instantiation, and conversion between -convertible expected types when the new type has a sort.β¦ A valid context is a finite sequence of declarations built from the empty context by adjoining whenever for some , where consists of the preceding declarations.β¦
A legal term in a context is a term occurring as either a subject or an expected type in a typing judgement in .β¦ A weakly normalizing specification is a pure type specification for which every legal term in every valid context is weakly normalizing, including both and whenever .β¦
Profiles and Typed Substitutions
The normal form sort profile of a term in a context is the set of all sorts typing in , as in (2).β¦ The axiom profile of a sort is the set of axiom successors of .β¦ For sets , the product output profile is the set of outputs of rules whose first two sorts belong to and , respectively.β¦ (2)β¦ (3)
A variable renaming is a map from variables to variables; it acts on terms by replacing free variables by their images, fixing sort constants and respecting binders, and its action is written .β¦ A simultaneous substitution is an assignment of terms to variables that acts recursively, avoiding capture under binders; write its action as .β¦ Context lookup gives the declared type of viewed in the full context.β¦ A typed simultaneous substitution from a context to a context is an assignment of terms to variables satisfying (4).β¦ (4)β¦
The Claim
Theorem 1. Let be normal and suppose for a sort . Then (5)β¦ For every valid context and sort , (6)β¦ If is normal and neutral, and , then (7)β¦ For a neutral term with , without a normality assumption, (8)β¦ When and are normal, (9)β¦ Suppose is weakly normalizing, , and is valid. Let be a variable renaming such that every lookup satisfies . Then (10)β¦ Suppose , , and . For every term , (11)β¦ Suppose is weakly normalizing, is weakly normalizing, is valid, and is a typed simultaneous substitution from to . Then (12)β¦
What Is Checked
The statements concern the typing judgement generated by and the normal form profiles of (2), with axiom and product-rule witnesses ranging over the relations in (3).
The libraryβs laws (10), (11) and (12) concern the renaming action, replacement of the newest declaration, and typed simultaneous substitution of (4), respectively.