The Setting
Subject reduction concerns computation in a typing judgement whose context and expected type have already been chosen. Fix a pure type system specification , where is a collection of sorts, is an arbitrary axiom relation, and is an arbitrary product-rule relation.✦
Terms over are the expressions generated by (1), where is a natural number and : (1)✦ Binder names are source notation; the library’s variables are de Bruijn indices, with zero referring to the nearest binder. A context is a finite list of terms in newest-first order.
Substitution and Typing
The renaming of a term by a map is the term obtained by replacing by .✦ It fixes sorts and acts recursively on applications and binder domains, using the lifted renaming in binder bodies. The simultaneous substitution in a term , for an assignment of terms to indices, is the term obtained by replacing by , fixing sorts, and acting recursively with the lifted substitution in binder bodies.✦ These lifts and the shift are given by (2): (2) For terms and , bound variable instantiation is the capture-avoiding substitution of for index zero in , using the single-variable substitution of (3): (3)
One-step beta reduction is the least relation containing (4) and closed under either position of an application, the annotation and body of an abstraction, and the domain and codomain of a dependent product: (4)✦ Multi-step beta reduction is the reflexive transitive closure of .✦ Beta convertibility is the smallest equivalence relation containing .✦
For a context , a subject term and an expected type , the typing judgement is the least relation generated by the axiom, variable and weakening rules in (5), together with product formation, abstraction, application and conversion in (6).✦ Here denotes extension by the newest entry , the letter ranges over terms, and the letters range over sorts. (5) (6)
The Claim
Theorem 1 (Subject reduction). Suppose . Every term with has the typing judgement (7): (7)✦ Every term with has the typing judgement (8): (8)✦
What Is Checked
The statements range over typing judgements for arbitrary pure type system specifications and over full beta reduction.
If equality of sorts is decidable, then equality of terms is decidable.