The Setting
An encoded predicate over an element type is a data term whose observation at each element of that type is a formula. Class predicates, unions of two classes, and pair predicates are formed through observation channels. The relevant comparison of formulas is by uniform typed proof-term transformers.
Fix a pure type specification , with arbitrary axiom and product-rule relations, a context , and an assignment of data and proof modes to variables. Terms have annotated abstractions and dependent products . Write when some proof-mode term has type in , and when there are typed open proof transformers from to and from to . In the latter judgment a temporary proof-mode input is available to each transformer. The labelled terms have an argument mode and a result mode on each application, annotated abstraction and dependent product; the allowed labels are data to data, data to proof and proof to proof. The mode discipline assigns variables their prescribed modes and sorts data mode, and checks applications and abstraction bodies against their argument and result labels. Abstraction annotations and both parts of a dependent product have data mode, with the bound variable assigned the argument mode of the label. A labelled term is data-only when every application, annotated abstraction and dependent product in it has data as both argument and result mode.
Full beta reduction on the underlying pure terms contracts an applied annotated abstraction by capture-avoiding substitution and permits reduction in function and argument positions, annotations and both binder bodies.✦ Labelled beta reduction has the same closure under term components, and its head contraction requires the application and abstraction to have the same label.✦ Beta convertibility is the equivalence relation generated by full beta reduction✦; labelled beta convertibility is the equivalence relation generated by labelled beta reduction.✦ The labelled typing judgment uses the axiom, variable, weakening, product, abstraction, application and conversion rules, with matching function and application labels and conversion to a sorted expected type along labelled beta convertibility.✦
Fix a classical logical interpretation , with its feasible witness family and proof paths. Its connectives are written ; the last denotes the conjunction of the two implications. Quantifier routes and supply universal quantification over elements and predicates, respectively. For logical base profile and quantifier domain profile , a quantifier route is a choice of a feasible product profile triple of nonempty sort profiles, each consisting of all sorts typing a normal term in a valid context, with output profile specified by (1), an even incoming proof path from to , and an even outgoing proof path from to , relative to the fixed witness family and collection of profiles. Existential quantification is the negation of a universally quantified negation.✦ The logical falsity of is the witness type chosen at its base profile, and logical truth is . Logical disjunction is the negation of the conjunction of and . Proof wrapping of a type leaves unchanged at the identity path; a positive extension by forms a nondependent arrow from to the preceding wrapped type with data input and proof output, and a negative extension by forms an arrow from the preceding wrapped type to with proof input and proof output.
A feasible product profile triple consists of feasible profiles satisfying (1): (1)✦ For a term with weak normalization, write for its chosen full beta normal form.✦ The normal form sort profile of a weakly normalizing term in a context is the set of all sorts for which .✦ The axiom profile is the set of axiom successors with .✦
The primary signed graph has a positive edge from a feasible profile to each feasible proper subprofile , a negative edge from to for every feasible product profile triple , and a positive edge from to for that triple.✦ Positive reachability is a finite, possibly empty path all of whose edges are positive.✦ For the logical collection of sort profiles, an observation layer is a profile positively reachable in the primary 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 .✦
An observation channel consists of logical, raw, and predicate retained data paths, each of odd parity.✦ A retained data path is generated by the identity path, positive extensions retaining a domain and dummy argument, and negative extensions with a data tail; parity counts the negative extensions modulo two.✦ A retained data path from to is formed relative to when it is generated from the identity at , permitting restriction of any target profile to a subset without changing the path or its parity. From a path ending at , a feasible triple permits a positive extension to using the chosen witness type and value at , whereas a feasible triple and a formed data tail ending at permit a negative extension to . A formed observation channel has logical path from to , raw path from to , and predicate path from to .✦ For a base type and a path , write for the type wrapped along , for its builder, and for its observation. The channel types are defined in (2): (2) Reencoding between two odd paths builds along the target path using the source observation as its body.✦ For , , , and a formula family on , the raw and logical reencodings, roundtrip, evaluation, and predicate constructor are given by (3) The functions in (3) are written with named bound variables; the underlying terms use de Bruijn indices and newest-first contexts, with capture-avoiding renaming and substitution.
A positive data path is a finite path generated by the identity and positive extensions, retaining a domain annotation and its chosen dummy argument at each extension.✦ A formed positive data path starts with the identity at its source profile and permits restriction of its target to any subset. A feasible triple extends a path ending at to using the fixed witness type and value at . The positive wrapper type of along a positive data path is at the identity; an extension by a domain forms the nondependent data arrow from to the preceding wrapper type.✦ Positive wrapper injection leaves a term unchanged at the identity path and, at an extension by a domain , forms the constant annotated data abstraction over with the preceding injection as its body.✦ Positive wrapper projection leaves a term unchanged at the identity path and, at each extension, applies it to the retained dummy argument before continuing along the preceding path.✦
The carrier of a data tail is the positive wrapper type of its terminal sort along its positive path.✦ Data tail encoding of a formula first wraps it along the tail’s encoding proof path and then takes its positive wrapper injection.✦ Data tail decoding first takes positive wrapper projection and then wraps the result along the tail’s decoding proof path.✦
Admissibility and Comparison
A stable formula family over assigns an interpretable formula to every typed data predicate and retains this property after every mode-preserving context embedding.✦ Such an embedding renames variables into a valid context, preserving their types and modes.✦ Interpretability requires sorting at the logical base profile, data mode, and stable witness extraction.✦ Stable witness extraction turns witness continuations into proof-mode inhabitants after every such embedding.✦
For data predicates and elements , the roundtrip invariance condition , admissibility guard , observational relation , and predicate comparison are the formulas in (4): (4) For elements , the class predicate and class union predicate are encoded predicates over with the bodies specified in (5): (5)
For a family of seven predicate queries , take in the admissibility guard. The class test on , for , is the formula obtained by applying query to the class predicate of its argument.✦ For , the edge test on two elements of is the formula combining their class tests with query of the union of their classes.✦ The pair membership formula and the pair predicate over , for and , are defined from the class tests and edge tests in (6): (6)
The Constructed Specialization
A specialized relational coding is a relational coding with a three-copy observation system and a chosen data type .✦ The underlying relational coding of has a uniform probe, which supplies a predicate probe for each predicate over the common probe type, and shares the probe’s raw path with the observation channel. Write for this shared channel. The base type of a specialized relational coding is the type wrapped along the probe’s initial path.✦ Write for the common probe type and for its logical element type. The specialized predicate type is ✦; evaluation uses (3) at .✦
For a probe and a type , the probe raw type is obtained by wrapping first along the initial path and then along the raw path.✦ A double channel consists of two odd retained data paths.✦ The probe double channel has the probe’s back path as its first path and its raw path as its second path.✦ The probe parameter type at is the double-channel parameter type at the probe raw type of , using the probe double channel.✦ The single bundle type at is the double wrapper carrier of the probe parameter type at , using the probe double channel.✦ The probe type parameter domain is the positive wrapper type of the seed sort along the probe’s lifting path.✦ The probe function type at is the nondependent data arrow from the single bundle type at to the carrier of the probe’s data tail.✦ The probe function abstraction with formula body is an annotated data abstraction over the single bundle type whose body is the data tail encoding of .✦ The wrapped probe abstraction at is obtained by applying the data path builder along the probe’s function path, at the probe function type of , to the probe function abstraction.✦ The uniform probe abstraction is an annotated data abstraction over the probe type parameter domain; at its bound parameter it takes positive wrapper projection along the lifting path and uses the resulting type in the wrapped probe abstraction.✦ Probe specialization of to applies in data mode to the positive wrapper injection of along the lifting path.✦ The probe application observation at specializes its probe to and observes the result along the function path, at the probe function type. Its test applies the newly supplied function to the argument in data mode and decodes the result through the data tail.✦
The tagged observation type is formed by nested inner and outer double channels over . The embedding , for , reencodes into the first copy path and then embeds through the inner and outer channels, with the inner marker set precisely at and the outer marker precisely at .✦ For tagged elements , tagged observational equivalence is the formula requiring equivalence of their inner markers, equivalence of their outer markers, and equivalence of all their observations by uniform predicate probes.✦ The double wrapper carrier of a type along a double channel is obtained by wrapping the type first along its first path and then along its second path.✦ Double-channel evaluation of a value against a formula body observes the value along the second path, using the builder along the first path applied to that body as its test.✦ The encoded bit observation of a double-channel value is its double channel evaluation against constant logical truth.✦ The signed payload embedding along a double channel builds along its second path from the observation of the newly bound first-path value against the payload. That observation is used unchanged when the sign is true and negated when it is false.✦ Signed payload recovery of a value against a formula body is its double-channel evaluation against that body when the encoded bit observation holds, and the negation of that evaluation otherwise; this choice is the logical disjunction of the two guarded branches.✦ The observation copy structure has the shared logical path as source, the probe’s raw path as first copy path, and the observation system’s inner and outer double channels as its two copy channels.✦
The iterated carrier of at depth zero is , and each successor depth applies the double wrapper carrier once more✦; the fourfold carrier is the iterated carrier at depth four.✦ The predicate code type at wraps the fourfold carrier of along the double channel’s first path.✦ Its bottom predicate is built along that path with constant body .✦ The double-channel parameter type at wraps its predicate code type along the second path.✦
The query tagged embedding of a payload uses the four binary digits of a query index from zero through eight, listed from the lowest digit upward, as its signs for iterated signed embedding.✦ Iterated embedding leaves the payload unchanged for the empty sign list and, for a leading sign, first embeds along the remaining signs and then applies that leading sign at the corresponding iterated carrier.✦ The tag predicate for an empty bit string is . For a leading bit it conjoins the encoded bit observation, negated precisely when that bit is false, with signed recovery of the tag predicate for the remaining bits, at the carrier whose depth is the length of those remaining bits. The tagged payload encoder for a tag from zero through seven builds along the first path over the fourfold carrier. Its body is the disjunction of the zero-query tag conjoined with fourfold signed recovery of the observation of the payload along its odd payload path, and the query tag whose index is .✦ For an odd path , the payload decoder builds along from the observation of the encoded payload along the double channel’s first path, tested against the zero-query tagged embedding of the newly supplied argument.✦
The dummy observation at is built along the second path over the predicate code type with constant body .✦ The dummy parameter test observes a parameter along that second path against the bottom predicate at .✦ The tagged observation query at tag observes its observation term along the second path, over the predicate code type, against the tagged payload encoding of its predicate argument.✦
The encoded data point for marker and payload is built along the second path over the predicate code type. Its body conjoins the observation along the first path at the fourfold carrier against the tagged embedding of at query index eight with the observation of the decoded predicate argument against along the payload path.✦ The source data bundle of is built along the second path over the first wrapper type. For a first-path input, its body takes the observation against when the observation against holds, and the observation against otherwise.✦ The inner observation probe for a predicate is built along the first path over the parameter type. Its body is when the dummy parameter test holds and otherwise is the tagged observation query at tag seven of the bound parameter against .✦ Bundle access observes its bundle along the second path at the first wrapper type, against a test built along the first path. At the bound input that test is when its guard holds and otherwise observes the bundle against the supplied inner data argument.✦ Recovery access at uses bundle access over the parameter type, with the dummy parameter test as guard and the inner observation probe applied to the supplied predicate as its inner data argument.✦
The three-copy observation of against first uses signed recovery through the outer channel at the middle copy carrier. Its test recovers through the inner channel at the first copy wrapper type and then observes against along the first copy path.
A formed specialization is a specialized relational coding with formed probe and observation channels, a chosen type of the probe’s seed sort in data mode, and matching channel shapes: , the outer second path is , and the outer first path sends the middle copy carrier over to .
For a predicate over and , the probe order is the observation along the logical path of against the uniform predicate probe for .✦ Probe element equivalence on is the relation that holds between two elements when their probe order observations are equivalent at every predicate over .✦ For a predicate over , the condition requires evaluation by to respect probe element equivalence.✦ The condition for an element requires the probe order observation to respect comparison of predicates over .✦
The relational point encoding of at is the encoded data point in the probe double channel at the probe raw type of , using the predicate path and constant truth marker, with the raw channel encoding of as payload.✦ The relational argument bundle of and at is the source data bundle in the probe double channel at the probe parameter type of , with entries the dummy observation at the probe raw type of , , and the relational point encoding of .✦ The diamond observation of a probe at , parameter , and element is its probe application observation against the relational argument bundle of and .✦ The probe section predicate of at and is the encoded predicate whose observation body sends to the diamond observation of at .✦ The section pair query for is the tagged observation query at tag six of against the pair predicate formed from the probe section predicate of and , using the probe double channel and predicate path at the probe raw type of .✦
The relational element lift of at is built along the logical path over the common probe type, with body assigning to each probe its section pair query for .✦ The predicate pullback of along lifting at is the encoded predicate whose body evaluates on the relational element lift of its argument.✦ Predicate pullback recovery of from a single-bundle argument at uses recovery access in the probe double channel at the probe raw type of , with the predicate path as payload path. Its supplied predicate sends a parameter to the pullback of along lifting at .✦
The structural parameter is the structural query realization in the probe double channel at the probe raw type of , using the predicate path, the constant truth marker, and the seven structural properties. For a specialized predicate , these queries are determined by the observation invariance property , class representation properties , edge representation properties , and relational closure property in (7). The left copy predicate of a specialized predicate is obtained with the predicate constructor over in (7); the indices are for and for : (7) The seven structural properties, in order, are . The specialized queries are the structural queries of ; the specialized guard is . Specialized observational comparison and pairing use these queries and this guard in (4) and (6). The structural query realization is built along the second path over the predicate code type from a finite marked disjunction of the seven structural properties. In the ordered branch for tag , the marker tests the tagged embedding of the chosen marker at query index , and the property is applied to the decoded predicate; the disjunction ends with .
The Claim
Theorem 1. Suppose the observation channels are formed, is a stable formula family over , and the element and predicate quantifier routes are fixed. Suppose also that for some sort . Let have type in and have data mode. Class evaluation satisfies (8): (8)✦ Union evaluation satisfies (9): (9)✦ If , class comparison gives (10): (10)✦
Let be a formed specialized relational coding, and use its specialized types, guard, and queries. Let have its predicate type and its tagged observation type, all in data mode in . Suppose and . Pair input evaluation satisfies (11): (11)✦ Pair comparison gives (12): (12)✦ For any data-mode of the indicated types, pair evaluation satisfies (13): (13)✦
In the paper, the result reads: and are unrounded evaluation equivalences; parameters and give and ; under the admissibility hypothesis , the tests and respect , and assumptions , , give , while the first two give , with under the same admissibility hypothesis.
What Is Checked
The channel statements concern formed logical, raw, and predicate paths from profiles to , to , and to , respectively, with the stable family and data-mode typing hypotheses in the theorem. Specialized formation requires formed underlying probe and copy channels, in data mode for the probe’s seed sort , and the equality ; it also requires the outer second path to equal and the outer first path, applied to the middle copy carrier over , to give .✦ The pair statements are over the formed specialized relational coding, its constructed admissibility guard and seven property queries, the fixed logical interpretation and element and predicate quantifier routes, and typed data-mode predicates and tagged observations. The congruence statements also assume proof-mode inhabitants of the indicated predicate and observation comparisons.