The Setting
A proof input at one fixed terminal type may be used to obtain a proof at another. The question is which such transformations can share a valid context whose proof variables have converter types.
A pure type system specification consists of a set of sorts and arbitrary axiom and product-rule relations.β¦ Its terms are variables, sorts, applications , annotated abstractions , and dependent products .β¦ Labelled terms attach one of , and to each application, abstraction and product; the two entries are the argument and result modes, with denoting data and proof. The erasure of a labelled term is the unlabelled term obtained by deleting its labels.β¦ A data-only term is a labelled term with label at every labelled constructor.β¦
Binder names are source notation; variables have de Bruijn indices and contexts are newest-first lists. Write for capture-avoiding renaming by , and for simultaneous substitution by an assignment of terms to indices. Under a binder the lifted renaming fixes zero and sends to ; the lifted substitution fixes the new variable and shifts each older image. The instantiation of a term by a term is the term obtained by the single-variable substitution sending zero to and to the variable of index . These operations preserve labels in labelled syntax. The successor renaming is written .
Full reduction contracts to and is closed under all term components, including annotations and binder bodies.β¦ Labelled contraction requires the application and abstraction to have the same label. In either syntax, convertibility is the equivalence relation generated by this reduction. A normal term is a term with no -reductβ¦; a weakly normalizing term is a term that reaches a normal term in finitely many steps, possibly zero.β¦ Write for the chosen full normal form when one exists, with a fixed fallback otherwise.β¦
The typing judgment uses the axiom, variable, weakening, product, abstraction, application and conversion rules of . Products use a triple in and sorts for their domain and codomain; abstraction requires the product itself to have a sort. Conversion permits a -convertible expected type that has a sort in . The labelled rules preserve the product label in abstraction and application. A valid context, in either syntax, is a finite context built from the empty context by adjoining a type with for some sort .
Profiles and Terminals
The normal form sort profile of an unlabelled term in a context is the set in (1).β¦ A feasible sort profile is a nonempty set of sorts equal to for some valid context and normal term .β¦ (1)β¦
The product output profile of sort sets is the set of sorts given in (2). A feasible product profile triple consists of feasible profiles with .β¦ (2)β¦
The signed primary profile graph has a positive edge whenever are feasible and . Each feasible product triple gives a negative edge and a positive edge . A signed directed walk is a finite walk whose sign counts the parity of its negative edges; the empty walk is positive.β¦ Directed reachability permits either sign.β¦ A strongly connected component of the primary profile graph is a set of profiles containing some and consisting exactly of the profiles reachable from that also reach .β¦
A logical terminal profile of is a profile admitting a feasible product triple with domain and output in . Write for the set of these profiles, as in (3). (3)β¦
Witnesses and Converter Contexts
A mode environment is a function assigning or to each variable index. The extension of a mode environment by a mode is the mode environment assigning to zero and to .β¦ The mode judgment assigns a variable its environment mode and a sort data mode. An application has its labelβs result mode when its function has that mode and its argument has the argument mode. An abstraction has the result mode when its annotation is data and its body has that result mode under extension by the argument mode. A product has data mode when its domain and codomain have data mode, with the latter checked under that extension.
A fixed feasible witness family in is an assignment of a type and a value to every sort set, satisfying (4) at each feasible profile .β¦ Sorting at means having every sort in , and permits additional sorting judgments.β¦ (4)
A positive telescope is a labelled term obtained from a data-only term by prefixing zero or more products, with arbitrary domains.β¦ A normal positive target is a positive telescope whose erasure is normal.β¦
Write for context lookup, shifting a declarationβs type past its own variable and all newer declarations.β¦ A converter proof context is a context with a mode environment satisfying (5).β¦ (5)β¦
A mode-preserving context embedding is a renaming into a valid context satisfying (6).β¦ (6)
A typed open proof transformer from to in is a term with a temporary proof input of type satisfying (7); write for its existence. (7)β¦
For a set of ordered profile pairs, a terminal transfer network for is a triple in the set defined by (8). (8)
The Claim
Theorem 1. Let be a strongly connected component of the primary profile graph. Let be valid, let hold, and let be a fixed feasible witness family in .
If the sort set is finite, then (9)β¦ For any finite set , (10)β¦ Let and be feasible product profile triples, with and . Then (11)β¦
In the paper, the result reads: there is a finite valid extension with a proof term in for every pair of terminals , and every declaration of has the form , where is a terminal and is a normal, constant telescope of products ending at a terminal, its suffixes are sorted, and its type contains no free proof variables.
What Is Checked
The statements (9), (10) and (11) concern labelled typing and mode judgments over a fixed feasible witness family, a primary strongly connected component and a valid converter proof context, with finiteness of the sort set assumed in (9).