The Setting
A pure type specification consists of a set of sorts, an axiom relation and a product-rule relation .✦ Both relations are arbitrary. The expressions of are generated by (1), where ranges over variables and over : (1)✦
A variable renaming is a map from variables to variables, acting on free occurrences without capture.✦ A simultaneous substitution is a map from variables to expressions; its action replaces free occurrences without capture.✦ The single-variable substitution is a substitution that replaces the variable by the expression and leaves all other free variables unchanged.✦ The instantiation of a binder body with argument is the expression obtained by substituting for its bound variable .✦
Full one-step reduction is the relation on expressions obtained by contracting (2) at any occurrence, including either component of an application and the annotation and body of an abstraction or dependent product: (2)✦ Write for a finite sequence of zero or more reduction steps. The convertibility relation is the smallest equivalence relation containing .✦
Typing and Legality
A context is a finite sequence of variable declarations . The typing judgement relates an expression to its expected type in and is generated by (3), where range over sorts and each newly declared variable is fresh for : (3)✦
A valid context is a finite sequence of variable declarations built from the empty context by successive extensions , where the part of preceding each declaration types at some sort .✦ A legal expression in is an expression occurring as either the subject or the expected type of a typing judgement, as in (4): (4)✦
Normalization
An expression is a normal form if it has no one-step reduct.✦ A weakly normalizing expression is an expression admitting a normal form with .✦ A strongly normalizing expression is an expression from which every reduction sequence is finite.✦
The system properties and require, respectively, weak and strong normalization of every legal expression in every valid context.
The Claim
Theorem 1. Let be a pure type specification satisfying . Then (5)✦
What Is Checked
The assertion (5) is stated for the typing and full reduction of an arbitrary pure type specification, with legality (4) quantified over valid contexts.
If equality of sorts is decidable, then equality of expressions is decidable.