The Setting
Typing assigns terms to types, which are themselves terms of the same language. Regularity concerns the typing judgements available for an assigned type.
A pure type system specification is a triple , where is a collection of sorts, is an axiom relation, and is a product-rule relation.✦ Terms over , with variables written , form the smallest collection generated by the grammar (1). (1)✦ Here is named source notation for a variable. In de Bruijn notation, denotes the variable with index , and index zero refers to the nearest enclosing binder. A context is a finite list of terms in newest-first order; the extension by is written .
Variable renaming by a map is the operation on terms that replaces by , fixes sorts, and acts recursively on applications and binder domains. Under a binder it uses the lifted map that fixes zero and sends to . Simultaneous substitution by an assignment of terms to indices is the operation on terms that replaces by , fixes sorts, and acts recursively on applications and binder domains. Under a binder its lift sends zero to and sends to with every free index increased by one.
The single-variable substitution determined by a term is the assignment that sends zero to and to .✦ Bound-variable instantiation of a binder body is simultaneous substitution by the single-variable substitution determined by the term ; substitution avoids capture.✦
One-step reduction is the least relation containing the contraction (2) and closed under reduction in either application position, in an abstraction’s annotation and body, and in a product’s domain and codomain. (2)✦ The convertibility relation is the smallest equivalence relation containing .✦
Typing
The typing judgement is the least relation generated by the axiom, variable, weakening, product, abstraction, application, and conversion rules.✦ An axiom gives . When , the variable rule gives , and weakening extends any judgement to , with fresh. In de Bruijn notation, context extension shifts the variable rule’s assigned type and both the subject and assigned type of the weakened judgement by successor on indices.
When , , and , the product rule gives . The abstraction rule applies when and for some sort ; it gives . When and , application gives . From , , and for some sort , conversion gives .
The Claim
Theorem 1. Let . Then (3)✦ Let . Then (4)✦
What Is Checked
The regularity statement (3) and the application statement (4) concern arbitrary pure type system specifications and derivable typing judgements over their terms and contexts.
When equality of sorts is decidable, equality of terms is decidable.