The Setting
Typing and mode assignment are separate judgments on annotated terms. The question is when a proof-mode inhabitant can have normal full erasure, given restrictions on its expected type and on the types of proof-mode variables.
A pure type specification consists of a collection of sorts, an arbitrary axiom relation , and an arbitrary product-rule relation .β¦ Pure terms are variables, sorts, applications , annotated abstractions , and dependent products .β¦ A labelled term is a term built from variables, sorts, applications, annotated abstractions and dependent products, with a label on each application, abstraction and product, written , and .β¦ The modes are data and proof β¦; the labels , and specify their argument and result modes in that order.β¦ Write and for those two modes.
Named binders are source notation. Variable indices are de Bruijn indices, with zero at the nearest binder, and contexts are newest-first. Renaming applies a map of indices to the variables of a term, fixing the newly bound variable and shifting older renamed indices under a binder.β¦ Simultaneous substitution replaces variables by assigned terms, lifting the assignment under binders to avoid capture. These operations preserve sorts and constructor labels. In either syntax, bound variable instantiation uses the single-variable substitution sending index zero to and index to the variable of index .
Label erasure is the pure term obtained by deleting every constructor label, recursively through annotations and bodies.β¦ Full reduction is the least relation containing the pure head contraction in (1) and closed under reduction in every term component.β¦ Labelled reduction is the least relation on labelled terms containing the labelled head contraction in (1) and closed under reduction in every term component; the head contraction requires the application and abstraction labels to agree.β¦ (1) Labelled convertibility is the smallest equivalence relation containing labelled reduction.β¦ A pure term is in full normal form, written , when it has no outgoing step.β¦
Targets and Contexts
A data-only term is a labelled term every constructor label of which is .β¦ Write for these terms. A positive telescope is a labelled term in the class generated by (2): its terminal is data-only, and each telescope binder has data argument mode and proof result mode, with an arbitrary domain . (2)β¦ A normal positive target is a labelled term in the class defined by (3). (3)β¦
For a labelled context , the labelled typing judgment assigns expected type to subject for the specification . Its axiom rule gives when . Variables and weakening require a sort-typed declaration; adjoining it shifts older variables and their expected types. Product formation assigns sort to a product with any label when its domain has sort , its codomain has sort in the extended context, and . Abstraction assigns the dependent product type to when the body has expected type in the context extended by and that product has a sort. Application requires a function of product type and an argument of its domain type; its label agrees with the product label, and its expected type is the codomain instantiated by the argument. Conversion changes the expected type to a labelled convertible type that itself has a sort.
A mode environment is a function assigning a mode 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 gives variables their assigned modes and sorts data mode. An application with label requires function mode and argument mode , and has mode . An abstraction requires a data-mode annotation and a body of mode under , and has mode . A product has data mode and requires data mode for its domain and for its codomain under .
Context lookup assigns the shifted head declaration to index zero.β¦ A converter proof context is a labelled context with a mode environment satisfying the restriction in (4); the codomain is arbitrary. (4)β¦
The Claim
Theorem 1. Let be a converter proof context and a normal positive target. The exclusion is (5)β¦
In the paper, the result reads: if is the ambient context or any legal extension of it by data declarations, there is no proof-mode term with and for any .
What Is Checked
The exclusion (5) is stated over arbitrary pure type specifications, labelled typing and mode judgments, with the context and target restrictions (4) and (3).
The data extension law is (6).
Theorem 2. Let be a converter proof context, and let be any labelled term. Write for the context obtained by adjoining the declaration to . Then (6)β¦