The Setting
The guarded diagonal construction compares incidence on tagged observations with an order on logical probe elements. These belong to different carriers: a probe is tested against an observation, whereas a channel predicate is evaluated at a logical element.
Fix a pure type specification , a context , and an assignment of data and proof modes to its variables. The axiom and product-rule relations are arbitrary. Write for typing together with data mode, and use for proof mode. A formula is inhabited in proof mode, written , when some term satisfies .β¦ Formula equivalence means the existence of uniform typed open proof-term transformers in both directions, with a temporary proof input of the respective source formula.β¦
Take an ambient logical calculus with its fixed feasible witness family and quantifier routes. Its logical operations use incoming and outgoing proof paths; and denote the routes for element and predicate quantification. The connectives below are those of , and and denote these two quantifiers. In particular, is the conjunction of the two logical implications between the formulas.β¦
Let be a specialized relational coding with distinguished type and a three-copy observation system. Write for its common probe type, and , and for the shared channelβs logical, raw and predicate paths. A path applied to a type denotes its data wrapper. If is the probeβs initial path, the carriers in (1) are the logical element type , predicate type , and specialized base type ; is the tagged observation carrier. (1) The last identity is a compatibility condition on the observation system. Its outer second path is the relational logical path, and its outer first wrapper of the middle-copy carrier is .
Incidence and Response
For a type , a channel predicate on and a logical element of , channel evaluation is the formula obtained by observing along the predicate path against the raw reencoding of .β¦ The channel predicate on a type is the predicate formed from a one-variable formula by reencoding its argument from the raw path to the logical path in its body.β¦ For a logical probe element of type , the tagged copy , for , is an observation of type obtained by reencoding from the logical path to the raw path and applying the inner and outer copy embeddings.β¦ Their marker bits are true precisely at and , respectively.
The channel predicate type on is .β¦ The structural parameter is the query realization of observation invariance, class representation in all three copies, edge representation in copies and , and relational closure.β¦ The relational closure condition for says that, if its left-copy predicate, whose body evaluates on tag-one copies of logical probe elements, is extensional, then that predicate lies below every valid logical element for which the right-copy evaluation holds.β¦ For a probe of type and a tagged observation of type , the incidence formula observes at against the relational bundle whose observations are the dummy observation, , and the point encoding of .β¦
For and , the specialized probe observation of by is the three-copy observation of against the uniform predicate probe , at the common probe type .β¦ For , specialized observational comparison is the formula asserting that their specialized probe observations are logically equivalent for every channel predicate .β¦ Tagged observational equivalence of is the conjunction of their specialized observational comparison and logical equivalence of their respective inner and outer markers.β¦
The left-copy evaluation of at is β¦; the left-copy predicate of is the channel predicate on with this evaluation as its body.β¦
The specialized observational relation between tagged observations and of type is the guarded formula (2). The admissibility condition on a channel predicate of type is the conjunction of roundtrip invariance of and its structural query of index zero at .β¦ Roundtrip invariance of a channel predicate of type is the condition that its evaluations are logically equivalent before and after reencoding to the raw channel and back to the logical channel.β¦ (2)β¦
At the base type with admissibility condition , the equivalence class predicate of is the channel predicate whose value at is .β¦ The class union predicate of , at the base type with admissibility condition , is the channel predicate whose value at is the disjunction of and .β¦ The class query placing in class is the structural query of index at applied to the equivalence class predicate of , for .β¦
For a probe of type , the response condition is the formula (3) requiring incidence with to respect the specialized observational relation. (3) The response predicate is the channel predicate on logical probe elements with tag-zero incidence as its body, as defined in (4). (4)β¦ The response predicate is defined for every probe , whether or not is inhabited in proof mode.
Order and Validity
For a probe of type , the section predicate is the channel predicate on whose body is incidence with .β¦ For a probe of type and a tagged observation of type , the section pair query is the structural query of index at , applied to the relational pair predicate of the section predicate of and .β¦ The pair predicate uses the actual admissibility condition and the structural query family: its membership formula at is the disjunction of a class- edge from an element satisfying the section and a class- edge from . The first alternative is existentially quantified over the witnessing element.
The relational element lift of a probe of type is a logical probe element of type whose observations are the section pair queries of . For a channel predicate , its uniform predicate probe recovers the pullback of along this lift, uniformly over the type parameter and single-bundle argument.β¦ For a channel predicate of type and a logical probe element of type , the probe order formula is the observation of along the logical path against .β¦
Predicate equivalence between channel predicates and of type , and probe element equivalence between logical probe elements and of type , are the formulas in (5). (5) Extensionality of a channel predicate of type and validity of a logical probe element of type are the formulas (6) expressing respect for probe element equivalence and predicate equivalence, respectively. (6)
The Claim
Theorem 1. Assume the specialized observation system satisfies its retained-path profile conditions and the carrier and path compatibilities above. Assume also , where is the probeβs seed sort. Let satisfy , and suppose is inhabited in proof mode.
For every satisfying , the exact evaluation law is (7). (7)β¦ The extensionality assertion is (8). (8)β¦ If, in addition, is inhabited in proof mode, the predecessor law is (9). (9)β¦
What Is Checked
The statements range over labelled terms with their typing judgments and data or proof modes, an ambient logical calculus with element and predicate quantifier routes, and compatible specialized three-copy observations with a seed-sorted distinguished type.