The Setting
Fix a pure type specification , where is a set of sorts, is an axiom relation, and is a product-rule relation.✦ Domain and codomain positions in a dependent product have different signs in the primary dependency graph on sort profiles.
Terms are variables, sort constants , applications , annotated abstractions , and dependent products .✦ The displayed names are source notation; de Bruijn indices count from the nearest binder, starting at zero. Contexts list the newest declaration first. A valid context is a finite context obtained from the empty context by adjoining whenever for some , where this judgement means that has sort in .✦
Variable renaming by a map on indices is the operation that replaces free variables according to , lifting the map under each binder by fixing zero and sending to .✦ Simultaneous substitution by an assignment of terms is the operation that replaces free variables according to ; under a binder, zero remains a variable and the image of is with its free indices increased by one.✦ The single-variable substitution for a term is the assignment that sends zero to and to the variable .✦ Bound-variable instantiation of a term by a term is the term obtained by simultaneous substitution in , sending zero to and to the variable .✦
One-step reduction is the least relation containing the contraction in (1) and closed under every term constructor, including annotations and binder bodies. (1)✦ convertibility is the least equivalence relation on terms containing one-step reduction. A term is normal if it admits no one-step reduction, and weakly normalizing if it reaches a normal term by finitely many steps.✦ Write for the unique full normal form when one exists, with a fixed arbitrary fallback otherwise.✦
The typing judgement is generated by the axiom, variable and weakening rules, dependent product formation, abstraction, application, and conversion.✦ An axiom types in the empty context. Variable introduction and weakening extend a context by a type having some sort. Product formation uses for a domain of sort and a codomain of sort in the extended context, giving the product sort . Abstraction requires its dependent product type to have a sort; application instantiates the codomain. Conversion replaces an expected type by a -convertible type that itself has a sort in the same context.
Normal Witnesses
An inhabited normal witness for a set in a context is a pair of terms such that is a normal type assigned every sort in and has type . Write for the existence condition in (2). (2)✦
The Claim
Definition 1 (Sort profiles and the primary graph). The normal-form sort profile of a term in a context is the set in (3). (3)✦ A feasible sort profile is a nonempty set realized by a normal term in a valid context, as specified in (4). (4)✦ The axiom profile of a sort is its set of axiom successors, given by (5). (5)✦ For sets , the product output profile is the set of outputs allowed by their domain and codomain sorts in (6). (6)✦ A profile triple is a triple of feasible sort profiles whose product profile is the output profile, as in (7). (7)✦ The signed primary dependency graph has feasible sort profiles as vertices and the least signed edge relation specified by (8), where denotes a positive edge and a negative edge. (8)✦
Theorem 1 (Feasibility and witnesses). Let be weakly normalizing, and suppose its normal-form sort profile in is nonempty. Then (9) holds. (9)✦ For a feasible sort profile , (10) holds. (10)✦
What Is Checked
These definitions and assertions are stated over arbitrary axiom and product-rule relations, full reduction, the typing judgement , and valid contexts.