The Setting
The relational diagonal construction uses a data parameter to select conditions on predicates. Here that parameter is fixed by seven structural properties of predicates on a carrier with three tagged copies. The formulas concern labelled terms in a pure type system , with arbitrary axiom and product-rule relations, a context , and an assignment of data and proof modes.
Fix a logical calculus with falsity , incoming and outgoing proof paths, and universal quantifiers and from its quantifier routes. Its implication applies the outgoing path to the proof-to-proof arrow from the incoming wrapper of the antecedent to the consequent. Negation is implication to ; conjunction is β¦, disjunction is β¦, and is the conjunction of the two implications.β¦ Existential quantification is .β¦ Element quantification uses and predicate quantification uses ; universal quantification applies its incoming proof path beneath a data-to-proof dependent product and its outgoing path outside it.β¦ The logical conditional with guard and branches is .
A formula is inhabited in proof mode in context under the mode assignment , written , when it has an inhabitant satisfying the proof mode discipline.β¦ Formula equivalence between formulas and in context under the mode assignment means uniform typed open transformers in both directions, with a temporary proof input: (1) The inputs and in (1) have proof mode. The mode discipline for labelled terms under gives each variable its assigned mode and each sort data mode, and an application has its labelled result mode when its function has that mode and its argument has the labelled argument mode. An abstraction has its labelled result mode when its annotation has data mode and its body has the result mode under extension by the argument mode; a dependent product has data mode when its domain and codomain have data mode, checking the codomain under that same extension.
Channels and Tagged Observations
A specialized relational coding fixes an observation system and a type .β¦ Its underlying relational coding has a common probe type , an initial data path , and odd retained data paths , and for logical, raw and predicate channels. A retained data path is generated by identity, positive extensions with a fixed domain and dummy value, and negative extensions with a data tail; its parity counts negative extensions.β¦ Positive extensions form data arrows into the previous wrapped type, and negative extensions form data arrows from that type to the tail carrier. A double channel consists of two odd paths.β¦
Let and be the inner and outer double channels of the observation system. The specialized base type , logical probe element type , tagged observation type , and predicate types are (2) Fix a seed sort for the probe. The common probe type is a data dependent product over a positive wrapper of that sort. At a type parameter, its codomain is a wrapped function from a single-bundle type to a data tail carrier.β¦ The tail encodes formulas by its encoding proof path followed by positive injectionβ¦, and reads them by positive projection followed by its decoding proof path.β¦
Reencoding between odd paths builds a term along the target path from the observation associated with the source path.β¦ Write for reencoding from to , and for the reverse reencoding. For a type , channel evaluation takes a predicate and an element , and the channel roundtrip takes an element ; their definitions are (3) The observation in (3) instantiates the supplied body at an identity path, applies the retained dummy at a positive step, and at a negative step builds the argument along the preceding path and decodes the resulting application through the tail.β¦ For a type and a formula-valued body on , the encoded predicate is a predicate in built along over from composed with reencoding from to .β¦ Write for specialized evaluation.β¦ The data path builder along a retained path returns its supplied term at the identity path and forms a constant data abstraction at a positive extension. At a negative extension it abstracts over the preceding wrapped type, observes that input along the preceding path against the supplied term, and encodes the resulting formula through the tail.
For and , the tagged copy is an element of obtained by first reencoding from to at . It then uses signed payload embedding along the inner double channel with sign true exactly at , and along the outer double channel with sign true exactly at . Signed embedding builds along the second path from the first pathβs contravariant observation, keeping that formula for a true sign and negating it for a false sign.β¦ Signed recovery uses the observed marker bit to choose between evaluation and its negation.β¦ Double channel evaluation at a type observes its input along the second path against the term built along the first path from the supplied predicate body. The iterated signed embedding of a term at a type along a finite list of signs leaves unchanged for the empty list. For a list beginning with , it first embeds along the remaining signs and then applies signed embedding with sign at the carrier obtained by one double channel iteration for each remaining sign. The iterated recovery predicate of a predicate body at depth zero is . At depth , it performs signed recovery at the carrier obtained by double channel iterations, using the depth recovery predicate as its test.
The query bit string of an index is the list of its binary digits at positions zero through three, in that order.β¦ The nonzero query index of an observation tag is .β¦ The query tagged embedding of a term at a type with query index is its iterated signed embedding along the query bit string of .β¦ The tag predicate for an empty list of signs is logical truth. For a list beginning with , it conjoins the marker bit when is true, or its negation when is false, with signed recovery of the tag predicate for the remaining signs, both at the carrier obtained by one double channel iteration for each remaining sign.
Let be the inner marker recovered through the outer channel, and let be the outer marker. For a predicate , let denote its uniform predicate probe. A specialized probe observation of recovers through both channels and tests the recovered payload with .β¦ Tagged observational equivalence of elements is the formula (4)β¦
Probe Order and Structural Properties
The uniform predicate probe of a predicate is a data abstraction over the lifted type parameter, followed by a wrapped abstraction over its single-bundle argument. Relational element lifting sends an element of the relational base type to by building along the logical path at from its section pair query as a function of the probe.β¦ The body of uses recovery access to the predicate pulled back along this lifting, at the positive projection of the type parameter. Recovery access retains the dummy parameter test as its guard. For a predicate and an element , the probe order is the formula obtained by observing along the logical path at against .β¦ Predicate equivalence for , probe element equivalence for , extensionality of a predicate , and order validity of an element are the formulas (5)
The probe double channel has the return path as its first path and as its second path.β¦ For a double channel at a type , its predicate code type is the first path wrapper of the fourfold carrier, obtained by applying the double channel carrier four times to , and its parameter type is the second path wrapper of that predicate code type. The probe parameter type at is this parameter type at the probe raw type obtained by applying the initial path and then the raw path to .β¦
For a double channel at a type , a source data bundle for observations is a term built along its second path from the conditional whose guard and branches are their contravariant observations along its first path, in that order.β¦
Bundle access observes its object along the second path against an access probe built along the first path.β¦ The probe tests the supplied guard, returns logical truth when it holds, and otherwise composes the object observation callback with the supplied inner data callback.β¦
The inner observation probe is built along the first path over the parameter type from the conditional that returns falsity on the dummy parameter test and otherwise returns the observation query at tag .β¦
Constant falsity determines the bottom predicate code at along the first path over the fourfold carrier of .β¦
Along the second path over the predicate code type, constant truth determines the dummy observation at .β¦
For marker and payload , construct the encoded data point along the second path over the predicate code type. Its body conjoins the marker at tag with the contravariant observation of after payload decoding.β¦
To specialize a probe to a type , apply in data mode to the positive injection of along the lifting path.β¦
The probe application observation at observes the specialized probe along the function path against the callback that applies the recovered function in data mode to the supplied single bundle and decodes the result through the tail.β¦
For the channel relation with an admissibility guard, the equivalence class predicate of is the encoded predicate whose value at is that guarded observational relation between and .β¦
The class union predicate of is the encoded predicate whose value at is the disjunction of the guarded observational relations from to and from to .β¦
For a seven-query family, the class query at applies query to the equivalence class predicate of the given element, with the supplied admissibility guard.β¦
A false tagged edge from to requires class queries and at its endpoints and query on their class union predicate. A true tagged edge instead uses endpoint classes and and query , throughout with the supplied admissibility guard.
Pair membership for a predicate and element at is the disjunction of the existence of an element satisfying with a false tagged edge to , and a true tagged edge from to , using the same queries and admissibility guard.β¦
The pair predicate of and is the encoded predicate whose body is their pair membership formula.β¦
At , encode a relational point as the encoded data point in the probe double channel at the probe raw type of , using the predicate path, the constant truth marker and the raw channel encoding of .β¦
For at , take the source data bundle in the probe double channel at the probe parameter type of as their relational argument bundle. Its three observations are the dummy observation at the probe raw type of , and the relational point encoding of .
Observing a probe at against the relational argument bundle of by probe application gives its diamond observation against .β¦
The relational base type of a type is the type obtained by applying the initial path to .β¦ Encode the function assigning to the diamond observation of against as a predicate over this base type; this is the probe section predicate of at .β¦
To obtain the relational pair predicate at , use the channel pair predicate over the relational base type of , taking roundtrip invariance conjoined with structural query as its admissibility guard and the seven structural queries of as its query family.β¦
Observation query of against the relational pair predicate of the probe section predicate of and gives the section pair query of at .β¦
For , observation invariance , class representation and edge representation are (6) For , the left copy predicate is the encoded predicate .β¦ Relational closure of a predicate is the formula (7)β¦ The seven properties selected by the structural parameter are, in their order, (8)β¦
The Chosen Parameter
The parameter is the structural query realization in the probe double channel at the raw type . Its constant truth marker is built along from logical truth.β¦ Its body is the finite marked disjunction of the seven branches , each composed with the payload decoder and conjoined with the corresponding marker.β¦ This realization uses the predicate path . For a predicate and one of the seven structural tags , the parameter query is the formula obtained by tagged observation of against the payload encoding of at tag .β¦
Roundtrip invariance of a predicate is the formula requiring uniform equivalence of its evaluations before and after the roundtrip.β¦ Goodness of a predicate and the specialized coded relation between elements are the formulas (9) The admissibility guard in (9) is the specialized structural admissibility predicate at and .
The Profile Conditions
The normal form sort profile of a term in context is the set of all sorts typing its chosen normal form : (10) A feasible profile is a nonempty set for some normal term in a valid context .β¦ A valid context is a context obtained from the empty context by extensions with for some sort .β¦ A feasible product profile triple consists of feasible profiles with , using (10).β¦ Normality here is for full reduction, including annotations and binder bodies. Relative to the collection of profiles used by , a terminal profile is a feasible profile occurring in a feasible product profile triple with .β¦ The product output profile consists of every output sort permitted by a product rule whose domain sort belongs to and whose codomain sort belongs to .β¦
In the primary signed graph, a positive inclusion edge goes from a feasible profile to a feasible proper subset . Every feasible product profile triple supplies a negative domain edge from to and a positive codomain edge from to , and these are all the primary edges. Positive reachability means a finite, possibly empty path all of whose edges are positive.β¦ Relative to a collection of profiles, an observation layer is a profile positively reachable in the primary signed graph from a nonempty axiom profile with .β¦ Relative to a collection of profiles, a direct observation layer is an observation layer for which a feasible product profile triple has .β¦
The ambient logical calculus has fixed feasible witnesses whose types are data-only normal forms sorted at every sort in the assigned profile, with a chosen inhabitant of each type; both types and inhabitants have data mode.β¦ For every two terminal profiles, the calculus has a uniform typed open proof transformer between their chosen witness types. It fixes a feasible product profile triple with all three profiles in , an even incoming proof path from to , and an even outgoing proof path from to . For every direct observation layer , a quantifier route chooses a feasible product profile triple , an even incoming proof path from to , and an even outgoing proof path from to . The probe has feasible product profile triples and , a seed with nonempty axiom profile, and paths with endpoints (11) In (11), the return and raw paths are odd, the function path is even, the lifting path is positive, and the data tail ends at . Let and be the target profiles of the logical and predicate channels. The shared logical channel runs from to , and the predicate channel from to . The inner observation double channel runs from through to , and the outer one from through to . The type satisfies in data mode. In addition to the carriers of (2), the specialization requires (12) The subscripts in (12) designate the first and second paths of the outer double channel. Each negative data tail has an even decoding proof path containing a negative step.
The Claim
Theorem 1 (Lemma 49). Let the specialized relational coding and the logical quantifiers satisfy their path, sorting and carrier conditions. For every with and data mode under , (13)β¦ For with and , both in data mode, (14)β¦ For with and , both in data mode, and every tag , (15)β¦ For such and distinct tags , (16)β¦
What Is Checked
The statements (13), (14), (15) and (16) concern the specialized relational coding under these profile and shape conditions, with labelled typing and the data and proof mode discipline interpreted by (1).