The Setting
The specialization of the guarded diagonal construction uses three tagged copies of a data type and an ambient logical calculus. The types assigned to those copies must agree with the data paths used by the calculus.
Fix a pure type specification , with arbitrary axiom and product-rule relations. Terms are variables, sorts, applications, annotated abstractions , and dependent products .β¦ Labelled terms attach to each application, abstraction, and product one of the labels , , and , whose argument and result modes are respectively data/data, data/proof, and proof/proof. Variable names are source notation for indices counted from zero at the nearest binder; contexts are written newest first. Label erasure deletes every labelβ¦, and a data-only term has label at every labelled constructor.β¦
Write for typing in , using its axiom, variable, weakening, product, abstraction, application, and conversion rules. In labelled typing, application uses the label of the functionβs product type. Full reduction contracts to the capture-avoiding substitution and closes under every term component, including annotations and binder bodiesβ¦; labelled head contraction requires matching application and abstraction labels. In either syntax, convertibility is the equivalence relation generated by this reduction. A normal form is a term that admits no step of full reduction, and a weakly normalizing term is a term that reaches a normal form in finitely many steps, possibly zero; write for its chosen normal form.
A mode environment assigns data or proof mode to each variable. Write for the mode discipline: variables have their assigned modes, sorts have data mode, and applications and abstractions respect their labelsβ argument and result modes. An abstractionβs annotation has data mode; both parts of a product have data mode, and the product has data mode. Binder bodies are considered in the environment extended by the labelβs argument mode. Proof-mode inhabitation of a labelled type means that some satisfies both and .β¦
Profiles and Logical Interpretation
For pure terms, a valid context is obtained from the empty context by adjoining a type that has some sort in the preceding context.β¦ For a pure context , a term having a normal form, a sort , and sets , the normal form sort profile , axiom profile , and product output profile are the sets in (1). (1) A feasible profile is a nonempty set realized as by a normal term in a valid context .β¦ A feasible product profile triple consists of three feasible profiles with .β¦
The primary signed graph has a positive edge for a strict inclusion of feasible profiles. Each feasible product profile triple supplies a negative edge and a positive edge . Positive reachability is the relation between profiles defined by the existence of a finite, possibly empty path using only positive edges in the primary signed graph.β¦ Fix a collection of profiles. An observation layer for a collection of profiles is a profile positively reachable in the primary signed graph from a nonempty with .β¦ A direct observation layer is an observation layer admitting a feasible triple with .β¦ A logical terminal profile for a collection of profiles is a profile that admits a feasible triple with .β¦
Sorting a labelled type at means for every ; additional sorts are permitted.β¦ A fixed feasible witness family assigns types and values to profiles. At every feasible , the type is data-only, its erasure is normal, and the conditions in (2) hold. (2)β¦
A proof wrapper is a finite sequence of positive and negative extensions, each with a fixed labelled annotation, starting from the identity wrapper.β¦ Its formation relative to specifies source and target profiles and parity. The identity has even parity; restricting a target to a subset changes neither wrapper nor parity. A positive extension along a feasible triple changes target to and records . A negative extension along records , requires , and changes parity. Parity counts negative extensions modulo two.
A typed open proof transformer from to is a term of type in that has proof mode when is assigned proof mode; the ambient variables in are renamed to avoid capture.β¦ An ambient logical calculus fixes and such transformers between every ordered pair of logical terminal witness types. It chooses a feasible triple with , an even proof wrapper from to , and an even proof wrapper from to . For every direct observation layer , it chooses a quantifier route: a feasible triple , an even proof wrapper from to , and an even proof wrapper from to . All these proof wrappers have formation relative to . The logical falsity witness of is the type .β¦
Retained Data Paths
A positive data path is an expression generated from the identity by extensions , each retaining a domain and a distinguished argument .β¦ The wrapped type and projection of a positive data path are defined in (3), where is the nondependent product with data argument and data result. (3) Formation of a positive path relative to starts at the identity, permits target restriction to a subset, and extends along a feasible triple using to change target to .β¦
A data path tail consists of a sort, a positive data path, and encoding and decoding proof wrappers.β¦ The carrier of a data path tail is .β¦ Formation of at requires , , and formation of from to . The wrappers must be formed even proof paths from to and back, respectively, and the decoding wrapper must contain a negative extension.
A retained data path is an expression generated from the identity by positive extensions and negative extensions .β¦ Positive extensions preserve parity and negative extensions reverse it. The wrapped type of a retained data path is defined in (4). (4) Formation of a retained data path relative to permits identity, target restriction to a subset, and positive extensions using the same witnesses as positive paths. A negative extension along a feasible triple changes target to and uses a formed tail ending at . Write for concatenation in path order, so that and the parities add modulo two.β¦
A double data channel consists of two odd retained paths.β¦ A double data channel is formed from through to when its two paths are formed at those successive endpoints.β¦ The double wrapper carrier , iterated carriers for , predicate code type , and parameter type of a double data channel are given in (5); the fourfold carrier is . (5)
Probes and Specialized Observations
A uniform probe is a tuple consisting of a seed sort , an initial path of parity , odd raw and back paths , an even function path , a positive lifting path , and a tail .β¦ Formation of a uniform probe at requires feasible triples and , a nonempty , a formed tail ending at , and the path endpoints in (6); the lifting path has formation relative to and the other paths relative to . (6)β¦
The probe double wrapper is .β¦ The probe domain , raw type, parameter type, single bundle type, function type, codomain family, and common carrier are defined in (7). Ambient paths and annotations under the binder are renamed without capture. (7)
An observation channel consists of odd logical, raw, and predicate paths .β¦ It is formed at when these paths run respectively from to , from to , and from to β¦; its logical channel type at is .β¦ A shared relational code is a triple consisting of a uniform probe and logical and predicate paths , whose observation channel uses the raw path of . A shared relational code is formed at when its probe and channel have formation at the indicated profiles.β¦ The relational base type of a shared relational code at is , where is the initial path of .β¦
Tagged copy syntax consists of odd source and first paths and double channels .β¦ Its first copy, middle copy, and three-copy carrier are defined in (8). (8) A three-copy observation code uses and ; its observation carrier is .β¦ A three-copy observation code is formed when is formed, is formed from through to , and is formed from through to .β¦
A specialized code is a pair consisting of a three-copy observation code and a type .β¦ The underlying relational code of a specialized code is , its specialized base type is β¦, and its tagged observation type is .β¦ Write when is formed and the seed sorting, data-mode condition, and carrier identities in (9) hold. Here are the first and second paths of . (9)
The Channel Return
A fixed channel configuration is a formed shared relational code at whose logical and predicate profiles are direct observation layers.β¦ Its access probe, double code, and relational code are , , and . A parity-matched channel return for is a retained data path formed from to with the same parity as .β¦ The even return loop, outer odd wrapper, outer double channel, source type, and specialized source code of a parity-matched channel return for a fixed channel configuration are defined in (10); its inner double channel is .β¦ (10)
The Claim
Theorem 1. Let be an ambient logical calculus in with mode environment . Let be a fixed channel configuration at and let be a parity-matched channel return for . Then (11)β¦
Theorem 2. Let be an ambient logical calculus in with mode environment , and let be a specialized code formed relative to at profiles . There is a term with (12)β¦
In the paper, the result reads: the specialized relational construction yields a proof of in the ambient labelled context.
What Is Checked
The source formation statement (11) and the inhabitation statement (12) are stated over labelled typing, the mode discipline, a fixed feasible witness family and ambient logical calculus, and the retained channel paths with their profile and carrier conditions.