The Setting
Consider data terms reencoded through two successive double data channels. Their observations include marker formulas and tests against predicates on the original carrier. The comparison of two such terms is a formula in the ambient logical calculus.
Fix a pure type specification with arbitrary axiom and product-rule relations, a context , and an assignment of data and proof modes to its variables. Terms have annotated abstractions and dependent products, with labels , , and specifying data-to-data, data-to-proof, and proof-to-proof arguments and results. Typing is written . The mode discipline gives variables their declared modes and sorts data mode; an application has its labelβs result mode when its function has that mode and its argument has the labelβs argument mode. An abstraction has its labelβs result mode when its annotation has data mode and its body has the result mode under the corresponding binder extension; a dependent product has data mode when its domain and codomain have data mode, with the codomain checked under that extension. Named bound variables below correspond to de Bruijn indices, with contexts ordered newest first. Substitution is capture-avoiding, and full reduction includes annotations and binder bodies. For ordinary terms, convertibility is the smallest equivalence relation containing one-step reduction. For labelled terms, labelled convertibility is the smallest equivalence relation containing labelled reduction.
Write when and has data mode under . A formula is inhabited in proof mode, written , when there is a term with and has proof mode.β¦ A typed open transformer from to is a proof-mode term of type in the context extended by a temporary proof-mode input of type .β¦ For formulas and , formula equivalence is the relation given by proof-mode terms that transform a temporary proof-mode input of either formula into a term of the other formula.β¦
A sort profile is the set of all sorts typing a chosen normal form of a type.β¦ A feasible profile is a nonempty set of sorts typing a normal type in a context obtained from the empty context by adjoining types that have a sort.β¦ For profiles , the product output is the set of all sorts for which some and satisfy β¦; a feasible product profile triple is a triple of feasible profiles satisfying .β¦
A term is weakly normalizing when some normal form is reachable from by zero or more steps.β¦
The signed primary graph has positive edges for proper inclusions of feasible profiles; each feasible product profile triple also gives a negative edge and a positive edge , and these are its only edges.β¦ Positive reachability in a signed graph means a finite, possibly empty path all of whose edges are positive.β¦
A fixed feasible witness family chooses, at each feasible sort profile, a type using only data syntax, in data mode, whose underlying unlabelled term is in normal form and which is sorted at every sort in that profile, together with a data-mode inhabitant.β¦ For a collection of profiles, a formed proof path starts with identity at its source profile and permits restriction of its target to any subset; a feasible triple extends a path ending at positively to using the chosen type at , while extends it negatively using the chosen type at when .β¦ Positive steps preserve parity and negative steps reverse it. Let be an ambient logical calculus with collection of profiles and domain, base and product profiles forming a feasible product profile triple, falsity equal to its chosen witness type at , and even proof paths and . For the collection of profiles of the ambient logical calculus , a logical terminal profile is a profile admitting a feasible product profile triple with β¦; converters connect the chosen types at any two such profiles. Relative to , an observation layer is a profile positively reachable in the primary graph from a nonempty axiom profile , the set of sorts with , where .β¦ A direct observation layer is an observation layer admitting a feasible product profile triple with .β¦ The calculus supplies at every direct observation layer a quantifier route, a pair of inward and outward proof paths for forming the universal quantifier. Proof wrapping leaves unchanged at identity, adds a data-to-proof arrow from the retained domain at a positive step, and adds a proof-to-proof arrow into the retained codomain at a negative step.β¦ The logical operations and a universal quantifier with proof paths are defined by (1). (1)The biconditional in (1) is a formula, whereas is equivalence by typed open transformers. Fix quantifier routes and for the logical and predicate carriers used below. Existential quantification is the formula .β¦ Guarded universal quantification of by over is , requiring a uniform typed proof transformer from the guard to the body at each bound element.β¦
A retained data path is a finite path generated by identity, positive extensions with a fixed domain and dummy argument, and negative extensions with a data tail.β¦ Its parity counts negative extensions modulo two. A formed data tail ending at profile has a sort with and nonempty axiom profile , a positive data path from to , and even encoding and decoding proof paths from the logical base to and back, respectively; the decoding path contains a negative step.β¦ For a retained path and a data type , write for its wrapped data type, for its builder with open formula body , and for its observation of a wrapped data term against a data term of type . Positive extensions add data arrows with fixed domains; negative extensions add data arrows into the tail carrier. A positive path has the associated constant annotated abstractions as injections and evaluation at its fixed dummy arguments as projections. For odd retained data paths and a wrapped data term along , wrapper reencoding is the term in (2), where is the distinguished free variable of the open formula. (2)β¦
The carrier of a data tail with sort and positive path is the positive wrapped type .β¦ Data-tail decoding of first projects along the tailβs positive data path and then applies its decoding proof path.β¦ Data-tail encoding of a formula first applies the encoding proof path and then injects along the positive data path.β¦
Let be formed relational coding with common probe type , odd logical path , odd raw path , and odd predicate path . Its uniform probe abstracts a wrapped type parameter and a single-bundle argument. The probeβs initial path has its fixed parity and runs from its singleton seed profile to , its odd raw and return paths run from through back to , its even function path runs from to , and its positive lifting path runs from the seedβs nonempty axiom profile to . Its product profiles are and , and its tail ends at . The logical path runs from to , and the predicate path from to .
For a base type , the logical and raw channel types are and , and the predicate channel type is β¦; channel evaluation observes along against the raw reencoding of .β¦ The encoded predicate is the builder along over whose body applies the open predicate to the logical reencoding of its fresh raw input.β¦ The source observational relation is guarded universal quantification over the predicate channel type, with guard and body .β¦ The channel roundtrip at is raw reencoding followed by logical reencodingβ¦; the roundtrip invariance formula of over universally quantifies over the logical channel type and asserts .β¦ The admissible predicate condition with supplied condition conjoins roundtrip invariance of with .β¦
The equivalence class predicate of over with guard is the encoded predicate whose value at is .β¦ The class union predicate of over with guard is the encoded predicate whose value at is .β¦ For a query family on seven tags and class index , the class query of applies query to the equivalence class predicate of .β¦ The tagged edge predicate of kind from to conjoins the class query placing in class , the class query placing in class when and class otherwise, and query when or otherwise applied to the class union predicate of .β¦ The pair membership formula for predicate and element at is the disjunction of an existentially quantified logical element with a false-kind tagged edge to satisfying by channel evaluation, and the true-kind tagged edge from to , with the same carrier, guard and query family throughout.β¦ The pair predicate of and is the encoded predicate whose value at is their pair membership formula.β¦
Tagged Observations
A double data channel is a pair of odd retained paths; its carrier is . Its signed embedding, bit test, and signed recovery are given in (4), using polarity selection and logical conditional as specified in (3). (3) (4)
Double-channel evaluation observes along the second path against the first pathβs builder with body .β¦
The iterated carrier is at depth zero and applies to the preceding carrier at each successor depthβ¦; the fourfold carrier is .β¦ Iterated signed embedding along a finite bit string leaves the payload unchanged for the empty string and, for a first bit followed by , applies the embedding selected by to the recursively embedded payload over .β¦ The query tagged embedding for is the iterated signed embedding along the four-bit string consisting of binary digits zero through three of , in that order.β¦ The iterated recovery predicate at depth zero is the original predicate body; at depth it performs one signed recovery over with the depth- recovery predicate as its test.β¦ The tag predicate for the empty bit string is truth; for a first bit followed by , it conjoins the signed marker selected by with signed recovery of the tag predicate for , over .β¦
The predicate code type over is .β¦ The bottom predicate code over is the first pathβs builder at the fourfold carrier of with constant body .β¦ Wrapping the predicate code type over along the second path gives the double-channel parameter type over .β¦ The dummy observation over is the second pathβs builder at the predicate code type over with constant body .β¦ The dummy parameter test over is the second pathβs open observation formula over the predicate code type of , with the observed term free and the bottom predicate code as its fixed test.β¦
The source data bundle of over is the second pathβs builder over with a branch predicate that uses the first pathβs contravariant observation of as guard and its observations of and as the two branches.β¦ The access probe over for guard , object and data function is the first pathβs builder with outer access predicate , where is the observation predicate of along the second path composed with .β¦ The bundle access observation over tests along the second path at against the access probe determined by its guard and inner data function.β¦
The tagged payload encoder of along an odd path , with tag over , is the first pathβs builder at the fourfold carrier with the encoding predicate as body.β¦ The encoding predicate for payload along an odd path , with tag over , is the formula given by the disjunction of the payload-zero tag conjoined with depth-four recovery of the observation predicate of along , and the tag predicate for query index .β¦ The payload decoder along an odd path builds along over with a decoding predicate that observes its predicate code along the first path at the fourfold carrier, after query-zero tagged embedding of the fresh payload.β¦ The tagged observation query at tag of against along an odd path is observation of along the second path at the predicate code type, with the tagged payload encoder of as its test.β¦ The query predicate of along an odd path is the second pathβs contravariant observation predicate at the predicate code type, with the tag- payload encoder of as its fixed argument.β¦ The inner observation probe of along an odd path is the first pathβs builder over the parameter type with an inner probe predicate that selects falsity when the dummy parameter test holds and the query predicate of otherwise.β¦
The marking predicate for tag and marker over observes a fresh first-path input against the query tagged embedding of at index , over the fourfold carrier.β¦ The encoded data point of marker and payload along an odd path is the second pathβs builder over the predicate code type with a data point predicate as body.β¦ The data point predicate of marker and payload along an odd path is the conjunction of the tag- marking predicate of with the contravariant observation of along after payload decoding.β¦ The recovery access observation of against a parameter-dependent predicate is bundle access over the parameter type, guarded by the dummy parameter test; its inner data function first evaluates that predicate and then applies the inner observation probe.β¦
The probe double wrapper has the probeβs odd return path as its first path and its odd raw path as its second.β¦ The probe raw type of is obtained by wrapping first along the initial path and then along the raw path.β¦ The probe parameter type of is the double-channel parameter type of its probe raw type, using the probe double wrapper.β¦ The single bundle type of is the carrier of its probe parameter type under the probe double wrapper.β¦ The data-to-data arrow from the single bundle type of to the carrier of the probeβs tail is the probe function type of .β¦ The probe type parameter domain is the positive lifting wrapper of the seed sortβ¦; at a parameter , its probe codomain family wraps the probe function type of the positive projection of along the function path.β¦ The common probe type is the dependent product in data mode of this domain and codomain family.β¦ The probe function abstraction with body over is the data abstraction over the single bundle type whose body is data-tail encoding of .β¦ The wrapped probe abstraction over is the builder along the function path, at the probe function type of , applied to the probe function abstraction.β¦ Probe specialization of to is data-mode application of to the positive lifting injection of .β¦ The probe application observation of at against observes the specialization of along the function path at the probe function type of , using as test the data-tail decoding of the fresh function applied to .β¦
An observation system consists of and inner and outer double channels and .β¦ Their successive profile paths are and , respectively. The first copy path is and the source path is . Its source carrier , predicate carrier , and three-copy carrier are defined in (5). (5)
The first copy wrapper type is the wrapped type of along the raw path .β¦ The middle copy wrapper type is the inner double-channel carrier of .β¦
The relational base type of a data type is its wrapped type along the probeβs initial path.β¦ The constant truth marker over is the raw pathβs builder at the relational base type of with constant body .β¦ The relational point encoding of over is the encoded data point in the probe double wrapper at the probe raw type of , using the predicate path, the constant truth marker and the raw channel reencoding of at the relational base type of .β¦ The relational argument bundle of parameter and element over is the source data bundle in the probe double wrapper at the probe parameter type, with the dummy observation at the probe raw type, , and the relational point encoding of as its three observations.β¦ Probe application observation against the relational argument bundle of and gives the diamond observation of at with parameter and element .β¦ The probe section predicate of over at parameter is the encoded predicate at the relational base type whose value at is the diamond observation of .β¦
The structural query function at tag over assigns to a predicate its tag- observation query against in the probe double wrapper, using the predicate path at the probe raw type.β¦ The structural admissibility condition for a predicate over the relational base type of , at parameter , conjoins that predicateβs roundtrip invariance with its structural query at tag .β¦ The relational pair predicate of over at parameter is the channel pair predicate at the relational base type, with structural admissibility for as guard and the structural query functions for as its query family.β¦ The section pair query for over at parameter is the tag- observation query of against the relational pair predicate of the probe section of and , in the probe double wrapper using the predicate path at the probe raw type.β¦ The relational element lift of over at parameter is the logical pathβs builder at the common probe type; its defining predicate assigns to a fresh probe the section pair query for that probe and .β¦ Predicate pullback along lifting of over at parameter is the encoded predicate at the relational base type whose value at is channel evaluation of on the relational element lift of , at the common probe type.β¦ Predicate pullback recovery of over against a single bundle is recovery access in the probe double wrapper, along the predicate path at the probe raw type, with the parameter-dependent pullback of as its test.β¦
The tags are , with exactly for and exactly for . The tagged copy of is the term in (6). (6)β¦
For , let be its uniform predicate probe in . For a data term of carrier , the inner and outer marker formulas , the three-copy observation , and the probe order formula are defined in (7); and denote the distinguished free variables of the outer and inner recovery formulas. (7)
Probe element comparison is a formula comparing data terms of the source carrier , while observational comparison and tagged observational equivalence are formulas comparing data terms of the three-copy carrier , as defined in (8). (8)
Specialized coding chooses a data-mode type with , where is the probeβs seed sort. Let be its wrapped type along the probeβs initial path.β¦ The specialization conditions are , , and . The channel roundtrip for specialized coding is the operation on data terms of carrier defined in (9), with the reencodings of (2). (9)β¦
The Claim
Theorem 1. Assume the relational and double-channel paths have the formations specified above, relative to , and use the fixed quantifier routes . Let , , and . The inner marker assertion (10), outer marker assertion (11), and predicate observation equivalence (12) hold. (10)β¦ (11)β¦ (12)β¦
Let . Reflexivity is the assertion (13); symmetry and transitivity are (14) and (15), with their stated inhabitation hypotheses. (13)β¦ (14)β¦ (15)β¦
For specialized coding satisfying the carrier and path identities above, the roundtrip assertion is (16). (16)β¦
Equal tags have the formula equivalence (17); distinct tags satisfy (18). (17)β¦ (18)β¦
In the paper, the result reads: for and , the signed formulas when and when , and the biconditionals , have proof-mode inhabitants; each and is invariant by biconditional under ; the formula is an equivalence relation with an inhabitant of for every ; and its restrictions satisfy , while distinct tags have inhabitants of .
What Is Checked
The assertions are stated over the labelled typing and mode judgments, the ambient logical calculus and its quantifier routes, the formed relational and observation paths, and, for the roundtrip assertion, the seed-sorted chosen type and specialized carrier identities.