The Setting
The logical calculus for the forbidden configuration uses mode labels on dependent terms and fixed wrappers along paths of sort profiles. Let be a pure type specification, with arbitrary axiom and product-rule relations. Ordinary terms are variables and sorts, applications , annotated abstractions , and dependent products .✦ Named binders denote de Bruijn terms, with index zero referring to the nearest binder; contexts are written in newest-first order.
Full reduction contracts to , where denotes substitution of for the bound variable in , and is closed under all term constructors, including annotations and binder bodies.✦ Convertibility is its least equivalence closure.✦ A normal term is an ordinary term with no reduct; a weakly normalizing term is an ordinary term that reaches a normal term in finitely many steps, possibly none. Write for the chosen full normal form when one exists, with a fixed arbitrary value otherwise.✦
The ordinary typing judgement has the axiom rule for , and the variable and weakening rules extend by when for some sort , shifting free indices. Product formation requires and , with , and gives . Abstraction requires a body of type in and a sorted product in . If and , application gives . Conversion changes an expected type to a convertible type that has a sort in . A valid context is a context obtained from the empty context by successive extensions by a type having a sort in the preceding context.✦
The normal form sort profile of an ordinary term in a context , the axiom profile of a sort , and the product output profile of sets of sorts are the sets in (1). (1) A feasible profile is a nonempty set of sorts equal to for some valid context and normal term .✦ Write when all three profiles are feasible and .✦
The primary signed graph has positive inclusion edges between feasible profiles with . Each feasible triple gives a negative edge and a positive edge . Positive reachability is the relation between feasible profiles given by finite paths of positive edges, including empty paths.✦ For a family of profiles, the observation layers , direct observation layers , and logical terminal profiles are the sets of profiles specified in (2). (2)
The Definition
Definition 1. The modes are the elements of the set in (3). (3)✦ The labels have argument and result modes , , and , respectively; for a label , write its argument and result modes as and . Labelled terms form the least collection given by (4), where , , and is a label. (4)✦ The erasure of a labelled term is the ordinary term obtained by removing all labels from . A data-only term is a labelled term in which every application, abstraction, and product has label .✦
For a labelled term , a renaming , and a simultaneous substitution , the terms and are obtained by replacing a variable by and , respectively, preserving sorts and labels and acting recursively on subterms. Under a binder they use the lifts in (5); denotes successor renaming. The single substitution and bound variable instantiation are also specified there. These operations on ordinary terms have the same clauses with labels omitted. (5) Labelled reduction is the full congruence closure of (6)✦; labelled convertibility is its least equivalence closure.✦ (6) Labelled typing uses the ordinary typing rules, with labels retained; in abstraction and application the label agrees with the product type’s label, and conversion uses labelled convertibility.✦
A mode assignment assigns modes to free variables. For a mode assignment and a mode , the extension is the mode assignment that sends zero to and to .✦ The mode judgement gives variable mode and sorts mode . An application labelled requires its function in mode and argument in mode , and has mode . An abstraction requires its annotation in data mode and its body in result mode under the argument-mode extension, and has result mode. A product requires its domain and body in data mode, with the body under the argument-mode extension, and itself has data mode.
A formula is inhabited by a genuine proof when (7) holds. (7)✦ A typed open proof transformer from to in a labelled context with mode assignment is a term in the fresh proof variable of type satisfying (8). (8) Formula equivalence is the relation between labelled formulas in a labelled context with mode assignment that requires uniform typed open proof transformers in both directions, as in (9). (9)✦
Sorting a labelled term at a profile means for every .✦ A fixed feasible witness family in a labelled context with mode assignment is a family of pairs of labelled terms, one pair for every profile, satisfying (10) for each feasible profile . (10)✦
A proof wrapper is a finite expression built by identity and signed extensions; a positive data wrapper is a finite expression built by identity and paired extensions. Their grammars are (11), with . (11) A data path tail is a tuple with , a positive data wrapper , and proof wrappers .✦ Retained data wrappers form the least family , indexed by parity , with the constructors in (12); here and is a data path tail. (12)✦
For a witness family , formation of a proof wrapper from to with parity is written $Q:I\xRightarrow[W,C]{\epsilon}J$ and is the least relation closed under (13). Parity counts negative extensions modulo two. $$\begin{gathered} \frac{}{\mathbf1:I\xRightarrow[W,C]{0}I},\qquad \frac{Q:I\xRightarrow[W,C]{\epsilon}J\quad K\subseteq J} {Q:I\xRightarrow[W,C]{\epsilon}K},\\[3pt] \frac{Q:I\xRightarrow[W,C]{\epsilon}J\quad\mathcal F(H,J,K)} {\operatorname{pos}(Q,T_H):I\xRightarrow[W,C]{\epsilon}K},\\[3pt] \frac{Q:I\xRightarrow[W,C]{\epsilon}J\quad\mathcal F(J,H,K)\quad J,K\in C} {\operatorname{neg}(Q,T_H):I\xRightarrow[W,C]{1-\epsilon}K}. \end{gathered}$$(13)✦ A quantifier route through a profile at base profile is a tuple of profiles and proof wrappers satisfying (14). Write for the collection of these routes. $$\mathcal F(I,J,K),\qquad Q_{\mathrm{in}}:b\xRightarrow[W,C]{0}J,\qquad Q_{\mathrm{out}}:K\xRightarrow[W,C]{0}b.$$(14)✦
An ambient logical setup for consists of a witness family , terminal converters given by typed open proof transformers from to for all , profiles , proof wrappers , and a quantifier route for each direct observation layer , subject to (15). $$\begin{gathered} T_J\rightsquigarrow_{\Gamma,\gamma}T_{J'} \quad(J,J'\in\mathcal T_C),\\ b,d,k\in C,\qquad\mathcal F(d,b,k),\\ Q_{\mathrm{in}}:b\xRightarrow[W,C]{0}d,\qquad Q_{\mathrm{out}}:k\xRightarrow[W,C]{0}b,\\ r_I\in\mathcal Q_{W,C}(b,I)\quad(I\in\mathcal D_C). \end{gathered}$$(15)✦
What Is Checked
The ambient logical setup of (15) is stated over an arbitrary pure type specification and a labelled context with mode assignment , relative to a family of sort profiles.