The Setting
Two reduction sequences from one pure type system term raise the question of a common reduct; conversion raises the question of how much of a sort or product’s form is retained.
The pure type system terms over a collection of sorts form the least collection generated by the grammar (1), where ranges over variables and . (1)✦ Variables use de Bruijn indices , with index referring to the nearest enclosing binder; the bound variable names in (1) are source notation.
A simultaneous substitution for terms over is an assignment of terms to variable indices. Its action fixes sort constants and replaces by . It acts recursively on applications and binder annotations. Within a binder body, it uses the lifted assignment, which fixes and sends to with all free indices increased by one.
The single-variable substitution for a term is the assignment in (2); bound-variable instantiation is its capture-avoiding action on a term . (2)
One-step reduction on terms over is the least relation containing the contraction (3) and closed under every term constructor in (1), including reduction in binder annotations and bodies. (3)✦ Multi-step reduction on terms over is the reflexive transitive closure of one-step reduction .✦ The convertibility relation on terms over is the least equivalence relation containing .✦
The Claim
Theorem 1. Let be terms over with and . Confluence gives (4). (4)✦
For sorts with , sort injectivity gives (5). (5)✦
Product sort inconvertibility for terms and a sort is (6). (6)✦
For terms with , product compatibility gives (7). (7)✦
What Is Checked
The claims concern terms over an arbitrary sort collection , with full reduction and its reflexive transitive and equivalence closures. Equality of these terms is decidable whenever equality of sorts in is decidable.