The Setting
The relational diagonal construction has source, left, and right tagged copies of each probe element. Class membership and incidence between tagged observations are formulas of its ambient logical calculus.
Fix a pure type specification , a valid context , and a mode assignment . The axiom and product-rule relations are arbitrary. Terms have annotated abstractions and dependent products, with application and binder labels specifying data and proof modes. The mode judgment assigns data mode to , and assigns proof mode; annotations and both parts of a product have data mode. Data typing and proof-mode inhabitation are the assertions in (1). (1)
A feasible profile of the pure type specification is a nonempty set of all sorts typing a normal type in a valid context; normality uses full reduction, including annotations and binder bodies.β¦ A feasible product triple has three feasible profiles and , where consists of all with for some , . The normal form sort profile is the set of all sorts for which , where is the chosen full normal form when is weakly normalizing.β¦ The axiom profile is the set of sorts with .β¦ The primary signed graph has feasible sort profiles as vertices, positive inclusion edges from to each feasible proper subset , and, for every feasible product triple , a negative edge from to and a positive edge from to .β¦ Positive reachability in a signed graph is reachability along a finite, possibly empty path consisting entirely of positive edges.β¦ An ambient logical calculus has a fixed collection of feasible profiles, domain, base, and product profiles forming a feasible product triple , an even incoming proof path from to , and an even outgoing proof path from to . The existential quantifier of the logical calculus is β¦; formula equivalence in is the conjunction of the implications in both directions. These equivalences mean uniform typed proof-term transformers. A typed open transformer from to in the logical calculus is a proof-mode term of type in the context extended by a proof-mode variable of type .β¦ The calculus fixes a witness type and inhabitant at every feasible profile , with for every and , and both have data mode under . Each is data-only and its label erasure is in full normal form; there are typed open transformers between the witness types at any two terminal profiles. For the fixed collection of profiles of , a terminal profile is a feasible profile belonging to a feasible product triple with .β¦ An observation layer is a profile positively reachable in the primary signed graph from a nonempty axiom profile with .β¦ A direct observation layer of is an observation layer for which a feasible product triple has .β¦ A quantifier route for a domain profile and logical base chooses a feasible product triple , an even incoming proof path from to , and an even outgoing proof path from to .β¦ The falsity type of is its witness type at , and supplies a quantifier route for every direct observation layer, including the quantifiers and used here.
A mode-preserving context embedding is a variable renaming into a valid context which assigns each renamed source variable its renamed type and preserves its mode.β¦ A witness continuation for a formula of is the condition that, under every mode-preserving context embedding and for every terminal witness type, a typed open transformer from the renamed to that witness type entails proof-mode inhabitation of the witness type.β¦ Stable witness extraction for a formula of is the condition that a witness continuation yields proof-mode inhabitation of under every mode-preserving context embedding.β¦ An interpretable formula of is a data-mode term sorted at every sort of the logical base profile and admitting stable witness extraction.β¦ Write for renaming along ; subscripts on types and operations transport all their fixed parameters as well.
Observations and Structural Queries
A specialized relational coding fixes a chosen type and a three-copy observation system .β¦ The underlying relational coding has a common probe carrier and a shared observation channel with logical, raw, and predicate paths , each of odd parity. A retained data path is a finite succession of positive and negative type wrappers from the identity; its parity counts negative extensions modulo two.β¦ The raw path is shared with the probe. The inner and outer double channels each consist of two successive odd retained data paths; let denote their carrier operations and the two outer paths. Writing for a pathβs action on a type, the specialized base type, probe element type, observation type, and two predicate types are defined in (2); is the probeβs initial path. (2)
A positive data path is a finite succession of positive extensions from the identity, each retaining a domain annotation and a fixed dummy argument.β¦ A data path tail consists of a sort, a positive data path from that sort, and fixed encoding and decoding proof paths.β¦ Its carrier is the positive wrapper of the sort; encoding first follows the encoding proof path and then the positive injection, while decoding first takes the positive projection and then follows the decoding proof path. The data path builder along a retained path returns its argument at the identity and adds a constant data abstraction at a positive extension. At a negative extension it abstracts over the inner wrapped type, observes the bound input against the supplied argument, and encodes the resulting formula through the tail. Data path observation along the identity substitutes the wrapped input into the supplied formula body. At a positive extension it applies the input to the retained dummy argument before continuing along the inner path; at a negative extension it applies the input to the argument constructed by the inner data path builder and decodes the result through the tail.
For a probe element and a tag , the tagged copy is the observation obtained by reencoding from the logical path to the raw path and embedding it in the inner and outer channels with respective bits and .β¦ For , let and be the recovered inner and outer marker formulas. For , the observation recovers the payload through these channels against the uniform predicate probe for .β¦ Tagged observational equivalence between observations is the formula in (3). (3)β¦
The signed payload embedding in a double channel builds along its second path from the observation of the payload along its first path, using that observation when the bit is true and its logical negation when the bit is false.β¦ Double channel evaluation observes an input along the second path against the data path builder along the first path applied to the supplied formula body.β¦ The encoded bit observation in a double channel is double channel evaluation against the constant truth body.β¦ The outer marker is this bit observation on the outer channel at the middle copy type.β¦ Signed payload recovery is the logical conditional whose guard is the encoded bit observation, whose true branch is double channel evaluation against the supplied body, and whose false branch is its logical negation.β¦ The inner marker recovers the inner bit observation through the outer channel.β¦ The logical conditional with guard and branches and is the disjunction of conjoined with and the negation of conjoined with .β¦
Channel evaluation observes a predicate along the predicate path against the raw reencoding of . At base , write for the same operation. The probe order observation observes along the logical path against the uniform predicate probe for .β¦ Probe element equivalence on is the relation in which two probe elements have equivalent order observations for every β¦, while predicate equivalence on is the relation in which two predicates have equivalent evaluations at every .β¦ The extensionality condition for a predicate is the requirement that respect probe element equivalence.β¦ The validity condition for a probe element is the requirement that respect predicate equivalence.β¦
For a formula body , write for the channel predicate with that body at the indicated base type. The left copy predicate has base .β¦ For , the observation invariance, class representation, edge representation, and relational closure properties of are defined in (4). (4)
The structural parameter is the probe double-channel realization with a constant truth marker and seven branches, in order from (4). Let be the structural query of the parameter at index , instantiated with .β¦ The channel roundtrip sends to the raw channel and back to the logical channel.β¦ Roundtrip invariance and the actual specialized admissibility guard are defined in (5). (5)
The specialized observational relation on is the relation that tests exactly the predicates admitted by the guard in (5): (6)β¦
The equivalence class predicate and class union predicate are channel predicates at base formed from (6), with the bodies in (7). The coded class predicate selects the class query tag , with numbered ; the coded edge predicate uses edge query tag or . (7)
The Claim
Theorem 1. Assume that is formed relative to : its probe, shared observation channel, and inner and outer double channels have their prescribed path formations, its chosen type has data-mode typing at the sort fixed by its probe, and its carrier identities are , , and .β¦ Every observation argument or has data typing at in . In the elimination rules, is an interpretable formula.
For , class introduction and elimination have the forms (8) and (9). In the elimination rule the continuation ranges over every mode-preserving context embedding and every data term in its target; denotes the tagged copy formed there. (8)β¦ (9)β¦
For , edge introduction and elimination have the forms (10) and (11), with the same data typing and continuation requirements. (10)β¦ (11)β¦
In the paper, the result reads: for , and for .
What Is Checked
The rules are stated over the formed specialized relational coding and its logical calculus, using the labelled typing and mode discipline of (1), the guarded class and edge constructions of (7), and stable witness extraction for their elimination targets under mode-preserving context embeddings.