The Setting
Applying a term of type to an argument gives the expected type . Observation layers concern the sort profiles of these types and the signs assigned to the domain and codomain positions of a product.
Let be a pure type specification, with arbitrary axiom and product-rule relations. Its terms are variables, sorts, applications , annotated abstractions , and dependent products .✦ We use named notation for terms whose unnamed variables are de Bruijn indices, with zero referring to the nearest binder. Renaming acts on free variables and is lifted under binders; simultaneous substitution is capture-avoiding. Bound variable instantiation substitutes for the bound variable and removes that binder.✦
Full reduction contracts to and is closed under every term position, including annotations and binder bodies.✦ Full convertibility is the smallest equivalence relation on terms containing full reduction.✦ A term is normal if it admits no full reduction step, and weakly normalizing if it reduces by full reduction in finitely many steps to a normal term. Write for the chosen full normal form when one exists, with a fixed fallback otherwise.✦
Typing uses the axiom, variable, weakening, product, abstraction, application and conversion rules of . Contexts are newest-first finite lists. A valid context for is a newest-first finite list obtained from the empty context by successive extensions of a context with a type whenever for some sort .✦ A legal term in is a term occurring as either the subject or the expected type of a typing judgement in .✦ System weak normalization means that every legal term in every valid context is weakly normalizing, including both subjects and expected types.✦
Profiles and Observation Layers
The normal form sort profile of a term in a context is the set of all sorts typing in .✦ The axiom profile of a sort is the set of its axiom successors, and the product output profile of profiles and is the set of every output allowed by a domain sort in and a codomain sort in : (1) A feasible profile is a nonempty set from (1), for some valid context and normal term .✦ A feasible product profile triple is a triple of feasible domain, codomain and product profiles satisfying ; we write for this condition.✦
The primary graph has profiles as vertices and signs and , denoting positive and negative edges. Its positive edges are strict inclusions with and both profiles feasible, and codomain edges from feasible triples . Its negative edges are the domain edges from those triples. Write for a primary edge of sign .
A signed directed walk is a finite walk, allowing repetitions, whose sign is the parity of its number of negative edges; the empty walk has sign .✦ Write for such a walk in graph , and for a walk using only positive edges. Directed reachability ignores the sign.✦ A strongly connected component is a set containing a vertex such that its members are exactly the vertices reachable from and from which is reachable.✦
An observation layer for a set of profiles is a profile positively reachable in the primary graph from a nonempty axiom profile whose singleton sort belongs to . The set of observation layers is (2)✦ On the layers in (2), the secondary graph retains every positive primary edge. It has a negative edge whenever holds and all three profiles belong to . These are exactly its edges.
A direct layer for a set of profiles is an observation layer occurring as the domain profile of a feasible triple whose codomain and product profiles lie in : (3) An active layer for a set of profiles is a profile that reaches a direct layer for through secondary edges. A plain layer for a set of profiles is a profile that reaches direct layers for by secondary walks of both parities, with possibly different endpoints. A free layer of sign for a set of profiles is a nonplain profile with a secondary walk of sign to a direct layer for .✦ We write , and for these conditions, using the direct layers of (3).
Tower Types and Application Frames
A saturated context tower is a family of valid contexts of length , each extending the preceding context by a type having a sort there. Every fixed-level type having a sort at stage is declared again at stages arbitrarily far beyond . Free names in the tower have fixed levels. Their translation to indices at stage is the renaming for , with otherwise.✦
Tower typing and the tower normal form profile are given by (4) A normalized active type in is a normal term having some sort in and an active profile .✦ An active application key for is a product presentation with a normal argument for which is active.✦ Under system weak normalization its target term is (5)✦
The Claim
Theorem 1. Let be a pure type specification and a set of profiles. If is plain and is a secondary edge, then (6) holds: (6)✦ If and are free with signs and , respectively, and is a secondary edge, their signs satisfy (7), where is addition modulo two: (7)✦ Let be a saturated context tower. Suppose for some sort and . There is a profile satisfying (8): (8)✦ Suppose further that is system weakly normalizing, is a strongly connected component of the primary graph, and is an active application key for a normalized active type . If and lie in and is active, then (9) holds: (9)✦
What Is Checked
The layer claims are stated over the secondary graph for an arbitrary specification and set ; the frame claims concern tower typings of both the product and its argument, with the component and activity hypotheses required for (9). Under system weak normalization, the target construction in (5) yields a normal term having a sort in and an active profile.