The Setting
A one-child interpretation assigns a set of terms to a type using actual variable images and a separate assignment of polarity bits. The comparison concerns a normal type before and after a typed substitution into another context.
A pure type specification consists of a set of sorts, an arbitrary axiom relation, and an arbitrary product-rule relation.✦ Its terms are variables, sorts, applications , annotated abstractions , and dependent products .✦ Named variables are used here; variable indices are de Bruijn indices, and contexts list the newest declaration first. The judgement uses the axiom, variable, weakening, product, abstraction, application, and conversion rules determined by .✦ A valid context for is a context obtained from the empty context by successive extensions by types having some sort in the preceding context.✦
Simultaneous substitution replaces each free variable by , lifting the substitution under binders to avoid capture.✦ Variable renaming replaces free indices by their images and also lifts under binders.✦ Bound-variable instantiation is the single substitution sending index zero to and index to variable .✦ Full reduction contracts to and is closed under every term constructor, including annotations and binder bodies✦; convertibility is its equivalence closure.✦ A normal term is a term that admits no reduction step.✦ A weakly normalizing term is a term that reaches a normal term in finitely many steps; its chosen normal form is .
Assume system weak normalization: every term occurring as a subject or as an expected type in a typing judgement in a valid context is weakly normalizing.✦ The normal-form sort profile in (1) records all possible sort witnesses. A feasible profile is a nonempty sort profile of a normal term in a valid context.✦ A feasible product profile triple consists of feasible profiles with , where (1) The product output profile of sets of sorts and consists of all sorts obtainable by a product rule with a domain sort in and a codomain sort in .
The primary signed graph has a positive edge for each strict inclusion of feasible profiles. Each feasible product profile triple gives a negative edge and a positive edge . A signed directed walk is a finite walk whose parity counts its negative edges modulo two; the empty walk has parity zero.✦ Write for the existence of such a walk, without specifying its parity.✦ A strongly connected component of the primary signed graph is a set consisting of exactly the profiles mutually reachable with one chosen member.✦ Fix such a ; a type is a type whose profile belongs to .
A saturated context tower is a sequence of valid contexts of length , each obtained from the preceding context by one typed extension. Every type typable at a stage, expressed with fixed free variable levels, is declared again beyond every prescribed stage. Translation between levels and indices at stage reverses indices below by and leaves larger indices fixed.✦ Tower typing means typing both translated terms in some .✦
A typed substitution is an assignment satisfying (2); here denotes the declared type of variable viewed in the full context, with the required index shifts.✦ A tower-typed substitution from a context to is an assignment of variable images satisfying (2) with as the target judgement.✦ (2)✦
Interpretation and Support
A polarity assignment is a map .✦ An environment for consists of a tower-typed substitution from and a polarity assignment .✦
Write for the recursive one-child interpretation. The tower profile of is the set of sorts typing its chosen normal form in the tower. When either or this tower profile lies outside , the interpretation is the upper tower candidate at . When both profiles belong to , a product is interpreted by the raw dependent product of the recursively interpreted domain and codomain: the terms whose application to each term of the domain candidate belongs to the corresponding codomain candidate, with the actual images and bits extended at the binder. For a nonproduct with variable head , the candidate is the upper tower candidate when and the lower tower candidate when ; a nonproduct without a variable head uses the upper candidate. The normal-form interpretation is defined by (3). (3)✦
The optional signed support of a type in a context is either absent, denoted , or a pair of a variable index and a parity bit. It is absent outside . Inside , a nonproduct has support when its head is variable , and absent support otherwise. For a product , if the domain profile belongs to , support follows the domain and reverses its parity; otherwise it follows the codomain, removing the bound variable from its support.
For a direction , signed inclusion is the relation between sets and specified in (4). Polarity assignments are compatible with a substitution at support in direction when the condition in (5) holds whenever ; absent support imposes no condition. The operation is addition modulo two. (4)✦ (5)✦
The Claim
Theorem 1. Let , with normal, and suppose that for some . Let be a valid context and a typed substitution. Take an environment for , a polarity assignment , and a direction . Suppose that are compatible with at in direction . With , the substitution comparison is (6)✦
In the paper, the result reads: for fixed typed actual images, the candidate of a type depends on the bits of its starting context only through its support, if any.
What Is Checked
The comparison (6) is stated over full reduction and typing for , a saturated context tower, the primary profile component , typed substitutions, and environments whose polarities satisfy the signed support condition.