The Setting
The sorts that classify a normal type determine a profile of that type. Product formation relates these profiles through a signed graph. The setting also includes labelled terms, whose labels distinguish data arguments from proof arguments.
A pure type system specification consists of a set of sorts, an arbitrary axiom relation , and an arbitrary product-rule relation .โฆ Its terms are variables, sorts, applications , annotated abstractions , and dependent products .โฆ Displayed binders use names; variables have de Bruijn indices, with zero referring to the nearest binder, and contexts list the newest declaration first.
A renaming is a map from variable indices to variable indices whose action on terms replaces each variable index by and fixes sorts. A simultaneous substitution is a map from variable indices to terms whose action on terms replaces index by the term . Both operations act recursively on every term component. Write for renaming by . Under a binder, the lifted renaming fixes the new index zero and shifts renamed older indices; the lifted substitution fixes the new variable and shifts the images of older variables. The single substitution determined by sends zero to and to variable .โฆ The bound variable instantiation of a term by a term is the result of applying to the substitution that sends zero to and to variable .โฆ
The typing judgement is generated by the pure type system rules. An axiom gives . A domain with permits the variable judgement and weakening into , shifting both subject and expected type by . Product formation uses , , and to assign to . An abstraction has type when its body has type in the extended context and the product has a sort. Application of a function of this product type to has type . Conversion changes an expected type to a -convertible type that itself has a sort. A valid context of is a finite list obtained from the empty context by adjoining domains having a sort in the preceding context.โฆ
Full one-step reduction contracts to and is closed under every term component, including annotations and binder bodies.โฆ convertibility of terms of is the smallest equivalence relation containing full one-step reduction.โฆ A normal term of is a term that admits no full reduction step.โฆ A weakly normalizing term of is a term that reaches a normal term by full reduction in finitely many steps, possibly zero; its chosen normal form is denoted by . A legal term in a context of is a term occurring as either the subject or the expected type of a judgement .โฆ System weak normalization means that every legal term in every valid context is weakly normalizing.โฆ
Profiles and Signed Graphs
The normal form sort profile is the set of all sorts typing .โฆ The axiom profile and the product output profile are the sets in (1): (1) A feasible sort profile is a nonempty set equal to for some valid context and normal term .โฆ A feasible product profile triple consists of feasible profiles satisfying ; write for the set of these triples.โฆ
The primary signed graph has sets of sorts as vertices and exactly the positive and negative edges in (2): (2)โฆ A signed directed walk in a signed directed graph is a finite directed walk whose parity is the number of negative edges modulo two; repetitions are permitted, and the empty walk has even parity. Write for such a walk of parity and for directed reachability with either parity. Positive reachability, written , uses only positive edges and permits the empty walk.โฆ A strongly connected component of is a set containing a vertex such that precisely when and .โฆ
For a family of profiles, the observation layers are the profiles positively reachable from a nonempty axiom profile of a sort whose singleton belongs to , as in (3): (3)โฆ A direct observation layer for is a profile in for which some satisfy . The secondary signed graph has exactly the edges in (4): (4)โฆ A plain observation layer is a profile with an even walk in to a direct observation layer and an odd walk in to a possibly different direct observation layer.โฆ
A forbidden configuration consists of a strongly connected component of all of whose vertices are plain observation layers, with a negative secondary edge having both endpoints in , and a triple and sort such that , , and .โฆ Relational exclusion is the condition that every strongly connected component of containing an odd closed walk and a triple of with all three profiles in has no forbidden configuration.โฆ
Labelled Targets
The modes are data and proof .โฆ A label specifies its argument mode and result mode by (5): (5) Labelled terms attach one of these labels to each application, annotated abstraction, and dependent product, written , , and .โฆ Label erasure deletes all labels and preserves every other term component.โฆ Labelled renaming, simultaneous substitution, single substitution, and bound variable instantiation act as above and preserve constructor labels.
Labelled reduction has full contextual closure and contracts to only when the two labels agree.โฆ Labelled convertibility of labelled terms is the smallest equivalence relation containing labelled reduction.โฆ Labelled typing uses the same typing rules, with any label in product formation, matching labels on an abstraction and its product type, matching labels on an application and its functionโs product type, and labelled convertibility in conversion.โฆ
A mode environment is a function from variable indices to modes. Its extension gives zero mode and index mode .โฆ The mode discipline is the least judgement assigning variable mode and each sort data mode, with the remaining rules in (6): (6)โฆ
A data-only labelled term is a labelled term in which every constructor label is .โฆ A positive telescope is a labelled term formed from a data-only labelled term by prefixing zero or more dependent products with arbitrary domains.โฆ A normal positive target is a positive telescope whose erasure is in full normal form.โฆ
Context lookup assigns index zero the successor shift of the newest declared type; on adjoining a declaration it shifts every older variableโs type once more.โฆ A converter proof context is a labelled context with a mode environment such that each declared variable assigned proof mode has, under context lookup, type for a normal positive target and an arbitrary codomain .โฆ
The Claim
Theorem 1. Suppose is system-wide weakly normalizing. Let be a converter proof context and a normal positive target. The exclusion of proof-mode inhabitants is (7): (7)โฆ If the sort set is finite, also satisfies (8): (8)โฆ
In the paper, the result reads: if every legal expression of is weakly -normalizing, then every primary component containing an odd closed walk and a feasible product profile triple entirely within satisfies the graph exclusion condition of $\S5$.
What Is Checked
Both statements assume system weak normalization: the relational statement concerns finite sort sets and the primary and secondary profile graphs, while the target statement concerns labelled typing and mode discipline in converter proof contexts with normal positive targets.