The proof theory and semantics of second-order (intuitionistic) tense logic Justus Becker and Anupam Das and Sonia Marin and Paaras Padhiar Abstract . We develop a second-order extension of intuitionistic modal logic, allowing quantification over propositions, both syntactically and semantically. A key feature of second-order logic is its capacity to define positive connectives from the negative fragment. Duly we are able to recover the diamond (and its associated theory) using only boxes, as long as we include both forward and backward modalities (‘tense’ modalities). We propose axiomatic, proof theoretic and model theoretic definitions of ‘second-order intuitionistic tense logic’, and ultimately prove that they all coincide. In particular we establish completeness of a labelled sequent calculus via a proof search argument, yielding at the same time a cut-admissibility result. Our methodology also applies to the classical version of second-order tense logic, which we develop in tandem with the intuitionistic case. 1. Introduction 1.1. Background and motivation Second-order logic extends first-order logic by allowing quantification over predicates. It has become a standard tool in mathematical and computational logic, including in type theory and programming languages (e.g. [ 28 , 59 , 47 , 52 ] ), computability and complexity (e.g. [ 67 , 21 , 13 , 16 ] ), and, more recently, knowledge representation in artificial intelligence (e.g. [ 4 , 5 , 3 , 8 ] ). The metalogical and proof theoretic foundations of second-order logic have posed significant challenges to logicians over the last century. Completeness for standard (or full ) semantics, where properties vary over the full powerset, fails, necessitating the more general Henkin semantics [ 35 ] . The corresponding theories typically admit the comprehension axiom, requiring impredicative techniques for metalogical analysis. Indeed cut-admissibility of second-order logic, known as Takeuti’s conjecture [ 58 ] , remained an open problem since the ’30s, before being resolved in the late ’60s by seminal works of Tait [ 71 ] , Prawitz [ 54 , 55 ] , Takahashi [ 72 ] and Girard [ 28 ] . Over intuitionistic logic, second-order quantification notably allows the encoding of positive connectives by the negative fragment. For example A\lor B is logically equivalent to \forall X((A\to X)\to(B\to X)\to X) . This is in stark contrast to the first-order setting, where connectives are infamously intuitionistically independent. In this work we apply the second-order methodology to modal logic , allowing us to recover a theory of positive modalities ( \Diamond s) from the negative ( \Box s) over an intuitionistic base. Unlike propositional and predicate logic, there is no consensus on what the intuitionistic fragment of modal logic is. While it is natural to admit distribution, \Box(A\to B)\to\Box A\to\Box B and necessitation, A/\Box A , these principles say nothing about \Diamond which, recall, cannot be defined in terms of \Box . For instance one might also want to admit \Diamond -distribution, \Box(A\to B)\to\Diamond A\to\Diamond B . This has led to several distinct proposals, e.g. [ 6 , 80 , 19 , 34 , 64 , 66 ] . Notably the choice of \Diamond -axioms also affects even the \Box -only (i.e. \Diamond -free) theorems of the logic [ 33 , 19 ] . (See [ 18 ] for a related survey.) Instead we show that we can encode the \Diamond over second-order intuitionistic logic, similarly to \lor earlier, as long as we admit also a backwards box \Boxblack , as in tense logic [ 57 ] : (1) \Diamond A\ \iff\ \forall X(\Box(A\to\Boxblack X)\to X) A symmetric equivalence holds for the backwards diamond \Diamondblack . This allows us to recover a theory of \Diamond (and \Diamondblack ), instead of choosing an arbitrary axiomatisation. The resulting second-order logic \mathsf{IK}\mathsf{t}2 conservatively extends Fischer Servi and Simpson’s \mathsf{IK} [ 64 , 66 ] and, furthermore, Ewald’s \mathsf{IK}\mathsf{t} [ 22 ] . \mathsf{K}\mathsf{t}2\vdash A \forall\mathfrak{R}\,\vDash_{\mathfrak{R}}A \ell\mathsf{K}\mathsf{t}2\setminus\mathsf{cut}\vdash A \ell\mathsf{K}\mathsf{t}2\vdash A Theorem 3.15 Theorem 5.1 Theorem 7.1 ( 2 ) 3.14 4.2 ( 1 ) (a) Classical results \mathsf{IK}\mathsf{t}2\vdash A \forall\mathfrak{B}\,\vDash_{\mathfrak{B}}A \forall\mathfrak{P}\,\vDash_{\mathfrak{P}}A \mathsf{m}\ell\mathsf{IK}\mathsf{t}2\setminus\mathsf{cut}\vdash A \ell\mathsf{IK}\mathsf{t}2\setminus\mathsf{cut}\vdash A \ell\mathsf{IK}\mathsf{t}2\vdash A Theorem 3.5 Proposition 3.11 Theorem 6.1 Proposition 4.5 Theorem 7.1 ( 1 ) 3.3 4.2 ( 2 ) (b) Intuitionistic results Figure 1 . The ‘grand tours’ of this work. 1.2. Contributions In this work we develop axiomatic, semantic and proof theoretic foundations for second-order tense logic, over both classical and intuitionistic bases. Our main results are: (i) soundness and completeness of our systems for corresponding (bi)relational semantics; and, (ii) cut-admissibility for associated labelled sequent calculi. These results are recovered from the ‘grand tours’ visualised in Fig. 1 , where they are indicated in blue, dashed. Our main completeness arguments, Theorems 5.1 and 6.1 , are proved via proof search , notably adapting Schütte’s notion of semivaluation [ 61 ] to the intuitionistic setting in order to overcome the hurdle of impredicativity (cf. [ 71 , 55 , 56 ] ). The main technicalities behind the converse direction lie in the translation from labelled proofs to axiomatic proofs, Theorems 7.1 and 7.1 , driven by a tree-like representation of labelled sequents in tense logic (see, e.g., [ 15 ] ). 1.3. Related works Second-order extensions of (classical) modal logic have been proposed since the ’70s, cf. [ 12 , 23 , 37 ] . Many aspects have since been investigated, including expressivity [ 75 , 36 ] , applications to interpolation theory [ 24 , 7 ] , and to the meta-theory of provability logics [ 2 ] . However most of these works focus on full semantics, and so are not suitable for proof theoretic investigations. More recently, second-order modal logics have been proposed as a specification language for knowledge representation in artificial intelligence [ 4 , 5 , 3 ] . This is more relevant to our approach as they interpret the second-order language over Henkin structures rather than full structures, although they only treat quantifier-free (or predicative ) comprehension. Notably in [ 3 ] the authors conclude that, for second-order modal logic “ to be adopted as a specification language in artificial intelligence and knowledge representation, appropriate theoretical results and formal tools need to be developed ”. Our work may be viewed as a contribution in this direction, developing the metalogical and proof theoretic foundations therein. 1.4. Structure of the paper Our main results are visualised in Fig. 1 . In Section 2 we introduce the axiomatisations \mathsf{K}\mathsf{t}2 and \mathsf{IK}\mathsf{t}2 of classical and intuitionistic second-order tense logic, respectively. Both include a full comprehension axiom, and duly prove Eq. 1 . In Section 3 we define relational semantics for \mathsf{K}\mathsf{t}2 , and two extensions by a partial order for \mathsf{IK}\mathsf{t}2 , following Simpson’s methodology [ 66 ] . The main results of this section are soundness of the axiomatisations for their semantics, Theorems 3.15 , 3.5 and 3.11 . In Section 4 we present labelled sequent calculi \ell\mathsf{K}\mathsf{t}2 and \ell\mathsf{IK}\mathsf{t}2 , again inspired by Simpson [ 66 ] , in particular including a left- \forall rule implementing full comprehension. We also present an intermediate multi-succedent version \mathsf{m}\ell\mathsf{IK}\mathsf{t}2 , à la Maehara [ 45 ] , more suitable for completeness-via-proof-search arguments (cf., e.g., [ 56 ] and [ 73 , Section 15] ), that is ultimately conservative over \ell\mathsf{IK}\mathsf{t}2 , Proposition 4.5 . Our main proof search arguments are presented in Section 5 (classical) and Section 6 (intuitionistic), yielding cut-free completeness of \ell\mathsf{K}\mathsf{t}2 , Theorem 5.1 , and \mathsf{m}\ell\mathsf{IK}\mathsf{t}2 , Theorem 6.1 . The intuitionistic case, in particular, exhibits novel intricacies, combining ideas from analogous constructions for simple type theory [ 55 ] and first-order intuitionistic logic [ 73 , Section 15] . In Section 7 we present a translation from labelled systems \ell\mathsf{K}\mathsf{t}2 and \ell\mathsf{IK}\mathsf{t}2 to axiomatic systems \mathsf{K}\mathsf{t}2 and \mathsf{IK}\mathsf{t}2 , Theorems 7.1 and 7.1 , respectively, completing the cycle of implications, viz. Figs. 1(a) and 1(b) . Finally we conclude the paper with some additional perspectives in Section 8 , in particular relating \mathsf{K}\mathsf{t}2 and \mathsf{IK}\mathsf{t}2 by a negative translation, and make some concluding remarks in Section 9 . 2. A second-order extension of tense logic In this section we present the syntax of second-order tense logic and provide axiomatisations of its intuitionistic and classical theory. One of the main points here is to show how diamonds may actually be defined in terms of the other connectives, even intuitionistically, allowing us to recover its theory, instead of providing arbitrary axioms therein. We point the reader to, e.g., [ 70 , Chapter 12] for some useful background on second-order (intuitionistic) propositional logic. 2.1. Syntax of second-order tense logic Let us fix a set \mathsf{Pr} of propositional symbols , written P,Q,R etc., and a (disjoint) set \mathsf{Var} of (formula/second-order) variables , written X,Y,Z etc. We shall work with second-order tense formulas , given by: A,B,C,\dots\quad::=\quad P\in\mathsf{Pr}\ \mid\ X\in\mathsf{Var}\ \mid\ A\to B\ \mid\ \Box A\ \mid\ \Boxblack A\ \mid\ \forall XA Write \mathsf{Fm} for the set of all formulas. We shall frequently omit external brackets of formulas and internal brackets of long implications, understanding them as rightmost bracketed. I.e. A\to B\to C=(A\to(B\to C)) and so on. The set of free variables of a formula A , written \mathsf{FV}(A) , is defined as expected: \begin{array}[]{r@{\ := \ }l}\mathsf{FV}(P)&\varnothing\\ \mathsf{FV}(X)&\{X\}\\ \mathsf{FV}(A\to B)&\mathsf{FV}(A)\cup\mathsf{FV}(B)\end{array}\qquad\begin{array}[]{r@{\ := \ }l}\mathsf{FV}(\Box A)&\mathsf{FV}(A)\\ \mathsf{FV}(\Boxblack A)&\mathsf{FV}(A)\\ \mathsf{FV}(\forall XA)&\mathsf{FV}(A)\setminus\{X\}\end{array} Note that propositional symbols are not variables. If \mathsf{FV}(A)=\varnothing then A is closed (or a sentence ). Otherwise it is open . Remark 2.1 (Propositional symbols vs variables) . We could have worked without propositional symbols at all, using only variables. However we take the current formulation so that we may safely deal with only closed formulas in the systems and semantics we present. This choice allows us to avoid the need for explicit environments when interpreting syntax, lightening the notation therein. It is well known that other propositional connectives and quantifiers can be defined from our minimal syntax via impredicative encodings. In particular, over pure second-order intuitionistic logic, we have the following equivalences: 1 1 1 In all cases, the variable X should be chosen not occurring free in A and B . Since we shall typically only deal with closed formulas, we shall gloss over this technicality throughout. (2) \begin{array}[]{r@{\ \iff\ }l}\bot&\forall XX\\ A\lor B&\forall X((A\to X)\to(B\to X)\to X)\\ A\land B&\forall X((A\to B\to X)\to X)\\ \exists YA&\forall X(\forall Y(A\to X)\to X)\end{array} Note that these equivalences hold even intuitionistically , in stark contrast to (first-order) intuitionistic logic: there all the propositional connectives are independent. See, e.g., [ 70 , Section 12.4] or [ 27 , Section 11.3] for a more detailed account. In the same vein, we will be able to define diamond modalities in the second-order setting by appropriate equivalences: (3) \begin{array}[]{r@{\ \iff\ }l}\Diamond A&\forall X(\Box(A\to\Boxblack X)\to X)\\ \Diamondblack A&\forall X(\Boxblack(A\to\Box X)\to X)\end{array} For now this is all rather informal, for the sake of motivation, as we have not yet given any meaning to our formulas. To justify these equivalences, we shall now turn to axiomatisations over our syntax, before presenting semantics in the next section. 2.2. A minimal axiomatisation We shall present only a minimal axiomatisation of formulas in this work. There are two reasons for this: (i) we want to justify the equivalences from Eq. 3 in the most general way, for any extension of our axiomatisation; and, (ii) we will later argue for the robustness of the minimal axiomatisation. Towards Item i , let us temporarily expand the language of formulas by unary operators \Diamond and \Diamondblack . We shall later drop these once we demonstrate that they are unnecessary. We consider a minimal axiomatisation extending second-order intuitionistic propositional logic \mathsf{IPL}2 only by normality of modalities, and adjunction of the pairs (\Box,\Diamondblack) and (\Boxblack,\Diamond) : Definition 2.2 (Axiomatisation with diamonds) . \mathsf{IK}\mathsf{t}2(\Diamond,\Diamondblack) is the logic axiomatised by: (1) All of second-order intuitionistic propositional logic \mathsf{IPL}2 , i.e. the axioms and rules: 2 2 2 Note that the propositional axioms and rules we give are rather those of minimal logic, without \bot . However in the second-order setting, given the definability of the latter, the difference between ‘minimal’ and ‘intuitionistic’ disappears. \begin{array}[]{r@{\ :\quad}l}\mathsf{K}&A\to B\to A\\ \mathsf{S}&(A\to B\to C)\to(A\to B)\to A\to C\\ \mathsf{D}_{\forall}&\forall X(A\to B)\to\forall XA\to\forall XB\\ \mathsf{V}&A\to\forall XA\text{ (when $(X\notin\mathsf{FV}(A))$)}\\ \vskip 3.0pt plus 1.0pt minus 1.0pt\cr\mathsf{C}&\forall XA\to A[C/X]\end{array}\qquad\begin{array}[]{c}{{}{}\vbox{\hbox{\kern 11.9555pt\hbox{\vbox{\hbox{\hbox{\hbox{\hbox{\hbox{\hbox{$A\to B$}}\kern 10.00002pt}\hbox{\hbox{$A$}}}}}\kern 1.43518pt\hbox{\kern 0.0pt\hbox to0.0pt{\hss\hbox{$\smash{\lower 2.5pt\hbox{$\scriptstyle\mathsf{mp}\;$}}$}}\vbox{\vbox to0.4pt{\vfill\hbox to43.64229pt{\leaders{\hrule}{\hfill}\kern 0.0pt}\vfill}}\hbox to0.0pt{\hbox{$\smash{\lower 2.5pt\hbox{$$}}$}\hss}\kern 0.0pt}\kern 1.43518pt\hbox{\kern 17.77774pt\hbox{\hbox{$B$}}\kern 17.77774pt}}}\kern 0.0pt}}}\\ \vskip 3.0pt plus 1.0pt minus 1.0pt\cr\qquad\quad{\vbox{\hbox{\kern 13.0055pt\hbox{\vbox{\hbox{\hbox{\hbox{\hbox{$A[P/X]$}}}}\kern 1.43518pt\hbox{\kern 0.0pt\hbox to0.0pt{\hss\hbox{$\smash{\lower 2.5pt\hbox{$\scriptstyle\mathsf{gen}\;$}}$}}\vbox{\vbox to0.4pt{\vfill\hbox to38.82285pt{\leaders{\hrule}{\hfill}\kern 0.0pt}\vfill}}\hbox to0.0pt{\hbox{$\smash{\lower 2.5pt\hbox{$\;\text{$P$ fresh}$}}$}\hss}\kern 0.0pt}\kern 1.43518pt\hbox{\kern 7.5156pt\hbox{\hbox{$\kern 0.0pt\hbox{$\forall XA$}\kern 0.0pt$}}\kern 7.5156pt}}}\kern 34.83678pt}}}\end{array} where ‘ P fresh’ means that the propositional symbol P does not occur in the conclusion of the rule. (2) Normality of white and black modalities, i.e. the distributivity axioms and necessitation rules: \begin{array}[]{r@{\ : \quad}l}\mathsf{D}_{\Box}&\Box(A\to B)\to\Box A\to\Box B\\ \mathsf{D}_{\Diamond}&\Box(A\to B)\to\Diamond A\to\Diamond B\\ \vskip 3.0pt plus 1.0pt minus 1.0pt\cr\mathsf{D}_{\Boxblack}&\Boxblack(A\to B)\to\Boxblack A\to\Boxblack B\\ \mathsf{D}_{\Diamondblack}&\Boxblack(A\to B)\to\Diamondblack A\to\Diamondblack B\end{array}\qquad\begin{array}[]{c}{\vbox{\hbox{\kern 16.86661pt\hbox{\vbox{\hbox{\kern 3.75pt\hbox{\hbox{\hbox{$A$}}}\kern 3.75pt}\kern 1.43518pt\hbox{\hbox to0.0pt{\hss\hbox{$\smash{\lower 2.5pt\hbox{$\scriptstyle\mathsf{nec}_{\Box}\;$}}$}}\vbox{\vbox to0.4pt{\vfill\hbox to15.00002pt{\leaders{\hrule}{\hfill}\kern 0.0pt}\vfill}}\hbox to0.0pt{\hbox{$\smash{\lower 2.5pt\hbox{$$}}$}\hss}}\kern 1.43518pt\hbox{\hbox{\hbox{$\kern 0.0pt\hbox{$\Box A$}\kern 0.0pt$}}}}}\kern 0.0pt}}}\\ \vskip 3.0pt plus 1.0pt minus 1.0pt\cr{\vbox{\hbox{\kern 16.86661pt\hbox{\vbox{\hbox{\kern 3.75pt\hbox{\hbox{\hbox{$A$}}}\kern 3.75pt}\kern 1.43518pt\hbox{\hbox to0.0pt{\hss\hbox{$\smash{\lower 2.5pt\hbox{$\scriptstyle\mathsf{nec}_{\Boxblack}\;$}}$}}\vbox{\vbox to0.4pt{\vfill\hbox to15.00002pt{\leaders{\hrule}{\hfill}\kern 0.0pt}\vfill}}\hbox to0.0pt{\hbox{$\smash{\lower 2.5pt\hbox{$$}}$}\hss}}\kern 1.43518pt\hbox{\hbox{\hbox{$\kern 0.0pt\hbox{$\Boxblack A$}\kern 0.0pt$}}}}}\kern 0.0pt}}}\end{array} (3) Adjunction of (\Box,\Diamondblack) and (\Boxblack,\Diamond) : \begin{array}[]{r@{\ : \quad}l}\mathsf{A}_{\Diamondblack\Box}&\Diamondblack\Box A\to A\\ \mathsf{A}_{\Box\Diamondblack}&A\to\Box\Diamondblack A\end{array}\qquad\begin{array}[]{r@{\ : \quad}l}\mathsf{A}_{\Diamond\Boxblack}&\Diamond\Boxblack A\to A\\ \mathsf{A}_{\Boxblack\Diamond}&A\to\Boxblack\Diamond A\end{array} Remark 2.3 (Full comprehension) . Note that the choice of C in the comprehension axiom \mathsf{C} is unrestricted: the formula A[C/X] may be more complex than \forall XA . For instance we can even set C=\forall XA . This apparent circularity (known as impredicativity ) complicates, e.g., the semantics of second-order logic, as we shall see in Section 3 . Remark 2.4 (Other logical operators) . As already mentioned, if we formulated \mathsf{IPL}2 with native operators \bot,\lor,\land,\exists , then the equivalences in Eq. 2 are all already provable. For example \forall XX\to\bot is just an instance of \mathsf{C} and \forall X((A\to X)\to(B\to X)\to X)\to A\lor B is derivable by setting C:=A\lor B in \mathsf{C} . We thus henceforth freely use those logical connectives in what follows, recasting those equivalences as definitions . We also write \lnot A:=A\to\bot and A\leftrightarrow B:=(A\to B)\land(B\to A) . Remark 2.5 (Minimality) . Over \mathsf{IPL} the axioms and rules for white (or black) modalities from Item 2 determine what is known as constructive modal logic \mathsf{CK} [ 6 ] . This is the smallest intuitionistic version of modal logic (with \Box and \Diamond ) usually considered, with other common ones obtained by adding further principles of (classical) modal logic, in particular among: (4) \begin{array}[]{l@{\ : \quad}l}\mathsf{N}_{\Diamond\lor}&\Diamond(A_{0}\lor A_{1})\to\Diamond A_{0}\lor\Diamond A_{1}\\ \mathsf{N}_{\Diamond\bot}&\Diamond\bot\to\bot\\ \mathsf{I}_{\Diamond\Box}&(\Diamond A\to\Box B)\to\Box(A\to B)\end{array} For instance \mathsf{WK}:=\mathsf{CK}+\mathsf{N}_{\Diamond\bot} was studied in [ 80 ] , \mathsf{WK}+\mathsf{N}_{\Diamond\lor} was studied in [ 19 ] , \mathsf{IK}^{N}:=\mathsf{CK}+\mathsf{N}_{\Diamond\bot}+\mathsf{I}_{\Diamond\Box} was studied in [ 34 ] , and \mathsf{IK} is the extension of \mathsf{CK} by all the axioms above [ 64 , 66 ] . The smallest intuitionistic modal logic without \Diamond , \mathsf{iK} , defined as the extension of \mathsf{IPL} by \mathsf{D}_{\Box} and \mathsf{nec}_{\Box} , is conservatively extended by \mathsf{CK} . In this sense Item 2 is a minimal commitment in terms of extending the underlying modal logics. On the other hand, the tense axioms in Item 3 state only that (\Box,\Diamondblack) and (\Boxblack,\Diamond) are adjoint pairs, assuming no further relationship. These are standard axioms in presentations of tense logic [ 8 ] , and so again Item 3 is a minimal commitment in terms of relating the white and black modalities. Example 2.6 ( \Box distributes over \forall ) . Let us see a simple example of \mathsf{IK}\mathsf{t}2(\Diamond,\Diamondblack) reasoning in action, not least so we can explain how we present axiomatic proofs: \begin{array}[]{ll}\forall XA\to A[P/X]&\text{by $\mathsf{C}$, setting $X=P$}\\ \Box\forall XA\to\Box A[P/X]&\text{by $\mathsf{nec}_{\Box}$ and $\mathsf{D}_{\Box}$}\\ \Box\forall XA\to\forall X\Box A&\text{by $\mathsf{gen},\mathsf{D}_{\forall},\mathsf{V}$}\end{array} Note that we leave routine \mathsf{IPL} reasoning here mostly implicit, rather focussing on the modal and quantifier axioms necessary at each step. To expand out the final step a little, consider the following gadget, where X\notin\mathsf{FV}(A) : \begin{array}[]{ll}A\to B&\\ \forall X(A\to B)&\text{by $\mathsf{gen}$}\\ \forall XA\to\forall XB&\text{by $\mathsf{D}_{\forall}$}\\ A\to\forall XB&\text{by $\mathsf{V}$}\end{array} We shall continue to write axiomatic proofs in this fashion henceforth, without additional explanation. Note that we can also recover a proof of \Boxblack\forall XA\to\forall X\Boxblack A , by simply exchanging white and black modalities in the proof above. We shall also continue to use this observation throughout, now just alluding to ‘symmetry’. Before showing further examples involving diamonds, let us first justify Eq. 3 , as promised: Theorem 2.7 . \mathsf{IK}\mathsf{t}2(\Diamond,\Diamondblack) (and so all its extensions) proves: (1) \Diamond A\leftrightarrow\forall X(\Box(A\to\Boxblack X)\to X) (2) \Diamondblack A\leftrightarrow\forall X(\Boxblack(A\to\Box X)\to X) Proof. By symmetry, we need only prove the first item, for which we give each direction separately: \begin{array}[]{ll}\Diamond\Boxblack P\to P&\text{by $\mathsf{A}_{\Diamond\Boxblack}$}\\ \Diamond A\to(\Diamond A\to\Diamond\Boxblack P)\to P&\text{by $\mathsf{IPL}$ reasoning}\\ \Diamond A\to\Box(A\to\Boxblack P)\to P&\text{by $\mathsf{D}_{\Diamond}$}\\ \Diamond A\to\forall X(\Box(A\to\Boxblack X)\to X)&\text{by $\mathsf{gen},\mathsf{D}_{\forall},\mathsf{V}$}\\ \vskip 6.0pt plus 2.0pt minus 2.0pt\cr A\to\Boxblack\Diamond A&\text{by $\mathsf{A}_{\Boxblack\Diamond}$}\\ \Box(A\to\Boxblack\Diamond A)&\text{by $\mathsf{nec}_{\Box}$}\\ (\Box(A\to\Boxblack\Diamond A)\to\Diamond A)\to\Diamond A&\text{by $\mathsf{IPL}$ reasoning}\\ \forall X(\Box(A\to\Boxblack X)\to X)\to\Diamond A&\text{by $\mathsf{C}$, setting $X=\Diamond A$}\qed\end{array} As we indicated earlier, we may now dispense with the native diamonds, under the equivalences we have just proved: Definition 2.8 . \mathsf{IK}\mathsf{t}2 is obtained from \mathsf{IK}\mathsf{t}2(\Diamond,\Diamondblack) by setting: \begin{array}[]{r@{\ := \ }l}\Diamond A&\forall X(\Box(A\to\Boxblack X)\to X)\\ \Diamondblack A&\forall X(\Boxblack(A\to\Box X)\to X)\end{array} All further references to \Diamond and \Diamondblack are bound by the definitions displayed above. Example 2.9 (Redundancy) . Note that, under the definitions of \Diamond,\Diamondblack above, some of the axioms we gave in \mathsf{IK}\mathsf{t}2(\Diamond,\Diamondblack) become redundant, in the sense that they are already derivable from the others. In particular this is the case for half of the adjunction axioms, \mathsf{A}_{\Diamond\Boxblack} and \mathsf{A}_{\Diamondblack\Box} , and the distribution axioms for diamonds, \mathsf{D}_{\Diamond} and \mathsf{D}_{\Diamondblack} : \begin{array}[]{ll}\Boxblack A\to\Boxblack A&\text{by $\mathsf{IPL}$ reasoning}\\ \Box(\Boxblack A\to\Boxblack A)&\text{by $\mathsf{nec}_{\Box}$}\\ (\Box(\Boxblack A\to\Boxblack A)\to A)\to A&\text{by $\mathsf{IPL}$ reasoning}\\ \Diamond\Boxblack A\to A&\text{by $\mathsf{C}$ and definition of $\Diamond$}\end{array} \begin{array}[]{ll}(A\to B)\to(B\to\Boxblack P)\to A\to\Boxblack P&\text{by $\mathsf{IPL}$ reasoning}\\ \Box(A\to B)\to\Box(B\to\Boxblack P)\to\Box(A\to\Boxblack P)&\text{by $\mathsf{nec}_{\Box}$ and $\mathsf{D}_{\Box}$s}\\ \Box(A\to B)\to((\Box A\to\Boxblack P)\to P)\to\Box(B\to\Boxblack P)\to P&\text{by $\mathsf{IPL}$ reasoning}\\ \Box(A\to B)\to\Diamond A\to\Box(B\to\Boxblack P)\to P&\text{by $\mathsf{C}$ and definition of $\Diamond$}\\ \Box(A\to B)\to\Diamond A\to\Diamond B&\text{by $\mathsf{gen},\mathsf{D}_{\forall},\mathsf{V}$ and definition of $\Diamond$}\end{array} Again, derivability of \mathsf{D}_{\Diamondblack} and \mathsf{A}_{\Diamondblack\Box} follow by symmetry. Example 2.10 ( \forall distributes over \Box ) . Referring to Example 2.6 , we also have the converse principle: 3 3 3 The reader familiar with predicate modal logics will notice the similarity to the so-called ‘Barcan’ formulas. \begin{array}[]{ll}\forall X\Box A\to\Box A[P/X]&\text{by $\mathsf{C}$, setting $X=P$}\\ \Boxblack(\forall X\Box A\to\Box A[P/X])&\text{by $\mathsf{nec}_{\Boxblack}$}\\ (\Boxblack(\forall X\Box A\to\Box A[P/X])\to A[P/X])\to A[P/X]&\text{by $\mathsf{IPL}$ reasoning}\\ \Diamondblack\forall X\Box A\to A[P/X]&\text{by $\mathsf{C}$, setting $X=A[P/X]$ and definition of $\Diamond$}\\ \Diamondblack\forall X\Box A\to\forall XA&\text{by $\mathsf{gen},\mathsf{D}_{\forall},\mathsf{V}$}\\ \Box\Diamondblack\forall X\Box A\to\Box\forall XA&\text{by $\mathsf{nec}_{\Box}$ and $\mathsf{D}_{\Box}$}\\ \forall X\Box A\to\Box\forall XA&\text{by $\mathsf{A}_{\Box\Diamondblack}$}\end{array} The two directions together comprise a sort of infinitary version of the usual distribution of \Box s over \land : \Box(A\land B)\leftrightarrow\Box A\land\Box B . Again, by symmetry, we also have \Boxblack\forall XA\leftrightarrow\forall X\Boxblack A . 2.3. On the underlying (first-order) modal and tense logics Now that we have addressed Item i , the general correctness of our definition of diamonds, let us move to Item ii , the robustness of the minimal axiomatisation \mathsf{IK}\mathsf{t}2 we have presented. As we mentioned earlier in Remark 2.5 , intuitionistic modal logics found in the literature may contain further axioms among Eq. 4 . It turns out that these are all derivable within the current presentation: \begin{array}[]{ll}\bot\to\Boxblack\bot&\text{by $\mathsf{IPL}$ reasoning}\\ \Box(\bot\to\Boxblack\bot)&\text{by $\mathsf{nec}_{\Box}$}\\ (\Box(\bot\to\Boxblack\bot)\to\bot)\to\bot&\text{by $\mathsf{IPL}$ reasoning}\\ \Diamond\bot\to\bot&\text{by $\mathsf{C}$ and definition of $\Diamond$}\\ \vskip 6.0pt plus 2.0pt minus 2.0pt\cr\Diamond A_{i}\to\Diamond A_{0}\lor\Diamond A_{1}&\text{for $i=0,1$, by $\mathsf{IPL}$ reasoning}\\ \Boxblack\Diamond A_{i}\to\Boxblack(\Diamond A_{0}\lor\Diamond A_{1})&\text{by $\mathsf{nec}_{\Boxblack}$ and $\mathsf{D}_{\Boxblack}$}\\ A_{i}\to\Boxblack(\Diamond A_{0}\lor\Diamond A_{1})&\text{by $\mathsf{A}_{\Boxblack\Diamond}$}\\ A\lor B\to\Boxblack(\Diamond A_{0}\lor\Diamond A_{1})&\text{by $\mathsf{IPL}$ reasoning}\\ \Box(A\lor B\to\Boxblack(\Diamond A_{0}\lor\Diamond A_{1}))&\text{by $\mathsf{nec}_{\Box}$}\\ (\Box(A\lor B\to\Boxblack(\Diamond A_{0}\lor\Diamond A_{1}))\to\Diamond A\lor\Diamond B)\to\Diamond A\lor\Diamond B&\text{by $\mathsf{IPL}$ reasoning}\\ \Diamond(A\lor B)\to\Diamond A\lor\Diamond B&\text{by $\mathsf{C}$, setting $X=\Diamond A\lor\Diamond B$, and definition of $\Diamond$}\\ \vskip 6.0pt plus 2.0pt minus 2.0pt\cr(\Boxblack\Diamond A\to\Diamondblack\Box B)\to A\to B&\text{by $\mathsf{A}_{\Boxblack\Diamond}$, $\mathsf{A}_{\Diamondblack\Box}$ and $\mathsf{IPL}$ reasoning}\\ \Diamondblack(\Diamond A\to\Box B)\to A\to B&\text{by $\mathsf{D}_{\Boxblack}$, $\mathsf{D}_{\Diamondblack}$ and $\mathsf{nec}_{\Boxblack}$}\\ \Box\Diamondblack(\Diamond A\to\Box B)\to\Box(A\to B)&\text{by $\mathsf{nec}_{\Box}$ and $\mathsf{D}_{\Box}$}\\ (\Diamond A\to\Box B)\to\Box(A\to B)&\text{by $\mathsf{A}_{\Box\Diamondblack}$}\end{array} To explain a little the step justified ‘by \mathsf{D}_{\Boxblack} , \mathsf{D}_{\Diamondblack} and \mathsf{nec}_{\Boxblack} ’, note that \Diamondblack(C\to D)\to\Boxblack C\to\Diamondblack D is indeed readily derivable using those axioms and rule. So \mathsf{IK}\mathsf{t}2 contains the intuitionistic modal logic \mathsf{IK} of Fischer Servi and Simpson [ 63 , 66 ] . By symmetry, it also contains all the black versions of the principles in Eq. 4 too. Altogether, we now have that \mathsf{IK}\mathsf{t}2 furthermore contains Ewald’s \mathsf{IK}\mathsf{t} [ 22 ] , justifying our chosen nomenclature. 4 4 4 Ewald includes a couple other axioms too, namely \Box(A\land B)\leftrightarrow\Box A\land\Box B and \Diamond(A\to B)\to\Box A\to\Diamond B (and their black analogues). Both are routinely derivable in even \mathsf{CK} (and its black analogue, respectively). Let us point out that the derivation of \mathsf{IK}\mathsf{t} in \mathsf{IK}\mathsf{t}2 does not really rely on the availability of second-order reasoning. A closer inspection of the arguments reveals that we need only the following (first-order) principles: • \Diamond A\to\Box(A\to\Boxblack C)\to C • \Diamondblack A\to\Boxblack(A\to\Box C)\to C • C\to\Box(\Diamondblack C\to A)\to\Box A • C\to\Boxblack(\Diamond C\to A)\to\Boxblack A These are derivable already from the modal axioms and rules, Item 2 , and the tense axioms, Item 3 , under \mathsf{IPL} similarly to the proof of Theorem 2.7 . That such a minimal axiomatisation already generates all of \mathsf{IK}\mathsf{t} seems to be a folklore fact in the (intuitionistic) tense community, e.g. as stated in [ 42 , Remark 2.3] . We have provided the derivations above nonetheless as we have not been able to find them explicitly in the literature. Proposition 2.11 . \mathsf{IK}\mathsf{t} proves the following: (1) (\Box A\wedge\Diamond B)\to\Diamond(A\wedge B) . (2) (\Boxblack A\wedge\Diamondblack B)\to\Diamondblack(A\wedge B) (3) (\Diamond A\mathbin{\to}\Box B)\mathbin{\to}\Box(A\mathbin{\to}B) (4) (\Diamondblack A\mathbin{\to}\Boxblack B)\mathbin{\to}\Boxblack(A\mathbin{\to}B) (5) \Diamond(A\mathbin{\to}B)\mathbin{\to}(\Diamond A\mathbin{\to}\Box B) (6) \Diamondblack(A\mathbin{\to}B)\mathbin{\to}(\Diamondblack A\mathbin{\to}\Boxblack B) 2.4. Classical theory Finally, let us conclude this section by giving a classical version of second-order tense logic. This is obtained, as expected, by adding double negation elimination: 5 5 5 We could have made other equivalent choices, e.g. by adding Peirce’s law ((A\to B)\to A)\to A . Definition 2.12 . \mathsf{K}\mathsf{t}2:=\mathsf{IK}\mathsf{t}2+\lnot\lnot A\to A . We shall address the relationship between our intuitionistic and classical theories later in Section 8 . 3. Model theory: (bi)relational structures In this section we introduce a standard form of semantics for intuitionistic modal logics, exhibiting two relations: the partial order from Kripke structures for intuitionistic logic, and an ‘accessibility’ relation from relational structures for modal and tense logic. The most interesting aspect herein is the accommodation of sets (or predicates ), i.e. the domain over which variables X,Y etc. vary. We also consider a special subset of birelational structures, what we call predicate structures, and their specialisation to classical models. 3.1. Two-sorted birelational semantics under full comprehension The birelational semantics of (first-order) intuitionistic tense formulas will be defined as usual, following the intuitionistic modal and tense traditions [ 63 , 22 , 53 , 66 ] . To account for second-order quantifiers, we must further include a domain of sets over which variables vary: Definition 3.1 (Birelational structures) . A (two-sorted) (birelational) structure \mathfrak{B} includes the following data: • A set W of worlds of \mathfrak{B} . • A partial order \leq on W . • A class {\mathcal{W}}\subseteq\mathcal{P}(W) of sets (or predicates ) that are upwards-closed, i.e. if V\in{\mathcal{W}} and v\leq v^{\prime} then Vv\implies Vv^{\prime} . • An interpretation P_{\mathfrak{B}}\in{\mathcal{W}} for each P\in\mathsf{Pr} . • An accessibility relation R_{\mathfrak{B}}\subseteq W\times W . We furthermore require in \mathfrak{B} that R_{\mathfrak{B}} is a bisimulation on \leq , i.e.: • \forall v,w,w^{\prime}\in W\,(vR_{\mathfrak{B}}w\leq w^{\prime}\implies\exists v^{\prime}\geq v\,v^{\prime}R_{\mathfrak{B}}w^{\prime}) . • \forall v,v^{\prime},w\in W\,(v^{\prime}\geq vR_{\mathfrak{B}}w\implies\exists w^{\prime}\geq w\,v^{\prime}R_{\mathfrak{B}}w^{\prime} . Now, let us temporarily expand the language of formulas by including each V\in{\mathcal{W}} as a propositional symbol, setting V_{\mathfrak{B}}=V . The judgement v\vDash_{\mathfrak{B}}A , for v\in W , is defined by induction on the size of a closed formula A : • v\vDash_{\mathfrak{B}}P if P_{\mathfrak{B}}v . 6 6 6 Note that this clause accounts for the new propositional symbols V\in{\mathcal{W}} too. • v\vDash_{\mathfrak{B}}A\to B if, whenever v\leq v^{\prime} and v^{\prime}\vDash_{\mathfrak{B}}A , we have v^{\prime}\vDash_{\mathfrak{B}}B . • v\vDash_{\mathfrak{B}}\Box A if, whenever v\leq v^{\prime} and vR_{\mathfrak{B}}w^{\prime} , we have w^{\prime}\vDash_{\mathfrak{B}}A . • v\vDash_{\mathfrak{B}}\Boxblack A if, whenever v\leq v^{\prime} and u^{\prime}R_{\mathfrak{B}}v^{\prime} , we have u^{\prime}\vDash_{\mathfrak{B}}A . • v\vDash_{\mathfrak{B}}\forall XA if, whenever v\leq v^{\prime} and V\in{\mathcal{W}} , we have v^{\prime}\vDash_{\mathfrak{B}}A[V/X] . We write simply \vDash_{\mathfrak{B}}A if w\vDash_{\mathfrak{B}}A for every w\in W . We say that \mathfrak{M} is comprehensive if, for each closed formula C (of the expanded language), it has a set [C]=\{w\in W\ |\ w\vDash_{\mathfrak{B}}C\} in {\mathcal{W}} . A birelational model is a comprehensive birelational structure. Let us point out that ‘comprehensive structures’ have several alternative names in the literature, including ‘full structures’, ‘complete structures’, ‘principal structures’ or even just ‘structures’ (where ‘pre-structures’ are not necessarily comprehensive). We prefer the present terminology as it is less ambiguous (e.g. full semantics, complete axiomatisation,…) and is suggestive of the role this property plays in modelling the comprehension axiom, \mathsf{C} . Remark 3.2 (Full vs Henkin) . A naive domain of sets is simply the full powerset \mathcal{P}(W) . Such a structure is comprehensive by default, since it has every possible set, it includes in particular the extensions [C] . This is often referred to as the full or standard semantics of second-order logic. 7 7 7 Traditionally the nomenclature ‘second-order’ would be reserved for only such semantics, while our framework is perhaps more correctly dubbed ‘two-sorted first-order’. We shall refrain from rehashing this discussion here but refer the reader to REF for a comprehensive explanation. The current terminology ‘second-order’ has become standard in computational logic. However such a semantics for second-order logic admits no complete proof systems, as its validities are not even analytical, let alone recursively enumerable. It is more typical in proof theoretic investigations to admit the Henkin structures that we have presented here, treating ‘second-order’ as simply another sort. A useful discussion of this distinction and source of further references is available in [ 77 ] , in particular Sections 5 and 9. On the other hand, we cannot admit arbitrary domains of sets if \mathsf{IK}\mathsf{t}2 is to be sound for our models. The condition of comprehensivity is required to ensure that structures model comprehension, \mathsf{C} . Note the awkwardness here: the class of sets \mathcal{W} must be specified outright, but whether it is comprehensive or not depends on the resulting notion of entailment. For this reason typical defininitions of comprehensive structures are impredicative . Henceforth let us reserve the metavariable \mathfrak{B} to vary over birelational models. One of the main results of this work is that our axiomatic system \mathsf{IK}\mathsf{t}2 and our birelational semantics above actually induce the same logic: Main Theorem 3.3 (Soundness and completeness) . \mathsf{IK}\mathsf{t}2\vdash A\iff\forall\mathfrak{B}\,\vDash_{\mathfrak{B}}A . The proof of the \impliedby direction, completeness, will be broken up into several steps, in fact factoring through a further proof theoretic presentation of the logic from Section 4 . We shall turn to this soon, but for the remainder of this subsection let us establish the \implies direction, soundness. First we need a standard intermediate result: Lemma 3.4 (Monotonicity) . If v\leq v^{\prime} and v\vDash_{\mathfrak{B}}A then v^{\prime}\vDash_{\mathfrak{B}}A . Proof. By induction on the structure of A . Assume v\leq v^{\prime} and v\vDash_{\mathfrak{B}}A . • A=P\in\mathsf{Pr} : P_{\mathfrak{B}}v for P_{\mathfrak{B}}\in\mathcal{W} . Thus, as P_{\mathfrak{B}} is upwards closed wrt. \leq , P_{\mathfrak{B}}v^{\prime} and v^{\prime}\vDash_{\mathfrak{B}}P . • A=B\to C : Consider arbitrary v^{\prime\prime} with v^{\prime}\leq v^{\prime\prime} and v^{\prime\prime}\vDash_{\mathfrak{B}}B . By transitivity of \leq , v\leq v^{\prime\prime} and therefore v^{\prime\prime}\vDash C . By arbitrariness of v^{\prime\prime} : v^{\prime}\vDash_{\mathfrak{B}}B\to C . • A=\Box B : Consider arbitrary v^{\prime\prime} and w^{\prime} with v^{\prime}\leq v^{\prime\prime} and v^{\prime\prime}R_{\mathfrak{B}}w^{\prime} . Again by transitivity of \leq : v\leq v^{\prime\prime} , thus w^{\prime}\vDash_{\mathfrak{B}}B and v^{\prime}\vDash_{\mathfrak{B}}\Box B . • A=\Boxblack B : Consider arbitrary v^{\prime\prime} and w^{\prime} with v^{\prime}\leq v^{\prime\prime} and w^{\prime}R_{\mathfrak{B}}v^{\prime\prime} . As before, v\leq v^{\prime\prime} , thus w^{\prime}\vDash_{\mathfrak{B}}B and v^{\prime}\vDash_{\mathfrak{B}}\Boxblack B . • A=\forall XB : Consider arbitrary v^{\prime\prime} with v^{\prime}\leq v^{\prime\prime} and some V\in\mathcal{W} . As before, we have v\leq v^{\prime\prime} and therefore v^{\prime\prime}\vDash_{\mathfrak{B}}B[V/X] . This gives us v^{\prime}\vDash_{\mathfrak{B}}\forall XB . ∎ Theorem 3.5 (Soundness) . \mathsf{IK}\mathsf{t}2\vdash A\implies\forall\mathfrak{B}\,\vDash_{\mathfrak{B}}A . Proof. We proceed by induction on \mathsf{IK}\mathsf{t}2\vdash A . The axioms and rules of \mathsf{IPL}2 , namely are standard, following from soundness of \mathsf{IPL}2 for comprehensive intuitionistic structures (see, e.g., [ 70 , Section 11.1] ). In particular notice that their verification, being modality-free, does not involve the accessibility relation R_{\mathfrak{B}} . The modal axioms \mathsf{D}_{\Box} , \mathsf{D}_{\Boxblack} and rules \mathsf{nec}_{\Box},\mathsf{nec}_{\Boxblack} are also standard, following from the soundness of \mathsf{IK} (equivalently its black variant) for birelational structures [ 64 , Theorem 4] . In particular notice that their verification, being quantifier-free, does not involve the class \mathcal{W} of sets. It remains to verify the axioms involving \Diamond,\Diamondblack , as they are coded by second-order formulas. • \Box(A\mathbin{\to}B)\mathbin{\to}(\Diamond A\mathbin{\to}\Diamond B) . Let w_{1}\geq w with w_{1}\vDash_{\mathfrak{B}}\Box(A\mathbin{\to}B) . Let w_{2}\geq w_{1} with w_{2}\vDash_{\mathfrak{B}}\Diamond A=\forall X(\Box(A\mathbin{\to}\Boxblack X)\mathbin{\to}X) with X fresh for A . We show w_{2}\vDash_{\mathfrak{B}}\Diamond B=\forall X(\Box(B\mathbin{\to}\Boxblack X)\mathbin{\to}X) for X fresh for B . Let w_{3}\geq w_{2} and V\in{\mathcal{W}} . We need to show w_{3}\vDash_{\mathfrak{B}}\Box(B\mathbin{\to}\Boxblack V)\mathbin{\to}V . Let w_{4}\geq w_{3} with w_{4}\vDash_{\mathfrak{B}}\Box(B\mathbin{\to}\Boxblack V) and so we are left to show that w_{4}\vDash_{\mathfrak{B}}V . For w_{4}\leq w_{5}R_{\mathfrak{B}}v_{5} , v_{5}\vDash_{\mathfrak{B}}B\mathbin{\to}\Boxblack V . Now, as w_{1}\vDash_{\mathfrak{B}}\Box(A\mathbin{\to}B) and w_{1}\leq w_{5}R_{\mathfrak{B}}v_{5} , v_{5}\vDash_{\mathfrak{B}}A\mathbin{\to}B . Through standard reasoning, we have v_{5}\vDash_{\mathfrak{B}}A\mathbin{\to}\Boxblack V and so w_{4}\vDash_{\mathfrak{B}}\Box(A\mathbin{\to}\Boxblack V) . As w_{2}\vDash_{\mathfrak{B}}\Diamond A=\forall X(\Box(A\mathbin{\to}\Boxblack X)\mathbin{\to}X) and w_{4}\geq w_{2} , w_{4}\vDash_{\mathfrak{B}}\Box(A\mathbin{\to}\Boxblack V)\mathbin{\to}V and so it follows that w_{4}\vDash_{\mathfrak{B}}V . • A\mathbin{\to}\Box\Diamondblack A . Let w_{1}\geq w with v_{1}\vDash_{\mathfrak{B}}A . We show for w_{2}\geq w_{1} and w_{2}R_{\mathfrak{B}}v_{2} that v_{2}\vDash_{\mathfrak{B}}\Diamondblack A=\forall X(\Boxblack(A\mathbin{\to}\Box X)\mathbin{\to}X) for X fresh for A . Let v_{3}\geq v_{2} and V\in{\mathcal{W}} . We show v_{3}\vDash_{\mathfrak{B}}\Boxblack(A\mathbin{\to}\Box V)\mathbin{\to}V . Let v_{4}\geq v_{3} with v_{4}\vDash_{\mathfrak{B}}\Boxblack(A\mathbin{\to}\Box V) . As w_{2}R_{\mathfrak{B}}v_{2}\leq v_{4} , there exists w_{4}\geq w_{2} with w_{4}R_{\mathfrak{B}}v_{4} . By Lemma 3.4 , w_{4}\vDash_{\mathfrak{B}}A , and as v_{4}\vDash_{\mathfrak{B}}\Boxblack(A\mathbin{\to}\Box V) , w_{4}\vDash_{\mathfrak{B}}A\mathbin{\to}\Box V . Through standard reasoning this means that w_{4}\vDash_{\mathfrak{B}}\Box V , and as w_{4}R_{\mathfrak{B}}v_{4} , we must have v_{4}\vDash_{\mathfrak{B}}V . • \Diamond\Boxblack A\mathbin{\to}A . Let w_{1}\geq w with w_{1}\vDash_{\mathfrak{B}}\Diamond\Boxblack A=\forall X(\Box(\Boxblack A\mathbin{\to}\Boxblack X)\mathbin{\to}X) for X fresh for \Boxblack A . Then by definition as A\in{\mathcal{W}} , w_{1}\vDash_{\mathfrak{B}}\Box(\Boxblack A\mathbin{\to}\Boxblack A)\mathbin{\to}A . For all worlds v , we must have v\vDash_{\mathfrak{B}}\Boxblack A\mathbin{\to}\Boxblack A , so therefore w_{1}\vDash_{\mathfrak{B}}\Box(\Boxblack A\mathbin{\to}\Boxblack A) . So it follows that w_{1}\vDash_{\mathfrak{B}}A . The remaining axioms \mathsf{D}_{\Diamondblack},\mathsf{A}_{\Boxblack\Diamond},\mathsf{A}_{\Diamondblack\Box} follow by a symmetric argument. ∎ 3.2. Two-sorted predicate semantics under full comprehension We shall also consider intuitionistic predicate structures, in which every world is a classical modal model. We introduce this additional semantics for two reasons: (i) in order to further test the robustness of the logic \mathsf{IK}\mathsf{t}2 ; and, (ii) since we shall use these for our ultimate countermodel construction in Section 6 . Definition 3.6 (Predicate structures) . A (two-sorted) predicate structure \mathfrak{P} includes the following data: • A set \Omega of intuitionistic worlds (or states ). • A partial order \leq on \Omega . • A set W of (modal) worlds . • A set {\mathcal{W}}\supseteq\mathsf{Pr} of (modal) sets (or (modal) predicates ). • An interpretation P^{a}\subseteq W for each P\in{\mathcal{W}} and a\in\Omega . We require monotonicity: a\leq b\implies P^{a}\subseteq P^{b} . • An accessibility relation R^{a}\subseteq W\times W at a . We require monotonicity: a\leq b\implies R^{a}\subseteq R^{b} . Let us temporarily expand the language of formulas by including each P\in{\mathcal{W}} as a propositional symbol. The judgement a,v\vDash_{\mathfrak{P}}A , for a\in\Omega,v\in W , is defined by induction on the size of a formula A as follows: • a,v\vDash_{\mathfrak{P}}P if v\in P^{a} . • a,v\vDash_{\mathfrak{P}}A\to B if, whenever a\leq b and b,v\vDash_{\mathfrak{P}}A , we have b,v\vDash_{\mathfrak{P}}B . • a,v\vDash_{\mathfrak{P}}\Box A if, whenever a\leq b and vR^{b}w , we have b,w\vDash_{\mathfrak{P}}A . • a,v\vDash_{\mathfrak{P}}\Boxblack A if, whenever a\leq b and uR^{b}v , we have b,u\vDash_{\mathfrak{P}}A . • a,v\vDash_{\mathfrak{P}}\forall XA if, whenever a\leq b and P\in{\mathcal{W}} , we have b,v\vDash_{\mathfrak{P}}A[P/X] . We write simply \vDash_{\mathfrak{P}}A if a,v\vDash_{\mathfrak{P}}A for every a\in\Omega,v\in W . We say that \mathfrak{M} is comprehensive if, for each formula C (of the expanded language), it has a set [C]\in{\mathcal{W}} with [C]^{a}=\{w\in W\ |\ a,w\vDash_{\mathfrak{P}}C\} . A predicate model is a comprehensive predicate structure. Henceforth let us reserve the metavariable \mathfrak{P} to vary over predicate models. In fact, predicate structures can be construed as particular birelational structures. Formally: Definition 3.7 (Birelational collapse) . Given a predicate structure \mathfrak{P} , as presented in Definition 3.6 , we define a birelational structure \mathfrak{B}_{\mathfrak{P}} by: • The set of worlds is W_{\mathfrak{B}_{\mathfrak{P}}}:=\Omega\times W . • The partial order \leq_{\mathfrak{B}_{\mathfrak{P}}} is given by (a,v)\leq_{\mathfrak{B}_{\mathfrak{P}}}(b,w) if a\leq b and v=w . • The class of sets \mathcal{W}_{\mathfrak{B}_{\mathfrak{P}}} includes each V_{\mathfrak{B}_{\mathfrak{P}}}:=\{(a,v)\in W_{\mathfrak{B}_{\mathfrak{P}}}\,|\,v\in V^{a}\} , for V\in\mathcal{W} . • The interpretation of propositional symbols P_{\mathfrak{B}_{\mathfrak{P}}} is given by \{(a,v)\in W_{\mathfrak{B}_{\mathfrak{P}}}\,|\,v\in P^{a}\} . • The accessibility relation R_{\mathfrak{B}_{\mathfrak{P}}} is given by (a,v)R_{\mathfrak{B}_{\mathfrak{P}}}(b,w) if a=b and vR^{a}w . We better show that \mathfrak{B}_{\mathfrak{P}} satisfies the appropriate conditions of Definition 3.1 : Proposition 3.8 . {\mathfrak{B}_{\mathfrak{P}}} is a well-defined birelational structure. Proof. First we show that each V\in\mathcal{W}_{\mathfrak{B}_{\mathfrak{P}}} is upwards closed. Suppose (a,v)\leq_{\mathfrak{B}_{\mathfrak{P}}}(b,v) , WLoG, i.e. a\leq b . We have: \begin{array}[]{r@{ \ \implies\ }ll}(a,v)\in V_{\mathfrak{B}_{\mathfrak{P}}}&v\in V^{a}&\text{by definition of $V_{\mathfrak{B}_{\mathfrak{P}}}$}\\ &v\in V^{b}&\text{by monotonicity of $V^{-}$}\\ &(b,v)\in V_{\mathfrak{B}_{\mathfrak{P}}}&\text{by definition of $V_{\mathfrak{B}_{\mathfrak{P}}}$}\end{array} Now let us show that R_{\mathfrak{B}_{\mathfrak{P}}} is a bisimulation on \leq_{\mathfrak{B}_{\mathfrak{P}}} : • Suppose (a,v)R_{\mathfrak{B}_{\mathfrak{P}}}(a,w)\leq_{\mathfrak{B}_{\mathfrak{P}}}(b,w) , WLoG, so vR^{a}w and a\leq b . Then: – (a,v)\leq_{\mathfrak{B}_{\mathfrak{P}}}(b,v) by definition of \leq_{\mathfrak{B}_{\mathfrak{P}}} ; and, – vR^{b}w by monotonicity of R^{-} , so (b,v)R_{\mathfrak{B}_{\mathfrak{P}}}(b,w) by definition of R_{\mathfrak{B}_{\mathfrak{P}}} . So we can choose (b,v) as the required world. • Suppose (b,v)\geq_{\mathfrak{B}_{\mathfrak{P}}}(a,v)R_{\mathfrak{B}_{\mathfrak{P}}}(a,w) , WLoG, so b\geq a and vR^{a}w . Then: – (b,w)\geq_{\mathfrak{B}_{\mathfrak{P}}}(a,w) by definition of \leq_{\mathfrak{B}_{\mathfrak{P}}} ; and, – vR^{b}w by monotonicity of R^{-} , so (b,v)R_{\mathfrak{B}_{\mathfrak{P}}}(b,w) by definition of R_{\mathfrak{B}_{\mathfrak{P}}} . So we can choose (b,w) as the required world. ∎ We can exhibit a rather strong equivalence between the theories of \mathfrak{P} and \mathfrak{B}_{\mathfrak{P}} : Proposition 3.9 (Equivalence) . Let A(\vec{X}) be a formula, all free variables displayed, and \vec{V}\in\mathcal{W} with |\vec{V}|=|\vec{X}| . Then (a,v)\vDash_{\mathfrak{B}_{\mathfrak{P}}}A(\vec{V})\iff a,v\vDash_{\mathfrak{P}}A(\vec{V}_{\mathfrak{B}_{\mathfrak{P}}}) . Proof. By induction on the structure of A(\vec{X}) : • If A(\vec{X})=X and \vec{V}=V then: \begin{array}[]{r@{ \ \iff\ }ll}(a,v)\vDash_{\mathfrak{B}_{\mathfrak{P}}}V_{\mathfrak{B}_{\mathfrak{P}}}&v\in V^{a}&\text{by definition of $\vDash_{\mathfrak{B}_{\mathfrak{P}}}$}\\ &a,v\vDash_{\mathfrak{P}}V&\text{by definition of $\vDash_{\mathfrak{P}}$}\end{array} • A=P . (a,v)\vDash_{\mathfrak{B}_{\mathfrak{P}}}P \Longleftrightarrow (a,v)\in P_{\mathfrak{B}_{\mathfrak{P}}} \Longleftrightarrow v\in P^{a} \Longleftrightarrow a,v\vDash_{\mathfrak{P}}P . • A(\vec{X})=B(\vec{X})\to C(\vec{X}) : Assume (a,v)\vDash_{\mathfrak{B}_{\mathfrak{P}}}B(\vec{V})\to C(\vec{V}) and consider any b\geq a with b,v\vDash_{\mathfrak{P}}B(\vec{V}_{\mathfrak{B}_{\mathfrak{P}}}) . By inductive hypothesis (b,v)\vDash_{\mathfrak{B}_{\mathfrak{P}}}B(\vec{V}) and by (a,v)\leq_{\mathfrak{B}_{\mathfrak{P}}}(b,v) we have (b,v)\vDash_{\mathfrak{B}_{\mathfrak{P}}}C(\vec{V}) . Again by inductive hypothesis we get b,v\vDash_{\mathfrak{P}}C(\vec{V}_{\mathfrak{B}_{\mathfrak{P}}}) , which shows a,v\vDash_{\mathfrak{P}}B(\vec{V}_{\mathfrak{B}_{\mathfrak{P}}})\to C(\vec{V}_{\mathfrak{B}_{\mathfrak{P}}}) . For the converse assume a,v\vDash_{\mathfrak{P}}B(\vec{V}_{\mathfrak{B}_{\mathfrak{P}}})\to C(\vec{V}_{\mathfrak{B}_{\mathfrak{P}}}) and consider any (b,v)\geq_{\mathfrak{B}_{\mathfrak{P}}}(a,v) with (b,v)\vDash_{\mathfrak{B}_{\mathfrak{P}}}B(\vec{V}) . By inductive hypothesis b,v\vDash_{\mathfrak{P}}B(\vec{V}_{\mathfrak{B}_{\mathfrak{P}}}) and by a\leq b we have b,v\vDash_{\mathfrak{P}}C(\vec{V}_{\mathfrak{B}_{\mathfrak{P}}}) . Again by inductive hypothesis we get (b,v)\vDash_{\mathfrak{B}_{\mathfrak{P}}}C(\vec{V}) , which shows (a,v)\vDash_{\mathfrak{B}_{\mathfrak{P}}}B(\vec{V})\to C(\vec{V}) . • A=\Box B(\vec{X}) : (a,v)\vDash_{\mathfrak{B}_{\mathfrak{P}}}\Box B(\vec{V}) \Longleftrightarrow (b,w)\vDash_{\mathfrak{B}_{\mathfrak{P}}}B(\vec{V}) for any (a,v)\leq_{\mathfrak{B}_{\mathfrak{P}}}(b,v)R_{\mathfrak{B}_{\mathfrak{P}}}(b,w) \overset{\text{I.H.}}{\Longleftrightarrow} b,w\vDash_{\mathfrak{P}}B(\vec{V}_{\mathfrak{B}_{\mathfrak{P}}}) for any a\leq b and vR^{b}w \Longleftrightarrow a,v\vDash_{\mathfrak{P}}\Box B(\vec{V}_{\mathfrak{B}_{\mathfrak{P}}}) • A=\Boxblack B(\vec{X}) : (a,v)\vDash_{\mathfrak{B}_{\mathfrak{P}}}\Boxblack B(\vec{V}) \Longleftrightarrow (b,w)\vDash_{\mathfrak{B}_{\mathfrak{P}}}B(\vec{V}) for any (a,v)\leq_{\mathfrak{B}_{\mathfrak{P}}}(b,v) and (b,w)R_{\mathfrak{B}_{\mathfrak{P}}}(b,v) \overset{\text{I.H.}}{\Longleftrightarrow} b,w\vDash_{\mathfrak{P}}B(\vec{V}_{\mathfrak{B}_{\mathfrak{P}}}) for any a\leq b and wR^{b}v \Longleftrightarrow a,v\vDash_{\mathfrak{P}}\Boxblack B(\vec{V}_{\mathfrak{B}_{\mathfrak{P}}}) • A=\forall XB(\vec{X},X) : (a,v)\vDash_{\mathfrak{B}_{\mathfrak{P}}}\forall XB(\vec{V},X) \Longleftrightarrow (b,v)\vDash_{\mathfrak{B}_{\mathfrak{P}}}B(\vec{V},V) for any (b,v)\geq_{\mathfrak{B}_{\mathfrak{P}}}(a,v) and V\in\mathcal{W}_{\mathfrak{B}_{\mathfrak{P}}} \overset{\text{I.H.}}{\Longleftrightarrow} b,v\vDash_{\mathfrak{P}}B(\vec{V}_{\mathfrak{B}_{\mathfrak{P}}},V_{\mathfrak{B}_{\mathfrak{P}}}) for any a\leq b and V_{\mathfrak{B}_{\mathfrak{P}}}\in\mathcal{W} \Longleftrightarrow a,v\vDash_{\mathfrak{P}}\forall XB(\vec{V}_{\mathfrak{B}_{\mathfrak{P}}},X) . ∎ We can now recover a couple further useful results from this identification: Corollary 3.10 (Comprehensivity) . If \mathfrak{P} is comprehensive then so is \mathfrak{B}_{\mathfrak{P}} . Proof. Suppose \mathfrak{B} is comprehensive, and consider the sets [C] with v\in[C]^{a}\iff a,v\vDash_{\mathfrak{P}}C . We have as required: \begin{array}[]{r@{\ = \ }ll}[C]_{\mathfrak{B}_{\mathfrak{P}}}&\{(a,v)\in W_{\mathfrak{B}_{\mathfrak{P}}}\,|\,v\in[C]^{a}\}&\text{by definition of $-_{\mathfrak{B}_{\mathfrak{P}}}$}\\ &\{(a,v)\in W_{\mathfrak{B}_{\mathfrak{P}}}\,|\,a,v\vDash_{\mathfrak{P}}C\}&\text{by definition of $[C]$}\\ &\{(a,v)\in W_{\mathfrak{B}_{\mathfrak{P}}}\,|\,(a,v)\vDash_{\mathfrak{B}_{\mathfrak{P}}}C\}&\text{by \lx@cref{creftype\lx@tilde refnum}{pred-str-equiv-brcol}}\qed\end{array} Putting the previous Propositions 3.9 and 3.10 together we have: Proposition 3.11 . \forall\mathfrak{B}\,\vDash_{\mathfrak{B}}A\implies\forall\mathfrak{P}\,\vDash_{\mathfrak{P}}A . Finally it will be useful in our proof search argument in Section 6 to also inherit: Lemma 3.12 (Monotonicity) . If a\leq b and a,v\vDash_{\mathfrak{P}}A then b,v\vDash_{\mathfrak{P}}A . Proof. Given a\leq b , we have: \begin{array}[]{r@{\ \implies\ }ll}a,v\vDash_{\mathfrak{P}}A&(a,v)\vDash_{\mathfrak{B}_{\mathfrak{P}}}A&\text{by \lx@cref{creftype\lx@tilde refnum}{pred-str-equiv-brcol}}\\ &(b,v)\vDash_{\mathfrak{B}_{\mathfrak{P}}}A&\text{since $(a,v)\leq_{\mathfrak{B}_{\mathfrak{P}}}(b,v)$ and \lx@cref{creftype\lx@tilde refnum}{monotonicity} }\\ &b,v\vDash_{\mathfrak{P}}A&\text{by \lx@cref{creftype\lx@tilde refnum}{pred-str-equiv-brcol}}\qed\end{array} 3.3. Two-sorted (uni)relational semantics under full comprehension Finally let us adapt the semantics we have presented to the classical setting. We can view classical structures as special cases of either birelational or predicate structure where \leq is trivial, i.e.: • a birelational structure where all points are incomparable; or, • a predicate model with only one intuitionistic world. For the sake of completeness, let us give a self-contained definition: Definition 3.13 (Classical structures) . A (uni)relational structure \mathfrak{R} includes the following data: • A set W of worlds . • A class \mathcal{W}\subseteq\mathcal{P}(W) of sets (or predicates ). • An interpretation P_{\mathfrak{R}}\in\mathcal{W} for each P\in\mathsf{Pr} . • An accessibility relation R\subseteq W\times W . Now, let us temporarily expand the language of formulas by including each V\in{\mathcal{W}} as a propositional symbol, setting V^{{\mathfrak{R}}}:=V . The judgement v\vDash_{{\mathfrak{R}}}A , for v\in W , is defined by induction on the size of a closed formula A : • v\vDash_{{\mathfrak{R}}}P if P_{{\mathfrak{R}}}v . • v\vDash_{{\mathfrak{R}}}A\to B if, whenever v\vDash_{{\mathfrak{R}}}A , we have v\vDash_{{\mathfrak{R}}}B . • v\vDash_{{\mathfrak{R}}}\Box A if, whenever vRw , we have w\vDash_{{\mathfrak{R}}}A . • v\vDash_{{\mathfrak{R}}}\Boxblack A if, whenever uRv , we have u\vDash_{{\mathfrak{R}}}A . • v\vDash_{{\mathfrak{R}}}\forall XA if, whenever V\in{\mathcal{W}} , we have v\vDash_{{\mathfrak{R}}}A[V/X] . We write simply \vDash_{{\mathfrak{R}}}A if v\vDash_{{\mathfrak{R}}}A for every v\in W . We say that {\mathfrak{R}} is comprehensive if, for each formula C (of the expanded language), it has a predicate [C]\in\mathcal{W} with {[C]}=\{w\in W\ |\ w\vDash_{{\mathfrak{R}}}C\} . A (uni)relational model is a comprehensive relational structure. Henceforth, let us reserve the metavariable {\mathfrak{R}} to vary over relational models. Our main metalogical result for classical second-order tense logic, analogous to 3.3 in the intuitionistic case, is: Main Theorem 3.14 (Soundness and Completeness) . \mathsf{K}\mathsf{t}2\vdash A\iff\forall{\mathfrak{R}}\,\vDash_{{\mathfrak{R}}}A . Like the intuitionistic case completeness, the \impliedby direction, is factored through a proof theoretic presentation of the logic from Section 4 . Given how we have defined relational models, we can factor soundness, the \implies direction, into (a) already established soundness of \mathsf{IK}\mathsf{t}2 for birelational structures; and (b) verification of the additional axiom \lnot\lnot A\to A : Theorem 3.15 (Soundness) . \mathsf{K}\mathsf{t}2\vdash A\implies\forall{\mathfrak{R}}\,\vDash_{{\mathfrak{R}}}A . Proof sketch. A relational model can be expanded into a birelational model by simply setting \leq to be equality on worlds. Thus all the axioms and rules of \mathsf{IK}\mathsf{t}2 are already sound for relational models, by Theorem 3.5 . It remains to verify the double negation axiom, \lnot\lnot A\to A . Suppose v\vDash_{{\mathfrak{R}}}\lnot\lnot A , then either v\not\vDash_{{\mathfrak{R}}}A or v\vDash_{{\mathfrak{R}}}\bot . We consider each case separately: \begin{array}[]{r@{\ \implies\ }ll}v\not\vDash_{{\mathfrak{R}}}\lnot A&v\vDash_{{\mathfrak{R}}}A\text{ and }v\not\vDash_{{\mathfrak{R}}}\bot&\text{by definition of $\vDash_{{\mathfrak{R}}}$ and $\lnot$}\\ &v\vDash_{{\mathfrak{R}}}A\\ \vskip 3.0pt plus 1.0pt minus 1.0pt\cr v\vDash_{{\mathfrak{R}}}\bot&v\vDash_{{\mathfrak{R}}}[A]&\text{since $\bot=\forall XX$ and by definition of $\vDash_{{\mathfrak{R}}}$}\\ &v\in[A]&\text{by definition of $\vDash_{{\mathfrak{R}}}$}\\ &v\vDash_{{\mathfrak{R}}}A&\text{by definition of $[A]$}\qed\end{array} 4. Proof theory: labelled systems We shall now turn to a proof theoretic presentation of second-order tense logic. As well as for self contained interest this will, as already mentioned, serve to factor our earlier stated axiomatic completeness results. Unlike the previous two sections, we shall first present the classical system, before recovering the intuitionistic versions via appropriate constraints. The only reason for this is brevity, allowing us to define all systems we consider without repeating rules. 4.1. Labelled sequent calculi Labelled deductive systems were proposed by Gabbay [ 25 ] as a uniform proof-theoretic framework for a wide range of logics. The idea has been applied to modal logic by using the strength of its (uni)relational semantics [ 60 ] in order to resolve the difficulty of designing proof systems for modal logic using standard Gentzen sequents. They reason about formulas labelled by the world in which they are evaluated, while keeping track of a ‘control’ constraining the accessibility relation between worlds. They were fully developed for intuitionistic modal logic by Simpson [ 66 ] , before being widely applied to e.g. classical modal logic with Horn [ 79 ] or coherent [ 49 ] extensions and beyond [ 50 ] , justification logic [ 26 ] , non-normal modal logics [ 17 ] , conditional logics [ 30 ] , first-order modal logic [ 51 ] , etc. Let us now fix a set \mathsf{Wl} of world symbols , written u,v,w etc. A relational atom is an expression vRw , where v,w\in\mathsf{Wl} . A labelled formula is an expression v:A where v\in\mathsf{Wl} and A is a formula. Write \ell\mathsf{Fm} for the set of labelled formulas. A (labelled) sequent is an expression \mathbf{R}\,|\,\Gamma\Rightarrow\Delta where \mathbf{R} is a set of relational atoms, called the relational context , and \Gamma and \Delta are multisets of labelled formulas, called the (LHS) cedent and (RHS) cedent , respectively. ‘ \,|\, ’ and ‘ \Rightarrow ’ here are just syntactic delimiters. Informally, we may read sequents as “if all of the LHS holds, then some of the RHS is true”. This intuition is developed more formally later in Section 7 . Identity and cut: \begin{array}[]{cc}{\vbox{\hbox{\kern 8.0666pt\hbox{\vbox{\hbox{\kern 37.29602pt\hbox{\hbox{\hbox{$$}}}\kern 37.29602pt}\kern 1.43518pt\hbox{\hbox to0.0pt{\hss\hbox{$\smash{\lower 2.5pt\hbox{$\scriptstyle\mathsf{id}\;$}}$}}\vbox{\vbox to0.4pt{\vfill\hbox to74.59206pt{\leaders{\hrule}{\hfill}\kern 0.0pt}\vfill}}\hbox to0.0pt{\hbox{$\smash{\lower 2.5pt\hbox{$$}}$}\hss}}\kern 1.43518pt\hbox{\hbox{\hbox{$\kern 0.0pt\hbox{$\mathbf{R}\,|\,v:A\Rightarrow v:A$}\kern 0.0pt$}}}}}\kern 0.0pt}}}&{{}{}\vbox{\hbox{\kern 12.03326pt\hbox{\vbox{\hbox{\hbox{\hbox{\hbox{\hbox{\hbox{$\mathbf{R}\,|\,\Gamma\Rightarrow\Delta,v:A$}}\kern 10.00002pt}\hbox{\hbox{$\mathbf{R}\,|\,\Gamma^{\prime},v:A\Rightarrow\Delta^{\prime}$}}}}}\kern 1.43518pt\hbox{\kern 0.0pt\hbox to0.0pt{\hss\hbox{$\smash{\lower 2.5pt\hbox{$\scriptstyle\mathsf{cut}\;$}}$}}\vbox{\vbox to0.4pt{\vfill\hbox to160.77235pt{\leaders{\hrule}{\hfill}\kern 0.0pt}\vfill}}\hbox to0.0pt{\hbox{$\smash{\lower 2.5pt\hbox{$$}}$}\hss}\kern 0.0pt}\kern 1.43518pt\hbox{\kern 43.68489pt\hbox{\hbox{$\mathbf{R}\,|\,\Gamma,\Gamma^{\prime}\Rightarrow\Delta,\Delta^{\prime}$}}\kern 43.68489pt}}}\kern 0.0pt}}}\end{array} Strutural rules: \begin{array}[]{cc}{\vbox{\hbox{\kern 10.46269pt\hbox{\vbox{\hbox{\kern 12.74182pt\hbox{\hbox{\hbox{$\mathbf{R}\,|\,\Gamma\Rightarrow\Delta$}}}\kern 12.74182pt}\kern 1.43518pt\hbox{\hbox to0.0pt{\hss\hbox{$\smash{\lower 2.5pt\hbox{$\scriptstyle\mathsf{w}_{l}\;$}}$}}\vbox{\vbox to0.4pt{\vfill\hbox to72.58061pt{\leaders{\hrule}{\hfill}\kern 0.0pt}\vfill}}\hbox to0.0pt{\hbox{$\smash{\lower 2.5pt\hbox{$$}}$}\hss}}\kern 1.43518pt\hbox{\hbox{\hbox{$\kern 0.0pt\hbox{$\mathbf{R}\,|\,\Gamma,v:A\Rightarrow\Delta$}\kern 0.0pt$}}}}}\kern 0.0pt}}}&{\vbox{\hbox{\kern 11.59119pt\hbox{\vbox{\hbox{\kern 12.74182pt\hbox{\hbox{\hbox{$\mathbf{R}\,|\,\Gamma\Rightarrow\Delta$}}}\kern 12.74182pt}\kern 1.43518pt\hbox{\hbox to0.0pt{\hss\hbox{$\smash{\lower 2.5pt\hbox{$\scriptstyle\mathsf{w}_{r}\;$}}$}}\vbox{\vbox to0.4pt{\vfill\hbox to72.58061pt{\leaders{\hrule}{\hfill}\kern 0.0pt}\vfill}}\hbox to0.0pt{\hbox{$\smash{\lower 2.5pt\hbox{$$}}$}\hss}}\kern 1.43518pt\hbox{\hbox{\hbox{$\kern 0.0pt\hbox{$\mathbf{R}\,|\,\Gamma\Rightarrow\Delta,v:A$}\kern 0.0pt$}}}}}\kern 0.0pt}}}\\ \vskip 6.0pt plus 2.0pt minus 2.0pt\cr{\vbox{\hbox{\kern 8.79047pt\hbox{\vbox{\hbox{\hbox{\hbox{\hbox{$\mathbf{R}\,|\,\Gamma,v:A,v:A\Rightarrow\Delta$}}}}\kern 1.43518pt\hbox{\kern 0.0pt\hbox to0.0pt{\hss\hbox{$\smash{\lower 2.5pt\hbox{$\scriptstyle\mathsf{c}_{l}\;$}}$}}\vbox{\vbox to0.4pt{\vfill\hbox to98.06425pt{\leaders{\hrule}{\hfill}\kern 0.0pt}\vfill}}\hbox to0.0pt{\hbox{$\smash{\lower 2.5pt\hbox{$$}}$}\hss}\kern 0.0pt}\kern 1.43518pt\hbox{\kern 12.74182pt\hbox{\hbox{$\kern 0.0pt\hbox{$\mathbf{R}\,|\,\Gamma,v:A\Rightarrow\Delta$}\kern 0.0pt$}}\kern 12.74182pt}}}\kern 0.0pt}}}&{\vbox{\hbox{\kern 9.91896pt\hbox{\vbox{\hbox{\hbox{\hbox{\hbox{$\mathbf{R}\,|\,\Gamma\Rightarrow\Delta,v:A,v:A$}}}}\kern 1.43518pt\hbox{\kern 0.0pt\hbox to0.0pt{\hss\hbox{$\smash{\lower 2.5pt\hbox{$\scriptstyle\mathsf{c}_{r}\;$}}$}}\vbox{\vbox to0.4pt{\vfill\hbox to98.06425pt{\leaders{\hrule}{\hfill}\kern 0.0pt}\vfill}}\hbox to0.0pt{\hbox{$\smash{\lower 2.5pt\hbox{$$}}$}\hss}\kern 0.0pt}\kern 1.43518pt\hbox{\kern 12.74182pt\hbox{\hbox{$\kern 0.0pt\hbox{$\mathbf{R}\,|\,\Gamma\Rightarrow\Delta,v:A$}\kern 0.0pt$}}\kern 12.74182pt}}}\kern 0.0pt}}}\end{array} Logical rules: \begin{array}[]{cc}{{}{}\vbox{\hbox{\kern 12.55429pt\hbox{\vbox{\hbox{\hbox{\hbox{\hbox{\hbox{\hbox{$\mathbf{R}\,|\,\Gamma\Rightarrow\Delta,v:A$}}\kern 10.00002pt}\hbox{\hbox{$\mathbf{R}\,|\,\Gamma^{\prime},v:B\Rightarrow\Delta^{\prime}$}}}}}\kern 1.43518pt\hbox{\kern 0.0pt\hbox to0.0pt{\hss\hbox{$\smash{\lower 2.5pt\hbox{$\scriptstyle\to_{l}\;$}}$}}\vbox{\vbox to0.4pt{\vfill\hbox to161.35915pt{\leaders{\hrule}{\hfill}\kern 0.0pt}\vfill}}\hbox to0.0pt{\hbox{$\smash{\lower 2.5pt\hbox{$$}}$}\hss}\kern 0.0pt}\kern 1.43518pt\hbox{\kern 20.52649pt\hbox{\hbox{$\mathbf{R}\,|\,\Gamma,\Gamma^{\prime},v:A\to B\Rightarrow\Delta,\Delta^{\prime}$}}\kern 20.52649pt}}}\kern 0.0pt}}}&{\vbox{\hbox{\kern 13.68279pt\hbox{\vbox{\hbox{\hbox{\hbox{\hbox{$\mathbf{R}\,|\,\Gamma,v:A\Rightarrow\Delta,v:B$}}}}\kern 1.43518pt\hbox{\kern 0.0pt\hbox to0.0pt{\hss\hbox{$\smash{\lower 2.5pt\hbox{$\scriptstyle\to_{r}\;$}}$}}\vbox{\vbox to0.4pt{\vfill\hbox to98.65105pt{\leaders{\hrule}{\hfill}\kern 0.0pt}\vfill}}\hbox to0.0pt{\hbox{$\smash{\lower 2.5pt\hbox{$$}}$}\hss}\kern 0.0pt}\kern 1.43518pt\hbox{\kern 3.7141pt\hbox{\hbox{$\kern 0.0pt\hbox{$\mathbf{R}\,|\,\Gamma\Rightarrow\Delta,v:A\to B$}\kern 0.0pt$}}\kern 3.7141pt}}}\kern 0.0pt}}}\\ \vskip 6.0pt plus 2.0pt minus 2.0pt\cr{\vbox{\hbox{\kern 11.87376pt\hbox{\vbox{\hbox{\hbox{\hbox{\hbox{$\mathbf{R}\,|\,\Gamma,v:A[C/X]\Rightarrow\Delta$}}}}\kern 1.43518pt\hbox{\kern 0.0pt\hbox to0.0pt{\hss\hbox{$\smash{\lower 2.5pt\hbox{$\scriptstyle\forall_{l}\;$}}$}}\vbox{\vbox to0.4pt{\vfill\hbox to104.23466pt{\leaders{\hrule}{\hfill}\kern 0.0pt}\vfill}}\hbox to0.0pt{\hbox{$\smash{\lower 2.5pt\hbox{$$}}$}\hss}\kern 0.0pt}\kern 1.43518pt\hbox{\kern 7.68121pt\hbox{\hbox{$\kern 0.0pt\hbox{$\mathbf{R}\,|\,\Gamma,v:\forall XA\Rightarrow\Delta$}\kern 0.0pt$}}\kern 7.68121pt}}}\kern 0.0pt}}}&{\vbox{\hbox{\kern 13.00226pt\hbox{\vbox{\hbox{\hbox{\hbox{\hbox{$\mathbf{R}\,|\,\Gamma\Rightarrow\Delta,v:A[P/X]$}}}}\kern 1.43518pt\hbox{\kern 0.0pt\hbox to0.0pt{\hss\hbox{$\smash{\lower 2.5pt\hbox{$\scriptstyle\forall_{r}\;$}}$}}\vbox{\vbox to0.4pt{\vfill\hbox to103.90344pt{\leaders{\hrule}{\hfill}\kern 0.0pt}\vfill}}\hbox to0.0pt{\hbox{$\smash{\lower 2.5pt\hbox{$\;\text{\footnotesize$P$ fresh}$}}$}\hss}\kern 0.0pt}\kern 1.43518pt\hbox{\kern 7.5156pt\hbox{\hbox{$\kern 0.0pt\hbox{$\mathbf{R}\,|\,\Gamma\Rightarrow\Delta,v:\forall XA$}\kern 0.0pt$}}\kern 7.5156pt}}}\kern 29.94336pt}}}\\ \vskip 6.0pt plus 2.0pt minus 2.0pt\cr{\vbox{\hbox{\kern 10.92935pt\hbox{\vbox{\hbox{\kern 2.63887pt\hbox{\hbox{\hbox{$\mathbf{R},vRw\,|\,\Gamma,w:A\Rightarrow\Delta$}}}\kern 2.63887pt}\kern 1.43518pt\hbox{\hbox to0.0pt{\hss\hbox{$\smash{\lower 2.5pt\hbox{$\scriptstyle\Box_{l}\;$}}$}}\vbox{\vbox to0.4pt{\vfill\hbox to104.82944pt{\leaders{\hrule}{\hfill}\kern 0.0pt}\vfill}}\hbox to0.0pt{\hbox{$\smash{\lower 2.5pt\hbox{$$}}$}\hss}}\kern 1.43518pt\hbox{\hbox{\hbox{$\kern 0.0pt\hbox{$\mathbf{R},vRw\,|\,\Gamma,v:\Box A\Rightarrow\Delta$}\kern 0.0pt$}}}}}\kern 0.0pt}}}&{\vbox{\hbox{\kern 12.05785pt\hbox{\vbox{\hbox{\hbox{\hbox{\hbox{$\mathbf{R},vRw\,|\,\Gamma\Rightarrow\Delta,w:A$}}}}\kern 1.43518pt\hbox{\kern 0.0pt\hbox to0.0pt{\hss\hbox{$\smash{\lower 2.5pt\hbox{$\scriptstyle\Box_{r}\;$}}$}}\vbox{\vbox to0.4pt{\vfill\hbox to99.55168pt{\leaders{\hrule}{\hfill}\kern 0.0pt}\vfill}}\hbox to0.0pt{\hbox{$\smash{\lower 2.5pt\hbox{$\;\text{\footnotesize$w$ fresh}$}}$}\hss}\kern 0.0pt}\kern 1.43518pt\hbox{\kern 9.73553pt\hbox{\hbox{$\kern 0.0pt\hbox{$\mathbf{R}\,|\,\Gamma\Rightarrow\Delta,v:\Box A$}\kern 0.0pt$}}\kern 9.73553pt}}}\kern 29.68874pt}}}\\ \vskip 6.0pt plus 2.0pt minus 2.0pt\cr{\vbox{\hbox{\kern 10.92935pt\hbox{\vbox{\hbox{\kern 3.4907pt\hbox{\hbox{\hbox{$\mathbf{R},uRv\,|\,\Gamma,u:A\Rightarrow\Delta$}}}\kern 3.4907pt}\kern 1.43518pt\hbox{\hbox to0.0pt{\hss\hbox{$\smash{\lower 2.5pt\hbox{$\scriptstyle\Boxblack_{l}\;$}}$}}\vbox{\vbox to0.4pt{\vfill\hbox to103.12576pt{\leaders{\hrule}{\hfill}\kern 0.0pt}\vfill}}\hbox to0.0pt{\hbox{$\smash{\lower 2.5pt\hbox{$$}}$}\hss}}\kern 1.43518pt\hbox{\hbox{\hbox{$\kern 0.0pt\hbox{$\mathbf{R},uRv\,|\,\Gamma,v:\Boxblack A\Rightarrow\Delta$}\kern 0.0pt$}}}}}\kern 0.0pt}}}&{\vbox{\hbox{\kern 12.05785pt\hbox{\vbox{\hbox{\hbox{\hbox{\hbox{$\mathbf{R},uRv\,|\,\Gamma\Rightarrow\Delta,u:A$}}}}\kern 1.43518pt\hbox{\kern 0.0pt\hbox to0.0pt{\hss\hbox{$\smash{\lower 2.5pt\hbox{$\scriptstyle\Boxblack_{r}\;$}}$}}\vbox{\vbox to0.4pt{\vfill\hbox to96.14433pt{\leaders{\hrule}{\hfill}\kern 0.0pt}\vfill}}\hbox to0.0pt{\hbox{$\smash{\lower 2.5pt\hbox{$\;\text{\footnotesize$u$ fresh}$}}$}\hss}\kern 0.0pt}\kern 1.43518pt\hbox{\kern 8.03186pt\hbox{\hbox{$\kern 0.0pt\hbox{$\mathbf{R}\,|\,\Gamma\Rightarrow\Delta,v:\Boxblack A$}\kern 0.0pt$}}\kern 8.03186pt}}}\kern 28.2952pt}}}\end{array} Figure 2 . Rules of the labelled system \ell\mathsf{K}\mathsf{t}2 (with cut). Here a symbol is fresh if it does not occur in the lower sequent. Definition 4.1 (Sequent calculi) . The system \ell\mathsf{K}\mathsf{t}2 is given by the rules in Fig. 2 . We also define two intuitionistic restrictions of this system: • \ell\mathsf{IK}\mathsf{t}2 is the restriction of \ell\mathsf{K}\mathsf{t}2 to sequents with singleton RHS. (In particular, there can be no right structural steps, \mathsf{w}_{r} and \mathsf{c}_{r} ). • \mathsf{m}\ell\mathsf{IK}\mathsf{t}2 is the restriction of \ell\mathsf{K}\mathsf{t}2 where each right logical step has singleton RHS in its premiss (i.e. \Delta=\varnothing ). The lower sequent of any inference step is the conclusion , and any upper sequents are premisses . Proofs and derivations in a system are defined as usual. We write \mathsf{L}\vdash\mathbf{R}\,|\,\Gamma\Rightarrow\Delta if the calculus \mathsf{L} proves the \mathbf{R}\,|\,\Gamma\Rightarrow\Delta . We write simply \mathsf{L}\vdash A if \mathsf{L}\vdash\cdot\,|\,\cdot\Rightarrow v:A . \ell\mathsf{K}\mathsf{t}2 is nothing more than the extension of the labelled calculus for tense logic [ 10 , 15 ] by the usual rules for second-order quantifiers (see, e.g., [ 29 , Section 3.A.1] , [ 58 , Section 5.1] or [ 73 , Definition 15.3] ). The singleton RHS restriction defining \ell\mathsf{IK}\mathsf{t}2 is standard for intuitionistic sequent calculi, with calculi for intuitionistic modal and tense logics obtained in the same way [ 66 , 69 , 44 ] . Finally \mathsf{m}\ell\mathsf{IK}\mathsf{t}2 is a somewhat intermediate calculus, in the spirit of Maehara [ 45 , 41 ] . The reason we introduce it is that it is necessary for our proof search argument later, in Section 6 . As we shall soon see, over the language we consider, there is no material difference between our two intuitionistic systems, cf. Proposition 4.5 . First let us state our main proof theoretic results: Main Theorem 4.2 (Hauptsatz) . We have the following: (1) \ell\mathsf{K}\mathsf{t}2\vdash A\implies\ell\mathsf{K}\mathsf{t}2\setminus\mathsf{cut}\vdash A . (2) \ell\mathsf{IK}\mathsf{t}2\vdash A\implies\ell\mathsf{IK}\mathsf{t}2\setminus\mathsf{cut}\vdash A . The admissibility of cut is a key desideratum in sequent calculus proof theory. In particular it renders the system more amenable to proof search , reducing non-determinism therein. As for our soundness and completness results, 3.3 and 3.14 , this result is obtained by the ‘grand tours’ of Figs. 1(a) and 1(b) . 4.2. Interlude: false positives Usual labelled calculi for \mathsf{IK} , e.g. from [ 66 , Section 7.2] , include the rule, (5) \mathbf{R}\,|\,\Gamma,v:\bot\Rightarrow w:A where \mathbf{R} (as well as \Gamma ) may be arbitrary . Under our second-order definition of falsity, \bot:=\forall XX , the above is derivable in \ell\mathsf{IK}\mathsf{t}2 when v and w are connected by some (undirected) path in \mathbf{R} . Formally, let us say that v and w are connected in \mathbf{R} if there is a sequence v=v_{0},\dots,v_{n}=w where, for each ii . The properties above simply exhaust all the possibilities of activity for a given principal formula, and possibilities for extension of the proof search branch from i . ∎ Returning to Schütte’s partial valuations, we can think of v:A\in\Gamma_{\omega} as indicating that A is true at world v , with respect to {\mathfrak{R}}^{-} (or an appropriate expansion of it by predicates). Symmetrically v:A\in\Delta_{\omega} indicates that A is false at world v . 5.5. A compatible countermodel via possible values To define an appropriate domain of sets, Prawitz’ idea in [ 55 ] was to simply take all possibilities consistent with the proof search branch, by way of so-called possible values . We shall follow a similar idea here, though again we avoid explicitly defining possible values. Recall that we have already fixed an unprovable sequent \mathcal{S}_{0} and extended it to the proof search branch \mathfrak{S}=(\mathcal{S}_{i})_{i<\omega} . Definition 5.8 (Possible extensions) . A possible extension of a formula C (with respect to \mathfrak{S} ) is a set \mathtt{C}\subseteq\mathsf{Wl} s.t.: • v:C\in\Gamma_{\omega}\implies v\in\mathtt{C} ; and, • v:C\in\Delta_{\omega}\implies v\notin\mathtt{C} . Write \mathtt{C}\geq_{\mathfrak{S}}C if \mathtt{C} is a possible extension of C . It is obvious but pertinent to state that every formula C admits a minimal (possible) extension \lfloor{C}\rfloor:=\{v\in\mathsf{Wl}\ |\ v:C\in\Gamma^{\omega}\} . A unirelational structure may now be obtained from our pre-structure by allowing all possible extensions as sets: Definition 5.9 (Countermodel) . We expand {\mathfrak{R}}^{-} into a structure {\mathfrak{R}} by including the following missing data: • The domain of sets \mathcal{W}\subseteq\mathcal{P}(\mathsf{Wl}) includes all possible extensions (of all formulas). • We set P_{{\mathfrak{R}}}:=\lfloor{P}\rfloor for each P\in\mathsf{Pr} . 12 12 12 In fact the interpretation of propositional symbols is inconsequential, among possible extensions, but we choose the minmal one for concreteness. The key technical result we need about this structure relates the evaluation of formulas over possible extensions to the desideratum that \Gamma_{\omega} be true and \Delta_{\omega} be false. Such compatibility with the partial valuation induced by proof search is what will allow us to show that {\mathfrak{R}} is, in fact, comprehensive. Lemma 5.10 (Compatibility) . For formulas A(\vec{X}) (all free variables among \vec{X}=X_{1},\dots,X_{n} ) and \vec{C}=C_{1},\dots,C_{n} we have: (1) v:A(\vec{C})\in\Gamma_{\omega}\implies v\vDash_{{\mathfrak{R}}}A(\vec{\mathtt{C}}) whenever \vec{\mathtt{C}}\geq_{\mathfrak{S}}\vec{C} . (2) v:A(\vec{C})\in\Delta_{\omega}\implies v\not\vDash_{{\mathfrak{R}}}A(\vec{\mathtt{C}}) whenever \vec{\mathtt{C}}\geq_{\mathfrak{S}}\vec{C} . where we write \vec{\mathtt{C}}\geq_{\mathfrak{S}}\vec{C} for \mathtt{C}_{1}\geq_{\mathfrak{S}}C_{1},\dots,\mathtt{C}_{n}\geq_{\mathfrak{S}}C_{n} . Before proving this, let us point out an immediate consequence. Write \vDash_{{\mathfrak{R}}}\mathbf{R}\,|\,\Gamma\Rightarrow\Delta if \mathbf{R}\subseteq\mathbf{R}_{\omega} and, for each v:A\in\Gamma (or v:A\in\Delta ) we have v\vDash_{{\mathfrak{R}}}A (or v\not\vDash_{{\mathfrak{R}}}A , respectively). As a special case of Lemma 5.10 above we have: Proposition 5.11 . \not\vDash_{{\mathfrak{R}}}\mathcal{S}_{0} . Proof of Lemma 5.10 . By induction on A(\vec{X}) : • Suppose A(\vec{X})=X , and fix C and \mathtt{C}\geq_{\mathfrak{S}}C . We have: \begin{array}[]{r@{\ \implies\ }ll}v:C\in\Gamma_{\omega}&v\in\mathtt{C}&\text{since $\mathtt{C}\geq_{\mathfrak{S}}C$}\\ &v\vDash_{{\mathfrak{R}}}\mathtt{C}&\text{by definition of $\vDash_{{\mathfrak{R}}}$}\\ \vskip 3.0pt plus 1.0pt minus 1.0pt\cr v:C\in\Delta_{\omega}&v\notin\mathtt{C}&\text{since $\mathtt{C}\geq_{\mathfrak{S}}C$}\\ &v\not\vDash_{{\mathfrak{R}}}\mathtt{C}&\text{by definition of $\vDash_{{\mathfrak{R}}}$}\end{array} • Suppose A(\vec{X})=A_{0}(\vec{X})\to A_{1}(\vec{X}) , and fix \vec{C} and \vec{\mathtt{C}}\geq_{\mathfrak{S}}\vec{C} . We have: \begin{array}[]{r@{\ \implies\ }ll}v:A(\vec{C})\in\Gamma_{\omega}&v:A_{0}(\vec{C})\in\Delta_{\omega}\text{ or }v:A_{1}(\vec{C})\in\Gamma_{\omega}&\text{by \lx@cref{creftype\lx@tilde refnum}{partial-val-props-classical}}\\ &v\not\vDash_{{\mathfrak{R}}}A_{0}(\vec{\mathtt{C}})\text{ or }v\vDash_{{\mathfrak{R}}}A_{1}(\vec{\mathtt{C}})&\text{by IH}\\ &v\vDash_{{\mathfrak{R}}}A(\vec{\mathtt{C}})&\text{by definition of $\vDash_{{\mathfrak{R}}}$}\\ \vskip 3.0pt plus 1.0pt minus 1.0pt\cr v:A(\vec{C})\in\Delta_{\omega}&v:A_{0}(\vec{C})\in\Gamma_{\omega}\text{ and }v:A_{1}(\vec{C})\in\Delta_{\omega}&\text{by \lx@cref{creftype\lx@tilde refnum}{partial-val-props-classical}}\\ &v\vDash_{{\mathfrak{R}}}A_{0}(\vec{\mathtt{C}})\text{ and }v:\not\vDash_{{\mathfrak{R}}}A_{1}(\vec{\mathtt{C}})&\text{by IH}\\ &v\not\vDash_{{\mathfrak{R}}}A(\vec{\mathtt{C}})&\text{by definition of $\vDash_{{\mathfrak{R}}}$}\end{array} • Suppose A(\vec{X})=\Box A^{\prime}(\vec{X}) , and fix \vec{C} and \vec{\mathtt{C}}\geq_{\mathfrak{S}}\vec{C} . We have: \begin{array}[]{r@{\ \implies\ }ll}v:A(\vec{C})\in\Gamma_{\omega}&\forall w\in\mathsf{Wl}\,(v\mathbf{R}_{\omega}w\implies w:A^{\prime}(\vec{C})\in\Gamma_{\omega})&\text{by \lx@cref{creftype\lx@tilde refnum}{partial-val-props-classical}}\\ &\forall w\in\mathsf{Wl}\,(v\mathbf{R}_{\omega}w\implies w\vDash_{{\mathfrak{R}}}A^{\prime}(\vec{\mathtt{C}}))&\text{by IH}\\ &v\vDash_{{\mathfrak{R}}}A(\vec{\mathtt{C}})&\text{by definition of $\vDash_{{\mathfrak{R}}}$}\\ \vskip 3.0pt plus 1.0pt minus 1.0pt\cr v:A(\vec{C})\in\Delta_{\omega}&\exists w\in\mathsf{Wl}\,(v\mathbf{R}_{\omega}w\text{ and }w:A^{\prime}(\vec{C})\in\Delta_{\omega})&\text{by \lx@cref{creftype\lx@tilde refnum}{partial-val-props-classical}}\\ &\exists w\in\mathsf{Wl}\,(v\mathbf{R}_{\omega}w\text{ and }w\not\vDash_{{\mathfrak{R}}}A^{\prime}(\vec{\mathtt{C}}))&\text{by IH}\\ &v\not\vDash_{{\mathfrak{R}}}A(\vec{\mathtt{C}})&\text{by definition of $\vDash_{{\mathfrak{R}}}$}\end{array} • The case when A(\vec{X})=\Boxblack A^{\prime}(\vec{X}) is similar to the one above. • Suppose A(\vec{X})=\forall XA^{\prime}(X,\vec{X}) , and fix \vec{C} and \vec{\mathtt{C}}\geq_{\mathfrak{S}}\vec{C} . We have: \begin{array}[]{r@{\ \implies\ }ll}v:A(\vec{C})\in\Gamma_{\omega}&\forall C\in\mathsf{Fm}\,v:A^{\prime}(C,\vec{C})\in\Gamma_{\omega}&\text{by \lx@cref{creftype\lx@tilde refnum}{partial-val-props-classical}}\\ &\forall C\in\mathsf{Fm}\,\forall\mathtt{C}\geq_{\mathfrak{S}}C\,v\vDash_{{\mathfrak{R}}}A^{\prime}(\mathtt{C},\vec{\mathtt{C}})&\text{by IH}\\ &v\vDash_{{\mathfrak{R}}}A(\vec{\mathtt{C}})&\text{by definition of $\vDash_{{\mathfrak{R}}}$}\\ \vskip 3.0pt plus 1.0pt minus 1.0pt\cr v:A(\vec{C})\in\Delta_{\omega}&\exists C\in\mathsf{Fm}\,v:A^{\prime}(C,\vec{C})\in\Delta_{\omega}&\text{by \lx@cref{creftype\lx@tilde refnum}{partial-val-props-classical}}\\ &\exists C\in\mathsf{Fm}\,v\not\vDash_{{\mathfrak{R}}}A^{\prime}(\lfloor{C}\rfloor,\vec{\mathtt{C}})&\text{by IH}\\ &v\not\vDash_{{\mathfrak{R}}}A(\vec{\mathtt{C}})&\text{by definition of $\vDash_{{\mathfrak{R}}}$}\qed\end{array} 5.6. Putting it all together: comprehensivity via a total valuation In light of Proposition 5.11 , for our completeness result it remains to show that {\mathfrak{R}} is comprehensive. Since {\mathfrak{R}} is already defined, we can do this in a somewhat backwards way: Definition 5.12 (Interpreting comprehension) . Define [C]:=\{v\in\mathsf{Wl}\,|\,v\vDash_{{\mathfrak{R}}}C\} . Now, Lemma 5.10 has another useful consequence: Proposition 5.13 . [C] is a possible extension of C , for all formulas C . Proof. Simply set A(\vec{X})=C and \vec{C}=\varnothing=\vec{X} in Lemma 5.10 . ∎ Corollary 5.14 . {\mathfrak{R}} is comprehensive, and so is a relational model. In the terminology of Schütte, [-] corresponds to a total valuation of formulas [ 61 , Definition 7.2] . Note the crucial use of impredicativity here: we are only able to define [C] in terms of a structure, {\mathfrak{R}} , that includes all possible extensions, including [C] itself. We have now established the main result of this section: Proof of Theorem 5.1 . By contraposition. Set \mathcal{S}_{0}:=\cdot\,|\,\cdot\Rightarrow v:A throughout this section and conclude by Corollaries 5.14 and 5.11 . ∎ 6. Completeness via proof search: the intuitionistic case We now turn to the intuitionistic case for cut-free completeness. As we have presented the classical case in detail, we shall focus in this section on how the intuitionistic case deviates from the classical one. Let us summarise the key points: • Not all rules of \ell\mathsf{IK}\mathsf{t}2 or \mathsf{m}\ell\mathsf{IK}\mathsf{t}2 can be made invertible. For the former this is because we lack right structural rules and so, e.g., \to_{l} is not invertible. For the latter this is because the right logical rules are not invertible. • As a result, instead of a proof search branch, we will construct a proof search tree . This is unsurprising given the shape of intuitionistic structures, which are partially ordered. • We will need to deal with limit sequents at each branching point of the countermodel construction, so our proof system must now work with genuinely infinite sequents . The obtention of an appropriate proof search tree from which we can extract countermodels is facilitated by working directly with the calculus \mathsf{m}\ell\mathsf{IK}\mathsf{t}2 , instead of \ell\mathsf{IK}\mathsf{t}2 . Cut-free completeness results for multi-succedent calculi have also appeared in [ 73 , pp. 52-59] for first-order intuitionistic predicate logic over Kripke models, and in [ 56 ] for second-order intuitionistic predicate logic over Beth models. Note that, in our setting we furthermore recover cut-free completeness of the single-succedent calculus \ell\mathsf{IK}\mathsf{t}2 thanks to Proposition 4.5 , even over all birelational models thanks to Proposition 3.11 . In summary, the main results of this section are: Theorem 6.1 (Intuitionistic cut-free completeness) . \forall\mathfrak{P}\,\vDash_{\mathfrak{P}}A\implies\mathsf{m}\ell\mathsf{IK}\mathsf{t}2~\setminus~\mathsf{cut}~\vdash~A . Corollary 6.2 . \forall\mathfrak{B}\,\vDash_{\mathfrak{B}}A\implies\ell\mathsf{IK}\mathsf{t}2~\setminus~\mathsf{cut}~\vdash~A . The remainder of this section is structured as the previous one. 6.1. Setting up proof search We now construe \mathsf{m}\ell\mathsf{IK}\mathsf{t}2 over (possibly) infinite sequents \mathbf{R}\,|\,\Gamma\Rightarrow\Delta , where some/all of \mathbf{R},\Gamma,\Delta may be (countably) infinite. We say that such a sequent is provable in, or a theorem of, \mathsf{m}\ell\mathsf{IK}\mathsf{t}2 if there are finite \mathbf{R}^{\prime}\subseteq\mathbf{R} , \Gamma^{\prime}\subseteq\Gamma and \Delta^{\prime}\subseteq\Delta such that \mathbf{R}^{\prime}\,|\,\Gamma^{\prime}\Rightarrow\Delta^{\prime} is provable in \mathsf{m}\ell\mathsf{IK}\mathsf{t}2 , in the usual sense. Note that infinitude of sequents does not affect the fact that inference steps on them are still determined by activity of finite data, cf. 5.2 . All the discussion of Section 5.1 still applies when building proofs of \mathsf{m}\ell\mathsf{IK}\mathsf{t}2 , however we shall consider only the left macro rules of Eq. 9 , as the right ones are not derivable in \mathsf{m}\ell\mathsf{IK}\mathsf{t}2 . We thus restrict our enumeration of activities from 5.2 to ones with left principal formulas. Our proof search algorithm will now alternate between two phases: the LHS phase , applying left rules, and the RHS phase , applying right rules. We will again recast proof search as a countermodel construction, building a predicate structure where the LHS phase determines interpretations within an intuitionistic world and the RHS phase determines a tree structure inducing the corresponding partial order. A bit more formally, the LHS phase initiates at some (possibly infinite) sequent \mathcal{S}_{0} unprovable in \mathsf{m}\ell\mathsf{IK}\mathsf{t}2 and is defined just like the proof search branch in Definition 5.4 , producing a branch (\mathcal{S}_{i})_{i<\omega} of unprovable sequents. That is, at the i th stage it applies the step with activity \alpha_{i} and conclusion \mathcal{S}_{i} (if it exists), setting \mathcal{S}_{i+1} to be some unprovable premiss (or \mathcal{S}_{i} , respectively). Just like in Section 5.2 this phase is monotone: i\leq j\implies\mathcal{S}_{i}\subseteq\mathcal{S}_{j} . Thus the steps applied are also invertible, by weakening. Writing again \mathcal{S}_{\omega}=\bigcup\limits_{i<\omega}\mathcal{S}_{i} , note that, if \mathcal{S}_{\omega} were provable then so also would be \mathcal{S}_{i} for some i<\omega , by definition of provability of infinite sequents, so we have: Observation 6.3 . If \mathsf{m}\ell\mathsf{IK}\mathsf{t}2\not\vdash\mathcal{S}_{0} and \mathcal{S}_{\omega} is the limit of the LHS phase from \mathcal{S}_{0} , then also \mathsf{m}\ell\mathsf{IK}\mathsf{t}2\not\vdash\mathcal{S}_{\omega} . The RHS phase initiates at a (possibly infinite) sequent \mathcal{S}=\mathbf{R}\,|\,\Gamma\Rightarrow\Delta unprovable in \mathsf{m}\ell\mathsf{IK}\mathsf{t}2 and simply applies, bottom-up, a single right logical step of \mathsf{m}\ell\mathsf{IK}\mathsf{t}2 . Such a step is determined by the choice of a principal formula in \Delta (up to renaming of fresh symbols). Again, the (only) premiss must remain unprovable. Note that, by inspection of the right logical steps, the RHS phase always ends at a sequent \mathcal{S}^{\prime}=\mathbf{R}^{\prime}\,|\,\Gamma^{\prime}\Rightarrow\Delta^{\prime} where \Delta^{\prime} is a singleton . Note that the RHS phase is not monotone for the RHS, but remains monotone for the LHS, i.e. we still have \mathbf{R}^{\prime}\supseteq\mathbf{R} and \Gamma^{\prime}\supseteq\Gamma but not, in general, \Delta^{\prime}\supseteq\Delta . Thus it is not, in general, invertible. 6.2. The proof search tree As already mentioned, branching in our proof search tree will occur in the RHS phase. Since the RHS phase is determined by a choice of principal labelled formula in the RHS, we shall name the nodes of our tree structure accordingly. Write \sigma,\tau, etc. to vary over \ell\mathsf{Fm}^{<\omega} . We shall write :: for concatenation of finite sequences. Write \sqsubseteq for the prefix order on \ell\mathsf{Fm}^{<\omega} , i.e. \sigma\sqsubseteq\tau if \tau can be written as \sigma::\sigma^{\prime} . Of course, \sqsubseteq is indeed a partial order. For the remainder of this section we fix a (possibly infinite) sequent \mathcal{S}^{\varepsilon}_{0}=\mathbf{R}^{\varepsilon}_{0}\,|\,\Gamma^{\varepsilon}_{0}\Rightarrow\Delta^{\varepsilon}_{0} that is unprovable in \mathsf{m}\ell\mathsf{IK}\mathsf{t}2 . Definition 6.4 (Proof search tree) . The proof search tree \mathfrak{S} consists of a tree T\subseteq\ell\mathsf{Fm}^{<\omega} and sequents \{\mathcal{S}^{\sigma}_{i}=\mathbf{R}^{\sigma}\,|\,\Gamma^{\sigma}_{i}\Rightarrow\Delta^{\sigma}_{i}\}_{\sigma\in T,i<\omega} defined as follows: • For any sequent \mathcal{S}^{\sigma}_{0} , apply the LHS phase to construct a chain \mathcal{S}^{\sigma}_{0}\subseteq\mathcal{S}^{\sigma}_{1}\subseteq\cdots of unprovable sequents. Define \mathcal{S}^{\sigma}=\mathbf{R}^{\sigma}\,|\,\Gamma^{\sigma}\Rightarrow\Delta^{\sigma} to be the limit \mathcal{S}^{\sigma}_{\omega} of this chain (which again must be unprovable, cf. 6.3 ). • For each formula v:A\in\Delta^{\sigma} , \sigma has a child \sigma::(v:A) in T . We set \mathcal{S}^{\sigma::(w:A)}_{0} to be the (unique) premisse of the (unique, up to renaming of fresh symbols) inference step with conclusion \mathcal{S}^{\sigma} and principal formula v:A . Once again, since \mathfrak{S} has been constructed to include only unprovable sequents, like Proposition 5.5 in the classical case we importantly have: Proposition 6.5 . \Gamma^{\sigma}\cap\Delta^{\sigma}=\varnothing , for all \sigma\in T . 6.3. Towards a countermodel: a pre-structure from proof search Just like in Section 5.3 , the proof search tree \mathfrak{S} we constructed gives rise to a ‘pre-structure’, i.e. a predicate structure lacking a domain of sets (and thus also an interpretation of propositional symbols): Definition 6.6 (Pre-structure) . We define the predicate structure \mathfrak{P}^{-} by: • The set of intuitionistic worlds is just T\subseteq\ell\mathsf{Fm}^{<\omega} . • The partial order is just the restriction of \sqsubseteq to T . • The set of modal worlds is just \mathsf{Wl} . • The accessibility relation at \sigma\in T is just \mathbf{R}^{\sigma} , i.e. v\mathbf{R}^{\sigma}w if vRw\in\mathbf{R}^{\sigma} . Note that \sigma\sqsubseteq\tau\implies\mathbf{R}^{\sigma}\subseteq\mathbf{R}^{\tau} , by monotonicity in the LHS and RHS phases. 6.4. Extracting a partial valuation This part of the argument is similar to the classical case, in Section 5.4 , instead establishing bespoke local properties compatible with our predicate semantics: Proposition 6.7 (Partial valuation) . We have the following: (1) v:A\to B\in\Gamma^{\sigma}\implies\forall\tau\sqsupseteq\sigma\,(v:A\in\Delta^{\tau}\text{ or }v:B\in\Gamma^{\tau}) (2) v:A\to B\in\Delta^{\sigma}\implies\exists\tau\sqsupseteq\sigma\,(v:A\in\Gamma^{\tau}\text{ and }v:B\in\Delta^{\tau}) (3) v:\Box A\in\Gamma^{\sigma}\implies\forall\tau\sqsubseteq\sigma\,\forall w\in\mathsf{Wl}\,(v\mathbf{R}^{\tau}w\implies w:A\in\Gamma^{\tau}) (4) v:\Box A\in\Delta^{\sigma}\implies\exists\tau\sqsupseteq\sigma\,\exists w\in\mathsf{Wl}\,(v\mathbf{R}^{\tau}w\text{ and }w:A\in\Delta^{\tau}) (5) v:\Boxblack A\in\Gamma^{\sigma}\implies\forall\tau\sqsupseteq\sigma\,\forall u\in\mathsf{Wl}\,(u\mathbf{R}^{\tau}v\implies u:A\in\Gamma^{\tau}) (6) v:\Boxblack A\in\Delta^{\sigma}\implies\exists\tau\sqsupseteq\sigma\,\exists u\in\mathsf{Wl}\,(u\mathbf{R}^{\tau}v\text{ and }u:A\in\Delta^{\tau}) (7) v:\forall XA\in\Gamma^{\sigma}\implies\forall\tau\sqsupseteq\sigma\,\forall C\in\mathsf{Fm}\ v:A[C/X]\in\Gamma^{\tau} (8) v:\forall XA\in\Delta^{\sigma}\implies\exists\tau\sqsupseteq\sigma\,\exists C\in\mathsf{Fm}\ v:A[C/X]\in\Delta^{\tau} Proof. We consider each case separately: (1) Let \tau\sqsupseteq\sigma . By monotonicity we have v:A\to B\in\Gamma^{\tau} , and so either v:A\in\Delta^{\tau} or v:B\in\Gamma^{\tau} , depending on which direction \Gamma^{\sigma} takes at the corresponding \to_{l} step. (2) If v:A\to B\in\Delta^{\sigma} then we can just set \tau=\sigma::(v:A\to B) . (3) Let \tau\sqsupseteq\sigma and v\mathbf{R}^{\tau}w . By monotonicity we have v:\Box A\in\Gamma^{\tau} , and so also w:A\in\Gamma^{\tau} by the corresponding \Box_{l} step. (4) If v:\Box A\in\Delta^{\sigma} , we can just set \tau=\sigma::(v:\Box A) and w the fresh world variable of the corresponding \Box_{r} step. (5) (Similar to (3)). (6) (Similar to (4)). (7) Let \tau\sqsupseteq\sigma and C\in\mathsf{Fm} . By monotonicity we have v:\forall XA\in\Gamma^{\tau} , and so also v:A[C/X]\in\Gamma^{\tau} by the corresponding \forall_{l} step. (8) If v:\forall XA\in\Delta^{\sigma} , we can just set \tau=\sigma::(v:\forall XA) and C the propositional eigenvariable of the corresponding \forall_{r} step. ∎ 6.5. A compatible countermodel via possible values We continue to adapt the machinery of Section 5 to the intuitionistic setting. Recall that we have already fixed an unprovable sequent \mathcal{S}^{\varepsilon}_{0} and extended it to the proof search tree \mathfrak{S} , cf. Definition 6.4 , in particular including the limit sequents (\mathcal{S}^{\sigma})_{\sigma\in T} . We duly adapt Definition 5.8 to the intuitionistic setting: Definition 6.8 (Possible extensions) . A possible extension of a formula C (wrt \mathfrak{S} ) is a family \mathtt{C}=\{\mathtt{C}^{\sigma}\subseteq\mathsf{Wl}\}_{\sigma\in T} such that: • \sigma\sqsubseteq\tau\implies\mathtt{C}^{\sigma}\subseteq\mathtt{C}^{\tau} ; and, • v:C\in\Gamma^{\sigma}\implies v\in\mathtt{C}^{\sigma} ; and, • v:C\in\Delta^{\sigma}\implies v\notin\mathtt{C}^{\sigma} . Let us write \mathtt{C}\geq_{\mathfrak{S}}C if \mathtt{C} is a possible extension of C , wrt \mathfrak{S} . Note that every formula C still admits a minimal (possible) extension \lfloor{C}\rfloor with \lfloor{C}\rfloor^{\sigma}:=\{v\in\mathsf{Wl}\ |\ v:C\in\Gamma^{\sigma}\} . Note that monoticity wrt \sqsubseteq is inherited from monotonicity of LHSs during proof search: if \sigma\sqsubseteq\tau then \Gamma^{\sigma}\subseteq\Gamma^{\tau} , and so \lfloor{C}\rfloor^{\sigma}\subseteq\lfloor{C}\rfloor^{\tau} , for any formula C . Again we obtain a predicate structure whose sets include all possible extensions: Definition 6.9 (Countermodel) . We expand \mathfrak{P}^{-} into a structure \mathfrak{P} by including the following missing data: • The class \mathcal{W} of modal predicates include all possible extensions all formulas. For each extension \mathtt{C} , the interpretation \mathtt{C}^{\sigma} is as defined in Definition 6.8 . • We identify each P\in\mathsf{Pr} with the possible extension \lfloor{P}\rfloor . Once again, we need a key compatibility result: Lemma 6.10 (Compatibility) . For formulas A(\vec{X}) and \vec{C} we have: (1) v:A(\vec{C})\in\Gamma^{\sigma}\implies\sigma,v\vDash_{\mathfrak{P}}A(\vec{\mathtt{C}}) whenever \vec{\mathtt{C}}\geq_{\mathfrak{S}}\vec{C} . (2) v:A(\vec{C})\in\Delta^{\sigma}\implies\sigma,v\not\vDash_{\mathfrak{P}}A(\vec{\mathtt{C}}) whenever \vec{\mathtt{C}}\geq_{\mathfrak{S}}\vec{C} . Once again, before proving this, let us point out an immediate consequence. Write \sigma\vDash_{\mathfrak{P}}\mathbf{R}\,|\,\Gamma\Rightarrow\Delta if \mathbf{R}\subseteq\mathbf{R}^{\sigma} and, for each v:A\in\Gamma (or v:A\in\Delta ) we have \sigma,v\vDash_{\mathfrak{P}}A (or \sigma,v\not\vDash_{\mathfrak{P}}A , respectively). As a special case of the Lemma 6.10 above we have: Proposition 6.11 . \varepsilon\not\vDash_{\mathfrak{P}}\mathcal{S}^{\varepsilon}_{0} . Proof of Lemma 6.10 . By induction on A(\vec{X}) : • Suppose A(\vec{X})=X , and fix C and \mathtt{C}\geq_{\mathfrak{S}}C . We have: \begin{array}[]{r@{\ \implies\ }ll}v:C\in\Gamma^{\sigma}&v\in\mathtt{C}^{\sigma}&\text{since $\mathtt{C}\geq_{\mathfrak{S}}C$}\\ &\sigma,v\vDash_{\mathfrak{P}}\mathtt{C}&\text{by definition of $\vDash_{\mathfrak{P}}$}\\ \vskip 6.0pt plus 2.0pt minus 2.0pt\cr v:C\in\Delta^{\sigma}&v\notin\mathtt{C}^{\sigma}&\text{since $\mathtt{C}\geq_{\mathfrak{S}}C$}\\ &\sigma,v\not\vDash_{\mathfrak{P}}\mathtt{C}&\text{by definition of $\vDash_{\mathfrak{P}}$}\end{array} • Suppose A(\vec{X})=A_{0}(\vec{X})\to A_{1}(\vec{X}) , and fix \vec{C} and \vec{\mathtt{C}}\geq_{\mathfrak{S}}\vec{C} . We have: \begin{array}[]{r@{\ \implies\ }ll}v:A(\vec{C})\in\Gamma^{\sigma}&\forall\tau\sqsupseteq\sigma\left[v:A_{0}(\vec{C})\in\Delta^{\tau}\text{ or }v:A_{1}(\vec{C})\in\Gamma^{\tau}\right]&\text{by \lx@cref{creftype\lx@tilde refnum}{t-induces-partial-val}}\\ &\forall\tau\sqsupseteq\sigma\left[\tau,v\not\vDash_{\mathfrak{P}}A_{0}(\vec{\mathtt{C}})\text{ or }\tau,v\vDash_{\mathfrak{P}}A_{1}(\vec{\mathtt{C}})\right]&\text{by IH}\\ &\sigma,v\vDash_{\mathfrak{P}}A(\vec{\mathtt{C}})&\text{by definition of $\vDash_{\mathfrak{P}}$}\\ \vskip 6.0pt plus 2.0pt minus 2.0pt\cr v:A(\vec{C})\in\Delta^{\sigma}&\exists\tau\sqsupseteq\sigma\left[v:A_{0}(\vec{C})\in\Gamma^{\tau}\text{ and }v:A_{1}(\vec{C})\in\Delta^{\tau}\right]&\text{by \lx@cref{creftype\lx@tilde refnum}{t-induces-partial-val}}\\ &\exists\tau\sqsupseteq\sigma\left[\tau,v\vDash_{\mathfrak{P}}A_{0}(\vec{\mathtt{C}})\text{ and }\tau,v\not\vDash_{\mathfrak{P}}A_{1}(\vec{\mathtt{C}})\right]&\text{by IH}\\ &\sigma,v\not\vDash_{\mathfrak{P}}A(\vec{\mathtt{C}})&\text{by definition of $\vDash_{\mathfrak{P}}$}\end{array} • Suppose A(\vec{X})=\Box A^{\prime}(\vec{X}) , and fix \vec{C} and \vec{\mathtt{C}}\geq_{\mathfrak{S}}\vec{C} . We have: \begin{array}[]{r@{\ \implies\ }ll}v:A(\vec{C})\in\Gamma^{\sigma}&\forall\tau\sqsupseteq\sigma\,\forall w\in\mathsf{Wl}\left[v\mathbf{R}^{\tau}w\implies w:A^{\prime}(\vec{C})\in\Gamma^{\tau}\right]&\text{by \lx@cref{creftype\lx@tilde refnum}{t-induces-partial-val}}\\ &\forall\tau\sqsupseteq\sigma\,\forall w\in\mathsf{Wl}\left[v\mathbf{R}^{\tau}w\implies\tau,w\vDash_{\mathfrak{P}}A^{\prime}(\vec{\mathtt{C}})\right]&\text{by IH}\\ &\sigma,v\vDash_{\mathfrak{P}}A(\vec{\mathtt{C}})&\text{by definition of $\vDash_{\mathfrak{P}}$}\\ \vskip 6.0pt plus 2.0pt minus 2.0pt\cr v:A(\vec{C})\in\Delta^{\sigma}&\exists\tau\sqsupseteq\sigma\,\exists w\in\mathsf{Wl}\left[v\mathbf{R}^{\tau}w\text{ and }w:A^{\prime}(\vec{C})\in\Delta^{\tau}\right]&\text{by \lx@cref{creftype\lx@tilde refnum}{t-induces-partial-val}}\\ &\exists\tau\sqsupseteq\sigma\,\exists w\in\mathsf{Wl}\left[v\mathbf{R}^{\tau}w\text{ and }\tau,w\not\vDash_{\mathfrak{P}}A^{\prime}(\vec{\mathtt{C}})\right]&\text{by IH}\\ &\sigma,v\not\vDash_{\mathfrak{P}}A(\vec{\mathtt{C}})&\text{by definition of $\vDash_{\mathfrak{P}}$}\end{array} • The case when A(\vec{X})=\Boxblack A^{\prime}(\vec{X}) is similar to the one above. • Suppose A(\vec{X})=\forall XA^{\prime}(X,\vec{X}) , and fix \vec{C} and \vec{\mathtt{C}}\geq_{\mathfrak{S}}\vec{C} . We have: \begin{array}[]{r@{\ \implies\ }ll}v:A(\vec{C})\in\Gamma^{\sigma}&\forall\tau\sqsupseteq\sigma\,\forall C\in\mathsf{Fm}\ v:A^{\prime}(C,\vec{C})\in\Gamma^{\tau}&\text{by \lx@cref{creftype\lx@tilde refnum}{t-induces-partial-val}}\\ &\forall\tau\sqsupseteq\sigma\,\forall C\in\mathsf{Fm}\,\forall\,\mathtt{C}\geq_{\mathfrak{S}}C\ \tau,v\vDash_{\mathfrak{P}}A^{\prime}(\mathtt{C},\vec{\mathtt{C}})&\text{by IH}\\ &\sigma,v\vDash_{\mathfrak{P}}A(\vec{\mathtt{C}})&\text{by definition of $\vDash_{\mathfrak{P}}$}\\ \vskip 6.0pt plus 2.0pt minus 2.0pt\cr v:A(\vec{C})\in\Delta^{\sigma}&\exists\tau\sqsupseteq\sigma\,\exists C\in\mathsf{Fm}\ v:A^{\prime}(C,\vec{C})\in\Delta^{\tau}&\text{by \lx@cref{creftype\lx@tilde refnum}{t-induces-partial-val}}\\ &\exists\tau\sqsupseteq\sigma\,\exists C\in\mathsf{Fm}\ \tau,v\not\vDash_{\mathfrak{P}}A^{\prime}(\lfloor{C}\rfloor,\vec{\mathtt{C}})&\text{by IH}\\ &\sigma,v\not\vDash_{\mathfrak{P}}A(\vec{\mathtt{C}})&\text{by definition of $\vDash_{\mathfrak{P}}$}\qed\end{array} 6.6. Putting it all together: comprehensivity via a total valuation Again, in light of Proposition 6.11 , for our completeness result it remains to show that \mathfrak{P} is comprehensive. We take the same impredicative approach as the classical setting. Definition 6.12 (Interpreting comprehension) . Define [C]:=\{[C]^{\sigma}\}_{\sigma\in T} where: [C]^{\sigma}:=\{v\in\mathsf{Wl}\ |\ \sigma,v\vDash_{\mathfrak{P}}C\} Now, Lemma 6.10 has another useful consequence: Proposition 6.13 . [C] is a possible extension of C , with respect to \mathfrak{S} . Proof. Simply set A(\vec{X})=C and \vec{C}=\varnothing in Lemma 6.10 . ∎ Corollary 6.14 . \mathfrak{P} is comprehensive, and so is a predicate model. We have now established the main result of this section: Proof of Theorem 6.1 . By contraposition. Set \mathcal{S}^{\varepsilon}_{0}:=\cdot\,|\,\cdot\Rightarrow v:A throughout this section and conclude by Corollaries 6.14 and 6.11 . ∎ 7. Simulating labelled proofs axiomatically The goal of this section is to establish the soundness of the labelled sequent calculi \ell\mathsf{IK}\mathsf{t}2 and \ell\mathsf{K}\mathsf{t}2 , wrt. \mathsf{IK}\mathsf{t}2 and \mathsf{K}\mathsf{t}2 respectively. To this end we show (i) each sequent can be interpreted as a formula of our syntax; and (ii) each rule can be interpreted as an admissible rule of the axiomatisation. The main result of this section is: Theorem 7.1 (Axiomatic soundness) . We have the following: (1) If \ell\mathsf{IK}\mathsf{t}2\vdash A then \mathsf{IK}\mathsf{t}2\vdash A . (2) If \ell\mathsf{K}\mathsf{t}2\vdash A then \mathsf{K}\mathsf{t}2\vdash A . 7.1. Formula interpretation A polytree is a directed acyclic graph whose underlying undirected graph is a tree. As a consequence, it is connected, i.e., there exists exactly one path of undirected edges between any pair of distinct nodes. A labelled polytree sequent is a labelled sequent {\mathbf{R}}\,|\,\Gamma\Rightarrow\Delta where {\mathbf{R}} encodes a labelled polytree and all the labels occurring in \Gamma and \Delta are connected by {\mathbf{R}} (as an undirected graph). By [ 15 , Lemma 5.2] any derivation in \ell\mathsf{K}\mathsf{t} of a labelled polytree sequent (and a fortiori of a labelled formula) contains only labelled polytree sequents, which generalises to our systems: Lemma 7.2 . Any labelled polytree sequent provable in \ell\mathsf{K}\mathsf{t}2 (or \ell\mathsf{IK}\mathsf{t}2 ) has a derivation in \ell\mathsf{K}\mathsf{t}2 (or \ell\mathsf{IK}\mathsf{t}2 respectively) that contains only labelled polytree sequents. Henceforth we will work with only labelled polytree sequents. This is used in [ 15 ] to translate labelled sequents into nested sequents , which on the other hand can readily be interpreted into the tense language [ 31 ] . We define here a direct interpretation of labelled polytree sequents into tense formulas. We write u\overset{{\mathbf{R}}}{\leftrightsquigarrow}v to indicate that u and v are connected in the underlying undirected graph encoded by {\mathbf{R}} . If uRv\in{\mathbf{R}} (or vRu\in{\mathbf{R}} ), we write {\mathbf{R}}_{u\setminus v} for the set of atoms xRy\in{\mathbf{R}} such that x is connected to u in {\mathbf{R}}\setminus\{uRv\} (or {\mathbf{R}}\setminus\{vRu\} respectively). Definition 7.3 (Left interpretation) . For a label u occuring in {\mathbf{R}} or \Gamma , the left (formula) interpretation \mathtt{lfm}^{u}({\mathbf{R}}\,|\,\Gamma) at u is given as: \underset{u:B\in\Gamma}{\bigwedge}B\wedge\underset{uRv\in{\mathbf{R}}}{\bigwedge}\Diamond\mathtt{lfm}^{v}({\mathbf{R}}_{v\setminus u}\,|\,\Gamma)\wedge\underset{vRu\in{\mathbf{R}}}{\bigwedge}\Diamondblack\mathtt{lfm}^{v}({\mathbf{R}}_{v\setminus u}\,|\,\Gamma) If {\mathbf{R}}=\varnothing or \Gamma=\varnothing this is well-defined, and we set \mathtt{lfm}^{u}(\cdot\,|\,\cdot)=\top . Note that this translation utilises the definition of \and , \top , \Diamond and \Diamondblack in terms of second-order quantifiers given in Eqs. 2 and 3 . Definition 7.4 (Right interpretation) . For a label u occurring in {\mathbf{R}} or \Delta , the right (formula) interpretation \mathtt{rfm}^{u}({\mathbf{R}}\,|\,\Delta) at u is: \underset{u:B\in\Delta}{\bigvee}B\mathbin{\vee}\underset{uRv\in{\mathbf{R}}}{\bigvee}\Box\mathtt{rfm}^{v}({\mathbf{R}}_{v\setminus u}\,|\,\Delta)\mathbin{\vee}\underset{vRu\in{\mathbf{R}}}{\bigvee}\Boxblack\mathtt{rfm}^{v}({\mathbf{R}}_{v\setminus u}\,|\,\Delta) If {\mathbf{R}}=\varnothing or \Delta=\varnothing this is well-defined, and we set \mathtt{rfm}^{u}(\cdot\,|\,\cdot)=\bot . Note that this translation utilises the definition of \mathbin{\vee} and \bot in terms of second-order quantifiers given in Eq. 2 . Definition 7.5 (Classical formula interpretation) . For a label u in {\mathbf{R}} , \Gamma or \Delta , the (classical) formula interpretation at u \mathtt{cfm}^{u}({\mathbf{R}}\,|\,\Gamma\Rightarrow\Delta) at u is given as: \mathtt{lfm}^{u}({\mathbf{R}}\,|\,\Gamma)\to\mathtt{rfm}^{u}({\mathbf{R}}\,|\,\Delta) In the intuitionistic setting, the asymmetry between the LHS and RHS of a sequent means that the formula interpretation requires a more careful analysis of the polytree structure of {\mathbf{R}} : Definition 7.6 (Intuitionistic formula interpretation) . For a label u occurring in {\mathbf{R}} or \Gamma , or for u=w , the (intuitionistic) formula interpretation \mathtt{ifm}^{u}({\mathbf{R}}\,|\,\Gamma\Rightarrow w:A) at u is defined as: • \mathtt{lfm}^{w}({\mathbf{R}}\,|\,\Gamma)\to A , if u=w . • \mathtt{lfm}^{u}({\mathbf{R}}_{u\setminus v}\,|\,\Gamma)\to\Box\mathtt{ifm}^{v}({\mathbf{R}}_{v\setminus u}\,|\,\Gamma\Rightarrow w:A) , if there exists v such that v\overset{{\mathbf{R}}\setminus\{uRv\}}{\leftrightsquigarrow}w and uRv\in{\mathbf{R}} . • \mathtt{lfm}^{u}({\mathbf{R}}_{u\setminus v}\,|\,\Gamma)\to\Boxblack\mathtt{ifm}^{v}({\mathbf{R}}_{v\setminus u}\,|\,\Gamma\Rightarrow w:A) , if there exists v such that v\overset{{\mathbf{R}}\setminus\{vRu\}}{\leftrightsquigarrow}w and vRu\in{\mathbf{R}} . If {\mathbf{R}}=\varnothing , this is only defined if u=w , e.g., \mathtt{ifm}^{w}(\cdot\,|\,\Rightarrow w:A)=A . Fact 7.7 . A property of the left interpretation: • \mathtt{lfm}^{u}({\mathbf{R}}\,|\,\Gamma,u:B)=\mathtt{lfm}^{u}({\mathbf{R}}\,|\,\Gamma)\and B • and if there is x such that uRx\in{\mathbf{R}} and x\overset{{\mathbf{R}}}{\leftrightsquigarrow}w \mathtt{lfm}^{u}({\mathbf{R}}\,|\,\Gamma,w:B)=\mathtt{lfm}^{u}({\mathbf{R}}_{u\setminus x}\,|\,\Gamma,w:B)\and\Diamond\mathtt{lfm}^{x}({\mathbf{R}}_{x\setminus u}\,|\,\Gamma,w:B) • and if there is x such that xRu\in{\mathbf{R}} and x\overset{{\mathbf{R}}}{\leftrightsquigarrow}w \mathtt{lfm}^{u}({\mathbf{R}}\,|\,\Gamma,w:B)=\mathtt{lfm}^{u}({\mathbf{R}}_{u\setminus x}\,|\,\Gamma,w:B)\and\Diamondblack\mathtt{lfm}^{x}({\mathbf{R}}_{x\setminus u}\,|\,\Gamma,w:B) Fact 7.8 . If v does not occur in {\mathbf{R}} : • \mathtt{lfm}^{u}(\mathbf{R}\,|\,\Gamma,v:A)=\mathtt{lfm}^{u}(\mathbf{R}\,|\,\Gamma) • \mathtt{ifm}^{u}(\mathbf{R}\,|\,\Gamma,v:A\Rightarrow w:C)=\mathtt{ifm}^{u}(\mathbf{R}\,|\,\Gamma\Rightarrow w:C) 7.2. Formula contexts As the formula translation changes due to the position of the succedent formula, we define two kinds of “formula contexts”. These are formulas of a certain shape with one unique atom \{\} , called the hole which can be substituted for a formula. The following kind of formula context has the shape of a left-hand-side interpretation. We call the following a conjunction context . F^{\land}\{\}::=\{\}\;|\;A\land F^{\land}\{\}\;|\;\Diamond F^{\land}\{\}\;|\;\Diamondblack F^{\land}\{\} We write F^{\land}\{A\} when substituting for the hole in F^{\land}\{\} the formula A . We also define the empty substitution F^{\land}\{\varnothing\} as F^{\land}\{\top\} . We also write F^{\land} instead of F^{\land}\{\varnothing\} . For the full formula interpretation, we define an implication context F^{\to}\{\} : F^{\to}\{\}::=\{\}\;|\;A\to F^{\to}\{\}\;|\;\Box F^{\to}\{\}\;|\;\Boxblack F^{\to}\{\} Note that we can translate between these contexts as follows: • F^{\land}\{\}=\{\} iff F^{\to}\{\}=\{\} • F^{\land}\{\}=A\land F^{\land\prime}\{\} iff F^{\to}\{\}=A\to F^{\to\prime}\{\} • F^{\land}\{\}=\Diamond F^{\land\prime}\{\} iff F^{\to}\{\}=\Box F^{\to\prime}\{\} • F^{\land}\{\}=\Diamondblack F^{\land\prime}\{\} iff F^{\to}\{\}=\Boxblack F^{\to\prime}\{\} Substitution for implication contexts F^{\to}\{A\} is defined by substituting the formula A for the hole (here, we do not need substitution for the empty context). This allows us to translate these contexts into one another which will be helpful for the rules cut and \to_{l} which swap the label of the succedent formula. Here we show that the formula interpretation of a sequent can be written in the form of contexts. Lemma 7.9 . Let u be a label in the support of \mathbf{R} . Then, there exists F such that (1) \mathtt{lfm}^{u}(\mathbf{R}\,|\,\Gamma,v:A)=F^{\and}\{A\} ; and (2) \mathtt{ifm}^{u}(\mathbf{R}\,|\,\Gamma\Rightarrow v:A)=F^{\mathbin{\to}}\{A\} . Proof. We proceed by induction on the path u\overset{R}{\leftrightsquigarrow}v For the base case we have u=v . \mathtt{lfm}^{u}(\mathbf{R}\,|\,\Gamma,u:A)=\mathtt{lfm}^{u}({\mathbf{R}}\,|\,\Gamma)\and A and \mathtt{ifm}^{u}(\mathbf{R}\,|\,\Gamma\Rightarrow u:A)=\mathtt{lfm}^{u}(\mathbf{R}\,|\,\Gamma)\mathbin{\to}A So we can set F^{\and}\{\}=\mathtt{lfm}^{u}({\mathbf{R}}\,|\,\Gamma)\and\{\} for (1), and therefore F^{\mathbin{\to}}\{\}=\mathtt{lfm}^{u}(\mathbf{R}\,|\,\Gamma)\mathbin{\to}\{\} for (2). For the inductive case there is a label x such that uRx or xRu , and x\overset{R}{\leftrightsquigarrow}v . \mathtt{lfm}^{u}(\mathbf{R}\,|\,\Gamma,v:A)=\mathtt{lfm}^{u}({\mathbf{R}}_{u\setminus x}\,|\,\Gamma)\and\Diamonddot\mathtt{lfm}^{x}({\mathbf{R}}_{x\setminus u}\,|\,\Gamma,v:A) and \mathtt{ifm}^{u}(\mathbf{R}\,|\,\Gamma\Rightarrow w:B)=\mathtt{lfm}^{u}({\mathbf{R}}_{u\setminus x}\,|\,\Gamma)\mathbin{\to}\Boxdot\mathtt{ifm}^{x}({\mathbf{R}}_{x\setminus u}\,|\,\Gamma\Rightarrow w:B) where \Diamonddot=\Diamond and \Boxdot=\Box if uRx\in{\mathbf{R}} , and \Diamonddot=\Diamondblack and \Boxdot=\Boxblack if xRu\in{\mathbf{R}} . By the inductive hypothesis there is F_{1} s.t. \mathtt{lfm}^{x}({\mathbf{R}}_{x\setminus u}\,|\,\Gamma,v:A)=F_{1}^{\and}\{A\} and \mathtt{ifm}^{x}({\mathbf{R}}_{x\setminus u}\,|\,\Gamma\Rightarrow v:A)=F_{1}^{\mathbin{\to}}\{A\} So we can set F^{\and}\{\}=\mathtt{lfm}^{u}({\mathbf{R}}_{u\setminus x}\,|\,\Gamma)\and\Diamonddot F_{1}^{\and}\{\} for (1), and therefore F^{\mathbin{\to}}\{\}=\mathtt{lfm}^{u}({\mathbf{R}}_{u\setminus x}\,|\,\Gamma)\mathbin{\to}\Boxdot F_{1}^{\mathbin{\to}}\{\} for (2). ∎ Lemma 7.10 . Given a sequent \mathbf{R}\,|\,\Gamma,v:A\Rightarrow w:B , with label u in the support of \mathbf{R} . Then, there exist F_{1},F_{2},F_{3} such that (1) \mathtt{ifm}^{u}(\mathbf{R}\,|\,\Gamma,v:A\Rightarrow w:B)=F_{1}^{\mathbin{\to}}\{F_{2}^{\and}\{A\}\mathbin{\to}F_{3}^{\mathbin{\to}}\{B\}\} ; and (2) \mathsf{IK}\mathsf{t}2\vdash\mathtt{ifm}^{u}(\mathbf{R}\,|\,\Gamma,w:B\Rightarrow v:A)\leftrightarrow F_{1}^{\mathbin{\to}}\{F_{3}^{\and}\{B\}\mathbin{\to}F_{2}^{\mathbin{\to}}\{A\}\} . Proof. Proof of (1): We proceed by induction on the path u\overset{{\mathbf{R}}}{\leftrightsquigarrow}w . • u=w : \mathtt{ifm}^{w}(\mathbf{R}\,|\,\Gamma,v:A\Rightarrow w:B)=\mathtt{lfm}^{w}(\mathbf{R}\,|\,\Gamma,v:A)\mathbin{\to}B Using Lemma 7.9 (1), there is F_{2} s.t. \mathtt{lfm}^{u}(\mathbf{R}\,|\,\Gamma,v:A)=F_{2}^{\and}\{A\} . So, \mathtt{ifm}^{w}(\mathbf{R}\,|\,\Gamma,v:A\Rightarrow w:B)=F_{2}^{\and}\{A\}\mathbin{\to}B • there is a label x such that uRx or xRu\in{\mathbf{R}} and x\overset{{\mathbf{R}}}{\leftrightsquigarrow}w : then, there are two possible cases: – v\in{\mathbf{R}}_{u\setminus x} : then, by 7.8 \mathtt{ifm}^{u}(\mathbf{R}\,|\,\Gamma,v:A\Rightarrow w:B)\\ =\mathtt{lfm}^{u}({\mathbf{R}}_{u\setminus x}\,|\,\Gamma,v:A)\mathbin{\to}\Boxdot\mathtt{ifm}^{x}({\mathbf{R}}_{x\setminus u}\,|\,\Gamma\Rightarrow w:B) where \Boxdot=\Box if uRx\in{\mathbf{R}} and \Boxdot=\Boxblack if xRu\in{\mathbf{R}} . Using Lemma 7.9 (1), there is F_{2} s.t. \mathtt{lfm}^{u}({\mathbf{R}}_{u\setminus x}\,|\,\Gamma,v:A)=F_{2}^{\and}\{A\} . Using Lemma 7.9 (2), there is F^{\prime}_{3} s.t. \mathtt{ifm}^{w_{1}}({\mathbf{R}}_{x\setminus u}\,|\,\Gamma\Rightarrow w:B)={F^{\prime}}_{3}^{\mathbin{\to}}\{B\} . Set F_{3}^{\mathbin{\to}}\{\ \}=\Boxdot{F^{\prime}}_{3}^{\mathbin{\to}}\{\ \} and we get \mathtt{ifm}^{u}(\mathbf{R}\,|\,\Gamma,v:A\Rightarrow w:B)=F_{2}^{\and}\{A\}\mathbin{\to}F_{3}^{\mathbin{\to}}\{B\} – v\in{\mathbf{R}}_{x\setminus u} : then, by 7.8 \mathtt{ifm}^{u}(\mathbf{R}\,|\,\Gamma,v:A\Rightarrow w:B)\\ =\mathtt{lfm}^{u}({\mathbf{R}}_{u\setminus x}\,|\,\Gamma)\mathbin{\to}\Boxdot\mathtt{ifm}^{x}({\mathbf{R}}_{x\setminus u}\,|\,\Gamma,v:A\Rightarrow w:B) where \Boxdot=\Box if uRx\in{\mathbf{R}} and \Boxdot=\Boxblack if xRu\in{\mathbf{R}} . By the inductive hypothesis, there exist F_{1}^{\prime},F_{2},F_{3} s.t. \mathtt{ifm}^{x}({\mathbf{R}}_{x\setminus u}\,|\,\Gamma,v:A\Rightarrow w:B)=F_{1}^{\prime\mathbin{\to}}\{F_{2}^{\and}\{A\}\mathbin{\to}F_{3}^{\mathbin{\to}}\{B\}\} Set F_{1}^{\mathbin{\to}}\{\ \}=\mathtt{lfm}^{u}({\mathbf{R}}_{u\setminus x}\,|\,\Gamma)\mathbin{\to}\Boxdot F_{1}^{\prime\mathbin{\to}}\{\ \} and we get \mathtt{ifm}^{u}({\mathbf{R}}\,|\,\Gamma,v:A\Rightarrow w:B)=F_{1}^{\mathbin{\to}}\{F_{2}^{\and}\{A\}\mathbin{\to}F_{3}^{\mathbin{\to}}\{B\}\} Proof of (2): We proceed by induction on the path u\overset{{\mathbf{R}}}{\leftrightsquigarrow}w . • u=w : – either u=v : \displaystyle\mathtt{ifm}^{u}(\mathbf{R}\,|\,\Gamma,u:A\Rightarrow u:B) \displaystyle=\mathtt{lfm}^{u}({\mathbf{R}}\,|\,\Gamma,u:A)\mathbin{\to}B \displaystyle=(\mathtt{lfm}^{u}({\mathbf{R}}\,|\,\Gamma)\and A)\mathbin{\to}B \displaystyle\mathtt{ifm}^{u}({\mathbf{R}}\,|\,\Gamma,u:B\Rightarrow u:A) \displaystyle=\mathtt{lfm}^{u}({\mathbf{R}}\,|\,\Gamma,u:B)\mathbin{\to}A \displaystyle=(B\and\mathtt{lfm}^{u}({\mathbf{R}}\,|\,\Gamma))\mathbin{\to}A \displaystyle\leftrightarrow B\mathbin{\to}\mathtt{lfm}^{u}({\mathbf{R}}\,|\,\Gamma)\mathbin{\to}A – or there is a label y such that uRy or yRu , and y\overset{{\mathbf{R}}}{\leftrightsquigarrow}v \mathtt{ifm}^{u}(\mathbf{R}\,|\,\Gamma,v:A\Rightarrow u:B)=\mathtt{lfm}^{u}({\mathbf{R}}_{u\setminus x}\,|\,\Gamma,v:A)\mathbin{\to}B\\ =(\mathtt{lfm}^{u}({\mathbf{R}}_{u\setminus x\setminus y}\,|\,\Gamma)\and\mathord{\scalebox{.9}{\raise 0.43057pt\hbox{$\diamondtimes$}}}\mathtt{lfm}^{y}({\mathbf{R}}_{y\setminus u}\,|\,\Gamma,v:A))\mathbin{\to}B \mathtt{ifm}^{u}({\mathbf{R}}\,|\,\Gamma,w:B\Rightarrow v:A)\\ =\mathtt{lfm}^{u}({\mathbf{R}}_{u\setminus y}\,|\,\Gamma,w:B)\mathbin{\to}\Boxplus\mathtt{ifm}^{y}({\mathbf{R}}_{y\setminus u}\,|\,\Gamma\Rightarrow v:A)\\ =(\mathtt{lfm}^{u}({\mathbf{R}}_{u\setminus x\setminus y}\,|\,\Gamma)\and B)\mathbin{\to}\Boxplus\mathtt{ifm}^{y}({\mathbf{R}}_{y\setminus u}\,|\,\Gamma\Rightarrow v:A)\\ \leftrightarrow B\mathbin{\to}\mathtt{lfm}^{u}({\mathbf{R}}_{u\setminus x\setminus y}\,|\,\Gamma)\mathbin{\to}\Boxplus\mathtt{ifm}^{y}({\mathbf{R}}_{y\setminus u}\,|\,\Gamma\Rightarrow v:A) where \Boxplus=\Box if uRy\in{\mathbf{R}} and \Boxplus=\Boxblack if yRu\in{\mathbf{R}} . • there is a label x such that uRx or xRu\in{\mathbf{R}} and x\overset{{\mathbf{R}}}{\leftrightsquigarrow}w and v\in{\mathbf{R}}_{u\setminus x} : – either u=v : \mathtt{ifm}^{v}(\mathbf{R}\,|\,\Gamma,v:A\Rightarrow w:B)\\ =\mathtt{lfm}^{v}({\mathbf{R}}_{v\setminus x}\,|\,\Gamma,v:A)\mathbin{\to}\Boxdot\mathtt{ifm}^{x}({\mathbf{R}}_{x\setminus v}\,|\,\Gamma\Rightarrow w:B)\\ =(\mathtt{lfm}^{v}({\mathbf{R}}_{v\setminus x}\,|\,\Gamma)\and A)\mathbin{\to}\Boxdot\mathtt{ifm}^{x}({\mathbf{R}}_{x\setminus v}\,|\,\Gamma\Rightarrow w:B) \mathtt{ifm}^{v}({\mathbf{R}}\,|\,\Gamma,w:B\Rightarrow v:A)\\ =\mathtt{lfm}^{v}({\mathbf{R}}\,|\,\Gamma,w:B)\mathbin{\to}A\\ =(\Diamonddot\mathtt{lfm}^{x}({\mathbf{R}}_{x\setminus v}\,|\,\Gamma,w:B)\and\mathtt{lfm}^{v}({\mathbf{R}}_{v\setminus x}\,|\,\Gamma))\mathbin{\to}A\\ \leftrightarrow\Diamonddot\mathtt{lfm}^{x}({\mathbf{R}}_{x\setminus v}\,|\,\Gamma,w:B)\mathbin{\to}\mathtt{lfm}^{v}({\mathbf{R}}_{v\setminus x}\,|\,\Gamma)\mathbin{\to}A – or there is a label y such that uRy or yRu , and y\overset{{\mathbf{R}}}{\leftrightsquigarrow}v \mathtt{ifm}^{u}(\mathbf{R}\,|\,\Gamma,v:A\Rightarrow w:B)\\ =\mathtt{lfm}^{u}({\mathbf{R}}_{u\setminus x}\,|\,\Gamma,v:A)\mathbin{\to}\Boxdot\mathtt{ifm}^{x}({\mathbf{R}}_{x\setminus u}\,|\,\Gamma\Rightarrow w:B)\\ =(\mathtt{lfm}^{u}({\mathbf{R}}_{u\setminus x\setminus y}\,|\,\Gamma)\and\mathord{\scalebox{.9}{\raise 0.43057pt\hbox{$\diamondtimes$}}}\mathtt{lfm}^{y}({\mathbf{R}}_{y\setminus u}\,|\,\Gamma,v:A))\\ \mathbin{\to}\Boxdot\mathtt{ifm}^{x}({\mathbf{R}}_{x\setminus u}\,|\,\Gamma\Rightarrow w:B) \mathtt{ifm}^{u}({\mathbf{R}}\,|\,\Gamma,w:B\Rightarrow v:A)\\ =\mathtt{lfm}^{u}({\mathbf{R}}_{u\setminus y}\,|\,\Gamma,w:B)\mathbin{\to}\Boxplus\mathtt{ifm}^{y}({\mathbf{R}}_{y\setminus u}\,|\,\Gamma\Rightarrow v:A)\\ =(\mathtt{lfm}^{u}({\mathbf{R}}_{u\setminus x\setminus y}\,|\,\Gamma)\and\Diamonddot\mathtt{lfm}^{x}({\mathbf{R}}_{x\setminus u}\,|\,\Gamma,w:B))\\ \mathbin{\to}\Boxplus\mathtt{ifm}^{y}({\mathbf{R}}_{y\setminus u}\,|\,\Gamma\Rightarrow v:A)\\ \leftrightarrow\Diamonddot\mathtt{lfm}^{x}({\mathbf{R}}_{x\setminus u}\,|\,\Gamma,w:B)\\ \mathbin{\to}\mathtt{lfm}^{u}({\mathbf{R}}_{u\setminus x\setminus y}\,|\,\Gamma)\mathbin{\to}\Boxplus\mathtt{ifm}^{y}({\mathbf{R}}_{y\setminus u}\,|\,\Gamma\Rightarrow v:A) where \Boxdot=\Box if uRx\in{\mathbf{R}} and \Boxdot=\Boxblack if xRu\in{\mathbf{R}} , and where \Boxplus=\Box if uRy\in{\mathbf{R}} and \Boxplus=\Boxblack if yRu\in{\mathbf{R}} . • there is a label x such that uRx or xRu\in{\mathbf{R}} and x\overset{{\mathbf{R}}}{\leftrightsquigarrow}w and v\in{\mathbf{R}}_{x\setminus u} : \mathtt{ifm}^{u}(\mathbf{R}\,|\,\Gamma,v:A\Rightarrow w:B)\\ =\mathtt{lfm}^{u}({\mathbf{R}}_{u\setminus x}\,|\,\Gamma)\mathbin{\to}\Boxdot\mathtt{ifm}^{x}({\mathbf{R}}_{x\setminus u}\,|\,\Gamma,v:A\Rightarrow w:B)\\ =\mathtt{lfm}^{u}({\mathbf{R}}_{u\setminus x}\,|\,\Gamma)\mathbin{\to}\Boxdot F_{1}^{\prime\mathbin{\to}}\{F_{2}^{\and}\{A\}\mathbin{\to}F_{3}^{\mathbin{\to}}\{B\}\} where \Boxdot=\Box if uRx\in{\mathbf{R}} and \Boxdot=\Boxblack if xRu\in{\mathbf{R}} . By inductive hypothesis, \mathtt{ifm}^{x}({\mathbf{R}}_{x\setminus u}\,|\,\Gamma,w:B\Rightarrow v:A) is equivalent to F_{1}^{\prime\mathbin{\to}}\{F_{3}^{\and}\{B\}\mathbin{\to}F_{2}^{\mathbin{\to}}\{A\}\} , so: \mathtt{ifm}^{u}({\mathbf{R}}\,|\,\Gamma,w:B\Rightarrow v:A)\\ =\mathtt{lfm}^{u}({\mathbf{R}}_{u\setminus x}\,|\,\Gamma)\mathbin{\to}\Boxdot\mathtt{ifm}^{x}({\mathbf{R}}_{x\setminus u}\,|\,\Gamma,w:B\Rightarrow v:A)\\ \leftrightarrow\mathtt{lfm}^{u}({\mathbf{R}}_{u\setminus x}\,|\,\Gamma)\mathbin{\to}\Boxdot F_{1}^{\prime\mathbin{\to}}\{F_{3}^{\and}\{B\}\mathbin{\to}F_{2}^{\mathbin{\to}}\{A\}\} ∎ 7.3. Technical lemmas The following lemmas capture the behaviour of contexts which we need for proving the soundness of the sequent rules. Note that we can view most of these lemmas as generalisations of modal rules and axioms such as necessitation or functoriality of modalities. Lemma 7.11 . If \mathsf{IK}\mathsf{t}2\vdash A then \mathsf{IK}\mathsf{t}2\vdash F^{\mathbin{\to}}\{A\} . Proof. We proceed by induction over the structure of F^{\mathbin{\to}}\{ }. The base case F^{\mathbin{\to}}\{\}=\{\} follows immediately. If F^{\mathbin{\to}}\{A\}=B\to F_{1}^{\and}\{A\} : By inductive hypothesis, \mathsf{IK}\mathsf{t}2\vdash F_{1}^{\and}\{A\} . By \mathsf{mp} on the axiom F_{1}^{\mathbin{\to}}\{A\}\mathbin{\to}B\mathbin{\to}F_{1}^{\mathbin{\to}}\{A\} : \mathsf{IK}\mathsf{t}2\vdash B\to F_{1}^{\mathbin{\to}}\{A\} . If F^{\mathbin{\to}}\{A\}=\Box F_{1}^{\mathbin{\to}}\{A\} or \Boxblack F_{1}^{\mathbin{\to}}\{A\} : By inductive hypothesis, \mathsf{IK}\mathsf{t}2\vdash F_{1}^{\mathbin{\to}}\{A\} . By \mathsf{nec}_{\Box} or \mathsf{nec}_{\Boxblack} , \mathsf{IK}\mathsf{t}2\vdash\Box F_{1}^{\mathbin{\to}}\{A\} or \Boxblack F_{1}^{\mathbin{\to}}\{A\} respectively. ∎ Lemma 7.12 . \mathsf{IK}\mathsf{t}2\vdash F^{\mathbin{\to}}\{A\mathbin{\to}B\}\mathbin{\to}F^{\mathbin{\to}}\{A\}\mathbin{\to}F^{\mathbin{\to}}\{B\} Proof. We proceed by induction on the structure of F^{\mathbin{\to}}\{\} . The base case F^{\mathbin{\to}}\{\}=\{\} follows from the fact that (A\mathbin{\to}B)\mathbin{\to}A\mathbin{\to}B is a theorem of \mathsf{IPL} . We have 3 inductive cases: • F^{\mathbin{\to}}\{\}=C\mathbin{\to}F_{1}^{\mathbin{\to}}\{\} . By inductive hypothesis \mathsf{IK}\mathsf{t}2\vdash F_{1}^{\mathbin{\to}}\{A\mathbin{\to}B\}\mathbin{\to}F_{1}^{\mathbin{\to}}\{A\}\mathbin{\to}F_{1}^{\mathbin{\to}}\{B\} . So propositional reasoning gives \mathsf{IK}\mathsf{t}2\vdash(C\mathbin{\to}F_{1}^{\mathbin{\to}}\{A\mathbin{\to}B\})\mathbin{\to}(C\mathbin{\to}F_{1}^{\mathbin{\to}}\{A\})\mathbin{\to}(C\mathbin{\to}F_{1}^{\mathbin{\to}}\{B\}) . • F^{\mathbin{\to}}\{\}=\Box F_{1}^{\mathbin{\to}}\{\} . By the inductive hypothesis, \mathsf{IK}\mathsf{t}2\vdash F_{1}^{\mathbin{\to}}\{A\mathbin{\to}B\}\mathbin{\to}F_{1}^{\mathbin{\to}}\{A\}\mathbin{\to}F_{1}^{\mathbin{\to}}\{B\} . Apply \mathsf{nec}_{\Box} to get \mathsf{IK}\mathsf{t}2\vdash\Box(F_{1}^{\mathbin{\to}}\{A\mathbin{\to}B\}\mathbin{\to}F_{1}^{\mathbin{\to}}\{A\}\mathbin{\to}F_{1}^{\mathbin{\to}}\{B\}) . By \mathsf{D}_{\Box} and \mathsf{mp} \mathsf{IK}\mathsf{t}2\vdash\Box F_{1}^{\mathbin{\to}}\{A\mathbin{\to}B\}\mathbin{\to}\Box F_{1}^{\mathbin{\to}}\{A\}\mathbin{\to}\Box F_{1}^{\mathbin{\to}}\{B\} . • F^{\mathbin{\to}}\{\}=\Boxblack F_{1}^{\mathbin{\to}}\{\} . By the inductive hypothesis \mathsf{IK}\mathsf{t}2\vdash F_{1}^{\mathbin{\to}}\{A\mathbin{\to}B\}\mathbin{\to}F_{1}^{\mathbin{\to}}\{A\}\mathbin{\to}F_{1}^{\mathbin{\to}}\{B\} . Apply \mathsf{nec}_{\Boxblack} to get \mathsf{IK}\mathsf{t}2\vdash\Boxblack(F_{1}^{\mathbin{\to}}\{A\mathbin{\to}B\}\mathbin{\to}F_{1}^{\mathbin{\to}}\{A\}\mathbin{\to}F_{1}^{\mathbin{\to}}\{B\}) . By \mathsf{D}_{\Boxblack} and \mathsf{mp} \mathsf{IK}\mathsf{t}2\vdash\Boxblack F_{1}^{\mathbin{\to}}\{A\mathbin{\to}B\}\mathbin{\to}\Boxblack F_{1}^{\mathbin{\to}}\{A\}\mathbin{\to}\Boxblack F_{1}^{\mathbin{\to}}\{B\} . ∎ Lemma 7.13 . \mathsf{IK}\mathsf{t}2\vdash F^{\mathbin{\to}}\{A\mathbin{\to}B\}\mathbin{\to}F^{\and}\{A\}\mathbin{\to}F^{\and}\{B\} Proof. We proceed by induction on the structure of F^{\and}\{\} . The base case F^{\and}\{\}=\{\} is follows from the fact that (A\mathbin{\to}B)\mathbin{\to}A\mathbin{\to}B is a theorem of IPL. We have 3 inductive cases: • F^{\and}\{\}=C\and F_{1}^{\and}\{\} hence F^{\mathbin{\to}}\{\}=C\mathbin{\to}F_{1}^{\mathbin{\to}}\{\} . By the inductive hypothesis, \mathsf{IK}\mathsf{t}2\vdash F_{1}^{\mathbin{\to}}\{A\mathbin{\to}B\}\mathbin{\to}F_{1}^{\and}\{A\}\mathbin{\to}F_{1}^{\and}\{B\} and so propositional reasoning gives \mathsf{IK}\mathsf{t}2\vdash(C\mathbin{\to}F_{1}^{\mathbin{\to}}\{A\mathbin{\to}B\})\mathbin{\to}(C\and F_{1}^{\and}\{A\})\mathbin{\to}(C\and F_{1}^{\and}\{B\}) . • F^{\and}\{\}=\Diamond F_{1}^{\and}\{\} and F^{\mathbin{\to}}\{\}=\Box F_{1}^{\mathbin{\to}}\{\} . By the inductive hypothesis, \mathsf{IK}\mathsf{t}2\vdash F_{1}^{\mathbin{\to}}\{A\mathbin{\to}B\}\mathbin{\to}F_{1}^{\and}\{A\}\mathbin{\to}F_{1}^{\and}\{B\} . Apply \mathsf{nec}_{\Box} to get \mathsf{IK}\mathsf{t}2\vdash\Box(F_{1}^{\mathbin{\to}}\{A\mathbin{\to}B\}\mathbin{\to}F_{1}^{\and}\{A\}\mathbin{\to}F_{1}^{\and}\{B\}) . By \mathsf{D}_{\Box} , \mathsf{D}_{\Diamond} and \mathsf{mp} \mathsf{IK}\mathsf{t}2\vdash\Box F_{1}^{\mathbin{\to}}\{A\mathbin{\to}B\}\mathbin{\to}\Diamond F_{1}^{\and}\{A\}\mathbin{\to}\Diamond F_{1}^{\and}\{B\} • F^{\and}\{\}=\Diamondblack F_{1}^{\and}\{\} and F^{\mathbin{\to}}\{\}=\Boxblack F_{1}^{\mathbin{\to}}\{\} . By the inductive hypothesis, \mathsf{IK}\mathsf{t}2\vdash F_{1}^{\mathbin{\to}}\{A\mathbin{\to}B\}\mathbin{\to}F_{1}^{\and}\{A\}\mathbin{\to}F_{1}^{\and}\{B\} Apply \mathsf{nec}_{\Boxblack} to get \mathsf{IK}\mathsf{t}2\vdash\Boxblack(F_{1}^{\mathbin{\to}}\{A\mathbin{\to}B\}\mathbin{\to}F_{1}^{\and}\{A\}\mathbin{\to}F_{1}^{\and}\{B\}) . By \mathsf{D}_{\Boxblack} , \mathsf{D}_{\Diamondblack} and \mathsf{mp} \mathsf{IK}\mathsf{t}2\vdash\Boxblack F_{1}^{\mathbin{\to}}\{A\mathbin{\to}B\}\mathbin{\to}\Diamondblack F_{1}^{\and}\{A\}\mathbin{\to}\Diamondblack F_{1}^{\and}\{B\} . ∎ Lemma 7.14 . \mathsf{IK}\mathsf{t}2\vdash F^{\and}\{A\mathbin{\to}B\}\mathbin{\to}F^{\mathbin{\to}}\{A\}\mathbin{\to}F^{\and}\{B\} . Proof. We proceed by induction on the structure of F^{\and}\{\} . The base case F^{\and}\{\}=\{\} follows from the fact that (A\mathbin{\to}B)\mathbin{\to}A\mathbin{\to}B is a theorem of \mathsf{IPL} . We have 3 inductive cases: • F^{\and}\{\}=C\and F_{1}^{\and}\{\} hence F^{\mathbin{\to}}\{\}=C\mathbin{\to}F_{1}^{\mathbin{\to}}\{\} By the inductive hypothesis, \mathsf{IK}\mathsf{t}2\vdash F_{1}^{\and}\{A\mathbin{\to}B\}\mathbin{\to}F_{1}^{\mathbin{\to}}\{A\}\mathbin{\to}F_{1}^{\and}\{B\} , and so propositional reasoning gives \mathsf{IK}\mathsf{t}2\vdash(C\and F_{1}^{\and}\{A\mathbin{\to}B\})\mathbin{\to}(C\mathbin{\to}F_{1}^{\mathbin{\to}}\{A\})\mathbin{\to}(C\and F_{1}^{\mathbin{\to}}\{B\}) . • F^{\and}\{\}=\Diamond F_{1}^{\and}\{\} hence F^{\mathbin{\to}}\{\}=\Box F_{1}^{\mathbin{\to}}\{\} . By the inductive hypothesis, \mathsf{IK}\mathsf{t}2\vdash F_{1}^{\and}\{A\mathbin{\to}B\}\mathbin{\to}F_{1}^{\mathbin{\to}}\{A\}\mathbin{\to}F_{1}^{\and}\{B\} . Apply \mathsf{nec}_{\Box} to get \mathsf{IK}\mathsf{t}2\vdash\Box(F_{1}^{\and}\{A\mathbin{\to}B\}\mathbin{\to}F_{1}^{\mathbin{\to}}\{A\}\mathbin{\to}F_{1}^{\and}\{B\}) . By axioms \mathsf{D}_{\Diamond} and \mathsf{mp} , \mathsf{IK}\mathsf{t}2\vdash\Diamond F_{1}^{\and}\{A\mathbin{\to}B\}\mathbin{\to}\Diamond(F_{1}^{\mathbin{\to}}\{A\}\mathbin{\to}F_{1}^{\and}\{B\}) . With Proposition 2.11 (5), transitivity of implication gives \mathsf{IK}\mathsf{t}2\vdash\Diamond F_{1}^{\mathbin{\to}}\{A\mathbin{\to}B\}\mathbin{\to}\Box F_{1}^{\mathbin{\to}}\{A\}\mathbin{\to}\Diamond F_{1}^{\mathbin{\to}}\{B\} . • F^{\and}\{\}=\Diamondblack F_{1}^{\and}\{\} hence F^{\mathbin{\to}}\{\}=\Boxblack F_{1}^{\mathbin{\to}}\{\} By the inductive hypothesis, \mathsf{IK}\mathsf{t}2\vdash F_{1}^{\and}\{A\mathbin{\to}B\}\mathbin{\to}F_{1}^{\mathbin{\to}}\{A\}\mathbin{\to}F_{1}^{\and}\{B\} . Apply \mathsf{nec}_{\Boxblack} to get \mathsf{IK}\mathsf{t}2\vdash\Boxblack(F_{1}^{\and}\{A\mathbin{\to}B\}\mathbin{\to}F_{1}^{\mathbin{\to}}\{A\}\mathbin{\to}F_{1}^{\and}\{B\}) . By axioms \mathsf{D}_{\Diamondblack} and \mathsf{mp} , \mathsf{IK}\mathsf{t}2\vdash\Diamondblack F_{1}^{\and}\{A\mathbin{\to}B\}\mathbin{\to}\Diamondblack(F_{1}^{\mathbin{\to}}\{A\}\mathbin{\to}F_{1}^{\and}\{B\}) . With Proposition 2.11 (6), transitivity of implication gives \mathsf{IK}\mathsf{t}2\vdash\Diamondblack F_{1}^{\mathbin{\to}}\{A\mathbin{\to}B\}\mathbin{\to}\Boxblack F_{1}^{\mathbin{\to}}\{A\}\mathbin{\to}\Diamondblack F_{1}^{\mathbin{\to}}\{B\} . ∎ Lemma 7.15 . \mathsf{IK}\mathsf{t}2\vdash(F^{\and}\{A\}\mathbin{\to}F^{\mathbin{\to}}\{B\})\mathbin{\to}F^{\mathbin{\to}}\{A\mathbin{\to}B\} . Proof. We proceed by induction on the structure of F^{\and}\{\} . The base case F^{\and}\{\}=\{\} follows from the fact that (A\mathbin{\to}B)\mathbin{\to}A\mathbin{\to}B is a theorem of \mathsf{IPL} . We have 3 inductive cases: • F^{\and}\{\}=C\and F_{1}^{\and}\{\} hence F^{\mathbin{\to}}\{\}=C\mathbin{\to}F_{1}^{\mathbin{\to}}\{\} . By the inductive hypothesis \mathsf{IK}\mathsf{t}2\vdash(F_{1}^{\and}\{A\}\mathbin{\to}F_{1}^{\mathbin{\to}}\{B\})\mathbin{\to}F_{1}^{\mathbin{\to}}\{A\mathbin{\to}B\} and propositional reasoning gives \mathsf{IK}\mathsf{t}2\vdash((C\and F_{1}^{\and}\{A\})\mathbin{\to}(C\mathbin{\to}F_{1}^{\mathbin{\to}}\{B\}))\mathbin{\to}(C\mathbin{\to}F^{\mathbin{\to}}\{A\mathbin{\to}B\}) . • F^{\and}\{\}=\Diamond F_{1}^{\and}\{\} and F^{\mathbin{\to}}\{\}=\Box F_{1}^{\mathbin{\to}}\{\} . By the inductive hypothesis \mathsf{IK}\mathsf{t}2\vdash(F_{1}^{\and}\{A\}\mathbin{\to}F_{1}^{\mathbin{\to}}\{B\})\mathbin{\to}F^{\mathbin{\to}}\{A\mathbin{\to}B\} . Applying \mathsf{nec}_{\Box} , \mathsf{IK}\mathsf{t}2\vdash\Box(F_{1}^{\and}\{A\}\mathbin{\to}F_{1}^{\mathbin{\to}}\{B\}\mathbin{\to}F_{1}^{\mathbin{\to}}\{A\mathbin{\to}B\}) . Then, \mathsf{D}_{\Box} and \mathsf{mp} gives \mathsf{IK}\mathsf{t}2\vdash\Box(F_{1}^{\and}\{A\}\mathbin{\to}F_{1}^{\mathbin{\to}}\{B\})\mathbin{\to}\Box F_{1}^{\mathbin{\to}}\{A\mathbin{\to}B\} . With Proposition 2.11 (3), transitivity of implication gives \mathsf{IK}\mathsf{t}2\vdash(\Diamond F_{1}^{\and}\{A\}\mathbin{\to}\Box F_{1}^{\mathbin{\to}}\{A\})\mathbin{\to}\Box F_{1}^{\mathbin{\to}}\{A\mathbin{\to}B\} . • F^{\and}\{\}=\Diamondblack F_{1}^{\and}\{\} hence F^{\mathbin{\to}}\{\}=\Boxblack F_{1}^{\and}\{\} . By the inductive hypothesis \mathsf{IK}\mathsf{t}2\vdash(F_{1}^{\and}\{A\}\mathbin{\to}F_{1}^{\mathbin{\to}}\{B\})\mathbin{\to}F^{\mathbin{\to}}\{A\mathbin{\to}B\} . Applying \mathsf{nec}_{\Boxblack} , \mathsf{IK}\mathsf{t}2\vdash\Boxblack(F_{1}^{\and}\{A\}\mathbin{\to}F_{1}^{\mathbin{\to}}\{B\}\mathbin{\to}F_{1}^{\mathbin{\to}}\{A\mathbin{\to}B\}) . Then, \mathsf{D}_{\Boxblack} and \mathsf{mp} gives \mathsf{IK}\mathsf{t}2\vdash\Boxblack(F_{1}^{\and}\{A\}\mathbin{\to}F_{1}^{\mathbin{\to}}\{B\})\mathbin{\to}\Boxblack F_{1}^{\mathbin{\to}}\{A\mathbin{\to}B\} . With Proposition 2.11 (4), transitivity of implication gives \mathsf{IK}\mathsf{t}2\vdash(\Diamondblack F_{1}^{\and}\mathbin{\to}\Boxblack F^{\mathbin{\to}}\{A\})\mathbin{\to}\Boxblack F_{1}^{\mathbin{\to}}\{A\} . ∎ Lemma 7.16 . \mathsf{IK}\mathsf{t}2\vdash\forall XF^{\mathbin{\to}}\{A\}\to F^{\mathbin{\to}}\{\forall XA\} whenever X does not occur freely in F^{\mathbin{\to}}\{\} . Proof. We proceed by induction on F^{\mathbin{\to}}\{\} . The base case F^{\mathbin{\to}}\{\}=\{\} follows immediately. We have 3 inductive cases: • F^{\mathbin{\to}}\{\}=C\to F_{1}^{\mathbin{\to}}\{\} with X\notin\mathsf{FV}(C) : The inductive hypothesis gives us \mathsf{IK}\mathsf{t}2\vdash\forall XF_{1}^{\mathbin{\to}}\{A\}\mathbin{\to}F_{1}^{\mathbin{\to}}\{\forall XA\} , By combining \mathsf{D}_{\forall} and \mathsf{V} \mathsf{IK}\mathsf{t}2\vdash\forall X(C\to F_{1}^{\mathbin{\to}}\{A\})\to C\to\forall XF_{1}^{\mathbin{\to}}\{A\} . which by transitivity of implication gives \mathsf{IK}\mathsf{t}2\vdash\forall X(C\to F_{1}^{\mathbin{\to}}\{A\})\to C\to F_{1}^{\mathbin{\to}}\{\forall XA\} . • F^{\mathbin{\to}}\{\}=\Box F_{1}^{\mathbin{\to}}\{\} : By inductive hypothesis we have \mathsf{IK}\mathsf{t}2\vdash\forall XF_{1}^{\mathbin{\to}}\{A\}\to F_{1}^{\mathbin{\to}}\{\forall XA\} . Applying \mathsf{nec}_{\Box} and \mathsf{D}_{\Box} , we have \mathsf{IK}\mathsf{t}2\vdash\Box\forall XF_{1}^{\mathbin{\to}}\{A\}\to\Box F_{1}^{\mathbin{\to}}\{\forall XA\} . With Example 2.10 , transitivity of implication gives \mathsf{IK}\mathsf{t}2\vdash\forall X\Box F_{1}^{\mathbin{\to}}\{A\}\to\Box F_{1}^{\mathbin{\to}}\{\forall XA\} . • F^{\mathbin{\to}}\{\}=\Boxblack F_{1}^{\mathbin{\to}}\{\} : By inductive hypothesis we have \mathsf{IK}\mathsf{t}2\vdash\forall XF_{1}^{\mathbin{\to}}\{A\}\to F_{1}^{\mathbin{\to}}\{\forall XA\} . Applying \mathsf{nec}_{\Boxblack} and \mathsf{D}_{\Boxblack} , we have \mathsf{IK}\mathsf{t}2\vdash\Boxblack\forall XF_{1}^{\mathbin{\to}}\{A\}\to\Boxblack F_{1}^{\mathbin{\to}}\{\forall XA\} . With Example 2.10 (4), transitivity of implication gives \mathsf{IK}\mathsf{t}2\vdash\forall X\Boxblack F_{1}^{\mathbin{\to}}\{A\}\to\Boxblack F_{1}^{\mathbin{\to}}\{\forall XA\} . ∎ 7.4. Axiomatic soundness for \ell\mathsf{IK}\mathsf{t}2 To prove Theorem 7.1 ( 1 ), we will establish a stronger statement: Lemma 7.17 (Soundness of interpretation) . If \ell\mathsf{IK}\mathsf{t}2\vdash{\mathbf{R}}\,|\,\Gamma\Rightarrow w:A then \mathsf{IK}\mathsf{t}2\vdash\mathtt{ifm}^{u}({\mathbf{R}}\,|\,\Gamma\Rightarrow w:A) , for u occurring in \mathbf{R} or u=w . This is proved by induction on the proof of {\mathbf{R}}\,|\,\Gamma\Rightarrow w:A in \ell\mathsf{IK}\mathsf{t}2 , where both the base case and the inductive cases are provided by the following lemma. Recall that we can assume that any sequent {\mathbf{R}}\,|\,\Gamma\Rightarrow w:A occurring in a proof is polytree labelled sequents; in particular labels in \Gamma\cup\{w:A\} are connected by {\mathbf{R}} . Lemma 7.18 (Local soundness) . Let \{{\mathbf{R}}\,|\,\Gamma_{i}\Rightarrow x_{i}:A_{i}\}_{i