The Setting
Pairing combines a predicate and an observation in the relational coding of a pure type system. The observations range over three tagged copies of a logical probe type. Fix a pure type specification , with arbitrary axiom and product-rule relations, a context , and a mode assignment taking values in data and proof.
Terms have applications, annotated abstractions , and dependent products , with labels for data to data, data to proof, or proof to proof. Typing is written ; the mode discipline separately assigns modes to variables and respects the argument and result modes of each label. Annotations and product types have data mode. Named variables below use source notation for de Bruijn terms in newest-first contexts. Full reduction includes annotations and binder bodies, and conversion is its equivalence closure. A valid context is a context obtained from the empty context by adjoining a type whenever for some sort .β¦ A normal form is a term admitting no one-step reduction.β¦ A term is weakly normalizing when a finite sequence of reductions reaches a normal form.β¦ Write for the chosen full normal form of when one exists, and for a fixed arbitrary term otherwise.β¦
The normal form sort profile is the set of all sorts for which .β¦ A feasible sort profile is a nonempty set of sorts for which some valid context and some normal form satisfy .β¦ The axiom profile is the set of sorts with .β¦ For sets of sorts, the product output profile consists of the sorts for which for some and .β¦ A feasible product profile triple consists of three feasible sort profiles satisfying , with the domain profile, the codomain profile and the product profile.β¦
The primary signed graph on sort profiles has positive inclusion edges between feasible profiles when . Each feasible product profile triple gives a negative domain edge and a positive codomain edge . Positive reachability is reachability by a finite, possibly empty path consisting entirely of positive edges.β¦
A labelled term is data-only when every application, abstraction and dependent product in it has the data-to-data label.β¦ Label erasure removes all argument and result labels from a labelled term, preserving its variables, sorts and term constructors.β¦
Fix a logical calculus and quantifier routes . Its implication and universal quantification use fixed incoming and outgoing proof wrappers, with a proof-to-proof arrow for implication and a data-to-proof dependent product for quantification. Write for its logical connectives, and for its quantifiers. A proof-mode inhabitant of a formula is a term with in proof mode.β¦ A typed open transformer is a proof-mode term with , where the fresh input has proof mode.β¦ Typed formula equivalence between formulas and is the relation defined in (1). (1)β¦ For a collection of sort profiles, the observation layers are the profiles positively reachable in the primary signed graph from a nonempty axiom profile with .β¦ A direct observation layer is an observation layer for which some form a feasible product profile triple .β¦ A logical terminal profile is a profile for which some form a feasible product profile triple .β¦ A labelled type is sorted at a profile in when for every ; it may also have sorts outside .β¦ A fixed feasible witness family is a choice of a type and a value at every sort set . At every feasible profile , the type is data-only, its erasure is a full normal form, it is sorted at in , and , with both and in data mode.β¦ A formed proof wrapper path is a proof wrapper path constructed from an even identity path at its source profile by the permitted target restrictions and extensions.β¦ A feasible product profile triple extends a path ending at positively to using the fixed witness type at , whereas extends it negatively using the fixed witness type at when , reversing parity. The falsity formula of is the type selected at its logical base profile by its fixed feasible witness family.β¦
Tagged Observations and Structural Queries
A specialized relational coding consists of a three-copy observation system and a chosen type .β¦ Its underlying relational system has a uniform probe type , an initial data path , and a shared channel with logical, raw, and predicate paths , all three of odd parity. A retained data path is a finite succession of positive and negative wrapper steps; its parity counts negative steps modulo two.β¦ Write a path applied to a type for its wrapper type. The specialized base type , logical probe element type , and channel predicate type at a type are given in (2). The tagged observation type is the carrier obtained from by the inner and outer double channels, each consisting of two odd paths.β¦ Assume the probe and channel formation conditions, and the specialized shape conditions: has the probeβs seed sort in and has data mode, , the outer second path is , and the outer first path applied to the middle copy carrier is .β¦ (2) A positive data path is a finite succession of steps retaining a domain type and a dummy argument at each step; its wrapper type is an iterated data-to-data arrow. Its injection forms constant annotated abstractions over those domains, and its projection applies to the retained dummy arguments. A formed positive data path is a positive data path constructed from the identity at its source profile by the permitted target restrictions and extensions.β¦ A feasible product profile triple extends a path ending at positively to , retaining the fixed witness type and value at . A data path tail consists of a sort, a positive data path and fixed encoding and decoding proof paths; its carrier is the positive wrapper of that sort. Encoding applies the encoding proof wrapper and then the positive injection, while decoding takes the positive projection and then applies the decoding proof wrapper. A data path tail ending at is formed when its sort satisfies , its axiom profile is nonempty, and its positive path runs from to . Its encoding and decoding proof paths run respectively from the logical base to and back with even parity, and the decoding path contains a negative step. A formed retained data path is a retained data path constructed from the identity at its source profile by the permitted target restrictions and extensions.β¦ A feasible product profile triple extends a path ending at positively to using the fixed witness type and value at , whereas together with a formed data path tail ending at permits a negative extension to , reversing parity. A formed double data channel from through to consists of a formed first odd path from to and a formed second odd path from to .β¦
For a type , a channel predicate , and a logical element , channel evaluation observes along the predicate path at , against the raw reencoding of .β¦ Reencoding observes along the source path and builds along the target path.β¦ The channel roundtrip reencodes a logical element into the raw channel and back.β¦ For a predicate body on logical elements at a type , the encoded predicate is the predicate path builder applied to the body after raw-to-logical reencoding.β¦ Subscripts on evaluation are omitted at . Data path observation of a wrapped term against a test substitutes that term into the test at the identity path. At a positive step it applies the term to the retained dummy argument and continues along the remaining path; at a negative step it applies the term to the test built along the remaining path and decodes the result through the data path tail.
The three tagged embeddings of into are written , for copy indices . They reencode the logical wrapper into the raw wrapper, then embed through the inner and outer channels; the inner embedding bit is true exactly at index , and the outer embedding bit exactly at index . Let be the corresponding marker observations, with the inner marker recovered through the outer channel. For , let be its uniform predicate probe. The observation recovers the payload of through both channels and tests it against .β¦ Tagged observational equivalence between observations is the formula in (3). (3)β¦ Double channel evaluation against a predicate body builds that body along the first odd path and observes the supplied element against the result along the second odd path.β¦ The encoded bit observation in a double channel is double channel evaluation against the constant truth predicate.β¦ Signed payload recovery in a double channel is the logical conditional that returns its double channel evaluation when its encoded bit observation holds, and the negation of that evaluation otherwise.β¦ Signed payload embedding of an element builds along the second odd path the observation predicate of that element along the first path, retaining that predicate for a true bit and negating it for a false bit.β¦
The probe order observation observes along the logical path at against .β¦ For predicates , predicate equivalence is the formula comparing their channel evaluations at every .β¦ Probe element equivalence for elements , predicate extensionality for , and order validity for are the formulas in (4); each quantifier over predicates uses , and each quantifier over elements uses . (4) The section pair query at a type , parameter , probe and element is query of against the relational pair of the section predicate of and .β¦ The relational element lift of at and is the logical-path encoding whose predicate on a probe is the section pair query at .β¦ The predicate pullback of along this lift is the encoded predicate on logical elements whose membership formula is channel evaluation of at the relational element lift of .β¦ Predicate pullback recovery tests a single-bundle argument by recovery access in the probe double channel, using the predicate path and the predicate pullback of as a function of the data parameter.β¦
For a predicate over and a copy index , observation invariance , class representation , edge representation , and relational closure are the formulas in (5). Here and , and the left copy predicate is .β¦ (5)
The structural parameter is the query realization, using the constant truth marker, with branches in that order.β¦ Write for the structural query at tag of against .β¦ An admissible predicate is a channel predicate satisfying the actual roundtrip and structural guard in (6). The specialized observational relation tests precisely this guard.β¦ (6) Roundtrip invariance of a channel predicate means that its evaluations at and are logically equivalent for every .β¦
Response and Pairing
For observations , the equivalence class predicate and class union predicate are encoded predicates defined using in (7). For an observation and a copy index , the class query is the formula obtained by applying structural query to .β¦ The left and right tagged edge predicates require their respective class queries and the query on the class union. (7)
The specialized pair predicate of and is the encoded predicate with membership formula (8). Its existential quantifier uses . (8)β¦
For a uniform probe , a structural parameter , and an observation , the diamond observation observes the specialization of at along the probeβs even function path against the test that applies its input to the relational argument bundle of and and decodes the result through the data path tail.β¦ This specialization is the data-mode application of to the positive wrapper injection of along the probeβs lifting path.β¦ That bundle combines the dummy observation, , and the point encoding of the raw reencoding of .β¦ Specialize this observation to .β¦ For a uniform probe , predicate extraction is the channel predicate over defined in (9). (9)β¦
The response predicate is the formula (10); its quantifiers over observations use . (10)β¦
The Claim
Theorem 1 (Lemma 51). Let be a data-mode term with . For data-mode terms and , assume a proof-mode inhabitant of . Then (11) holds. (11)β¦ For data-mode terms and , the law (12) holds without a response hypothesis. (12)β¦
In the paper, the result reads: under , set ; for every there are proofs of and .
What Is Checked
The claims are stated over labelled typing and the data and proof mode discipline in the fixed logical calculus, with quantifier routes and specialized relational coding satisfying the probe, channel, seed-sorting and copy-shape conditions stated above.