The Setting
Relational coding of the diagonal argument uses observations of elements and observations of probes. Lifting passes from the element level to the probe level; predicate extraction passes from a probe to its incidence with elements.
Fix a pure type specification , with arbitrary axiom and product-rule relations, a context , and a mode assignment . Terms have annotated abstractions and dependent products , with data and proof modes on applications and binders. Write for with in data mode, and when some proof-mode term satisfies . Formula equivalence means uniform typed open proof-term transformers in both directions: a temporary proof input of one formula yields a proof-mode term of the other.β¦ Contexts are newest-first in the indexed syntax; bound variables below are written with names. The labels on applications and binders are data to data, data to proof, and proof to proof. Labelled convertibility is the smallest equivalence relation on labelled terms containing one-step labelled reduction.
A normal form sort profile is the set of all sorts typing in , where is a chosen normal form when weak normalization supplies one.β¦ Full reduction includes annotations and binder bodies. Valid contexts start with the empty context and admit extension by whenever for some sort . A feasible profile is a nonempty profile of a normal term in a valid context.β¦ A feasible product triple consists of feasible profiles with , as defined in (1).β¦ (1) The axiom profile consists of the axiom successors of . The product output profile consists of the sorts obtainable by a product rule with domain sort in and codomain sort in . convertibility of pure type system terms is the smallest equivalence relation containing one-step reduction.
Let be a collection of profiles. In the primary signed graph, strict feasible profile inclusions give positive edges, while a feasible triple gives a negative edge and a positive edge .β¦ Observation layers are reached by positive edges from a nonempty with β¦; a direct observation layer also occurs as the domain of a feasible triple whose codomain and output belong to .β¦ A logical terminal profile for a collection of profiles is a feasible profile occurring as the codomain of a feasible product triple whose domain and output belong to .β¦ Positive reachability in a signed graph is the relation given by finite, possibly empty paths consisting entirely of positive edges.
An ambient logical calculus chooses, at every feasible profile , a data-only type with normal erasure, sorted at every sort of , and a value , with both and in data mode. It has uniform proof transformers between the chosen types at logical terminal profiles. A proof path is built from identity by positive arrow extensions with data input and negative arrow extensions with proof input; negative steps reverse parity and require their endpoint profiles in . The logical domain, base, and product profiles of form a feasible triple in , with even input and output proof paths connecting the base to the domain and the product to the base. For every direct observation layer, supplies a quantifier route: a feasible product triple at that domain together with even proof paths from the logical base to its codomain and from its output to the base. The falsity formula is the chosen type at the logical base.β¦ Implication applies the output proof path to the proof arrow from the input-wrapped antecedent to the consequent. Negation is implication to falsity. Conjunction and disjunction are defined from negation and implication. Universal quantification is the dependent product with data input and proof output along a selected quantifier route; existential quantification is the negation of universal quantification of the negated body.β¦ Logical equivalence is the conjunction of both implications.β¦ The truth formula of is the implication from its falsity formula to itself. For formulas , the logical conditional with guard and branches is , with all connectives taken in . For a formula and a Boolean polarity , polarity selection gives the formula when is true and when is false.
Fix routes and for the logical element and predicate profiles and ; subscripts on quantifiers indicate the selected route. Guarded quantification has body .β¦
Channels and Incidence
A retained data path is a finite path generated by identity, positive extensions retaining a domain annotation and chosen argument, and negative extensions retaining a data tail.β¦ Its parity counts negative extensions modulo two. Write for its wrapped data type, for its builder, and for its observation. Positive extensions add data arrows and constant annotated abstractions; observation applies the retained argument. A negative extension adds a data arrow into its tail carrier; its builder sends the inner observation through the tail, and its observation decodes application to the inner builder. A data tail uses a positive path from a nonempty axiom profile and even encoding and decoding proof paths at its terminal sort, whose singleton belongs to ; the decoding path contains a negative step.β¦ Its positive injection uses constant data abstractions and its projection applies the chosen arguments. Data tail encoding first applies the encoding proof path to a formula and then takes the positive injection along the tailβs positive path. Data tail decoding first takes the positive projection along the tailβs positive path and then applies its decoding proof path.
A shared relational system has a uniform probe with seed sort and an initial path , together with odd logical, raw, and predicate paths .β¦ The raw path is also the probeβs raw path. The channel types and evaluation are (2); wrapper reencoding observes along its source path and builds along its target path .β¦ (2) An encoded predicate is built along after precomposing its body with .β¦ The logical channel type is the wrapped data type of along . Wrapping along gives the raw channel type . The channel predicate type is the wrapped data type of along . Reencoding from the logical path to the raw path gives the raw channel encoding . The logical channel encoding reencodes from the raw path to the logical path.
The probe also has an odd return path , an even function path, a positive type lifting path, and a data tail. Its double channel applies and then .β¦ For a type , put , and write for iterations of the double carrier. For a type , the raw type of the probe at is , its parameter type is β¦, and its single bundle type is . The common probe type is the data dependent product over the lifted seed sort, with codomain the function-path wrapper of the data arrow from the single bundle type to the tail carrier at the projected type parameter.β¦ Probe specialization applies a probe to the positive injection of .β¦ A uniform probe abstracts over that parameter and a single bundle argument, sending its formula body through the tail before wrapping along the function path.β¦ The relational base type is the wrapped data type of along the initial path .
Formation of requires feasible triples and , a nonempty , and paths , , , , ; the function path runs from to , the positive lifting path from to , and the tail ends at .β¦ Path formation permits target restriction and extensions along feasible product triples, using the fixed witness types and values.
For , put , , and . For a predicate , the doubled probe channel has tagged queries for on a parameter . A query observes against a tagged payload encoding of .β¦ The encoding uses four binary markers, reserving zero for its payload and for the query tag. The dummy predicate observes against the bottom predicate code; write . The constant truth marker is built along the raw path.β¦ For an element , a point encodes with that marker, and the relational argument bundle combines the dummy observation, , and this point.β¦ Diamond incidence of a probe with an element is the probe application observation of on the relational argument bundle.β¦ The logical probe element type is the logical channel type of the common probe type . The probe predicate type is the channel predicate type over . The predicate code type over is , the first-path wrapper of its fourfold double carrier. Double channel evaluation at a type observes its input along the second path of against the term built along the first path from a formula body over . The query bit string of is the four-entry Boolean string of binary digits zero through three of , in that order. Iterated signed embedding along a finite Boolean string leaves its input unchanged for the empty string. For a nonempty string, it first embeds along the remaining string, then applies the signed embedding selected by the first marker at the carrier whose depth is the length of that remaining string. The query tagged embedding of a term over at query is its iterated signed embedding along the query bit string of . The tag predicate for the empty marker string is truth. For a nonempty string, it conjoins the bit observation, negated when the first marker is false, with signed recovery of the tag predicate for the remaining string, both at the carrier whose depth is the length of that remaining string.
An admissible predicate satisfies the guard in (3). The relation on relates two elements when every admissible predicate has equivalent evaluations at those elements, as specified in (3). (3) Roundtrip invariance of a predicate is the condition that has equivalent evaluations at every logical element and its channel roundtrip.
The class predicate has body β¦; the class union predicate has the disjunction of those bodies.β¦ For elements and a predicate , class queries, the two edge predicates, and the pair predicate are defined in (4), where and the displayed bodies denote encoded predicates. (4)
For a probe and an element , the section predicate is an encoded predicate on , the section pair query is a tagged query, and the element lift is a logical probe element, with the defining conditions in (5). (5) The pullback of along lifting is the encoded predicate with body .β¦ The uniform predicate probe associated with a predicate is the probe whose body recovers the pullback of along lifting from the single bundle. The predicate pullback recovery is the recovery access observation of a single bundle against the pullback of along lifting, with its parameter left variable.
For probe elements and predicates , probe order , probe element comparison , and predicate comparison are the relations defined by the formulas in (6). Write for . (6) An extensional predicate is a predicate that respects probe comparison, and a valid element is an element whose order observations respect predicate comparison, as defined in (7). (7)
Specialized Admissibility
A specialized relational system fixes a type and three tagged copies of .β¦ Its inner double channel has profile route , and its outer channel has route . The three tagged copies of a probe element , indexed by , reencode along the raw path, then use signed inner and outer embeddings with marker bits and . Tagged observational equivalence is the conjunction of equivalence of their inner markers, equivalence of their outer markers, and equivalence of every observation by a uniform predicate probe.β¦ Signed recovery through the two copy channels defines these observations.
The tagged observation carrier is required to equal . The second outer path equals , and the first outer path applied to the middle copy carrier of equals . The fixed type has data mode. For a predicate , its structural properties are (8); the left copy predicate has body .β¦ (8) The parameter is the structural query realization, with constant truth marker, of the seven branches in that order. The realization is the marked disjunction of these branch predicates after payload decoding. The specialized admissibility guard at is the predicate on given by the admissibility condition.β¦ Write , , , and for the corresponding constructions at . A responsive probe at is a probe whose incidence respects the specialized relation on , as in (9). (9) The observation invariance property requires equivalent evaluations of at any two tagged observationally equivalent observations. A predicate has the class representation property when it represents the tagged observational equivalence class of some element in copy . The edge representation property says that represents the union of the tagged observational equivalence classes of the copies and of some logical probe element. When the left copy predicate is extensional, the relational closure property requires every valid logical probe element whose copy satisfies to satisfy the order observation .
The Claim
Theorem 1. Let have the formed relational paths specified above in the ambient logical calculus , with quantifier routes . For , reflexivity is (10). (10)β¦ For data terms with , symmetry gives (11). (11)β¦ For data terms with and , transitivity gives (12). (12)β¦ For , rounding satisfies (13). (13)β¦ Suppose and . For data terms and , lift evaluation is (14). (14)β¦ For data terms and , assume in addition . The rounded probe law is (15). (15)β¦ Let the specialized system at satisfy its observation formation and carrier identities. For data terms with , lifting gives (16). (16)β¦ For every data term , validity is (17). (17)β¦ For data terms and with , exact probe evaluation is (18). (18)β¦ For a data term with , response is (19). (19)β¦ For data terms and with , predicate extraction satisfies (20). (20)β¦
In the paper, the result reads: is an equivalence relation with the congruence builder of Lemma 44 and ; data cancellation supplies ; under an admissibility witness there are builders , for , and ; if also , then and ; under , .
What Is Checked
The statements are over labelled typing and the mode discipline, the ambient logical calculus with its feasible witness family and quantifier routes, formed relational paths, and the specialized three-copy system with its fixed type and carrier identities.