The Setting
The diagonal construction acts on logical probe elements, while predicate shifting constructs a predicate from evaluation at a diagonal image. Element comparison uses order observations, and predicate comparison uses channel evaluation.
Fix a pure type specification , with arbitrary axiom and product-rule relations, a valid context , and a mode assignment . Terms have annotated abstractions and dependent products. The judgment includes its expected type ; calling a data term also requires data mode under . A formula is inhabited in proof mode, written , when some satisfies in proof mode.✦
A uniform typed transformer from formulas to is a proof-mode term of type with a temporary proof-mode input of type .✦ Typed logical equivalence means that such transformers exist in both directions.✦ The connectives and quantifiers below belong to a fixed ambient logical calculus ; in particular, denotes its formula of mutual implication. Neither notation asserts equality or convertibility of data. The calculus has chosen falsity and incoming and outgoing proof wrappers, together with universal quantifier routes for logical elements and for predicates.
A sort profile is the set of all with , where is a chosen normal form when is weakly normalizing.✦ A feasible sort profile is a nonempty sort profile of a normal type in a valid context.✦ A feasible product profile triple consists of feasible domain, codomain and product profiles with the output condition in (1). (1)✦ The axiom profile of a sort is the set of sorts for which .✦ The primary signed graph has a positive inclusion edge from a feasible profile to a feasible profile when , and a feasible product profile triple gives a negative domain edge from to and a positive codomain edge from to .✦ Positive reachability in a signed graph means reachability by a finite, possibly empty path containing only positive edges.✦ An observation layer for a collection of sort profiles is a profile positively reachable in the primary signed 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 for is a profile for which some form a feasible product profile triple .✦
The logical calculus uses a fixed feasible witness family: at each feasible profile , a data-only type in data mode under whose erasure is a full normal form, and a data term with . Sorting at requires for every .✦ Full reduction includes annotations and binder bodies.
Channels and Probe Order
A retained data path is a finite path generated from an identity path by positive steps retaining a domain type and a chosen argument, and negative steps retaining a data path tail.✦ Its wrapper sends to at the identity, replaces the preceding wrapper by the data function type from the retained domain to that wrapper at a positive step, and by the data function type from that wrapper to the retained tail carrier at a negative step.✦ Its parity counts negative path steps. An observation channel consists of odd logical, raw and predicate paths , and .✦ Its logical element type and predicate type are the wrapper types in (2). (2) A positive data path is a finite path of positive extensions, each retaining a fixed domain type and a chosen argument✦; its wrapper forms successive nondependent function types in data mode with those domains.✦ A data path tail consists of a terminal sort, a positive data path, and fixed encoding and decoding proof paths✦; its carrier is the positive wrapper of that sort✦, encoding follows the encoding proof path and positive injection✦, and decoding follows positive projection and the decoding proof path.✦ A data path tail ending at is formed when the singleton of its terminal sort belongs to , that sort has a nonempty axiom profile, its positive path runs from the axiom profile to , and its encoding and decoding proof paths run from the logical base to the singleton and back with even parity, with at least one negative step in the decoding path.✦
Wrapper reencoding sends an element from one retained path to another by observation along the source path and building along the target path.✦ Write and for the two channel reencodings. For a predicate and an element , channel evaluation is the formula obtained by observing along the predicate path against .✦ The encoded predicate is built along the predicate path with body , where is the raw input.✦
The channel roundtrip on is the map defined by . For a predicate , roundtrip invariance is the formula in (3). (3)✦
Relational coding fixes a uniform probe type , a logical path, and a predicate path, sharing the probe’s raw path.✦ The uniform probe type is the dependent product in data mode over the positive wrapper of the seed sort along the lifting path. Its codomain at a bound parameter is the wrapper along the even function path of the data function type from the single-bundle type at the positive projection of that parameter to the data tail carrier. Its elements specialize to that parameter and observe a single-bundle argument. Write , , and . Uniform probe syntax fixes a seed sort, an initial retained data path of chosen parity, odd raw and return paths, an even function path, a positive lifting path, and a data path tail. The specialization of a probe to a type is its application in data mode to the positive wrapper injection of along the lifting path.
For a type , its relational base type is its wrapper along the probe’s initial path.✦ The relational incidence formula observes the specialization of to against a bundle containing a dummy observation, the parameter , and the point encoding of .✦ The point encoding uses the raw channel encoding of and a constant truth marker. The section predicate of is the encoded predicate with body .✦
The relational lift is a logical-path builder whose body asks the section pair query at tag .✦ That query tests against the relational pair predicate of the section predicate and .✦ The pair construction uses class and edge queries with their actual admissibility guard: roundtrip invariance conjoined with the structural query at tag . For the observation channel over and admissibility condition , guarded observational equivalence of requires equivalent channel evaluations at and for every predicate satisfying .✦ The equivalence class predicate of , with admissibility condition , is the encoded predicate whose body compares its bound element with by guarded observational equivalence.✦ The class union predicate of , with admissibility condition , is the encoded predicate whose body is the disjunction of guarded observational equivalence with and with .✦ The pair membership condition for a predicate , an element , and a tested element holds when either some element satisfying has an edge of the first kind to , or has an edge of the second kind to , using the same admissibility condition and structural queries.✦
For a predicate , the uniform predicate probe is a data abstraction over the wrapped type parameter whose single-bundle body recovers the pullback of along relational lifting.✦ Recovery uses the dummy parameter test as its access guard. For a predicate and an element , the probe order formula is the observation of along the logical path against .✦ Predicate comparison and element comparison are the formulas in (4). (4)
An extensional predicate respects element comparison.✦ A valid element has order observations that respect predicate comparison.✦ Their defining formulas and are given by (5); quantification over elements uses , and quantification over predicates uses . (5)
Tagged Diagonal Data
A specialized relational coding fixes a three-copy observation system and a distinguished data type sorted at the probe’s seed sort.✦ Its specialized base type is ✦, and its tagged observation type is .✦ For , the copy embedding from to sends to by reencoding from the logical path to the first copy path and then using inner and outer signed embeddings. Their embedding bits are true exactly for and , respectively.
For a tagged element , the outer copy marker is the encoded bit observation of in the outer copy channel.✦ The inner copy marker is signed recovery along the outer copy channel with the inner channel bit observation as its test.✦ Let be the three-copy observation of against .✦ For tagged elements , tagged observational equivalence is the formula comparing their copy markers and all three-copy observations, as in (6). (6)✦
Write for specialized channel evaluation.✦ The left copy predicate of a predicate on is the encoded predicate in (7). (7)✦
The structural parameter is the structural query realization in the probe’s double channel, using the predicate path, the raw type of , and the constant truth marker.✦ Its seven branches, in order, are observation invariance , class representation , edge representation , and relational closure .✦ These properties of are defined in (8); the universal and existential element binders use and the logical existential construction. (8)
For a tagged element , the specialized lift is the logical element ✦; for a probe , specialized incidence is the formula .✦ The diagonal map is a map from to that sends each element to the lift of its tag-zero copy, by (9). (9)✦
The shifted predicate of a predicate is a predicate on encoded with a body that evaluates at the diagonal image of its bound argument, as in (10). (10)✦
A probe has a response predicate on , encoded with a body that tests incidence of with the tag-zero copy of its bound argument, as in (11). (11)✦
The Claim
Theorem 1. Assume the specialized coding satisfies its observation and channel formation conditions and its wrapper identities. For each data term with , the validity assertion is (12). (12)✦ For data terms with and , assume . Their diagonal images satisfy (13). (13)✦ Let be a data term with and assume . For every data term with , the evaluation equivalence is (14). (14)✦ The extensionality assertion for this predicate is (15). (15)✦ The response predicate of satisfies (16). (16)✦ For a data term with , assume also . The predecessor equivalence is (17). (17)✦
What Is Checked
The claims are stated over the ambient logical calculus and a specialized coding whose distinguished type is sorted at the seed sort in data mode, whose probe and retained paths satisfy their formation conditions at the prescribed feasible product profiles, whose inner and outer copy channels consist of successive odd paths, and whose wrapper identities identify with , the second outer path with the relational logical path, and the first outer wrapper of the middle-copy type with .