The Setting
Substitution can change which variable controls a one-child candidate. The issue is how the old and new polarity choices constrain the direction of comparison between the resulting sets of terms.
Fix a pure type specification with arbitrary axiom and product-rule relations. Its terms are variables, sort constants, applications, annotated abstractions and dependent products .✦ Named variables are source notation; variables use de Bruijn indices, with zero referring to the nearest binder, and context lists are newest-first. Typing is generated by the axiom, variable and weakening rules, dependent product formation permitted by , annotated abstraction, application and conversion of the expected type to a type admitting a sort.✦ A valid context is a list of declared types generated from the empty context by adjoining whenever for some sort .✦
Full reduction closes the contraction under every term constructor, including annotations and binder bodies.✦ Convertibility on terms is the smallest equivalence relation containing full reduction.✦ A normal term is a term admitting no reduction step✦; a weakly normalizing term is a term having a normal reduct, denoted .✦ A legal term in a context is a term occurring as either subject or expected type in a judgement ✦; system weak normalization is the property that every legal term in every valid context is weakly normalizing.✦
For a term and a family of term images for variables, capture-avoiding simultaneous substitution replaces free variables and acts beneath a binder using the lift that fixes index zero and shifts each inserted image.✦ For an index map , variable renaming acts recursively with the lifted index map fixing zero and sending to .✦ For a term , the single substitution sends zero to and to ✦; bound variable instantiation is .✦
Profiles and Actual Substitutions
For a term in a context and sets of sorts, the normal form sort profile and product output profile are the sets in (1). (1) A feasible profile is a nonempty set of sorts realized as by a normal term in a valid context.✦ A feasible product profile triple consists of three feasible profiles satisfying .✦
The signed primary profile graph has positive edges for proper inclusions between feasible profiles; each feasible product triple gives a negative edge and a positive edge .✦ A signed directed walk is a finite directed walk, allowing repetitions, whose parity counts negative edges modulo two; the empty walk has parity zero.✦ Write when such a walk exists, irrespective of parity.✦ A strongly connected component of the signed primary profile graph is the set of profiles mutually reachable with some fixed member of .✦
A saturated context tower is a sequence of valid contexts with prefixes of length , each next prefix adjoining a type that admits a sort. Every fixed-level expression having a sort at stage occurs as a declared type at arbitrarily late stages . Free tower variables use fixed levels. Index-to-level reversal and tower typing are defined by (2); the renaming acts on both subject and expected type. (2)
Context lookup assigns an index its declared type shifted into the full context.✦ A typed substitution is a family of terms such that for every lookup .✦ A tower typed substitution from a context into a tower is a family of term images satisfying the typed substitution condition with target .✦ An environment from into is a tower typed substitution together with a bit assignment .✦
Support and Candidate Interpretation
The support of a term in a context is either absent or a pair of a variable index and a parity. It is absent when . For a product whose profile belongs to , support follows the domain and reverses parity when ; otherwise it follows the codomain in , discarding support on the bound variable and decreasing surviving indices. A nonproduct whose profile belongs to has support when its variable head is , and absent support when it has no variable head.
For a bit and a bit sequence , the bit sequence extension has value at zero and at .✦ The chosen support bit of a term in a context is the bit equal to when , and equal to otherwise.✦
The recursive one-child interpretation of a term in a context under an environment into is a set of terms. Put . Unless both and the substituted tower profile belong to , this set is the upper candidate of typed strongly normalizing terms. When both profiles belong to , a product receives the raw product candidate formed from and the codomain interpretations for each term and bit ; here sends zero to and to . A nonproduct receives if it has no variable head or its head has bit , and the lower candidate if its head has bit . The normal form candidate interpretation of a term in a context under an environment into is the set of terms defined by (3). (3)✦
For sets and a direction bit , signed inclusion means for and for ; these directions are called positive and negative.✦ The compatibility condition on an optional support , a direction , a substitution and bit assignments is defined by (4), where is addition modulo two. (4)✦
The Claim
Theorem 1. Let , let be normal, and suppose for some . Let be valid, let be typed, and let be an environment from into . Take a bit assignment and a direction satisfying . With the actual composite images , the substitution comparison is (5)✦ For any context , terms and bit assignment , (6)✦
In the paper, the result reads: let be valid, let , and let be normal with , put and , and take typed substitutions and with bits whose images respect composition up to conversion, so that and the other images agree up to conversion; if the bits agree on every variable supported by both and and, whenever supports with parity , its bit is when and when , then at their common actual normal type.
What Is Checked
The comparison (5) is stated over typed substitutions into a saturated tower, normal types whose primary profiles reach , and compatible support bits, whereas (6) quantifies over arbitrary contexts, terms and bit assignments.