The Setting
For an annotated dependent lambda calculus, normalization asks whether a term and its expected type admit normal forms, or whether all their beta reductions terminate. The admissible typing judgements depend on sort axioms and dependent product rules.
The Definition
Definition 1. A pure type specification is a triple consisting of a set of sorts and arbitrary axiom and product-rule relations, as in (1). (1)✦
An expression over the sort set is an annotated lambda term generated by (2), where ranges over variables and over . (2)✦ A variable renaming on expressions over is a map from free variables to variables that respects binding.✦ A simultaneous substitution on expressions over is a map from free variables to expressions that acts on expressions without capture.✦ A single-variable substitution on expressions over is a map from free variables to expressions that sends the variable to an expression and leaves the other free variables fixed; its action on a binder body is bound-variable instantiation.
Full beta reduction on expressions over is the least relation satisfying (3), where ranges over expression contexts with one hole, including annotations and binder bodies. (3)✦ Beta convertibility on expressions over is the least equivalence relation containing ; the notation denotes the reflexive transitive closure of .
In named variable notation, a context is a finite sequence ; an extension uses a fresh . For a fixed specification , the typing judgement is the least relation closed under the rules in (4), where range over sorts and over expressions. (4)✦
A valid context for is a finite sequence of declarations generated by (5). (5)✦ An expression is legal in a context when it occurs as a subject or an expected type of a typing judgement in , as in (6). (6)✦
A beta normal form is an expression with no outgoing beta step, as in (7). $$M\in\mathrm{NF}_\beta \quad\Longleftrightarrow\quad \not\exists N\; M\to_\beta N.$$(7)✦ An expression is weakly normalizing when it reaches a beta normal form by finitely many steps, as in (8). (8)✦ An expression is strongly normalizing when no infinite beta reduction starts from , as in (9). $$M\in\mathrm{SN}_\beta \quad\Longleftrightarrow\quad \not\exists (M_i)_{i\in\mathbb N}\; \bigl(M_0=M\ \land\ \forall i\in\mathbb N,\ M_i\to_\beta M_{i+1}\bigr).$$(9)✦
A pure type system is weakly normalizing when every expression legal in a valid context is weakly normalizing, as in (10). (10)✦ A pure type system is strongly normalizing when every expression legal in a valid context is strongly normalizing, as in (11). (11)✦
What Is Checked
The system normalization properties are stated over arbitrary specifications and all legal expressions in their valid contexts.