The Setting
In the diagonal construction, induction is expressed through data predicates and their observations on logical probe elements. The order observation of a predicate at an element is distinct from its evaluation there.
Fix a pure type specification , with arbitrary axiom and product-rule relations, a context , and a mode assignment . Terms have variables, sort constants, applications, annotated abstractions , and dependent products .β¦ Variable names are source notation; the terms use de Bruijn indices and newest-first contexts. Renaming and simultaneous substitution act without capture under binders; instantiation replaces index zero and lowers the older indices. Full reduction includes annotations and binder bodies, and convertibility is its equivalence closure. A normal term is a term admitting no step; a weakly normalizing term is a term that reduces to a normal term. Erasure removes the labels from labelled terms.β¦
The labels , , and specify data to data, data to proof, and proof to proof.β¦ The mode discipline assigns variables their modes in and sorts data mode. Applications use their labelβs argument and result modes; abstractions use the argument mode for the bound variable and the result mode for the body. Abstraction annotations and product domains and codomains are checked in data mode; products themselves have data mode. A productβs bound variable has the labelβs argument mode. A data-only term is a labelled term with label at every labelled constructor.β¦ Extending assigns the fresh variable its declared mode and shifts the older assignments.β¦
Proof-mode inhabitation is the existence of a proof-mode term of type .β¦ A typed open transformer from to uses a temporary proof input of type ; formula equivalence means uniform typed transformers in both directions, as in (1). (1)
Profiles and Logical Operations
The axiom successors, product outputs, and normal form sort profile are the sets in (2); denotes the chosen full normal form when one exists, with a fixed fallback otherwise. (2) A valid context is a context built from the empty context by repeatedly adjoining a type whenever the current context satisfies for some sort . A feasible profile is a nonempty set for a normal term in a valid context .β¦ A feasible product profile triple consists of feasible profiles with .β¦ Sorting a labelled type at requires its typing at every sort in , and permits additional sorts.β¦
Fix a collection of profiles. In the primary signed profile graph, strict feasible inclusions give positive edges . A feasible triple gives a negative edge and a positive edge . An observation layer is a profile reachable in the primary signed profile graph by a possibly empty path of positive edges from a nonempty with .β¦ A direct observation layer is an observation layer admitting a feasible triple with .β¦ A logical terminal profile is a middle profile of a feasible triple with .β¦
A fixed feasible witness family is a family of pairs consisting, for every feasible , of a data-only type with normal erasure, sorted at , and a value with ; both choices have data mode.β¦ An ambient logical calculus supplies such witnesses, uniform typed transformers between their types at logical terminal profiles, and a feasible triple in . It has paths from to and from to built from the identity by positive data-to-proof and negative proof-to-proof arrow extensions, with an even number of negative extensions, and quantifier routes for direct observation layers. A quantifier route for chooses a triple and even proof wrapper paths from to and from to .β¦
A proof wrapper is a path built from the identity by positive and negative arrow extensions: a positive extension forms a data-to-proof arrow into the preceding wrapped type, and a negative extension forms a proof-to-proof arrow out of it. Its paths may restrict the target profile; extensions follow feasible product triples, and a negative extension requires its source and target in . Parity counts negative steps. Write for the logical wrappers and for a quantifierβs wrappers. The falsity type is , and the logical operations in (3) use these fixed paths. Here denotes a formula body with the indicated fresh variable. (3) A guarded universal quantifier is a universal formula with body . The logical conditional with guard and branches is ; a finite marked disjunction joins marker and property at each index and ends in . Fix quantifier routes and , and write and for quantification along these routes, respectively.
Channels and Relational Lifting
A positive data path is a path built from the identity by adding data arrow domains with retained witness arguments; its target may be restricted to a subset. Its injection uses constant annotated abstractions, and its projection applies those arguments. A retained data path is a path starting with the identity and allowing positive data arrow extensions and negative extensions by data tails, with parity given by the number of negative extensions modulo two.β¦ Positive extensions follow triples using ; negative extensions follow triples using a data tail ending at . A data tail is a choice of a terminal sort with and nonempty , a positive path from to its endpoint, an even encoding proof path from to , and an even decoding proof path back. The decoding path contains a negative step. Its carrier is the positive wrapper of ; encoding applies the encoding proof path before injection, and decoding projects before applying the decoding proof path.
For a retained path and a type , write for the wrapped data type, for the data realization of a body , and for the observation of an element against a test . The identity leaves types and realizations unchanged and observes by instantiation. At a positive extension the wrapped type adds a data domain, the data realization adds a constant abstraction, and observation applies the retained argument. At a negative extension the wrapped type is a data arrow to the tail carrier, the data realization sends an inner observation through the tail, and observation applies the input to an inner realization before decoding. An odd pathβs observation body fixes and varies its test; its contravariant observation body fixes the test and varies . Reencoding from one odd path to another realizes the first pathβs observation body along the second path.β¦ Open composition substitutes one formula body into another.β¦
A double channel consists of two successive odd retained paths.β¦ The carrier of a double channel at a type is the type obtained by applying its two successive wrappers; the fourfold carrier of the double channel at is the type obtained by iterating that operation four times. Its bit observation tests the first channelβs constant truth realization along the second channel.β¦ Signed payload embedding realizes a positive or negated observation body, and recovery uses its marker bit to select evaluation or negated evaluation. Query tags use four binary digits: query zero is the payload query, while a tag uses query . For a double channel at a type , the tagged payload encoder is the data realization along its first path at the fourfold carrier of whose body is the disjunction of the nonzero tag predicate and the conjunction of the payload tag predicate with depth-four recovery of the payload observation. A query observes a parameter against that encoder. Structural realization is the data realization along the second path at the predicate code type, with body the finite marked disjunction of its seven decoded branches. An encoded data point at is the data realization along the second path at the predicate code type of whose body conjoins the final tagβs marker with the payload observation after decoding. The dummy observation at is the data realization of the constant truth body along the second path at the predicate code type of . The bottom predicate code realizes constant falsity along the first path at the fourfold carrier; the dummy parameter test observes a parameter against that code. For a double channel at a type , the predicate code type is the first pathβs wrapper of the fourfold carrier of . Double channel evaluation of against a formula body at observes along the second path against the first pathβs data realization of at . The query bit string of a query among the nine indices is the list of its binary digits zero through three, in that order. Iterated signed embedding of a payload along an empty bit string leaves it unchanged; along a nonempty string it first embeds along the remaining bits, then applies signed embedding with the first bit at the carrier iterated once for each remaining bit. The query tagged embedding of a payload at is its iterated signed embedding along the query bit string. The payload decoder into an odd retained path at is the data realization along that path of the predicate codeβs observation against the query tagged embedding at query zero.
A shared relational construction has a uniform probe and odd logical, raw, and predicate paths .β¦ The probe has seed sort , an initial retained path, odd raw and return paths, an even function path, and a positive lifting path. Its common type is a data dependent product over the positively wrapped seed sort. At a bound parameter, its codomain applies the function path to the data arrow from the single-bundle type at the parameterβs positive projection to the data tail carrier. The probe double channel uses the return path followed by the raw path.β¦ The probe raw type applies the initial path and then the raw path to a type ; its parameter type applies the first and second probe double wrappers to that raw typeβs fourfold carrier. A single-bundle type is the probe double wrapper of this parameter type.β¦ Specialization applies a probe to the positive injection of a type parameter. The uniform probe for a formula body is a data abstraction over the positively wrapped seed sort; at the positive projection of its bound parameter, its body is the data realization along the function path, at the probe function type of , of the data abstraction over the single-bundle type of whose body is the tail encoding of . Probe observation specializes, observes along the function path, and decodes the resulting application through the tail.β¦
The shared channelβs types and evaluation are given in (4). The channel predicate realizes the body along at , after reencoding its fresh argument from to .β¦ (4) At a type let be its initial wrapper type, and let be a probe parameter. Write for its structural query at tag , for . A channel predicate is admissible when it satisfies roundtrip invariance and the tag-zero query.β¦ Its guarded observational equivalence is defined in (5). (5) The class predicate is the channel predicate with body , and its class query at is . The class union predicate of two guarded observational equivalence classes is the channel predicate whose body is the disjunction of their class predicate bodies. The left edge formula joins the class of at index zero to the class of at index one and tests their union at query four; the right edge formula joins the class of at index zero to the class of at index two and uses query five.β¦ The pair membership formula and relational pair predicate are defined in (6). (6)
The diamond observation is probe observation against the bundle containing the dummy observation, , and the point encoding of .β¦ The bundleβs conditional selects the parameter or point observation using the contravariant dummy observation as its guard.β¦ The section predicate of a probe is a channel predicate with body .β¦ The relational lift in (7) realizes the tag-six query of the pair formed from that section and its argument. (7) For a predicate on logical probe elements, the uniform predicate probe abstracts the positively wrapped type parameter and recovers the pullback predicate with body from its single bundle. The inner recovery probe uses the dummy parameter test with falsity as its dummy branch; the outer access uses the same test with truth as its dummy branch. The recovered parameter supplies the pullbackβs . Logical probe elements, their predicates, and the probe order are defined in (8). (8)
Validity and the Induction Object
Predicate equivalence is the relation between predicates on the logical probe elements given by pointwise formula equivalence under .β¦ Probe element equivalence is the relation between logical probe elements requiring equivalence of all their order observations under .β¦ Extensionality and validity are the respect conditions in (9). (9)
A specialized relational construction fixes a chosen type and a three-copy observation system.β¦ Require and data mode for , where is the probe seed. Its copy source is , its first path is , and its inner and outer double channels form the middle wrapper and tagged observation type in (10). Write for the inner and outer channels, for the outer channelβs first and second paths, and . The specialized carrier conditions are the equalities in that display. (10) The observation paths use profiles with feasible triples and and nonempty . The probeβs initial path runs from to , its raw path from to , its return path from to , and its function path from to . Its positive lifting path runs from to , and its tail ends at . The channel paths and run from to and from to ; the inner double channel runs from through to , and the outer double channel from through to .
The tagged copy of a logical probe element , for , is the tagged observation obtained by reencoding from to and using signed inner and outer embeddings with positive bits exactly at and , respectively.β¦ The inner marker is recovered through the outer channel; the outer marker is its bit observation. The specialized observation of a predicate at a tagged observation is the formula obtained by recovering the copy payload against the uniform probe .β¦ Tagged observational equivalence is the relation between tagged observations requiring equivalence of both markers and, uniformly for , equivalence of and .β¦
For a channel predicate at the specialized carrier and a tagged observation , write .β¦ The seven structural properties of are observation invariance , class representations , edge representations , and relational closure , defined in (11). The left-copy predicate is . (11) The structural parameter is the probe double channelβs structural realization of the branches , using the predicate path and the constant truth marker on the probe raw type of .β¦ Specialized incidence and lifting are and .
The induction formula is the guarded universal formula in (12). The response predicate is the channel predicate given by incidence with the zeroth copy; the shifted predicate is the channel predicate given by evaluation at the specialized lift of the zeroth tagged copy of a logical probe element . (12) The well-foundedness object is the logical data realization of the response induction body in (13). (13)β¦
The Claim
Theorem 1. Fix an ambient logical calculus and its quantifier routes, and specialized relational data satisfying the observation formation and carrier conditions above. Then (14)β¦ Let be a data-mode term with , and assume . Then (15)β¦ If is also inhabited in proof mode, then (16)β¦
What Is Checked
Statements (14), (15), and (16) are over labelled typing and mode discipline in , a logical calculus with its fixed feasible witnesses and quantifier routes, and specialized relational data whose probe and channel paths follow the specified feasible product profiles, whose chosen type has seed sorting and data mode, and whose carriers satisfy (10).