The Setting
A head redex can stand at the front of a finite argument spine. Full reduction also acts inside the abstraction’s annotation and body, and inside each argument of the spine.
The terms over a sort collection form the smallest collection generated by (1), where ranges over variables and over . (1)✦ Names denote binders in this notation; de Bruijn indices count outwards from the nearest enclosing binder, starting at zero.
Simultaneous substitution for an assignment of terms to variable indices is the operation on terms that replaces the variable of index by and fixes sort constants. It acts recursively on both parts of an application and on the annotation of an abstraction or the domain of a dependent product. Under either binder it uses the lifted assignment: index zero maps to the variable of index zero, and index maps to with every free index increased by one.
The single-variable substitution associated with a term is the assignment in (2), where denotes the variable of index . (2)✦ Bound variable instantiation is simultaneous substitution of into the body of a binder named .✦
One-step reduction on annotated terms is the least relation containing (3) and closed under application in either position, dependent products in the domain and codomain, and abstractions in the annotation and body. (3)✦ A term is strongly normalizing, written , when no infinite sequence of these full reductions begins at .✦
For a term and a finite argument list , iterated application is the left-associated application defined by (4), where denotes the empty list and denotes the list with first entry and remaining entries . (4)✦ Argument list reduction is the relation on finite lists of terms in which exactly one entry is replaced by a one-step reduct and all other entries remain fixed.✦ A finite argument list of terms is strongly normalizing when no infinite sequence of argument list reductions begins at .✦
The Claim
Theorem 1. Let be an annotation, an abstraction body with bound variable , a term, and a finite argument list. Suppose that , and are strongly normalizing, that is a strongly normalizing argument list, and that is strongly normalizing. The head expansion satisfies (5). (5)✦
What Is Checked
The claim (5) is stated over annotated terms with capture-avoiding bound variable instantiation and full reduction, using strong normalization of terms and of finite lists under argument list reduction.
When equality of sorts in is decidable, equality of terms over is decidable.