The Setting
The sort collection of a pure type system need not be finite. The question is whether a typed failure of strong normalization in a system with normal forms for every expression occurring as the subject or expected type of a derivable judgement needs the ambient system’s whole collection of sorts.
A pure type system specification consists of a sort collection , an arbitrary axiom relation , and an arbitrary product-rule relation .✦
Terms over form the collection generated by the grammar (1). (1)✦ Displayed variable names are source notation for de Bruijn indices, with index zero referring to the nearest enclosing binder; contexts are finite lists in newest-first order.
The variable renaming of a term over , for , is the term obtained by replacing each free index by .✦ The simultaneous substitution in a term over , for , is the term obtained by replacing each free index by .✦ Both operations fix sorts and act recursively on applications and binder domains; under a binder, renaming fixes zero and sends to , while substitution fixes zero and sends to with free indices increased by one. For terms and over , bound variable instantiation is capture-avoiding substitution using the single variable substitution that sends zero to and each to the variable of index .✦
Full one-step reduction on terms over is the least relation containing (2) and closed under application in either position, reduction in abstraction annotations and bodies, and reduction in product domains and codomains. (2)✦ Write for zero or more reduction steps, and for convertibility, the smallest equivalence relation containing .✦
For a context and terms over , the typing judgement is the least relation generated by the sort axioms for , variable introduction, and weakening by a type with for some sort , together with the product, abstraction, application, and conversion rules.✦ A product has sort when , , and . An abstraction has type when and that product has some sort in . Application of to has type . Conversion changes an expected type to when and for some sort .
A valid context for is a list generated from the empty context by extending a valid to whenever for some sort .✦
A legal term for in a context is a term occurring as the subject or expected type of a derivable typing judgement in that context, as in (3). (3)✦
A normal form over is a term with no one-step reduct.✦ A term over is weakly normalizing if it has a reachable normal form , as specified in (4); the term is strongly normalizing, written , if no infinite full reduction sequence begins at . (4)✦
System weak normalization of is the condition (5) on every legal subject and expected type in every valid context. (5)✦
For , the induced restriction is the specification over retaining every original axiom and product rule on those sorts, given by (6). (6)✦
The Claim
Theorem 1. Suppose is system weakly normalizing. Every nonempty subset satisfies (7). (7)✦ Suppose also that and that is not strongly normalizing. There are a finite subset , a context over , and terms satisfying (8). (8)✦
In the paper, the result reads: if every legal expression of is weakly normalizing for full reduction but some legal expression is not strongly normalizing, there are finite sets , , and such that has both properties.
What Is Checked
The finite counterexample statement (8) concerns a typed subject that fails strong normalization in a system satisfying (5); the restriction statement (7) concerns a nonempty subset of its sorts. Equality of terms is decidable whenever equality of sorts is decidable.