The Setting
A context supplies the declarations of a typeβs free variables. One-child candidate evaluation also takes an actual image and a polarity bit for each variable.
A pure type specification consists of a sort set , an arbitrary axiom relation , and an arbitrary product-rule relation .β¦ Its terms are variables, sorts, applications , annotated abstractions , and dependent products .β¦ Variable names are source notation; indices count outwards from the nearest binder, starting at zero, and contexts list newest declarations first.
For an index map , the renamed term is obtained from by replacing each free index by .β¦ Under a binder its lift fixes zero and sends to . For a simultaneous substitution , an assignment of terms to indices, the substituted term is obtained from by replacing each free index by the term , acting on every annotation, and lifting under binders by fixing the bound variable and shifting the free indices of each substituted image.β¦ Both operations preserve sorts and act on both parts of an application. The single-variable substitution determined by sends zero to and to variable β¦; bound-variable instantiation is substitution by this assignment.β¦
Full one-step reduction is the closure of under all term positions, including annotations and binder bodies.β¦ Convertibility is the least equivalence relation containing .β¦ A normal form is a term with no outgoing step.β¦ A term is weakly normalizing when some normal form is reachable by finitely many such steps, including zero steps.β¦
Typing is the pure type system judgment with the axiom relation , product rules , variable and weakening rules, abstraction and application rules, and conversion of an expected type to a sortable -convertible type.β¦ A valid context of the pure type system is a context obtained from the empty context by extensions that adjoin to an already obtained context whenever for some sort .β¦ A term is legal in when some judgment or holds.β¦ System weak normalization means that every legal term in every valid context is weakly normalizing, including both subjects and expected types.β¦
A saturated context tower is a sequence of valid contexts of length , each extended at the next stage by a type admitting a sort. The index-to-level reversal is the index map that sends to and fixes .β¦ Saturation requires that, whenever , every bound admits with . Here the free names of are fixed levels, while bound variables remain indices.
Declarations and Assignments
Context lookup is the relation expressing that index has declared type viewed in the full context .β¦ With , its generating rules are (1). (1)β¦ A declaration-preserving renaming from to is an index map satisfying (2). (2)β¦
Context equivalence is the relation on valid contexts defined by agreement on subjects and expected types as in (3). (3)β¦
A polarity assignment assigns a Boolean bit to each index.β¦ Fix the ambient tower and the class of profiles used by the one-child interpretation. The sort profile of a term in a context is the set of sorts typing the chosen normal form in when weak normalization supplies that form.
The recursive one-child interpretation is a set of terms selected by the sort profile of in its context and the sort profile of in the ambient tower. When both profiles lie in , a product receives the raw product candidate, whose membership condition tests applications against the recursive interpretations of and , with and extended at the binder for each actual image and bit. A nonproduct receives the upper candidate of typed strongly normalizing terms at the normal-form selection of if it has no variable head or its headβs bit is , and the lower ground tested-stack candidate if its headβs bit is . When either profile test fails, the interpretation receives the upper candidate at that same normal-form selection.
The Claim
Theorem 1. Suppose for a sort . Let be valid and let be a declaration-preserving renaming from to . Let actual substitutions and polarity assignments satisfy and . The renaming law is (4). (4)β¦ For a context equivalent to , arbitrary actual substitution and polarity assignment , the context law is (5). (5)β¦
In the paper, the result reads: valid thinning and context conversion preserve the support, its polarity and the candidates, and pointwise -convertible actual images preserve the candidates when the old polarity bits agree.
What Is Checked
The laws are stated over types admitting a sort, declaration-preserving renamings into valid contexts, context equivalence, and arbitrary actual substitutions and polarity assignments for the fixed recursive one-child interpretation.