The Setting
Boolean valuations then concern the propositional connections, while inhabitation concerns labelled terms in the proof mode of a pure type system.
A pure type specification consists of sorts and arbitrary axiom and product-rule relations.β¦ Its terms are variables, sorts, applications, annotated abstractions and dependent products .β¦ Labelled terms have the same constructors, with a label on each application, abstraction and product.β¦ The labels , and specify respectively data to data, data to proof and proof to proof.β¦ Write and for the argument and result modes of a label . The erasure of a labelled term is the unlabelled term obtained by deleting all labels from . A data-only term is a labelled term whose constructor labels are all .β¦
Contexts are finite lists in newest-first order. A valid context is the empty context or an extension of a valid context with for some sort . In either term language, typing is generated by the axiom, variable and weakening rules, dependent product formation along , annotated abstraction, application and conversion. Product formation uses and with ; abstraction also requires the resulting product to have a sort. Application substitutes the argument into the codomain. Conversion replaces an expected type by a convertible type that has a sort. In labelled application the functionβs product label matches the application label.
Named binders are used in the displayed terms. Variable indices follow the de Bruijn convention, with index zero the newest variable. Renaming replaces free indices according to , lifting beneath binders to fix the bound variable. Simultaneous substitution replaces free indices by terms and lifts their images beneath binders to avoid capture. The single-variable substitution determined by sends zero to and to variable ; its action on a body is bound-variable instantiation . These operations preserve labels in the labelled language. Write for successor renaming.
Full reduction contracts to and permits reduction in every component, including annotations and binder bodies.β¦ Labelled head contraction requires matching application and abstraction labels. In either language, convertibility is the equivalence relation generated by reduction. A normal term has no reduction step.β¦ A weakly normalizing term reaches a normal term in finitely many steps; denotes its chosen normal form.
A mode assignment assigns each variable data mode or proof mode . Its extension assigns to zero and to .β¦ The mode discipline gives a variable its assigned mode and a sort data mode. An application with label requires function mode and argument mode , and has mode . An abstraction requires a data-mode annotation and a body of mode under , and has mode . A product requires a data-mode domain and a data-mode codomain under , and has data mode.
Proof-mode inhabitation is the existence of a labelled inhabitant satisfying the proof-mode discipline, as in (1). (1)β¦ An open proof transformer is a proof-mode term with one temporary proof input of type , with the condition in (2). (2)β¦
Profiles and Observation Layers
The normal form sort profile of a weakly normalizing unlabelled term is the set of all sorts typing in , as in (3).β¦ A feasible profile is a nonempty sort set equal to for some normal term in a valid context .β¦ (3)β¦ For a sort and sort sets and , the axiom profile and the product output profile are the sort sets in (4). A feasible product profile triple consists of feasible profiles with .β¦ (4)
The primary signed graph is the graph on sort sets with positive edges for strict inclusions of feasible profiles, and, for each feasible triple , a negative edge and a positive edge .β¦ Positive reachability allows a finite, possibly empty path using only positive edges.β¦ For a collection of sort sets, an observation layer is a profile positively reachable from a nonempty with .β¦ A direct observation layer for is an observation layer for which a feasible triple has .β¦ A logical terminal profile for is a profile for which a feasible triple has ; write for their collection.β¦
Witnesses and Wrapper Routes
A fixed feasible witness family assigns a labelled type and value to each sort set. At every feasible profile , the type is data-only, its erasure is normal, and for every . The value satisfies , and both and have data mode under . More generally, a labelled type is sorted at when for every ; this permits additional sorting judgments.β¦
A proof wrapper is a finite expression built from an identity wrapper by positive or negative extensions, each adjoining a fixed labelled term.β¦ A wrapper path relative to and assigns such an expression a source profile, a target profile and a parity, given by the number of negative extensions modulo two. The identity path starts and ends at its source with even parity. Inclusion replaces a target by any subset without changing the expression or parity. A positive extension at target uses a feasible triple , adjoins and preserves parity. A negative extension uses a feasible triple with , adjoins and reverses parity. The wrapper expression and its annotations remain fixed under input substitution and enlargement of sorting profiles.
A quantifier wrapper route for a base profile and domain profile consists of a feasible triple and even wrapper paths from to and from to .β¦ An ambient logical calculus consists of a fixed witness family , open proof transformers for every pair of terminal profiles, and a feasible triple with . It has even wrapper paths from to and from to , and a quantifier wrapper route with base for every direct observation layer.
Interpretable Formulas
A mode-preserving context embedding is a variable renaming into a valid labelled context that preserves the type and mode of each variable.β¦ Context lookup assigns the newest variable the successor shift of the head declaration, and shifts the retrieved type once more for each step to an older declaration.β¦ If lookup assigns to index in , the embedding requires and . Witness family renaming gives in the target context.β¦
The witness continuation condition for a labelled term is the requirement that, in every embedded context, a transformer from to a terminal witness type have a proof-mode inhabited target, as in (5).β¦ (5)β¦ The stable witness extraction condition for a labelled term is the requirement in (6) of extraction from its witness continuation after every mode-preserving context embedding.β¦ (6)β¦ An interpretable formula for is a labelled term sorted at the base profile , having data mode and stable witness extraction.β¦ Write for this condition, as in (7). (7)β¦
Propositional Syntax and Interpretation
A propositional formula over atoms is a finite expression generated by atoms, falsity and implication .β¦ Negation is .β¦ A Boolean valuation is a map from atoms to truth values, extended to formulas by (8). For a finite list , iterated implication is , associated to the right, with .β¦ (8)β¦
Classical derivability from a set of propositional assumptions is the least relation closed under assumption, implication introduction and elimination, and double negation elimination.β¦ Introduction derives from a derivation of under ; double negation elimination derives from .
Write and for the ambient calculusβs falsity and implication types. The propositional interpretation associated to an atom assignment , where denotes the labelled terms over , is the labelled term defined by (9). (9)β¦
The Claim
Theorem 1 (Tautologies are derivable). Suppose equality of atoms is decidable. Let be a propositional formula true under every Boolean valuation. For every set of propositional assumptions, (10) holds. (10)β¦
Theorem 2 (Propositional consequence). Let be an ambient logical calculus, and let assign an interpretable formula for to every atom. Let be a finite list of propositional formulas, and let be a propositional formula. Suppose is true under every Boolean valuation and each has a proof-mode inhabitant in . There is a labelled term satisfying (11). (11)β¦
What Is Checked
The statements range over finite propositional formulas with Boolean valuations and over labelled typing and mode judgments in an ambient logical calculus with fixed feasible witnesses and stable witness extraction for its atom interpretations.
Renaming a fixed feasible witness family along a mode-preserving context embedding preserves its data-only types, normality of their erasures, sorting, typing and data modes.