The Setting
The guarded diagonal argument takes place between logical probe elements and a carrier with three tagged copies. Its induction formulas are labelled terms, alongside the data terms on which their observations are taken.
Fix a family of sorts . Labelled terms are variables, sorts, applications, annotated abstractions , and dependent products .✦ The label records the argument and result modes: means data to data, data to proof, and proof to proof.✦ Bound variables below are written by name, and substitution avoids capture.
A retained data path is a finite path generated by the identity, positive extensions with a fixed domain and dummy argument, and negative extensions with a fixed data tail.✦ The parity of a retained data path is the number of its negative extensions modulo two. A positive extension adds a constant annotated data abstraction; its observation applies the retained dummy argument. A negative extension reverses the arrow and uses its tail to encode and decode the resulting formula. A data tail consists of a terminal sort, a positive data path containing only positive extensions, and encoding and decoding proof paths generated by identity, positive data-to-proof arrows, and negative proof-to-proof arrows. Positive data path injection uses constant data abstractions, and projection applies the retained dummy arguments. The carrier of a data tail is the positive wrapper of its terminal sort along its positive path. Data tail encoding applies the encoding proof path to a formula and then takes the positive injection. Data tail decoding of a term first takes its projection along the positive path and then applies the decoding proof path.
For a retained data path and a data type , write for the wrapped data type. For odd , write for its data path builder from a one-variable formula body, and for its data path observation. The wrapper reencoding from an odd path to an odd path is the operation on data terms defined by (1). (1)✦
A logical syntax is a choice of falsity and incoming and outgoing proof paths .✦ A universal quantifier syntax is a choice of proof paths .✦ Implication and quantification are the labelled constructions in (2); a nondependent arrow has a codomain independent of its bound variable. (2)
The logical connectives and guarded quantification are defined by (3). Formula equivalence denotes uniform typed proof-term transformers in both directions. (3)
Channels and Relational Lifting
A uniform probe is a choice of a seed sort, an initial path of either parity, odd raw and back paths, an even function path, a positive lifting path, and a data tail.✦ A relational coding is a choice of a uniform probe and odd logical and predicate paths .✦ The raw path of a relational coding is the raw path of its uniform probe . These three paths form the shared logical channel.✦ For a relational coding and a base type , the logical, raw, and predicate types are , , and . Channel evaluation and predicate construction are given by (4); the latter takes an open formula on logical elements. (4) The logical channel encoding of a raw term at is its wrapper reencoding from the raw path to the logical path .
The channel roundtrip is . Fix universal quantifier syntaxes . Roundtrip invariance and observational equivalence with an admissibility guard are the formulas in (5). (5)
A double data channel consists of two odd paths, with carrier . For a double data channel at a type , the fourfold carrier is , the predicate code type is , and the parameter type is . Signed payload embedding uses the builder along with the positive or negated contravariant observation along .✦ Its bit observation tests against constant truth.✦ Signed payload recovery is the logical conditional selecting double channel evaluation or its negation by that bit.✦ Double channel evaluation observes along against a predicate built along .✦
Query tags use four bits, the binary digits zero through three of an index among , in that order.✦ The corresponding tagged embedding iterates signed embedding four times.✦ Tag predicates combine the selected bit conditions with successive signed recoveries.✦ For a double channel , an odd predicate path , a type , and a predicate , the tagged payload code for query is built along over . Its body is the disjunction of the tag- marker and the conjunction of the tag-zero marker with four successive signed recoveries of observation by along ; payload decoding builds a predicate along at whose body observes the code along against the tag-zero embedding of its argument. A tagged query observes a parameter against the corresponding encoded predicate.✦ A structural query realization is the second-path builder whose body is the finite marked disjunction of seven branches, each branch conjoining its tag marker with its formula on the decoded predicate.✦ The disjunction ends in .
The double channel of is .✦ For a type , write for its initial-path wrapper.✦ The probe raw type is ✦; its parameter type is the double-channel parameter type at ✦, and its single bundle type is the double carrier of that parameter type.✦ The common probe type of a uniform probe is a dependent data product over the positive wrapper of the seed sort whose codomain at a parameter is the function-path wrapper of the data arrow from the single bundle type at the positive projection of to the data tail carrier. Uniform probe abstraction binds that parameter and then a single bundle argument, encoding its formula through the tail and building along the function path.✦ Probe specialization applies a probe in data mode to the positive injection of ✦; probe application observation decodes its result after function-path observation.✦
For a type and parameter , the relational incidence formula is the probe application observation of at against the relational argument bundle of and .✦ The relational argument bundle of a parameter and an element at a type is the data term built along the raw path over the back-path wrapper of the probe parameter type of . Its body is a logical conditional whose guard, true branch, and false branch are respectively the contravariant observations along the back path of the dummy observation, , and the relational point encoding of .✦ The dummy observation at is the term built along the raw path over the predicate code type of the probe double channel at , with constant truth body. The relational point encoding of at is the term built along the raw path over the predicate code type of the probe double channel at . Its body conjoins marker seven, using the constant truth marker , with predicate-path observation of the decoded input against the raw channel encoding of .✦
Write for structural query of against , using the predicate path at probe raw type .✦ The structural admissibility condition is .✦ The equivalence class predicate has body ✦; the union of two class predicates has the disjunction of their bodies.✦ The class query is for .✦ The two edge formulas and the relational pair predicate are defined in (6). (6)
The section predicate , the section pair query , and the relational element lift are respectively the channel predicate, formula, and labelled term defined by (7). (7)
For a predicate , its uniform predicate probe abstracts the type parameter and single bundle argument and uses recovery access with the parameter-dependent predicate pullback .✦ Here is the positive projection of the bound type parameter, and is the bound parameter. Recovery access uses the dummy parameter test as its outer conditional guard, with truth as its dummy branch. Its inner probe has falsity as its dummy branch and the payload query as its other branch; the non-dummy branches retain the negated dummy test through the conditional of (3). For a double channel at a type , the dummy parameter test is the observation of a fresh parameter along against the bottom predicate code, the data path builder along over with constant falsity body.
The probe order is the logical-path observation .✦ Put .✦ Predicate equivalence, probe element equivalence, predicate extensionality , and probe order validity are the formulas in (8). (8)
The Specialized Observation System
A three-copy observation system is a choice of a relational coding and inner and outer double channels .✦ Its copy source is and its first copy path is . The tagged observation carrier and tagged copies are given in (9), where denotes signed payload embedding with positive sign when holds and negative sign otherwise. (9)
The specialized probe observation performs outer signed recovery and then inner signed recovery, with raw-path observation against as its innermost test.✦ The outer marker is the outer channel bit✦; the inner marker is recovered through the outer channel.✦ Tagged observational equivalence is defined by (10). (10)✦
A specialized relational coding consists of and a chosen type .✦ For a specialized relational coding with chosen type , the specialized base type is , and the specialized channel evaluation is . The left copy predicate is .✦ Observation invariance , class representation , edge representation , and relational closure are the structural formulas in (11). (11)
The structural parameter is the structural query realization in the probe double channel at , using predicate path , constant truth marker , and the seven branches, in order, , , , , , , .✦ Specialized incidence and specialized lifting are the fixed-parameter constructions in (12). (12)
The Definition
Definition 1. Fix a specialized relational coding , logical syntax , and universal quantifier syntaxes .
The response predicate of a term is the channel predicate in (13). (13)✦
The data shift is the operation on labelled terms defined by (14). (14)✦
Pulling a predicate back along gives the shifted predicate in (15). (15)✦
For a predicate , define its guarded induction formula by (16). (16)✦
The well-foundedness object is the labelled term defined by the logical-path data construction in (17). (17)✦
What Is Checked
These definitions are stated over labelled terms and the fixed specialized relational coding, logical syntax, and two universal quantifier syntaxes.