The Setting
The relational diagonal construction tests data by formulas obtained from retained paths. A common probe takes a type parameter and observes a bundle containing a query parameter and a data point. Three tagged copies of probe elements supply the observations used to choose that parameter.
Fix a sort set . Terms have variables and sorts, applications, annotated abstractions , and dependent products .✦ Each application and binder has one of the mode labels , , and , denoting data to data, data to proof, and proof to proof.✦ Named variables below are subject to capture-avoiding substitution. An expression is an open term with one distinguished input; composition substitutes for that input. A nondependent arrow is a dependent product in mode whose codomain does not depend on its bound variable.
A positive data path is a finite sequence of data arrows with retained domain annotations and dummy arguments.✦ Its wrapped type , injection , and projection are given by (1); the empty path is the identity. Here denotes extension by annotation and dummy argument . (1)
A proof path is a finite sequence of positive and negative extensions, acting on formulas as in (2).✦ A positive extension retains a data domain ; a negative extension retains a formula . (2)✦
A data tail is a tuple consisting of a sort , a positive path , and encoding and decoding proof paths and .✦ Its carrier and its sending and reading operations are defined in (3). (3)
A retained data path is generated by the identity, positive extensions , and negative extensions .✦ The parity of a retained data path is the number of its negative extensions modulo two. The wrapped type , builder , and observation are the recursive operations in (4). A builder takes an open term at odd parity and a term at even parity; an observation takes a term at odd parity and an open term at even parity. Fresh bound variables do not capture the distinguished input of an open term. (4)
For odd paths , reencoding is the operation in (5). The open terms and are respectively evaluation and contravariant observation. (5)✦
A logical code is a choice of falsity and incoming and outgoing proof paths .✦ A quantifier code is a pair of proof paths .✦ Their implication and universal quantifier are (6); and will be the quantifier codes for elements and predicates, respectively. (6)
All logical notation below denotes the formula operations of in (7). A guarded universal quantifier with guard and body is a universal quantifier whose body is ✦; a finite disjunction is a disjunction associated to the right with final term . The negation of a formula is its implication to falsity.✦ Implication from falsity to itself gives the truth formula .✦ The conjunction of formulas and is the negation of the implication from to the negation of .✦ For formulas and , negating the conjunction of their negations gives their disjunction .✦ The logical equivalence is the conjunction of the implications in both directions; it expresses typed proof-term transformers in both directions.✦ Negating universal quantification over of the negation of gives the existential quantifier .✦ The logical conditional is the disjunction of and .✦ Polarity selection is the formula for and its negation for .✦ (7)
Double Channels and Finite Queries
A double channel is a pair of odd retained data paths.✦ Its carrier and iterates give the fourfold carrier , predicate code type , and parameter type of (8). (8)
Double channel evaluation , its bit test , the signed embedding , and signed recovery are defined by (9). (9)
A query index has the four-bit string of its binary digits, in increasing order of significance.✦ A query tag has nonzero index .✦ Iterated signed embedding and the tag formula are defined in (10), where is the length of the remaining string . For an input term denoted here by , write ✦ and . (10)
Iterated recovery is the open formula that equals at depth zero and has successor value .✦ For an odd payload path , the decoder , encoder , and tagged query are the operations in (11). (11)
The marking formula , encoded point , dummy parameter , and dummy test are defined by (12). (12)
A bundle is the term in (13). (13)✦
Access , the inner probe , and recovery access retain the dummy test in (14). The terms and are open terms. (14)
The structural realization of seven open formulas is the finite marked disjunction in (15). (15)✦
A common probe is a choice of a seed sort , an initial retained path of parity , odd raw and back paths , an even function path , a positive lifting path , and a data tail .✦ Put .✦ For a type parameter , the probe’s base type , raw type , parameter type , and single bundle type are given in (16). The common probe type is . Type parameters range over the positive wrapped sort .✦ The probe function type is the data arrow from the single bundle type to the tail carrier .✦ (16)
Probe specialization , observation , and uniform abstraction are defined by (17). The open term has the type parameter and bundle as distinguished inputs. (17)
Admissibility and Comparison
Fix odd logical and predicate paths . The shared observation channel is ✦; more generally a channel is any triple of odd paths.✦ Its logical, raw, and predicate types are , , and . The conversions , predicate builder , evaluation , and roundtrip are defined by (18). (18)
Roundtrip respect and predicate comparison are formulas given in (19). (19)
For a type parameter and query parameter , write for .✦ For a predicate of type , admissibility at query parameter is the formula in (20). Observational equivalence quantifies only over these predicates. (20)
The class predicate and class union use . Class queries and edge formulas are given by (21). The Boolean is identified with or . (21)
The pair predicate is the encoded formula in (22). Its existential quantifier uses the logical channel type. (22)✦
The truth marker , point parameter , bundle , and diamond observation are defined by (23). (23)
For a type parameter , query parameter , and probe of type , the probe section is the predicate on with body . The section pair query and element lift are defined in (24). (24)
For a predicate on , the predicate pullback is the predicate on obtained by evaluating after element lifting.✦ Its recovery and the uniform predicate probe are defined by (25). (25)
Put ✦ and . Probe order , element comparison , extensionality , and validity are the formulas in (26). (26)
A three-copy construction is a choice of odd source and first paths and inner and outer double channels .✦ Its first, middle, and final carriers at are , , and . For the shared probe take , , , and put , , . The tagged embedding is the expression in (27), for ; denotes its Boolean test. (27)✦
The inner and outer markers , observation , comparison , and tagged observational equivalence are defined by (28). The observation uses the uniform probe . (28)
Fix a labelled type term . The specialized base is ✦; write .✦ Observation invariance , class representation , and edge representation are the formulas in (29). Class indices range from to ; edge indices used below are and . (29)
The left-copy predicate , relational closure , and ordered family of seven structural formulas are defined by (30). (30)
The Definition
Definition 1. A relational code over is a common probe with odd logical and predicate paths , as in (31). (31)✦ An observation code over is a relational code with inner and outer double channels , as in (32). (32)✦ A specialized relational code over is an observation code with a labelled type term , as in (33). (33)✦ For logical code and quantifier codes , the chosen structural query parameter of is the term in (34). (34)✦
What Is Checked
These definitions are stated over labelled terms, retained data and proof paths, and the logical and quantifier codes, with the initial, raw, back, and function path parities specified by the common probe.