The Setting
The observational relation compares data through predicate evaluations in a logical calculus. A formula selects the predicates to be tested. Channel rounding sends a logical value through a raw channel and then back to its logical channel.
Fix a pure type specification , with arbitrary axiom and product-rule relations. Terms are variables, sorts, applications, annotated abstractions , and dependent products .✦ Writing for data mode and for proof mode, labelled terms attach the argument and result modes , , or to each application, abstraction and product.✦ Bound names below denote terms whose variables use de Bruijn indices; contexts list the newest declaration first. Label erasure deletes the labels.✦
The typing judgment uses the axiom and product rules of , variable introduction and weakening, abstraction and application, and conversion.✦ For labelled terms, application and abstraction use the label of their product type. Full reduction contracts by capture-avoiding substitution and reduces every annotation and binder body; labelled contraction requires matching labels. Convertibility is the equivalence relation generated by these steps. A valid context is a context obtained from the empty context by adjoining a type having some sort in the preceding context.✦
A mode assignment gives each variable its mode. Sorts have data mode. An application has the result mode of its label when its function has that result mode and its argument has the argument mode of the label. An abstraction has a data-mode annotation and a body of its result mode under extension by its argument mode. A dependent product has data mode when its domain has data mode in the original mode assignment and its codomain has data mode under extension by the argument mode of its label. A data-only term is a term with label at every constructor.✦
Profiles and the Logical Calculus
A weakly normalizing term is a term that reaches a term with no full step in finitely many steps.✦ For a weakly normalizing term , write for its chosen normal form. The normal form sort profile, axiom successors and product outputs are the sets in (1): (1) A feasible profile is a nonempty set for a normal term in a valid context .✦ A feasible product profile triple consists of feasible profiles with .✦ A labelled type in context is sorted at a profile when for every .✦
Fix a collection of profiles. In the primary signed graph, proper restriction between feasible profiles is positive. A feasible triple gives a negative edge from to and a positive edge from to . An observation layer is a feasible profile reachable by a finite, possibly empty, positive path from a nonempty with .✦ A direct observation layer is an observation layer admitting a feasible triple with .✦ A logical terminal profile is a feasible profile admitting a feasible product profile triple with codomain and with its domain and output in .✦
A fixed feasible witness family chooses a type and value at every feasible profile . The type is data-only, is normal, and is sorted at ; both and have data mode, and .✦ A typed open proof transformer is a proof-mode term with , where is weakened into the extended context and has proof mode.✦ Proof-mode inhabitation and typed logical equivalence have the meanings in (2): (2)
A mode-preserving context embedding from a context into a valid context is a variable renaming that preserves each variable’s renamed type and mode.✦ Renaming and simultaneous substitution avoid capture by fixing a newly bound variable and shifting the images of older ones; instantiation substitutes for the newest variable and lowers the older indices. A witness continuation for is an operation that, after every mode-preserving context embedding and at each logical terminal profile , takes a transformer to proof-mode inhabitation of .✦ Stable witness extraction for means that, after every embedding into a context with mode assignment , a witness continuation for yields .✦
An ambient logical calculus has the witness family and transformers between its witness types at any two terminal profiles. Its domain , base and output belong to and form a feasible triple . A formed proof path is a path that starts with the identity at a set of sorts and is built from target restrictions to arbitrary subsets and positive and negative extensions along feasible product profile triples; is even when its number of negative extensions is even. Fix even proof paths from to and from to . A quantifier route at a direct observation layer is a feasible triple with domain , together with even proof paths from to its codomain and from its output to ; choose one at every direct observation layer.✦ An interpretable formula is a data-mode term sorted at and admitting stable witness extraction.✦ A stable formula family over a type is a one-variable open term whose instance at every data-mode argument , after every embedding , is an interpretable formula for the transported calculus.✦ All witness types, values and paths are renamed along the same embedding.
Retained Paths and Guarded Observation
A proof wrapper is generated from the identity by positive and negative extensions.✦ For a domain witness type in a positive extension and a codomain witness type in a negative extension, application is given by (3), where is the nondependent labelled product with label : (3)✦ A negative extension requires the preceding target and new output to lie in .
A positive data path is a path that retains a domain type and its chosen dummy value at each positive extension.✦ Its formed paths start with the identity at , allow target restriction from to any subset, and extend from to along a feasible triple using .✦ A data tail over consists of a sort , a positive data path, and encoding and decoding proof wrappers.✦ It is formed at a target when , is nonempty, its positive path is formed from to , and its encoding and decoding paths are formed from to and back with even parity, with a negative step in the decoding path.✦ A retained data path is a path generated by the identity, positive extensions retaining domain types and their chosen dummy values, and negative extensions retaining a data tail.✦ Its formed paths start with the identity at and allow target restriction. A positive extension follows a feasible triple from to , retaining ; a negative extension follows a feasible triple using a formed tail ending at . Parity counts negative extensions modulo two.
For a retained data path and a type , write for the wrapped type. For a term of type and a one-variable observation callback , write for its builder and for observation. The identity returns , returns , and substitutes into the distinguished input of , respectively. A positive step forms a data arrow into the preceding wrapped type; its builder is a constant data abstraction, and observation applies to the retained dummy value before continuing. A negative step forms a data arrow from the preceding wrapped type to its tail carrier. Its builder abstracts over the preceding wrapped type and sends the inner observation through the tail; observation applies to the inner builder and reads through the tail. For odd paths , reencoding uses the observation term with one free variable in (4): (4)✦
The logical operations of use falsity and its fixed incoming and outgoing proof wrappers and . Their definitions are (5): (5) A quantifier route has incoming and outgoing wrappers defining the universal and guarded universal formulas in (6): (6) Wrappers under binders are renamed into the extended context, retaining their annotations and step signs. The guard implication callback is the logical implication from the open guard to the open body , with the logical operations renamed under their common binder.✦
An observation channel consists of odd retained paths .✦ Formed channels have paths from to , from to , and from to , respectively, relative to .✦ Their types and operations are (7): (7) Here is the logical channel type. Wrapping along the raw path gives the raw channel type .✦ The type is the channel predicate type. The map is raw channel encoding. The map is logical channel encoding. The predicate evaluation callback at is the open term that evaluates the newly bound predicate at over , with the channel, type and element renamed under the predicate binder.✦
For a stable formula family over , a quantifier route at and data-mode terms , the observation relation is the guarded comparison in (8). The pointwise observational comparison at and is the encoded logical equivalence between their predicate evaluation callbacks, with logical operations renamed under the predicate binder.✦ (8)✦ For a quantifier route at , a stable formula family over and a channel predicate , the roundtrip invariance formula and the admissible predicate formula are defined by (9): (9) The roundtrip invariance callback of is the encoded logical equivalence between its evaluation at the newly bound element and its evaluation after that element’s channel roundtrip, with the parameters renamed under the element binder.✦
The Claim
Theorem 1. Let be an ambient logical calculus and let have formed observation channels from through . Let have data mode and be sorted at . Choose a quantifier route at and a stable formula family over .
For every data-mode term , reflexivity is (10): (10)✦ Let have data mode and type in , and suppose . Symmetry is (11): (11)✦ Let have data mode and type in . Suppose both and are inhabited in proof mode. Transitivity is (12): (12)✦ Choose also a quantifier route at and a stable formula family over . For every data-mode term , roundtrip relatedness is (13): (13)✦ Let have data mode and type in , and suppose and are inhabited in proof mode. The congruence law is the typed logical equivalence in (14): (14)✦
What Is Checked
The claims are stated over labelled typing and the mode discipline, with formed retained channels, an ambient logical calculus and stable formula families; their inhabitation and equivalence conclusions use proof-mode terms and uniform typed open proof transformers. Renaming along a mode-preserving context embedding preserves the witness family’s sorting, typing, normality and modes, and transports the logical calculus and its quantifier routes while preserving their profiles and feasible product profile triples.