The Setting
Relational coding compares data predicates through the formulas obtained by observing logical elements. Its structural queries concern invariance under observation, the representation of tagged classes and edges, and a guarded closure condition. The parameter in this item is a data term assembled from those seven conditions.
Fix a pure type specification , a context , and a mode assignment to its variables. The axiom and product-rule relations are arbitrary. Terms have annotated abstractions and dependent products ; their labels distinguish data and proof arguments and results. Write when and has data mode, and use for proof mode. Conversion uses full reduction, including annotations and binder bodies. Named binders below correspond to de Bruijn indices in newest-first contexts. A full normal form is a term with no one-step reduct, including reductions in annotations and binder bodies.✦ A term is weakly normalizing when a finite sequence of reductions, possibly empty, reaches a full normal form.✦ Write for the unique full normal form of when it exists, with a fixed arbitrary choice otherwise.✦ A valid context is obtained from the empty context by adjoining a type whenever for some sort .✦ The normal form sort profile of a term is the set of all sorts for which .✦ A feasible sort profile is a nonempty set of sorts realized as by a full normal form in a valid context .✦ The axiom profile of a sort is the set of sorts with .✦ For sort sets , their product output profile consists of the sorts for which for some and .✦ A feasible product profile triple consists of feasible sort profiles with ; , and are its domain, codomain and product profiles.✦ The edges of the primary profile graph are exactly the positive edges from a feasible profile to a feasible proper subset , and the negative edges from to and positive edges from to supplied by feasible product profile triples .✦ Positive reachability in a signed graph means reachability along a finite sequence of positive edges, allowing the empty sequence.✦
Proof-mode inhabitation of a formula is the condition in (1). A typed open transformer from to is a term with in proof mode, with assigned proof mode.✦ Formula equivalence between formulas and is the relation given by the existence of typed open proof-mode transformers in both directions, uniformly in the displayed data variables.✦ (1)✦
Let be an ambient classical logical interpretation, with its fixed data witnesses and incoming and outgoing proof paths. Its logical operations are written , , , , and . The symbol denotes the conjunction of the two internal implications.✦ Universal quantification uses fixed routes for elements and for predicates; each route wraps a data-to-proof dependent product by its incoming and outgoing proof paths.✦ Existential quantification is .✦ These connectives and quantifiers denote formulas of . The logical conditional with guard and branches is .✦ For a collection of sort sets, an observation layer is a profile positively reachable in the primary graph from a nonempty axiom profile with .✦ A direct observation layer for is an observation layer for which some form a feasible product profile triple .✦ A logical terminal profile for is a profile for which some form a feasible product profile triple .✦ A labelled term is data-only when every application, abstraction and dependent product in it has data argument and result modes.✦ The erasure of a labelled term removes its labels and preserves its variables, sorts, applications, annotated abstractions and dependent products.✦ A labelled type is sorted at a profile when for every , with additional sorting judgments permitted.✦ A fixed feasible witness family chooses types and values for sort sets ; at every feasible , is data-only with full normal erasure, is sorted at , and satisfies for every , while .✦
Relational Predicates and Observations
A retained data path is a finite wrapper path generated by identity, positive extensions with a fixed annotation and argument, and negative extensions with a fixed data tail.✦ The parity of a retained data path is the number of its negative extensions modulo two. A double data channel consists of two odd retained data paths.✦ For a path , write for its wrapped type and for its observation of against at . Positive injection along a positive data path leaves a term unchanged at identity and forms a constant data abstraction over the retained annotation at each extension.✦ Positive projection along a positive data path leaves a term unchanged at identity and applies it to each retained argument before continuing along the preceding path.✦
For a double data channel and a type , the double wrapper carrier of is the type obtained by wrapping along the channel’s first path and then along its second path.✦ The carrier of a data tail is the positive wrapper of its terminal sort along its positive path.✦
A relational coding consists of a uniform probe and odd logical and predicate paths .✦ The probe has a seed sort, an initial path, odd raw and return paths, an even function path, a positive lifting path, and a data tail.✦ The common type of the uniform probe of a relational coding is a dependent product in data mode over the probe’s type parameter. The shared channel uses the probe’s raw path .✦ The logical and predicate types of this channel are those of (2). (2) The probe type parameter domain is the positive wrapper of the seed sort along the lifting path.✦ At a type , the probe function type is the data arrow from its single bundle type to its data tail carrier.✦ The probe codomain family projects the bound type parameter along the positive lifting path, forms the probe function type at that projection, and wraps the result along the even function path.✦ The probe parameter type at is the parameter type of the probe double channel at the probe raw type of .✦ The single bundle type at is the double wrapper carrier of the probe parameter type at , using the probe double channel.✦
For a type , a predicate and a logical element , channel evaluation is the formula obtained by observing along against the raw reencoding of , at .✦ For a type and an open formula on logical elements of , the encoded predicate is the data predicate obtained by composing with reencoding from the raw path to the logical path and applying the predicate path builder. Predicate comparison is the formula in (3). (3)✦ The channel roundtrip of a logical element is its reencoding to the raw path followed by reencoding back to the logical path.✦ A predicate is roundtrip invariant when its evaluation at every logical element is internally equivalent to its evaluation after the channel roundtrip.✦ The admissibility guard for a predicate is the conjunction of its roundtrip invariance and the supplied predicate condition.✦ Guarded observational equivalence of two logical elements means that their evaluations are internally equivalent for every predicate satisfying the chosen admissibility guard.✦
The equivalence class predicate of an element is the encoded predicate of logical elements guardedly observationally equivalent to it.✦ The class union predicate of two logical elements is the encoded predicate whose formula is the disjunction of membership in their guarded observational classes.✦
A structural query observes a parameter along the second path against a tagged payload encoding of the supplied predicate.✦ The class query tags for copy indices are the structural tags , respectively.✦ The edge query tags for the first and second edge kinds are and , respectively.✦ A class query at copy index applies the structural query at class tag to the guarded equivalence class predicate of the given logical element.✦ A tagged edge of the first kind from to requires the class queries placing in class and in class , together with the tag query on their guarded class union predicate. The second kind uses class for and tag for the union query. For a predicate and logical element , a logical element satisfies the pair membership formula if either some logical element has a first-kind tagged edge to and satisfies , or has a second-kind tagged edge to , with the chosen guard and query family throughout.✦ The pair predicate of and is the encoded predicate of elements satisfying their pair membership formula.✦
For a data predicate , the uniform predicate probe is the data term that abstracts over a type parameter and a single-bundle argument. Its test recovers the pullback of along the relational element lift. For a data predicate and a logical element , the probe order is the observation formula .✦ Put and . Probe element comparison, predicate extensionality and order validity are the formulas in (4). (4) Probe specialization at applies the probe in data mode to the positive injection of along its lifting path.✦ Probe application observation specializes the probe at , observes the result along its even function path at the probe function type, and tests it by applying the recovered function to the supplied bundle and decoding the result through the data tail.✦
For relational coding at and parameter , the relational base type is the initial probe wrapper of .✦ The structural admissibility guard requires roundtrip invariance together with the tag structural query of , over this base type.✦ The relational pair predicate of and is their channel pair predicate over the relational base type, using the structural admissibility guard and the seven structural queries of the parameter.✦
A source data bundle with entries is built along the second path over the first-path wrapper of its base type. Its formula tests the input against along the first path and chooses its observation against when that test holds and against when its negation holds.✦ An encoded data point is built along the second path at the predicate code type. Its body conjoins the tag marker for the chosen truth marker with observation of its decoded payload against the point, along the supplied odd path.✦ The relational point encoding of is the encoded data point in the probe double channel at the probe raw type, using the predicate path, the constant truth marker, and the raw channel reencoding of as payload.✦ The relational argument bundle of and is the source data bundle in the probe double channel at the probe parameter type, with entries the dummy observation, , and the relational point encoding of .✦ The diamond observation of a probe at and parameter is its probe application observation against the relational argument bundle of and .✦
For a probe and a chosen type and parameter, the probe section predicate of is the encoded predicate whose value at is the diamond observation of at .✦ The section pair query for and is the tag query of the parameter on the relational pair predicate of the probe section predicate of and the element .✦
Bundle access observation tests the bundle along the second path against a first-path probe.✦ The probe uses a logical conditional with the chosen guard, truth as its true branch, and observation of the bundle after the supplied inner callback as its false branch.✦ Recovery access observation is bundle access at the parameter type, with the dummy test as its guard and the inner observation probe of the supplied payload as its inner callback.✦
Predicate pullback recovery for the single bundle in the probe double channel is the recovery access observation that uses the predicate path at the probe raw type and tests each parameter with the corresponding predicate pullback.✦
A three-copy observation system consists of and inner and outer double data channels.✦ Its copy structure starts with , reencodes along , and embeds successively through the inner and outer channels.✦ For , write for its tagged copy, . The inner embedding has its marker set precisely for , and the outer embedding precisely for . Write for the resulting observation carrier, for its two marker observations, and for its observation against after recovery through both copy channels. Tagged observational comparison is the formula in (5). (5)✦ Signed payload embedding with bit builds along the second path from observation against the payload along the first path, retaining that formula when is true and negating it when is false.✦ Double channel evaluation observes its input along the second path against the first-path builder of the supplied predicate.✦ Signed payload recovery is the logical conditional with the encoded bit observation as guard, double channel evaluation as its true branch, and the negation of that evaluation as its false branch.✦ The encoded bit observation tests the input along the second path against the first-path builder of the constant truth predicate.✦
Specialized observational comparison of is universal quantification over of the internal equivalence between and .✦
The Seven Structural Conditions
A specialized relational coding is an observation system with a chosen type .✦ Write for its base type. The predicate type of is .✦ Write and . The specialization has the seed-sort judgment , where is the probe’s seed. Its shape conditions identify with , the second outer path with , and the first outer wrapper of the middle copy type of with .
For , the left-copy predicate is . The observation invariance formula , class representation formulas , edge representation formulas , and relational closure formula are defined in (6). (6)
The structural property , for , is the branch selected by (7). (7)✦
Let be the probe’s double channel and the probe raw type of . A query is the second-path observation of against the tagged payload encoding of , using the predicate path and tag .✦ The eight query tags use the nonzero indices among nine marker indices, whose four binary digits are read from least to most significant. The dummy formula is the second-path observation of against the bottom predicate code at .✦
For a double data channel and a type , the iterated carrier of is the type that equals at depth zero and applies the channel’s double wrapper carrier once more at each successive depth.✦ The fourfold carrier of is its iterated carrier at depth four.✦
The parameter type at is the second-path wrapper of its predicate code type.✦ The dummy observation at is built along the second path at the predicate code type, with constant truth as its body.✦ The inner observation probe of a payload is built along the first path at the parameter type. Its body is the logical conditional with the dummy test as guard, falsity as its true branch, and the tag query of the payload as its false branch.✦
Iterated signed embedding leaves the payload unchanged for an empty bit string; for a first bit and remaining string, it first embeds along the remaining string and then performs the signed embedding selected by the first bit at the corresponding iterated carrier.✦ The iterated recovery predicate at depth zero is the supplied predicate, and at each successive depth it performs signed payload recovery at the preceding iterated carrier using the preceding recovery predicate.✦ The tag predicate for an empty bit string is truth. For a first bit and remaining string, it conjoins the encoded bit observation or its negation, according to that bit, with signed recovery of the tag predicate for the remaining string.
The constant truth marker is built along the raw path at with constant body .✦ The structural realization is built along the second path of at its predicate code type. Write for the marker that tests the first path against the tagged embedding with tag , and for the payload decoder using the predicate path. The body of the structural realization is the right-associated disjunction of the seven branches , ending in ; here is its input predicate code. The chosen parameter is defined by (8). (8)✦
Query respect and admissibility are the formulas in (9). The finite conjunction is right-associated. (9)
The Claim
Theorem 1. Let be a relational coding for satisfying its typing and mode conditions, with element and predicate quantifier routes . Let be data terms of type in , and suppose . Their extensionality formulas satisfy (10). (10)✦
Let be a specialized relational coding for the same logical interpretation and its quantifier routes, satisfying the typing and mode conditions for its observations. Fix . If are data terms of type in and , then (11) holds. (11)✦
For every data term of type in , the query answer is related to its structural formula by (12). (12)✦
The chosen parameter satisfies (13). (13)✦
What Is Checked
The statements are over labelled terms with their typing and mode judgments, an ambient logical interpretation, retained paths and quantifier routes satisfying their typing and mode conditions, and a specialization satisfying the typing and mode conditions for its observations, its seed-sort judgment and its three shape conditions.