The Setting
The guarded diagonal construction uses data predicates whose observations are formulas of an internal logical calculus. Its induction condition concerns a predicate at logical probe elements satisfying an order validity condition.
Fix a pure type specification , with arbitrary axiom and product-rule relations. Terms are variables, sorts, applications, annotated abstractions , and dependent products .β¦ The labelled syntax distinguishes argument and result modes by the labels , and , denoting data to data, data to proof and proof to proof. Label erasure deletes these labels.β¦ Contexts are newest-first; a valid context is obtained from the empty context by adjoining a type for which for some sort .β¦
Typing is written . The product rule uses any with and ; abstraction and application retain the productβs label. Conversion changes the expected type to a convertible type that has a sort. Full reduction contracts an application of an annotated abstraction with the same label and acts in every annotation and binder body; convertibility is its equivalence closure. Capture-avoiding simultaneous substitution includes single-variable instantiation. Renaming under a binder fixes its new variable and shifts renamed older indices; index zero denotes the newest variable.β¦ Named binders here denote this syntax with capture avoided. The nondependent labelled arrow is the product in which does not occur in .
A mode assignment gives each variable data or proof mode. The mode judgement assigns variables their given modes and sorts data mode. An application requires its function in the labelβs result mode and its argument in the labelβs argument mode. An abstraction requires a data annotation and a body in the result mode under extension by the argument mode. A dependent product has data mode when its domain and its codomain have data mode under the corresponding binder extension. A term is data-only if every application, abstraction and product in has label .β¦
For formulas and in context with mode assignment , proof mode inhabitation, a typed open proof transformer, and typed logical equivalence are the relations in (1); the fresh temporary variable has proof mode. (1)
Profiles and Logical Operations
A term is weakly normalizing if it reaches a full normal form by finitely many reductions; write for a chosen such normal form. A normal form admits no further reduction.β¦ The sort profile of a weakly normalizing term , the axiom successor profile of a sort , and the product output profile of profiles are the sets in (2). (2) A feasible profile is a nonempty set of sorts realized by a normal type in a valid context.β¦ A feasible product profile triple consists of feasible profiles satisfying .β¦ In the primary signed graph, proper inclusion between feasible profiles gives a positive edge towards the smaller profile; a feasible triple gives a negative domain edge and a positive codomain edge .β¦ Positive reachability permits finitely many positive edges, including none.β¦
Fix a collection of profiles. An observation layer for a collection of profiles is a profile positively reachable in the primary 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 admitting a feasible triple with .β¦
A fixed feasible witness family is a family of types and values indexed by profiles . For every feasible , the type is data-only and its erasure is normal; for every , and . Both and have data mode under . A type is sorted at a profile in when for every sort .
A proof wrapper is a finite sequence of positive and negative extensions of the identity.β¦ Applied to a formula , a positive extension with annotation gives , and a negative extension with annotation gives , where is the preceding wrapper.β¦ A formed proof wrapper is a proof wrapper that follows feasible product triples, with the annotations chosen by the witness family , and may restrict its target profile by inclusion. Positive steps follow the codomain and negative steps the domain; the domain and output profiles of every negative step lie in . Path parity counts negative steps modulo two.
An ambient logical calculus has a fixed feasible witness family and open proof transformers between its chosen types at any two logical terminal profiles. Its domain, base and product profiles lie in and form a feasible triple . It has even input and output proof paths from to and from to . Its falsity formula is .β¦ A quantifier route at a domain profile chooses a feasible triple and even proof paths from to and from to ; provides such a route at every direct observation layer.β¦
The logical implication and universal quantifier associated with these paths are the formulas in (3). Here are the logical paths and the paths of a quantifier route ; path application under a named binder includes its capture-avoiding renaming. (3) A guarded universal formula is a universally quantified formula with body . Existential quantification is , and the logical conditional with guard and branches is . Logical negation of a formula is its logical implication to falsity. Logical conjunction is the negation of the implication from to the negation of . Encoded logical equivalence is the logical conjunction of the implications from to and from to .
Observation Channels and Specialized Probes
A data tail at a profile is a choice of a terminal sort with and , a positive path from to , and even proof paths from to and back. The decoding proof path contains a negative step. The tail carrier is the positive wrapper of β¦; encoding applies the incoming proof path and positive injectionβ¦, while decoding applies positive projection and the outgoing proof path.β¦
A retained data path is a finite path with positive steps retaining a domain and a dummy value, and negative steps retaining a data tail.β¦ Its wrapped type is at the identity; a positive step gives , and a negative step gives , where is the tail carrier.β¦ Formation follows feasible product triples and target inclusions, using the witness family at positive steps and a formed tail at the codomain profile of each negative step.β¦ A positive data path is a retained data path containing only positive steps.β¦ Its injection is iterated constant annotated abstractionβ¦, and its projection applies the retained dummy values.β¦
The builder along a data path returns its input at the identity and forms constant data abstractions at positive steps. At a negative step it abstracts a wrapped input and tail-encodes its observation. For an input type , a wrapped value , and an observation callback , the observation instantiates with at the identity. At a positive step it applies to the retained dummy value and continues; at a negative step it applies to the recursively built argument and tail-decodes the result. Reencoding between odd paths builds along the observation callback of along .β¦ The open composition of callbacks and replaces the distinguished input of by , keeping their common ambient variables fixed.
An observation channel consists of odd logical, raw and predicate paths .β¦ Its logical, raw and predicate types, together with channel evaluation, are defined in (4). (4) An encoded predicate over a type in an observation channel is the term of built along after composing its body with reencoding from to .β¦ The channel roundtrip reencodes from to and back.β¦ Roundtrip invariance of a predicate requires logically equivalent evaluations before and after this roundtrip at every logical element.β¦ An admissible predicate in an observation channel is a predicate that is roundtrip invariant and satisfies its supplied guard.β¦ Observational equivalence of elements quantifies over predicates satisfying that actual guard and compares their evaluations.β¦ The logical channel encoding of a raw element at is its reencoding from the raw path to the logical path .β¦
A uniform probe is a choice of a seed sort , an initial data path of fixed parity, odd raw and return paths , an even function path , a positive lifting path , and a data tail with carrier .β¦ The double channel has carrier ; write for its fourth iterate. The probe raw, parameter, single-bundle and function types, and the common probe type , are defined in (5). (5) Probe specialization applies a probe to the positive injection of its type argumentβ¦; probe observation then observes its specialization along and decodes the resulting function application through the tail.β¦ Uniform probe abstraction binds the lifted type parameter and builds the tail-encoded data function along .β¦
A shared relational coding is a choice of a uniform probe and odd logical and predicate paths, with the same raw path as the probe.β¦ Its relational base type at is .β¦ The probe formation requires feasible triples and and a nonempty . Its initial, raw, return and function paths run from to , from to , from to , and from to , respectively; the positive lifting path runs from to , and the tail ends at . For profiles and , channel formation requires paths , and .β¦
A specialized relational code is a choice of a type and a three-copy observation system with relational component .β¦ Its first copy uses , its middle copy applies an inner double channel to the first copy, and its observation carrier applies an outer double channel to the middle copy. Observation formation requires the inner paths and the outer paths . Specialized formation further requires and data mode for . Writing , the observation carrier must equal ; the second outer path is the relational logical path, and its first outer path applied to the middle copy of equals . The observation systemβs tagged copy syntax has source path , first path , and the observation systemβs inner and outer double channels.β¦ The specialized base type is the relational base type of the chosen type .β¦
Relational Lifting
Fix quantifier routes for logical and predicate channel types. For a type , put . The double channel has tagged observation queries , obtained by observing the parameter against the tagged payload encoding of , using the relational predicate path at .β¦ At raw type , the predicate code type is ; its bottom code is the first-path builder with constant falsity, and its dummy observation is the second-path builder with constant truth. Tags use the nonzero query indices ; index zero selects the payload.β¦ A query index has its four binary digits in increasing order of significance.β¦ The payload encoder builds along at the fourfold double carrier. Its body is the disjunction of the payload tag conjoined with fourfold recovery of the predicate-path observation callback and the nonzero query tag.β¦ Tagged embeddings iterate signed embeddings along these four bits; tag predicates test each bit and recover the remaining tag recursively. For an odd data path , the payload decoder at builds along from a callback that observes the encoded payload along the first double-channel path at the fourfold carrier of , against the input embedded with payload query zero.
Roundtrip invariance, structural admissibility and observational equivalence at are the formulas in (6). Here is the channel roundtrip on . (6) The class predicate is the encoded predicate with body ; the class union predicate has body . Class queries apply tags to the class predicate.β¦ The two tagged edge formulas and the pair predicate are defined in (7), where denotes the encoded predicate with body over . (7)
The relational point of is its raw channel encoding placed in the double channelβs point construction with the constant truth marker.β¦ That marker is the raw-path builder with constant body .β¦ The point predicate conjoins its marker test at tag with the decoded payload observation.β¦ A relational argument bundle combines the dummy observation, a parameter , and this point in the double channelβ¦; its branch predicate is the logical conditional on the first observation, with the other two as branches.β¦ The diamond observation is the probe observation of at against this bundle.β¦ The section predicate of the diamond observation is the encoded predicate over with body .β¦
The relational element lift is the term built along the logical path at with body . This body is the section pair query. The predicate pullback of along this lift is .β¦ Its recovery at a single-bundle argument is the double channelβs recovery access observation, tested with the data parameter callback assigning this pullback to .β¦
The dummy parameter test observes its argument against the constant falsity predicate code.β¦ Recovery access uses this test as its guard: the outer access conditional has truth as its first branch and the composed observation callback as its second; the inner probe conditional has falsity as its first branch and the tag query as its second. The uniform predicate probe is the uniform probe abstraction whose body is this pullback recovery of , at the positive projection of its bound type parameter.β¦ The inner observation probe is built along the first double-channel path over the parameter type, with the inner probe conditional as its body. The access probe over a type is built along the first double-channel path at , with the outer access conditional as its body. The bundle access observation of over observes along the second double-channel path, at the first-path wrapper of , against the access probe.
Validity and Induction
For the common probe type , put and using (4). Pointwise predicate comparison is the formula in (8). (8)β¦
The probe order formula is .β¦ The pointwise validity condition, validity at a predicate, and order validity are defined in (9). (9) The guarded induction condition and its universally quantified induction formula are those in (10). (10)
The Claim
Theorem 1 (Lemma 54). Fix an ambient logical calculus , the quantifier routes , and a formed specialized relational code as above. Let be data-mode terms with and . Suppose holds. Then the induction formulas satisfy (11). (11)β¦
What Is Checked
Lemma 54 is stated over labelled typing and its data and proof mode discipline, an ambient logical calculus with fixed feasible witnesses and quantifier routes, and a specialized relational code satisfying its probe, observation and carrier shape conditions.