The Setting
Typed data channels package a dummy value with a parameter and a payload. An access observation combines a formula guard on parameters with a data callback into the inner channel. Its result is a formula in an ambient logical calculus.
Fix a pure type specification , with arbitrary axiom and product-rule relations. Terms have variables and sorts, application, annotated abstraction , and dependent products .✦ Labelled terms attach one of , , or to each application or binder, specifying data to data, data to proof, or proof to proof.✦ Erasure deletes these labels.✦ Named binders are used below; variable indices are de Bruijn indices, and contexts list the newest declaration first.
The typing judgment is . Contexts are valid when they arise from the empty context by adjoining types having a sort in the preceding context.✦ Full reduction contracts applications of annotated abstractions and acts in every annotation and binder body; labelled head contraction requires matching labels. Convertibility is the equivalence relation generated by this reduction.✦ A term is in normal form when it has no reduction step, and is weakly normalizing when a normal form is reachable from it. Write for the chosen normal form when it exists. For sets , the normal form sort profile, axiom profile, and product output profile are given by (1). (1)
A feasible profile is a nonempty profile of a normal term in a valid context.✦ A feasible product profile triple consists of feasible profiles with .✦ A labelled type is sorted at when for every .✦
The primary signed graph has positive edges from a feasible profile to a strict feasible subprofile and from to in each feasible triple ; its negative edges go from to in such triples.✦ Positive reachability allows a finite, possibly empty path of positive edges.✦ For a collection of profiles, an observation layer is a profile positively reachable from a nonempty with .✦ A direct observation layer for a collection of profiles is an observation layer for admitting a feasible product profile triple with .✦ A logical terminal profile for a collection is a profile admitting a triple with .✦
Let assign data or proof mode to variables. The mode discipline assigns each variable its mode in and gives sorts data mode. An application has its labelled result mode when its function has that mode and its argument has the labelled argument mode. An annotated abstraction or dependent product has a data-mode domain; under its binder, the variable has the labelled argument mode. The abstraction and its body have the labelled result mode, while the product and its codomain have data mode. Write or for these mode judgments. A data-only term is a labelled term with label at every application and binder.✦
Proof mode inhabitation, typed open proof transformation, and typed logical equivalence are the relations in (2). The temporary variable has proof mode. Equivalence concerns uniform typed proof-term transformers. (2)
A raw data callback from to is an open term satisfying and ; belongs to the ambient context.✦ Its instance substitutes for the distinguished variable without capture.✦ Open composition substitutes for that variable while preserving the common ambient context.✦
The nondependent labelled arrow is the dependent product with label , domain , and codomain independent of the bound variable.✦
The Logical Calculus and Paths
A fixed feasible witness family is a family of pairs of terms indexed by sets . At every feasible , the type is data-only with normal erasure and is sorted at , while and both terms have data mode.✦ A proof wrapper is a finite sequence of positive extensions by types and negative extensions by types , acting on types as in (3). (3) The proof wrapper application to a labelled type is the type specified recursively by (3).
A formed proof path is a sequence of steps beginning with the identity at its source profile and permitting restriction of its target to any subset. A triple permits a positive extension from to using . A triple permits a negative extension using when . Its parity counts negative steps modulo two; the negative-step presence test records whether there is any such step.
A logical setup for consists of and typed open proof transformers between the witness types of any two terminal profiles, together with a feasible triple with and even proof paths and . At each direct observation layer , its quantifier route chooses a triple and even proof paths from to and from to .✦ The logical operation code consists of the falsity type and the two fixed proof wrappers.✦ Its connectives are those of (4); all connectives below belong to this code. (4) Logical implication between labelled formulas is the outgoing proof wrapper applied to the proof-to-proof arrow from the incoming wrapper applied to to . Logical negation is implication from the labelled formula to the falsity type of . Implication from the falsity type of to itself gives logical truth . Logical conjunction of labelled formulas is the negation of implication from to the negation of , with all operations taken in . Negating the conjunction of the negations of labelled formulas gives their logical disjunction , with all operations taken in . The logical conditional with guard and branches is the disjunction of and , with all operations taken in .
A mode-preserving context embedding is a renaming of variables into a valid context that preserves their types and modes.✦ Such embeddings transport witness families and logical setups, including the fixed proof paths and quantifier routes. A witness continuation for a term is the condition that, after every mode-preserving context embedding and at every terminal profile , a typed open proof transformer from the renamed to the renamed entails proof mode inhabitation of that .✦ A term has stable witness extraction when, after every mode-preserving context embedding, a witness continuation for its image entails proof mode inhabitation of that image.✦ An interpretable formula in is a data-mode term sorted at with stable witness extraction.✦ A stable formula family over is a raw callback whose instances are interpretable formulas after every mode-preserving embedding and every data-mode input of the renamed type .✦
A positive data path is a finite sequence of positive extensions retaining an annotation and dummy value at each step.✦ Its formation starts with the identity, permits target restriction, and extends from to along using .✦ A data tail is a sort with a positive data path and encoding and decoding proof wrappers.✦ It is formed with endpoint when , the profile is nonempty, its positive path is formed from to , and its encoding and decoding proof paths go from to and back with even parity, with a negative step in the decoding path.✦ Write for its carrier, with formula transport operations and .
A retained data path is a finite sequence generated by the identity, positive extensions retaining a domain and its dummy value, and negative extensions retaining a data tail.✦ Formation permits target restriction; a positive extension along retains , and a negative extension along uses a formed tail ending at . Positive extensions preserve parity and negative extensions reverse it. The wrapped type , builder , and observation have the recursive forms in (5), where is a retained domain, its dummy value, and a retained data tail, with capture avoided under the displayed binders. (5)
For an odd path , its observation and contravariant observation callbacks are the open terms in (6). (6)
Renaming a retained path or proof wrapper renames its fixed annotations and values, preserving the sequence of steps and its parity.
Bundles and Access Observations
A double data channel is a pair of odd retained data paths.✦ It is formed from through to when is formed from to and from to .✦ Subscripts and on builders and observations refer to these paths. For a type , a dummy value , a parameter , and a payload of type , the bundle branch predicate and source data bundle are defined by (7). (7)
For a type , a guard callback , a channel value , and a raw data callback , the outer access predicate , access probe, and bundle access observation are given by (8). (8)
Write for the channel carrier. For a nonnegative integer , its iterated carrier and fourfold carrier, together with the predicate code type and parameter type , are specified in (9). (9)
The bottom predicate code , dummy parameter , and dummy predicate are the terms in (10). The open dummy parameter test is .✦ (10)
For , let list binary digits zero through three, in that order.✦ A tag has nonzero query index .✦ Write for the one-stage signed embedding, for the one-stage recovery predicate, and for the bit predicate. The iterated signed embedding, indexed by a finite list of binary digits, and query-tagged embedding are specified by (11), where denotes the empty list, denotes the length of , and prefixes the digit to the list ; the tagged variable embedding is . (11)
The iterated recovery predicate and tag predicate satisfy (12), where and ; write for . (12)
Let be an odd retained data path. For a type , a payload of type , and a predicate code of type , the tagged payload encoder for uses the encoding predicate in (13), and its payload decoder uses the decoding callback in the same display. The decoding map is the open callback .✦ (13)
For a tag and data-mode terms of type , the marking predicate and data point predicate define the encoded data point in (14). (14)
The query predicate , inner probe predicate , and inner observation probe are defined by (15). (15)
The inner probe callback is .✦ For a raw data callback from to , its composition with the inner probe callback is the parameter access callback ; recovery access is the observation in (16). (16)
The Claim
Theorem 1. Fix a logical setup and a formed double channel with initial profile . Let have data mode, be sorted at , and satisfy for some sort . Let be data-mode terms of type , let be a stable formula family over , and let be a raw data callback from to . Suppose , , and . The bundle access law is (17). (17)✦
Let have data mode and be sorted at , let be an odd retained data path, and let be a raw data callback from to . Let be a data-mode term of type , and data-mode terms of type . Suppose and for some sorts , and suppose . The recovered access law is (18). (18)✦
What Is Checked
The two laws are stated over labelled typing and the data and proof mode discipline, with formed retained paths under a logical setup; their hypotheses concern stable formula families, raw data callbacks, and proof mode inhabitation of the displayed guards.