Sahlqvist Correspondence Theory for Sabotage Modal Logic

Zhiguang Zhao School of Mathematics and Statistics, Taishan University, Tai’an, 271000, China

Abstract

Sabotage modal logic (SML) [23] is a kind of dynamic logic. It extends static modal logic with a dynamic modality which is interpreted as “after deleting an arrow in the frame, the formula is true”. In the present paper, we are aiming at solving an open problem stated in [5], namely giving a Sahlqvist-type correspondence theorem [20] for sabotage modal logic. In this paper, we define sabotage Sahlqvist formulas and give an algorithm $\mathsf{ALBA}^{\mathsf{SML}}$ to compute the first-order correspondents of sabotage Sahlqvist formulas. We give some remarks and future directions at the end of the paper.

Keywords: Sabotage modal logic, dynamic logic, modal logic, Sahlqvist correspondence theory, algorithmic method.

Math. Subject Class. 03B45, 03B99.

1 Introduction

Sabotage modal logic (SML) [23] belongs to the class of logics collectively called dynamic logics. It extends static modal logic with a dynamic modality $\Diamondblack$ such that $\Diamondblack\varphi$ is interpreted as “after deleting an arrow in the frame, $\varphi$ is true”. There are several existing works on sabotage modal logic. In [5], a bisimulation characterization theorem as well as a tableau system were given for sabotage modal logic, [17] proved the undecidability of the satisfiability problem and gave the complexity of the model-checking problem, and [18] gave the complexity of solving sabotage game. Several similar formalisms are also investigated, such as graph modifiers logic [4], swap logic [1] and arrow update logic [15], modal logic of definable link deletion [16], modal logic of stepwise removal [24]. These logics are collectively called relation changing modal logics [2, 3]. In the present paper, we are aiming at solving an open problem stated in [5], namely giving a Sahlqvist-type correspondence theorem [20] for sabotage modal logic. We define the Sahlqvist formulas in the sabotage modal language and give the sabotage counterpart of the algorithm $\mathsf{ALBA}^{\mathsf{SML}}$ (Ackermann Lemma Based Algorithm), which is sound over Kripke frames and is successful on sabotage Sahlqvist formulas, to show that every Sahlqvist formula in the sabotage modal language has a first-order correspondent.

The structure of the paper is as follows: in Section 2, we give a brief sketch on the preliminaries of sabotage modal logic, including its syntax, semantics as well as the standard translation. In Section 3 we define sabotage Sahlqvist formulas and the algorithm $\mathsf{ALBA}^{\mathsf{SML}}$ , show its soundness over Kripke frames and its success on sabotage Sahlqvist inequalities. In Section 4 we discuss the completeness and canonicity issues and give some further directions.

2 Preliminaries on sabotage modal logic

In this section, we collect some preliminaries on sabotage modal logic. For further details, see [5].

Given a set $\mathsf{Prop}$ of propositional variables, the set of sabotage modal formulas is recursively defined as follows:

\varphi::=\bot\mid\top\mid p\mid\neg\varphi\mid(\varphi\land\varphi)\mid\Diamond\varphi\mid\Diamondblack\varphi

where $p\in\mathsf{Prop}$ , $\Diamond$ is the alethic connective of ordinary modal logic and $\Diamondblack$ is the sabotage connective of sabotage modal logic. We will follow the standard rules for omission of the parentheses. $\lor,\to,\leftrightarrow,\Box,\blacksquare$ can be defined in the standard way. We call a formula static if it does not contain $\Diamondblack$ or $\blacksquare$ . An occurence of $p$ is said to be positive (resp. negative) in $\varphi$ if $p$ is under the scope of an even (resp. odd) number of negations in the original sabotage modal language. A formula $\varphi$ is positive (resp. negative) if all occurences of propositional variables in $\varphi$ are positive (resp. negative).

For the semantics of sabotage modal logic, we use Kripke frames $\mathbb{F}=(W,R)$ and Kripke models $\mathbb{M}=(\mathbb{F},V)$ where $V:\mathsf{Prop}\to\mathcal{P}(W)$ . The satisfaction relation is defined as follows:

$(W,R,V),w\Vdash\bot$	:	never;
$(W,R,V),w\Vdash\top$	:	always;
$(W,R,V),w\Vdash p$	iff	$w\in V(p)$ ;
$(W,R,V),w\Vdash\neg\varphi$	iff	$(W,R,V),w\nVdash\varphi$ ;
$(W,R,V),w\Vdash\varphi\land\psi$	iff	$(W,R,V),w\Vdash\varphi$ and $(W,R,V),w\Vdash\psi$ ;
$(W,R,V),w\Vdash\Diamond\varphi$	iff	there exists a $v\in W$ such that $(w,v)\in R$ and $(W,R,V),v\Vdash\varphi$ ;
$(W,R,V),w\Vdash\Diamondblack\varphi$	iff	there exists an edge $(w_{0},w_{1})\in R\mbox{ s.t.\ }(W,R\setminus\{(w_{0},w_{1})\},V),w\Vdash\varphi.$

Intuitively, $\Diamondblack\varphi$ is true at $w$ iff there is an edge $(w_{0},w_{1})$ of $R$ such that after deleting this edge from $R$ , the formula $\varphi$ is still true at $w$ . It is easy to see that the semantic clause for $\blacksquare$ is defined as follows:

(W,R,V),w\Vdash\blacksquare\varphi\mbox{ iff for all edges }(w_{0},w_{1})\in R,(W,R\setminus\{(w_{0},w_{1})\},V),w\Vdash\varphi.

The standard translation of sabotage modal language into first-order logic is given as follows (notice that we need to record the edges already deleted from $R$ so that we know what edges could still be deleted):

Definition 1.

([5, Definition 1]) Let $E$ be a set of pairs $(y,z)$ of variables standing for edges and let $x$ be a designated variable. The translation $ST^{E}_{x}$ is recursively defined as follows:

•

$ST^{E}_{x}(p):=Px$ ;
•

$ST^{E}_{x}(\bot):=x\neq x$ ;
•

$ST^{E}_{x}(\neg\varphi):=\neg ST^{E}_{x}(\varphi)$ ;
•

$ST^{E}_{x}(\varphi\land\psi):=ST^{E}_{x}(\varphi)\land ST^{E}_{x}(\psi)$ ;
•

$ST^{E}_{x}(\Diamond\varphi):=\exists y(Rxy\land(\bigwedge\limits_{(v,w)\in E}\neg(x=v\land y=w))\land ST^{E}_{y}(\varphi))$ ;
•

$ST^{E}_{x}(\Diamondblack\varphi):=\exists y\exists z(Ryz\land(\bigwedge\limits_{(v,w)\in E}\neg(y=v\land z=w))\land ST^{E\cup\{(y,z)\}}_{x}(\varphi))$ .

It is proved in [5, Theorem 1] that this translation is correct:

Theorem 2.1.

For any pointed model $(\mathbb{M},w)$ and sabotage modal formula $\varphi$ ,

(\mathbb{M},w)\Vdash\varphi\mbox{ iff }\mathbb{M}\vDash ST^{\varnothing}_{x}(\varphi)[w].

3 Algorithmic correspondence for sabotage modal logic

In the present section, we will develop the correspondence algorithm $\mathsf{ALBA}^{\mathsf{SML}}$ for sabotage modal logic, in the style of [8, 10]. The basic idea is to use an algorithm $\mathsf{ALBA}^{\mathsf{SML}}$ to transform the modal formula $\varphi(\vec{p})$ into an equivalent set of pure quasi-(universally quantified) inequalities which does not contain occurrences of propositional variables, and therefore can be translated into the first-order correspondence language via the standard translation of the expanded language of sabotage modal logic (which will be defined on page 3.1).

The key ingredients of the algorithmic correspondence proof can be listed as follows:

•

An expanded sabotage modal language as the syntax of the algorithm, as well as their interpretations in the relational semantics;
•

An algorithm $\mathsf{ALBA}$ which transforms a given sabotage modal formula $\varphi(\vec{p})$ into equivalent pure quasi-(universally quantified) inequalities $\mathsf{Pure}(\varphi(\vec{p}))$ ;
•

A soundness proof of the algorithm;
•

A syntactically identified class of formulas on which the algorithm is successful;
•

A first-order correspondence language and first-order translation which transform pure quasi-(universally quantified) inequalities into their equivalent first-order correspondents.

In the remainder of the chapter, we will define an expanded sabotage modal language which the algorithm will manipulate (Section 3.1.1), define the first-order correspondence language of the expanded sabotage modal language and the standard translation (Section 3.1.2). We report on the definition of Sahlqvist inequalities (Section 3.2), define a modified version of the algorithm $\mathsf{ALBA}^{\mathsf{SML}}$ (Section 3.3), and show its soundness (Section 3.4) and success on Sahlqvist inequalities (Section 3.5).

3.1 The expanded sabotage modal language $\mathcal{L}_{\blacksquare}^{+}$ , the first-order correspondence language and the standard translation

3.1.1 The expanded sabotage modal language $\mathcal{L}_{\blacksquare}^{+}$

In the present subsection, we give the definition of the expanded sabotage modal language $\mathcal{L}_{\blacksquare}^{+}$ and its standard translations, which will be used in the execution of the algorithm:

\varphi::=p\mid\bot\mid\top\mid\mathbf{i}\mid\neg\varphi\mid(\varphi\land\varphi)\mid(\varphi\lor\varphi)\mid(\varphi\to\varphi)\mid\Box\varphi\mid\Diamond\varphi\mid\blacksquare\varphi\mid\Diamondblack\varphi\mid

\Box^{S}\varphi\mid\Diamond^{S}\varphi\mid(\Box^{S})^{-1}\varphi\mid(\Diamond^{S})^{-1}\varphi\mid\mathsf{A}\varphi\mid\mathsf{E}\varphi\mid\forall\mathbf{i}\varphi\mid\exists\mathbf{i}\varphi

S::=\varnothing\mid S\cup\{(\mathbf{i}_{k0},\mathbf{i}_{k1})\}

where $\mathbf{i}$ is called nominal as in hybrid logic [6, Chapter 14], $\mathbf{i}_{k0},\mathbf{i}_{k1}$ are fresh nominals not in $S$ . We use the notation $\varphi(\vec{p})$ to indicate that the propositional variables occurring in $\varphi$ are all in $\vec{p}$ . We call a formula pure if it does not contain propositional variables.

When interpreting the formulas in the expanded language, we assume that we start from a given pointed model $((W,R_{0},V),w)$ , and use $S$ to record the edges deleted from $R_{0}$ . $\Box^{S}$ , $\Diamond^{S}$ correspond to the relation $R_{0}\setminus\{(V(\mathbf{i}_{k0}),V(\mathbf{i}_{k1}))\mid(\mathbf{i}_{k0},\mathbf{i}_{k1})\in S\}$ (denoted as $R_{0}\setminus S$ ), $(\Box^{S})^{-1}$ , $(\Diamond^{S})^{-1}$ correspond to the relation $R_{0}^{-1}\setminus\{(V(\mathbf{i}_{k1}),V(\mathbf{i}_{k0}))\mid(\mathbf{i}_{k0},\mathbf{i}_{k1})\in S\}$ (denoted as $(R_{0}\setminus S)^{-1}$ ), which intuitively means first delete the edges in S and then take the inverse relation. Unlabelled $\Box$ and $\Diamond$ correspond to the relation $R$ after certain deletions of edges. Therefore, we can say that $\Box^{S}$ , $\Diamond^{S}$ , $(\Box^{S})^{-1}$ , $(\Diamond^{S})^{-1}$ are “absolute connectives” whose interpretations just depend on $R_{0}$ and $S$ , while $\Box$ and $\Diamond$ are “contextual connectives” whose interpretations depend on the concrete $R$ after certain steps of deletions. For $\blacksquare$ and $\Diamondblack$ , their interpretations depend on the context. $\mathsf{A}$ and $\mathsf{E}$ are global box and diamond modalities respectively, $(W,R,V),w\Vdash\forall\mathbf{i}\varphi$ indicates that for all valuation variant $V^{\mathbf{i}}_{v}$ such that $V^{\mathbf{i}}_{v}$ is the same as $V$ except that $V^{\mathbf{i}}_{v}(\mathbf{i})=\{v\}$ , $(W,R,V^{\mathbf{i}}_{v}),w\Vdash\varphi$ , and $(W,R,V),w\Vdash\exists\mathbf{i}\varphi$ is the corresponding existential statement.

For the semantics of the expanded sabotage modal language, the valuation is defined as $V:\mathsf{Prop}\cup\mathsf{Nom}\to\mathcal{P}(W)$ similar to hybrid logic, and for the modal and dynamic connectives, the additional semantic clauses can be given as follows (notice that here $R$ is the “actual” accessibility relation in the model $(W,R,V)$ after some (maybe none) edges have been deleted, while $R_{0}$ is the “starting accessibility” relation when no edge has been deleted yet, and $R_{0}\setminus S$ is the notation for $R_{0}\setminus\{(V(\mathbf{i}_{k0}),V(\mathbf{i}_{k1}))\mid(\mathbf{i}_{k0},\mathbf{i}_{k1})\in S\}$ ):

$(W,R,V),w\Vdash\Box\varphi$	iff	for all $v$ s.t. $(w,v)\in R$ , $(W,R,V),v\Vdash\varphi$
$(W,R,V),w\Vdash\Diamond\varphi$	iff	there exists a $v$ s.t. $(w,v)\in R$ and $(W,R,V),v\Vdash\varphi$
$(W,R,V),w\Vdash\blacksquare\varphi$	iff	for all edges $(w_{0},w_{1})\in R,(W,R\setminus\{(w_{0},w_{1})\},V),w\Vdash\varphi$
$(W,R,V),w\Vdash\Diamondblack\varphi$	iff	there exists an edge $(w_{0},w_{1})\in R$ s.t. $(W,R\setminus\{(w_{0},w_{1})\},V),w\Vdash\varphi$
$(W,R,V),w\Vdash\Box^{S}\varphi$	iff	for all $v$ s.t. $(w,v)\in(R_{0}\setminus S)$ , $(W,R,V),v\Vdash\varphi$
$(W,R,V),w\Vdash\Diamond^{S}\varphi$	iff	there exists a $v$ s.t. $(w,v)\in(R_{0}\setminus S)$ and $(W,R,V),v\Vdash\varphi$
$(W,R,V),w\Vdash(\Box^{S})^{-1}\varphi$	iff	for all $v$ s.t. $(v,w)\in(R_{0}\setminus S)$ , $(W,R,V),v\Vdash\varphi$
$(W,R,V),w\Vdash(\Diamond^{S})^{-1}\varphi$	iff	there exists a $v$ s.t. $(v,w)\in(R_{0}\setminus S)$ and $(W,R,V),v\Vdash\varphi$
$(W,R,V),w\Vdash\mathsf{A}\varphi$	iff	for all $v\in W$ , $(W,R,V),v\Vdash\varphi$
$(W,R,V),w\Vdash\mathsf{E}\varphi$	iff	there exists a $v\in W$ s.t. $(W,R,V),v\Vdash\varphi$
$(W,R,V),w\Vdash\forall\mathbf{i}\varphi$	iff	for all $v\in W$ , $(W,R,V^{\mathbf{i}}_{v}),w\Vdash\varphi$
$(W,R,V),w\Vdash\exists\mathbf{i}\varphi$	iff	there exists a $v\in W$ s.t. $(W,R,V^{\mathbf{i}}_{v}),w\Vdash\varphi$ .

Here we do not require that each pair of nominals in $S$ denote different edges in $R_{0}$ .

For the convenience of the algorithm, we introduce the following definitions:

Definition 2.

•

An inequality is of the form $\varphi\leq^{S}_{S^{\prime}}\psi$ , where $\varphi$ and $\psi$ are formulas, $S$ and $S^{\prime}$ record the context of $\varphi$ and $\psi$ respectively, i.e. which edges have already been deleted. Its interpretation is given as follows:

(W,R_{0},V)\Vdash\varphi\leq^{S}_{S^{\prime}}\psi\mbox{ iff }

(\mbox{for all }w\in W,\mbox{ if }(W,R_{0}\setminus S,V),w\Vdash\varphi,\mbox{ then }(W,R_{0}\setminus S^{\prime},V),w\Vdash\psi).

We use $\varphi\leq\psi$ to denote $\varphi\leq^{\varnothing}_{\varnothing}\psi$ .

•

A quasi-inequality is of the form $\varphi_{1}\leq^{S_{1}}_{S^{\prime}_{1}}\psi_{1}\ \&\ \ldots\ \&\ \varphi_{n}\leq^{S_{n}}_{S^{\prime}_{n}}\psi_{n}\ \Rightarrow\ \varphi\leq^{S}_{S^{\prime}}\psi$ . Its interpretation is given as follows:

(W,R_{0},V)\Vdash\varphi_{1}\leq^{S_{1}}_{S^{\prime}_{1}}\psi_{1}\ \&\ \ldots\ \&\ \varphi_{n}\leq^{S_{n}}_{S^{\prime}_{n}}\psi_{n}\ \Rightarrow\ \varphi\leq^{S}_{S^{\prime}}\psi\mbox{ iff }

(W,R_{0},V)\Vdash\varphi\leq^{S}_{S^{\prime}}\psi\mbox{ holds whenever }(W,R_{0},V)\Vdash\varphi_{i}\leq^{S_{i}}_{S^{\prime}_{i}}\psi_{i}\mbox{ for all }1\leq i\leq n.

•

A Mega-inequality is defined inductively as follows:

\mathsf{Mega}::=\mathsf{Ineq}\mid\mathsf{Mega}\mathop{\mbox{\Large\&}}\mathsf{Mega}\mid\forall\mathbf{i}\forall\mathbf{j}(\mathbf{i}\leq^{S}_{S}\Diamond^{S}\mathbf{j}\Rightarrow\mathsf{Mega})

where $\mathsf{Ineq}$ is an inequality, $\mathop{\mbox{\Large\&}}$ is the meta-conjunction and $\Rightarrow$ is the meta-implication. Its interpretation is given as follows:

–

$(W,R_{0},V)\Vdash\mathsf{Ineq}$ iff the inequality holds as defined in the definition above;
–

$(W,R_{0},V)\Vdash\mathsf{Mega_{1}}\mathop{\mbox{\Large\&}}\mathsf{Mega_{2}}$ iff $(W,R_{0},V)\Vdash\mathsf{Mega_{1}}$ and $(W,R_{0},V)\Vdash\mathsf{Mega_{2}}$ ;
–

$(W,R_{0},V)\Vdash\forall\mathbf{i}\forall\mathbf{j}(\mathbf{i}\leq^{S}_{S}\Diamond^{S}\mathbf{j}\Rightarrow\mathsf{Mega})$ iff for all $w,v$ , if $(w,v)\in(R_{0}\setminus S)$ then $(W,R_{0},V^{\mathbf{i},\mathbf{j}}_{w,v})\Vdash\mathsf{Mega}$ , where $V^{\mathbf{i},\mathbf{j}}_{w,v}$ is the same as $V$ except that $V^{\mathbf{i},\mathbf{j}}_{w,v}(\mathbf{i})=\{w\}$ , $V^{\mathbf{i},\mathbf{j}}_{w,v}(\mathbf{j})=\{v\}$ .

•

A universally quantified inequality is defined as $\forall\mathbf{i}_{1}\ldots\forall\mathbf{i}_{n}(\varphi\leq^{S}_{S^{\prime}}\psi)$ , and its interpretation is given as follows:

$(W,R_{0},V)\Vdash\forall\mathbf{i}_{1}\ldots\forall\mathbf{i}_{n}(\varphi\leq^{S}_{S^{\prime}}\psi)$ iff for all $w_{1},\ldots,w_{n}\in W$ , $(W,R_{0},V^{\mathbf{i}_{1},\ldots,\mathbf{i}_{n}}_{w_{1},\ldots,w_{n}})\Vdash\varphi\leq^{S}_{S^{\prime}}\psi$ , where $V^{\mathbf{i}_{1},\ldots,\mathbf{i}_{n}}_{w_{1},\ldots,w_{n}}$ is the same as $V$ except that $V^{\mathbf{i}_{1},\ldots,\mathbf{i}_{n}}_{w_{1},\ldots,w_{n}}(\mathbf{i}_{i})=\{w_{i}\}$ , $i=1,\ldots,n$ .

•

A quasi-universally quantified inequality is defined as $\mathsf{UQIneq_{1}}\&\ldots\&\mathsf{UQIneq_{n}}\Rightarrow\mathsf{UQIneq}$ where $\mathsf{UQIneq},\mathsf{UQIneq_{i}}$ are universally quantified inequalities. Its interpretation is given as follows:

(W,R_{0},V)\Vdash\mathsf{UQIneq_{1}}\&\ldots\&\mathsf{UQIneq_{n}}\Rightarrow\mathsf{UQIneq}\mbox{ iff }

(W,R_{0},V)\Vdash\mathsf{UQIneq}\mbox{ holds whenever }(W,R_{0},V)\Vdash\mathsf{UQIneq_{i}}\mbox{ for all }1\leq i\leq n.

It is easy to see that $(W,R_{0},V)\Vdash\varphi\leq^{\varnothing}_{\varnothing}\psi$ iff $(W,R_{0},V)\Vdash\varphi\to\psi$ . We will find it easy to work with inequalities $\varphi\leq\psi$ in place of implicative formulas $\varphi\to\psi$ in Section 3.2.

For inequalities, we have the following properties, which will be useful in the soundness proofs:

Proposition 3.

•

$(W,R_{0},V)\Vdash\mathbf{i}\leq^{S}_{S}\Diamond^{S}\mathbf{j}$ iff $(V(\mathbf{i}),V(\mathbf{j}))\in(R_{0}\setminus S)$ ;
•

$(W,R_{0},V)\Vdash\mathbf{i}\leq^{S}_{S^{\prime}}\alpha$ iff $(W,(R_{0}\setminus S^{\prime}),V),V(\mathbf{i})\Vdash\alpha$ , where $\alpha$ is a formula in the expanded sabotage modal language;
•

$(W,R_{0},V)\Vdash A(\mathbf{i}\to\Diamond^{S}\mathbf{j})$ iff $(V(\mathbf{i}),V(\mathbf{j}))\in(R_{0}\setminus S)$ .

3.1.2 The first-order correspondence language and the standard translation

In the first-order correspondence language, we have a binary relation symbol $R$ corresponding to the binary relation, a set of constant symbols $i$ corresponding to each nominal $\mathbf{i}$ , a set of unary predicate symbols $P$ corresponding to each propositional variable $p$ .

The standard translation of the expanded sabotage modal language is defined as follows:

Definition 4.

Let $E$ be a finite set of pairs $(y,z)$ of variables standing for edges and let $x$ be a designated variable. The translation $ST^{E}_{x}$ is recursively defined as follows:

•

$ST^{E}_{x}(\bot):=x\neq x$ ;
•

$ST^{E}_{x}(\top):=x=x$ ;
•

$ST^{E}_{x}(\mathbf{i}):=x=i$ ;
•

$ST^{E}_{x}(p):=Px$ ;
•

$ST^{E}_{x}(\neg\varphi):=\neg ST^{E}_{x}(\varphi)$ ;
•

$ST^{E}_{x}(\varphi\land\psi):=ST^{E}_{x}(\varphi)\land ST^{E}_{x}(\psi)$ ;
•

$ST^{E}_{x}(\varphi\lor\psi):=ST^{E}_{x}(\varphi)\lor ST^{E}_{x}(\psi)$ ;
•

$ST^{E}_{x}(\varphi\to\psi):=ST^{E}_{x}(\varphi)\to ST^{E}_{x}(\psi)$ ;
•

$ST^{E}_{x}(\Box\varphi):=\forall y(Rxy\land(\bigwedge\limits_{(v,w)\in E}\neg(x=v\land y=w))\to ST^{E}_{y}(\varphi))$ ;
•

$ST^{E}_{x}(\Diamond\varphi):=\exists y(Rxy\land(\bigwedge\limits_{(v,w)\in E}\neg(x=v\land y=w))\land ST^{E}_{y}(\varphi))$ ;
•

$ST^{E}_{x}(\blacksquare\varphi):=\forall y\forall z(Ryz\land(\bigwedge\limits_{(v,w)\in E}\neg(y=v\land z=w))\to ST^{E\cup\{(y,z)\}}_{x}(\varphi))$ ;
•

$ST^{E}_{x}(\Diamondblack\varphi):=\exists y\exists z(Ryz\land(\bigwedge\limits_{(v,w)\in E}\neg(y=v\land z=w))\land ST^{E\cup\{(y,z)\}}_{x}(\varphi))$ ;
•

$ST^{E}_{x}(\Box^{S}\varphi):=\forall y(Rxy\land(\bigwedge\limits_{(\mathbf{i}_{k0},\mathbf{i}_{k1})\in S}\neg(x=i_{k0}\land y=i_{k1}))\to ST^{E}_{y}(\varphi))$ ;
•

$ST^{E}_{x}(\Diamond^{S}\varphi):=\exists y(Rxy\land(\bigwedge\limits_{(\mathbf{i}_{k0},\mathbf{i}_{k1})\in S}\neg(x=i_{k0}\land y=i_{k1}))\land ST^{E}_{y}(\varphi))$ ;
•

$ST^{E}_{x}((\Box^{S})^{-1}\varphi):=\forall y(Ryx\land(\bigwedge\limits_{(\mathbf{i}_{k0},\mathbf{i}_{k1})\in S}\neg(y=i_{k0}\land x=i_{k1}))\to ST^{E}_{y}(\varphi))$ ;
•

$ST^{E}_{x}((\Diamond^{S})^{-1}\varphi):=\exists y(Ryx\land(\bigwedge\limits_{(\mathbf{i}_{k0},\mathbf{i}_{k1})\in S}\neg(y=i_{k0}\land x=i_{k1}))\land ST^{E}_{y}(\varphi))$ .
•

$ST^{E}_{x}(\mathsf{A}\varphi):=\forall yST^{E}_{y}(\varphi)$ ;
•

$ST^{E}_{x}(\mathsf{E}\varphi):=\exists yST^{E}_{y}(\varphi)$ ;
•

$ST^{E}_{x}(\forall\mathbf{i}\varphi):=\forall iST^{E}_{x}(\varphi)$ ;
•

$ST^{E}_{x}(\exists\mathbf{i}\varphi):=\exists iST^{E}_{x}(\varphi)$ .

It is easy to see that this translation is correct:

Proposition 5.

For any pointed model $(\mathbb{M},w)$ and sabotage modal formula $\varphi$ ,

(\mathbb{M},w)\Vdash\varphi\mbox{ iff }\mathbb{M}\vDash ST^{\varnothing}_{x}(\varphi)[w].

For inequalities, quasi-inequalities, mega-inequalities, universally quantified inequalities and quasi-universally quantified inequalities, the standard translation is given in a global way:

Definition 6.

•

$ST(\varphi\leq^{S}_{S^{\prime}}\psi):=\forall x(ST^{S}_{x}(\varphi)\to ST^{S^{\prime}}_{x}(\psi))$ ;
•

$ST(\varphi_{1}\leq^{S_{1}}_{S^{\prime}_{1}}\psi_{1}\&\ldots\&\varphi_{n}\leq^{S_{n}}_{S^{\prime}_{n}}\psi_{n}\Rightarrow\varphi\leq^{S}_{S^{\prime}}\psi):=ST(\varphi_{1}\leq^{S_{1}}_{S^{\prime}_{1}}\psi_{1})\land\ldots\land ST(\varphi_{n}\leq^{S_{n}}_{S^{\prime}_{n}}\psi_{n})\to ST(\varphi\leq^{S}_{S^{\prime}}\psi)$ ;
•

$ST(\mathsf{Mega}_{1}\ \&\ \mathsf{Mega}_{2})=ST(\mathsf{Mega}_{1})\land ST(\mathsf{Mega}_{2})$ ;
•

$ST(\forall\mathbf{i}\forall\mathbf{j}(\mathbf{i}\leq^{S}_{S}\Diamond^{S}\mathbf{j}\Rightarrow\mathsf{Mega})):=\forall i\forall j(Rij\land(\bigwedge\limits_{(v,w)\in S}\neg(i=v\land j=w))\to ST(\mathsf{Mega}))$ ;
•

$ST(\forall\mathbf{i}_{1}\ldots\forall\mathbf{i}_{n}\mathsf{Ineq}):=\forall i_{1}\ldots\forall i_{n}ST(\mathsf{Ineq})$ ;
•

$ST(\mathsf{UQIneq_{1}}\&\ldots\&\mathsf{UQIneq_{n}}\Rightarrow\mathsf{UQIneq}):=ST(\mathsf{UQIneq_{1}})\land\ldots\land ST(\mathsf{UQIneq_{n}})\to ST(\mathsf{UQIneq})$ .

Proposition 7.

For any model $\mathbb{M}$ and inequality $\mathsf{Ineq}$ , quasi-inequality $\mathsf{Quasi}$ , mega-inequality $\mathsf{Mega}$ , universally quantified inequality $\mathsf{UQIneq}$ , quasi-universally quantified inequality $\mathsf{QUQIneq}$ ,

\mathbb{M}\Vdash\mathsf{Ineq}\mbox{ iff }\mathbb{M}\vDash ST(\mathsf{Ineq});

\mathbb{M}\Vdash\mathsf{Quasi}\mbox{ iff }\mathbb{M}\vDash ST(\mathsf{Quasi});

\mathbb{M}\Vdash\mathsf{Mega}\mbox{ iff }\mathbb{M}\vDash ST(\mathsf{Mega});

\mathbb{M}\Vdash\mathsf{UQIneq}\mbox{ iff }\mathbb{M}\vDash ST(\mathsf{UQIneq});

\mathbb{M}\Vdash\mathsf{QUQIneq}\mbox{ iff }\mathbb{M}\vDash ST(\mathsf{QUQIneq}).

3.2 Sahlqvist inequalities

In the present section, since we will use the algorithm $\mathsf{ALBA}^{\mathsf{SML}}$ which is based on the classsification of nodes in the signed generation trees of sabotage modal formulas, we will use the unified correspondence style definition (cf. [11, 12, 19]) to define Sahlqvist inequalities. We will collect all the necessary preliminaries on Sahlqvist formulas/inequalities.

Definition 8 (Order-type of propositional variables).

(cf. [10, page 346]) For an $n$ -tuple $(p_{1},\ldots,p_{n})$ of propositional variables, an order-type $\varepsilon$ of $(p_{1},\ldots,p_{n})$ is an element in $\{1,\partial\}^{n}$ . In the order-type $\varepsilon$ , we say that $p_{i}$ has order-type 1 if $\varepsilon_{i}=1$ , and denote $\varepsilon(p_{i})=1$ or $\varepsilon(i)=1$ ; we say that $p_{i}$ has order-type $\partial$ if $\varepsilon_{i}=\partial$ , and denote $\varepsilon(p_{i})=\partial$ or $\varepsilon(i)=\partial$ .

Definition 9 (Signed generation tree).

(cf. [12, Definition 4]) The positive (resp. negative) generation tree of any given formula $\varphi$ is defined by first labelling the root of the generation tree of $\varphi$ with $+$ (resp. $-$ ) and then labelling the children nodes as follows:

•

Assign the same sign to the children nodes of any node labelled with $\lor,\land,\Box$ , $\Diamond$ , $\blacksquare,\Diamondblack,\Box^{S},\Diamond^{S},(\Box^{S})^{-1},(\Diamond^{S})^{-1},\mathsf{A},\mathsf{E},\forall\mathbf{i},\exists\mathbf{i}$ ;
•

Assign the opposite sign to the child node of any node labelled with $\neg$ ;
•

Assign the opposite sign to the first child node and the same sign to the second child node of any node labelled with $\to$ .

Nodes in signed generation trees are positive (resp. negative) if they are signed $+$ (resp. $-$ ).

Signed generation trees will be used in the inequalities $\varphi\leq\psi$ , where the positive generation tree $+\varphi$ and the negative generation tree $-\psi$ will be considered. We will also say that an inequality $\varphi\leq\psi$ is uniform in a variable $p_{i}$ if all occurrences of $p_{i}$ in $+\varphi$ and $-\psi$ have the same sign, and that $\varphi\leq\psi$ is $\varepsilon$ -uniform in an array $\vec{p}$ if $\varphi\leq\psi$ is uniform in $p_{i}$ , occurring with the sign indicated by $\varepsilon$ (i.e., $p_{i}$ has the sign $+$ if $\varepsilon(p_{i})=1$ , and has the sign $-$ if $\varepsilon(p_{i})=\partial$ ), for each propositional variable $p_{i}$ in $\vec{p}$ .

For any given formula $\varphi(p_{1},\ldots p_{n})$ , any order-type $\varepsilon$ over $n$ , and any $1\leq i\leq n$ , an $\varepsilon$ -critical node in a signed generation tree $\ast\varphi$ (where $\ast\in\{+,-\}$ ) is a leaf node $+p_{i}$ when $\varepsilon_{i}=1$ or $-p_{i}$ when $\varepsilon_{i}=\partial$ . An $\varepsilon$ -critical branch in a signed generation tree is a branch from an $\varepsilon$ -critical node. The $\varepsilon$ -critical occurrences are intended to be those which the algorithm $\mathsf{ALBA}^{\mathsf{SML}}$ will solve for. We say that $+\varphi$ (resp. $-\varphi$ ) agrees with $\varepsilon$ , and write $\varepsilon(+\varphi)$ (resp. $\varepsilon(-\varphi)$ ), if every leaf node in the signed generation tree of $+\varphi$ (resp. $-\varphi$ ) is $\varepsilon$ -critical.

We will also use the notation $+\psi\prec\ast\varphi$ (resp. $-\psi\prec\ast\varphi$ ) to indicate that an occurence of a subformula $\psi$ inherits the positive (resp. negative) sign from the signed generation tree $\ast\varphi$ , where $\ast\in\{+,-\}$ . We will write $\varepsilon(\gamma)\prec\ast\varphi$ (resp. $\varepsilon^{\partial}(\gamma)\prec\ast\varphi$ ) to indicate that the signed generation subtree $\gamma$ , with the sign inherited from $\ast\varphi$ , agrees with $\varepsilon$ (resp. with $\varepsilon^{\partial}$ ). We say that a propositional variable $p$ is positive (resp. negative) in $\varphi$ if $+p\prec+\varphi$ (resp. $-p\prec+\varphi$ ).

Definition 10.

(cf. [12, Definition 5]) Nodes in signed generation trees are called outer nodes and inner nodes, according to Table 1.

A branch in a signed generation tree is called a excellent branch if it is the concatenation of two paths $P_{1}$ and $P_{2}$ , one of which might be of length $0$ , such that $P_{1}$ is a path from the leaf consisting (apart from variable nodes) of inner nodes only, and $P_{2}$ consists (apart from variable nodes) of outer nodes only.

Outer

Inner

$+$	$\vee$	$\wedge$	$\Diamond$	$\Diamondblack$	$\neg$
$-$	$\wedge$	$\vee$	$\Box$	$\blacksquare$	$\neg$	$\to$

$+$	$\wedge$	$\Box$	$\blacksquare$	$\neg$
$-$	$\vee$	$\Diamond$	$\Diamondblack$	$\neg$

Table 1: Outer and Inner nodes.

Definition 11 (Sahlqvist and inequalities).

(cf. [12, Definition 6]) For any order-type $\varepsilon$ , the signed generation tree $*\varphi$ of a formula $\varphi(p_{1},\ldots p_{n})$ is $\varepsilon$ -Sahlqvist if for all $1\leq i\leq n$ , every $\varepsilon$ -critical branch with leaf $p_{i}$ is excellent. An inequality $\varphi\leq\psi$ is $\varepsilon$ -Sahlqvist if the signed generation trees $+\varphi$ and $-\psi$ are $\varepsilon$ -Sahlqvist. An inequality $\varphi\leq\psi$ is Sahlqvist if it is $\varepsilon$ -Sahlqvist) for some $\varepsilon$ .

3.3 The algorithm $\mathsf{ALBA}^{\mathsf{SML}}$ for the sabotage modal language

In the present section, we define the correspondence algorithm $\mathsf{ALBA}^{\mathsf{SML}}$ for sabotage modal logic, in the style of [8, 10]. The algorithm goes in four steps.

Preprocessing and first approximation:

In the generation tree of $+\varphi$ and $-\psi$ ¹¹1The discussion below relies on the definition of signed generation tree in Section 3.2. In what follows, we identify a formula with its signed generation tree.,

(a)

Apply the distribution rules:
1. i.
  
  Push down $+\Diamond,+\Diamondblack,-\neg,+\land,-\to$ by distributing them over nodes labelled with $+\lor$ which are outer nodes, and
2. ii.
  
  Push down $-\Box,-\blacksquare,+\neg,-\lor,-\to$ by distributing them over nodes labelled with $-\land$ which are outer nodes.
(b)

Apply the splitting rules:

$\alpha\leq\beta\ \ \ \alpha\leq\gamma\alpha\leq\beta\land\gamma\qquad\alpha\leq\gamma\ \ \ \beta\leq\gamma\alpha\lor\beta\leq\gamma$

(c)

Apply the monotone and antitone variable-elimination rules:

\alpha(\perp)\leq\beta(\perp)\alpha(p)\leq\beta(p)\qquad\beta(\top)\leq\alpha(\top)\beta(p)\leq\alpha(p)

for $\beta(p)$ positive in $p$ and $\alpha(p)$ negative in $p$ .

We denote by $\mathsf{Preprocess}(\varphi\leq\psi)$ the finite set $\{\varphi_{i}\leq\psi_{i}\}_{i\in I}$ of inequalities obtained after the exhaustive application of the previous rules. Then we apply the following first approximation rule to every inequality in $\mathsf{Preprocess}(\varphi\leq\psi)$ :

\mathbf{i}_{0}\leq\varphi_{i}\ \ \ \psi_{i}\leq\neg\mathbf{i}_{1}\varphi_{i}\leq\psi_{i}

Here, $\mathbf{i}_{0}$ and $\mathbf{i}_{1}$ are special fresh nominals. Now we get a set of inequalities $\{\mathbf{i}_{0}\leq\varphi_{i},\psi_{i}\leq\neg\mathbf{i}_{1}\}_{i\in I}$ .

The reduction stage:

In this stage, for each $\{\mathbf{i}_{0}\leq\varphi_{i},\psi_{i}\leq\neg\mathbf{i}_{1}\}$ , we first add superscripts and subscripts $\varnothing$ to the two $\leq$ s, and then apply the following rules to prepare for eliminating all the proposition variables in $\{\mathbf{i}_{0}\leq^{\varnothing}_{\varnothing}\varphi_{i},\psi_{i}\leq^{\varnothing}_{\varnothing}\neg\mathbf{i}_{1}\}$ :

(a)

Substage 1: Decomposing the outer part

In the current substage, the following rules are applied to decompose the outer part of the Sahlqvist signed formula:

Splitting rules:

\alpha\leq^{S}_{S^{\prime}}\beta\ \ \ \alpha\leq^{S}_{S^{\prime}}\gamma\alpha\leq^{S}_{S^{\prime}}\beta\land\gamma\qquad\alpha\leq^{S}_{S^{\prime}}\gamma\ \ \ \beta\leq^{S}_{S^{\prime}}\gamma\alpha\lor\beta\leq^{S}_{S^{\prime}}\gamma

ii.

Approximation rules:

\mathbf{j}\leq^{S^{\prime}}_{S^{\prime}}\alpha\ \ \ \mathbf{i}\leq^{S}_{S^{\prime}}\Diamond^{S^{\prime}}\mathbf{j}\mathbf{i}\leq^{S}_{S^{\prime}}\Diamond\alpha\qquad\alpha\leq^{S}_{S}\neg\mathbf{j}\ \ \ \Box^{S}\neg\mathbf{j}\leq^{S}_{S^{\prime}}\neg\mathbf{i}\Box\alpha\leq^{S}_{S^{\prime}}\neg\mathbf{i}

\mathbf{i}_{m0}\leq^{S^{\prime}}_{S^{\prime}}\Diamond^{S^{\prime}}\mathbf{i}_{m1}\ \ \ \ \ \ \ \mathbf{i}\leq^{S}_{S^{\prime}\cup\{(\mathbf{i}_{m0},\mathbf{i}_{m1})\}}\alpha\mathbf{i}\leq^{S}_{S^{\prime}}\Diamondblack\alpha\qquad\mathbf{i}_{m0}\leq^{S}_{S}\Diamond^{S}\mathbf{i}_{m1}\ \ \ \ \ \ \alpha\leq^{S\cup\{(\mathbf{i}_{m0},\mathbf{i}_{m1})\}}_{S^{\prime}}\neg\mathbf{i}\blacksquare\alpha\leq^{S}_{S^{\prime}}\neg\mathbf{i}

\mathbf{j}\leq^{S}_{S}\alpha\ \ \ \ \ \ \ \beta\leq^{S}_{S}\neg\mathbf{k}\ \ \ \ \ \ \ \mathbf{j}\rightarrow\neg\mathbf{k}\leq^{S}_{S^{\prime}}\neg\mathbf{i}\alpha\rightarrow\beta\leq^{S}_{S^{\prime}}\neg\mathbf{i}

The nominals introduced by the approximation rules must not occur in the system before applying the rule.

iii.

Residuation rules:

\alpha\leq^{S^{\prime}}_{S}\neg\mathbf{i}\mathbf{i}\leq^{S}_{S^{\prime}}\neg\alpha\qquad\mathbf{i}\leq^{S^{\prime}}_{S}\alpha\neg\alpha\leq^{S}_{S^{\prime}}\neg\mathbf{i}

(b)

Substage 2: Decomposing the inner part

In the current substage, the following rules are applied to decompose the inner part of the Sahlqvist signed formula:

Splitting rules:

\alpha\leq^{S}_{S^{\prime}}\beta\ \ \ \alpha\leq^{S}_{S^{\prime}}\gamma\alpha\leq^{S}_{S^{\prime}}\beta\land\gamma\qquad\alpha\leq^{S}_{S^{\prime}}\gamma\ \ \ \beta\leq^{S}_{S^{\prime}}\gamma\alpha\lor\beta\leq^{S}_{S^{\prime}}\gamma

ii.

Residuation rules:

\beta\leq^{S^{\prime}}_{S}\neg\alpha\alpha\leq^{S}_{S^{\prime}}\neg\beta\qquad\neg\beta\leq^{S^{\prime}}_{S}\alpha\neg\alpha\leq^{S}_{S^{\prime}}\beta\qquad\alpha\leq^{S}_{S^{\prime}}(\Box^{S})^{-1}\beta\Diamond\alpha\leq^{S}_{S^{\prime}}\beta\qquad(\Diamond^{S^{\prime}})^{-1}\alpha\leq^{S}_{S^{\prime}}\beta\alpha\leq^{S}_{S^{\prime}}\Box\beta

\forall\mathbf{i}_{m0}\forall\mathbf{i}_{m1}(\mathbf{i}_{m0}\leq^{S^{\prime}}_{S^{\prime}}\Diamond^{S^{\prime}}\mathbf{i}_{m1}\ \Rightarrow\ \alpha\leq^{S}_{S^{\prime}\cup\{(\mathbf{i}_{m0},\mathbf{i}_{m1})\}}\beta)\alpha\leq^{S}_{S^{\prime}}\blacksquare\beta

\forall\mathbf{i}_{m0}\forall\mathbf{i}_{m1}(\mathbf{i}_{m0}\leq^{S}_{S}\Diamond^{S}\mathbf{i}_{m1}\ \Rightarrow\ \alpha\leq^{S\cup\{(\mathbf{i}_{m0},\mathbf{i}_{m1})\}}_{S^{\prime}}\beta)\Diamondblack\alpha\leq^{S}_{S^{\prime}}\beta

The nominals introduced by the residuation rules must not occur in the system before applying the rule.

iii.

Second splitting rules:

\forall\mathbf{i}_{m0}\forall\mathbf{i}_{m1}(\mathbf{i}_{m0}\leq^{S}_{S}\Diamond^{S}\mathbf{i}_{m1}\Rightarrow\mathsf{Mega_{1}})\ \ \ \forall\mathbf{i}_{m0}\forall\mathbf{i}_{m1}(\mathbf{i}_{m0}\leq^{S}_{S}\Diamond^{S}\mathbf{i}_{m1}\Rightarrow\mathsf{Mega_{2}})\forall\mathbf{i}_{m0}\forall\mathbf{i}_{m1}(\mathbf{i}_{m0}\leq^{S}_{S}\Diamond^{S}\mathbf{i}_{m1}\Rightarrow\ \mathsf{Mega_{1}}\mathop{\mbox{\Large\&}}\mathsf{Mega_{2}})

Here $\mathsf{Mega_{1}}$ and $\mathsf{Mega_{2}}$ denote mega-inequalities.

(c)

Substage 3: Preparing for the Ackermann rules

In this substage, we prepare for eliminating the propositional variables by the Ackermann rules, with the help of the following packing rules:

Packing rules:

\exists\mathbf{i}_{m_{0}0}\exists\mathbf{i}_{m_{0}1}\ldots\exists\mathbf{i}_{m_{k}0}\exists\mathbf{i}_{m_{k}1}(A(\mathbf{i}_{m_{0}0}\to\Diamond^{S_{0}}\mathbf{i}_{m_{0}1})\land A(\mathbf{i}_{m_{k}0}\to\Diamond^{S_{k}}\mathbf{i}_{m_{k}1})\land\alpha)\leq^{\varnothing}_{\varnothing}p\forall\mathbf{i}_{m_{0}0}\forall\mathbf{i}_{m_{0}1}(\mathbf{i}_{m_{0}0}\leq^{S_{0}}_{S_{0}}\Diamond^{S_{0}}\mathbf{i}_{m_{0}1}\Rightarrow\ldots\forall\mathbf{i}_{m_{k}0}\forall\mathbf{i}_{m_{k}1}(\mathbf{i}_{m_{k}0}\leq^{S_{k}}_{S_{k}}\Diamond^{S_{k}}\mathbf{i}_{m_{k}1}\ \Rightarrow\ \alpha\leq^{S}_{S^{\prime}}p)\ldots)

where $\alpha$ is pure and does not contain contextual connectives $\Box,\Diamond,\blacksquare,\Diamondblack$ ;

p\leq^{\varnothing}_{\varnothing}\forall\mathbf{i}_{m_{0}0}\forall\mathbf{i}_{m_{0}1}\ldots\forall\mathbf{i}_{m_{k}0}\forall\mathbf{i}_{m_{k}1}(A(\mathbf{i}_{m_{0}0}\to\Diamond^{S_{0}}\mathbf{i}_{m_{0}1})\land A(\mathbf{i}_{m_{k}0}\to\Diamond^{S_{k}}\mathbf{i}_{m_{k}1})\to\beta)\forall\mathbf{i}_{m_{0}0}\forall\mathbf{i}_{m_{0}1}(\mathbf{i}_{m_{0}0}\leq^{S_{0}}_{S_{0}}\Diamond^{S_{0}}\mathbf{i}_{m_{0}1}\Rightarrow\ldots\forall\mathbf{i}_{m_{k}0}\forall\mathbf{i}_{m_{k}1}(\mathbf{i}_{m_{k}0}\leq^{S_{k}}_{S_{k}}\Diamond^{S_{k}}\mathbf{i}_{m_{k}1}\ \Rightarrow\ p\leq^{S}_{S^{\prime}}\beta)\ldots)

where $\beta$ is pure and does not contain contextual connectives $\Box,\Diamond,\blacksquare,\Diamondblack$ .

\forall\mathbf{i}_{m_{0}0}\forall\mathbf{i}_{m_{0}1}\ldots\forall\mathbf{i}_{m_{k}0}\forall\mathbf{i}_{m_{k}1}(\top\leq^{\varnothing}_{S^{\prime}}A(\mathbf{i}_{m_{0}0}\to\Diamond^{S_{0}}\mathbf{i}_{m_{0}1})\land A(\mathbf{i}_{m_{k}0}\to\Diamond^{S_{k}}\mathbf{i}_{m_{k}1})\land\alpha\to\gamma)\forall\mathbf{i}_{m_{0}0}\forall\mathbf{i}_{m_{0}1}(\mathbf{i}_{m_{0}0}\leq^{S_{0}}_{S_{0}}\Diamond^{S_{0}}\mathbf{i}_{m_{0}1}\Rightarrow\ldots\forall\mathbf{i}_{m_{k}0}\forall\mathbf{i}_{m_{k}1}(\mathbf{i}_{m_{k}0}\leq^{S_{k}}_{S_{k}}\Diamond^{S_{k}}\mathbf{i}_{m_{k}1}\ \Rightarrow\ \alpha\leq^{S}_{S^{\prime}}\gamma)\ldots)

where $\alpha$ is pure and does not contain contextual connectives $\Box,\Diamond,\blacksquare,\Diamondblack$ .

\forall\mathbf{i}_{m_{0}0}\forall\mathbf{i}_{m_{0}1}\ldots\forall\mathbf{i}_{m_{k}0}\forall\mathbf{i}_{m_{k}1}(\top\leq^{\varnothing}_{S}A(\mathbf{i}_{m_{0}0}\to\Diamond^{S_{0}}\mathbf{i}_{m_{0}1})\land A(\mathbf{i}_{m_{k}0}\to\Diamond^{S_{k}}\mathbf{i}_{m_{k}1})\land\gamma\to\alpha)\forall\mathbf{i}_{m_{0}0}\forall\mathbf{i}_{m_{0}1}(\mathbf{i}_{m_{0}0}\leq^{S_{0}}_{S_{0}}\Diamond^{S_{0}}\mathbf{i}_{m_{0}1}\Rightarrow\ldots\forall\mathbf{i}_{m_{k}0}\forall\mathbf{i}_{m_{k}1}(\mathbf{i}_{m_{k}0}\leq^{S_{k}}_{S_{k}}\Diamond^{S_{k}}\mathbf{i}_{m_{k}1}\ \Rightarrow\ \gamma\leq^{S}_{S^{\prime}}\alpha)\ldots)

where $\alpha$ is pure and does not contain contextual connectives $\Box,\Diamond,\blacksquare,\Diamondblack$ .

(d)

Substage 4: The Ackermann stage

In this substage, we compute the minimal/maximal valuation for propositional variables and use the Ackermann rules to eliminate all the propositional variables. These two rules are the core of $\mathsf{ALBA}$ , since their application eliminates proposition variables. In fact, all the preceding steps are aimed at reaching a shape in which the rules can be applied. Notice that an important feature of these rules is that they are executed on the whole set of (universally quantified) inequalities, and not on a single inequality.

The right-handed Ackermann rule:

The system $\left\{\begin{array}[]{ll}\alpha_{1}\leq^{\varnothing}_{\varnothing}p\\ \vdots\\ \alpha_{n}\leq^{\varnothing}_{\varnothing}p\\ \forall\vec{\mathbf{i}_{1}}(\beta_{1}\leq^{T_{1}}_{T^{\prime}_{1}}\gamma_{1})\\ \vdots\\ \forall\vec{\mathbf{i}_{m}}(\beta_{m}\leq^{T_{m}}_{T^{\prime}_{m}}\gamma_{m})\\ \end{array}\right.$

is replaced by $\left\{\begin{array}[]{ll}\forall\vec{\mathbf{i}_{1}}(\beta_{1}((\alpha_{1}\lor\ldots\lor\alpha_{n})/p)\leq^{T_{1}}_{T^{\prime}_{1}}\gamma_{1}((\alpha_{1}\lor\ldots\lor\alpha_{n})/p))\\ \vdots\\ \forall\vec{\mathbf{i}_{m}}(\beta_{m}((\alpha_{1}\lor\ldots\lor\alpha_{n})/p)\leq^{T_{m}}_{T^{\prime}_{m}}\gamma_{m}((\alpha_{1}\lor\ldots\lor\alpha_{n})/p))\\ \end{array}\right.$

where:
1. i.
  
  $p,\vec{\mathbf{i}_{1}},\ldots,\vec{\mathbf{i}_{m}}$ do not occur in $\alpha_{1},\ldots,\alpha_{n}$ ;
2. ii.
  
  Each $\beta_{i}$ is positive in $p$ , and each $\gamma_{i}$ negative in $p$ , for $1\leq i\leq m$ ;
3. iii.
  
  Each $\alpha_{i}$ is pure and contains no contextual modalities $\Box,\Diamond,\blacksquare,\Diamondblack$ .
The left-handed Ackermann rule:

The system $\left\{\begin{array}[]{ll}p\leq^{\varnothing}_{\varnothing}\alpha_{1}\\ \vdots\\ p\leq^{\varnothing}_{\varnothing}\alpha_{n}\\ \forall\vec{\mathbf{i}_{1}}(\beta_{1}\leq^{T_{1}}_{T^{\prime}_{1}}\gamma_{1})\\ \vdots\\ \forall\vec{\mathbf{i}_{m}}(\beta_{m}\leq^{T_{m}}_{T^{\prime}_{m}}\gamma_{m})\\ \end{array}\right.$

is replaced by $\left\{\begin{array}[]{ll}\forall\vec{\mathbf{i}_{1}}(\beta_{1}((\alpha_{1}\land\ldots\land\alpha_{n})/p)\leq^{T_{1}}_{T^{\prime}_{1}}\gamma_{1}((\alpha_{1}\land\ldots\land\alpha_{n})/p))\\ \vdots\\ \forall\vec{\mathbf{i}_{m}}(\beta_{m}((\alpha_{1}\land\ldots\land\alpha_{n})/p)\leq^{T_{m}}_{T^{\prime}_{m}}\gamma_{m}((\alpha_{1}\land\ldots\land\alpha_{n})/p))\\ \end{array}\right.$
where:
1. i.
  
  $p,\vec{\mathbf{i}_{1}},\ldots,\vec{\mathbf{i}_{m}}$ do not occur in $\alpha_{1},\ldots,\alpha_{n}$ ;
2. ii.
  
  Each $\beta_{i}$ is negative in $p$ , and each $\gamma_{i}$ positive in $p$ , for $1\leq i\leq m$ .
3. iii.
  
  Each $\alpha_{i}$ is pure and contains no contextual modalities $\Box,\Diamond,\blacksquare,\Diamondblack$ .

3.

Output: If in the previous stage, for some $\{\mathbf{i}_{0}\leq\varphi_{i},\psi_{i}\leq\neg\mathbf{i}_{1}\}$ , the algorithm gets stuck, i.e. some proposition variables cannot be eliminated by the application of the reduction rules, then the algorithm halts and output “failure”. Otherwise, each initial tuple $\{\mathbf{i}_{0}\leq\varphi_{i},\psi_{i}\leq\neg\mathbf{i}_{1}\}$ of inequalities after the first approximation has been reduced to a set of pure (universally quantified) inequalities $\mathsf{Reduce}(\varphi_{i}\leq\psi_{i})$ , and then the output is a set of quasi-(universally quantified) inequalities $\{\&\mathsf{Reduce}(\varphi_{i}\leq\psi_{i})\Rightarrow\mathbf{i}_{0}\leq\neg\mathbf{i}_{1}:\varphi_{i}\leq\psi_{i}\in\mathsf{Preprocess}(\varphi\leq\psi)\}$ , where $\&$ is the big meta-conjunction in quasi-inequalities. Then the algorithm use the standard translation to transform the quasi-(universally quantified) inequalities into first-order formulas.

3.4 Soundness of $\mathsf{ALBA}^{\mathsf{SML}}$

In the present subsection, we will prove the soundness of the algorithm $\mathsf{ALBA}^{\mathsf{SML}}$ with respect to Kripke frames. The basic proof structure is similar to [10].

Theorem 3.1 (Soundness).

If $\mathsf{ALBA}^{\mathsf{SML}}$ runs successfully on $\varphi\leq\psi$ and outputs $\mathsf{FO}(\varphi\leq\psi)$ , then for any Kripke frame $\mathbb{F}=(W,R_{0})$ ,

\mathbb{F}\Vdash\varphi\leq\psi\mbox{ iff }\mathbb{F}\models\mathsf{FO}(\varphi\leq\psi).

Proof.

The proof goes similarly to [10, Theorem 8.1]. Let $\varphi_{i}\leq\psi_{i}$ , $1\leq i\leq n$ denote the inequalities produced by preprocessing $\varphi\leq\psi$ after Stage 1, and $\{\mathbf{i}_{0}\leq\varphi_{i},\psi_{i}\leq\neg\mathbf{i}_{1}\}$ denote the inequalities after the first-approximation rule, $\mathsf{Reduce}(\varphi_{i}\leq\psi_{i})$ denote the set of pure (universally quantified) inequalities after Stage 2, and $\mathsf{FO}(\varphi\leq\psi)$ denote the standard translation of the quasi-(universally quantified) inequalities into first-order formulas, then we have the following chain of equivalences:

It suffices to show the equivalence from (1) to (5) given below:

	$\displaystyle\mathbb{F}\Vdash\varphi\leq\psi$		(1)
	$\displaystyle\mathbb{F}\Vdash\varphi_{i}\leq\psi_{i},\mbox{ for all }1\leq i\leq n$		(2)
	$\displaystyle\mathbb{F}\Vdash(\mathbf{i}_{0}\leq^{\varnothing}_{\varnothing}\varphi_{i}\ \&\ \psi_{i}\leq^{\varnothing}_{\varnothing}\neg\mathbf{i}_{1})\Rightarrow\mathbf{i}_{0}\leq\neg\mathbf{i}_{1}\mbox{ for all }1\leq i\leq n$		(3)
	$\displaystyle\mathbb{F}\Vdash\mathsf{Reduce}(\varphi_{i}\leq\psi_{i})\Rightarrow\mathbf{i}_{0}\leq\neg\mathbf{i}_{1}\mbox{ for all }1\leq i\leq n$		(4)
	$\displaystyle\mathbb{F}\Vdash\mathsf{FO}(\varphi\leq\psi)$		(5)

•

The equivalence between (1) and (2) follows from Proposition 12;
•

the equivalence between (2) and (3) follows from Proposition 13;
•

the equivalence between (3) and (4) follows from Propositions 14, 20, 24, 25;
•

the equivalence between (4) and (5) follows from Proposition 7.

∎

In the remainder of this subsection, we prove the soundness of the rules in Stage 1, 2 and 3.

Proposition 12 (Soundness of the rules in Stage 1).

For the distribution rules, the splitting rules and the monotone and antitone variable-elimination rules, they are sound in both directions in $\mathbb{F}$ , i.e., it is sound from the premise to the conclusion and the other way round.

Proof.

For the soundness of the distribution rules, it follows from the fact that the following equivalences are valid in $\mathbb{F}$ :

•

$\Diamond(\alpha\lor\beta)\leftrightarrow\Diamond\alpha\lor\Diamond\beta$ ;
•

$\Diamondblack(\alpha\lor\beta)\leftrightarrow\Diamondblack\alpha\lor\Diamondblack\beta$ ;
•

$\neg(\alpha\lor\beta)\leftrightarrow\neg\alpha\land\neg\beta$ ;
•

$(\alpha\lor\beta)\land\gamma\leftrightarrow(\alpha\land\gamma)\lor(\beta\land\gamma)$ ;
•

$\alpha\land(\beta\lor\gamma)\leftrightarrow(\alpha\land\beta)\lor(\alpha\land\gamma)$ ;
•

$((\alpha\lor\beta)\to\gamma)\leftrightarrow((\alpha\to\gamma)\land(\beta\to\gamma))$ ;
•

$\Box(\alpha\land\beta)\leftrightarrow\Box\alpha\land\Box\beta$ ;
•

$\blacksquare(\alpha\land\beta)\leftrightarrow\blacksquare\alpha\land\blacksquare\beta$ ;
•

$\neg(\alpha\land\beta)\leftrightarrow\neg\alpha\lor\neg\beta$ ;
•

$(\alpha\land\beta)\lor\gamma\leftrightarrow(\alpha\lor\gamma)\land(\beta\lor\gamma)$ ;
•

$\alpha\lor(\beta\land\gamma)\leftrightarrow(\alpha\lor\beta)\land(\alpha\lor\gamma)$ ;
•

$(\alpha\to\beta\land\gamma)\leftrightarrow(\alpha\to\beta)\land(\alpha\to\gamma)$ .

For the soundness of the splitting rules, it follows from the following fact:

\mathbb{F}\Vdash\alpha\leq\beta\land\gamma\mbox{ iff }(\mathbb{F}\Vdash\alpha\leq\beta\mbox{ and }\mathbb{F}\Vdash\alpha\leq\gamma);

\mathbb{F}\Vdash\alpha\lor\beta\leq\gamma\mbox{ iff }(\mathbb{F}\Vdash\alpha\leq\gamma\mbox{ and }\mathbb{F}\Vdash\beta\leq\gamma).

For the soundness of the monotone and antitone variable elimination rules, we show the soundness for the first rule. Suppose $\alpha(p)$ is negative in $p$ and $\beta$ is positive in $p$ .

If $\mathbb{F}\Vdash\alpha(p)\leq\beta(p)$ , then for all valuations $V$ , $(\mathbb{F},V)\Vdash\alpha(p)\leq\beta(p)$ , thus for the valuation $V^{p}_{\varnothing}$ such that $V^{p}_{\varnothing}$ is the same as $V$ except that $V^{p}_{\varnothing}(p)=\varnothing$ , $(\mathbb{F},V^{p}_{\varnothing})\Vdash\alpha(p)\leq\beta(p)$ , therefore $(\mathbb{F},V^{p}_{\varnothing})\Vdash\alpha(\bot)\leq\beta(\bot)$ , thus $(\mathbb{F},V)\Vdash\alpha(\bot)\leq\beta(\bot)$ , so $\mathbb{F}\Vdash\alpha(\bot)\leq\beta(\bot)$ .

For the other direction, suppose $\mathbb{F}\vDash\alpha(\bot)\leq\beta(\bot)$ , then by the fact that $\alpha(p)$ is negative in $p$ and $\beta$ is positive in $p$ , we have that $\mathbb{F}\vDash\alpha(p)\leq\alpha(\bot)$ and $\mathbb{F}\vDash\beta(\bot)\leq\beta(p)$ , therefore $\mathbb{F}\vDash\alpha(p)\leq\beta(p)$ .

The soundness of the other rule is similar. ∎

Proposition 13.

(2) and (3) are equivalent, i.e. the first-approximation rule is sound in $\mathbb{F}$ .

Proof.

(2) $\Rightarrow$ (3): Suppose $\mathbb{F}\Vdash\varphi_{i}\leq\psi_{i}$ . Then for any valuation $V$ on $\mathbb{F}$ , if $(\mathbb{F},V)\Vdash\mathbf{i}_{0}\leq^{\varnothing}_{\varnothing}\varphi_{i}$ and $(\mathbb{F},V)\Vdash\psi_{i}\leq^{\varnothing}_{\varnothing}\neg\mathbf{i}_{1}$ , then $(\mathbb{F},V),V(\mathbf{i}_{0})\Vdash\varphi_{i}$ and $(\mathbb{F},V),V(\mathbf{i}_{1})\nVdash\psi_{i}$ , so by $\mathbb{F}\Vdash\varphi_{i}\leq\psi_{i}$ we have $(\mathbb{F},V),V(\mathbf{i}_{0})\Vdash\psi_{i}$ , so $\mathbf{i}_{0}\neq\mathbf{i}_{1}$ , so $(\mathbb{F},V)\Vdash\mathbf{i}_{0}\leq\neg\mathbf{i}_{1}$ .

(3) $\Rightarrow$ (2): Suppose $\mathbb{F}\Vdash(\mathbf{i}_{0}\leq^{\varnothing}_{\varnothing}\varphi_{i}\ \&\ \psi_{i}\leq^{\varnothing}_{\varnothing}\neg\mathbf{i}_{1})\Rightarrow\mathbf{i}_{0}\leq\neg\mathbf{i}_{1}$ . Then if $\mathbb{F}\nVdash\varphi_{i}\leq\psi_{i}$ , then there is a valuation $V$ on $\mathbb{F}$ and a $w\in W$ such that $(\mathbb{F},V),w\Vdash\varphi_{i}$ and $(\mathbb{F},V),w\nVdash\psi_{i}$ . Then by taking $V^{\mathbf{i}_{0},\mathbf{i}_{1}}_{w,w}$ to be the valuation which is the same as $V$ except that $V^{\mathbf{i}_{0},\mathbf{i}_{1}}_{w,w}(\mathbf{i}_{0})=V^{\mathbf{i}_{0},\mathbf{i}_{1}}_{w,w}(\mathbf{i}_{1})=\{w\}$ , then since $\mathbf{i}_{0},\mathbf{i}_{1}$ do not occur in $\varphi_{i}$ and $\psi_{i}$ , we have that $(\mathbb{F},V^{\mathbf{i}_{0},\mathbf{i}_{1}}_{w,w}),w\Vdash\varphi_{i}$ and $(\mathbb{F},V^{\mathbf{i}_{0},\mathbf{i}_{1}}_{w,w}),w\nVdash\psi_{i}$ , therefore $(\mathbb{F},V^{\mathbf{i}_{0},\mathbf{i}_{1}}_{w,w})\Vdash\mathbf{i}_{0}\leq^{\varnothing}_{\varnothing}\varphi_{i}$ and $(\mathbb{F},V^{\mathbf{i}_{0},\mathbf{i}_{1}}_{w,w})\Vdash\psi_{i}\leq^{\varnothing}_{\varnothing}\neg\mathbf{i}_{1}$ , by $\mathbb{F}\Vdash(\mathbf{i}_{0}\leq^{\varnothing}_{\varnothing}\varphi_{i}\ \&\ \psi_{i}\leq^{\varnothing}_{\varnothing}\neg\mathbf{i}_{1})\Rightarrow\mathbf{i}_{0}\leq\neg\mathbf{i}_{1}$ , we have that $(\mathbb{F},V^{\mathbf{i}_{0},\mathbf{i}_{1}}_{w,w})\Vdash\mathbf{i}_{0}\leq\neg\mathbf{i}_{1}$ , so $(\mathbb{F},V^{\mathbf{i}_{0},\mathbf{i}_{1}}_{w,w}),w\Vdash\mathbf{i}_{0}$ implies that $(\mathbb{F},V^{\mathbf{i}_{0},\mathbf{i}_{1}}_{w,w}),w\Vdash\neg\mathbf{i}_{1}$ , a contradiction. So $\mathbb{F}\Vdash\varphi_{i}\leq\psi_{i}$ . ∎

The next step is to show the soundness of Stage 2, for which it suffices to show the soundness of each rule in each substage.

Proposition 14.

The splitting rules, the approximation rules for $\Diamond,\Box,\Diamondblack,\blacksquare,\to$ , the residuation rules for $\neg$ in Substage 1 are sound in $\mathbb{F}$ .

Proof.

By Lemma 15, 16, 17, 18 and 19 below. ∎

Lemma 15.

The splitting rules in Substage 1 and Substage 2 are sound in $\mathbb{F}$ .

Proof.

For the soundness of the splitting rules, it follows from the fact that for any Kripke frame $\mathbb{F}=(W,R_{0})$ , any valuation $V$ on $\mathbb{F}$ ,

•

$(\mathbb{F},V)\Vdash\alpha\leq^{S}_{S^{\prime}}\beta\land\gamma\mbox{ iff }((\mathbb{F},V)\Vdash\alpha\leq^{S}_{S^{\prime}}\beta\mbox{ and }(\mathbb{F},V)\Vdash\alpha\leq^{S}_{S^{\prime}}\gamma),$
•

$(\mathbb{F},V)\Vdash\alpha\lor\beta\leq^{S}_{S^{\prime}}\gamma\mbox{ iff }((\mathbb{F},V)\Vdash\alpha\leq^{S}_{S^{\prime}}\gamma\mbox{ and }(\mathbb{F},V)\Vdash\beta\leq^{S}_{S^{\prime}}\gamma).$

∎

Lemma 16.

The approximation rules for $\Diamond,\Box$ in Substage 1 are sound in $\mathbb{F}$ .

Proof.

We prove for $\Diamond$ , the case for $\Box$ is similar. For the soundness of the approximation rule for $\Diamond$ , it suffices to show that for any Kripke frame $\mathbb{F}=(W,R_{0})$ , any valuation $V$ on $\mathbb{F}$ ,

1.

if $(\mathbb{F},V)\Vdash\mathbf{i}\leq^{S}_{S^{\prime}}\Diamond\alpha$ , then there is a valuation $V^{\mathbf{j}}$ such that $V^{\mathbf{j}}$ is the same as $V$ except $V^{\mathbf{j}}(\mathbf{j})$ , and $(\mathbb{F},V^{\mathbf{j}})\Vdash\mathbf{i}\leq^{S}_{S^{\prime}}\Diamond^{S^{\prime}}\mathbf{j}$ and $(\mathbb{F},V^{\mathbf{j}})\Vdash\mathbf{j}\leq^{S^{\prime}}_{S^{\prime}}\alpha$ ;
2.

if $(\mathbb{F},V)\Vdash\mathbf{i}\leq^{S}_{S^{\prime}}\Diamond^{S^{\prime}}\mathbf{j}$ and $(\mathbb{F},V)\Vdash\mathbf{j}\leq^{S^{\prime}}_{S^{\prime}}\alpha$ , then $(\mathbb{F},V)\Vdash\mathbf{i}\leq^{S}_{S^{\prime}}\Diamond\alpha$ .

For item 1, if $(\mathbb{F},V)\Vdash\mathbf{i}\leq^{S}_{S^{\prime}}\Diamond\alpha$ , then $(W,(R_{0}\setminus S^{\prime}),V),V(\mathbf{i})\Vdash\Diamond\alpha$ , therefore there exists a $w\in W$ such that $(V(\mathbf{i}),w)\in(R_{0}\setminus S^{\prime})$ and $(W,(R_{0}\setminus S^{\prime}),V),w\Vdash\alpha$ . Now take $V^{\mathbf{j}}$ such that $V^{\mathbf{j}}$ is the same as $V$ except that $V^{\mathbf{j}}(\mathbf{j})=\{w\}$ , then $(V^{\mathbf{j}}(\mathbf{i}),V^{\mathbf{j}}(\mathbf{j}))\in(R_{0}\setminus S^{\prime})$ , so $(\mathbb{F},V^{\mathbf{j}})\Vdash\mathbf{i}\leq^{S}_{S^{\prime}}\Diamond^{S^{\prime}}\mathbf{j}$ and $(\mathbb{F},V^{\mathbf{j}})\Vdash\mathbf{j}\leq^{S^{\prime}}_{S^{\prime}}\alpha$ .

For item 2, suppose $(\mathbb{F},V)\Vdash\mathbf{i}\leq^{S}_{S^{\prime}}\Diamond^{S^{\prime}}\mathbf{j}$ and $(\mathbb{F},V)\Vdash\mathbf{j}\leq^{S^{\prime}}_{S^{\prime}}\alpha$ . Then $(V(\mathbf{i}),V(\mathbf{j}))\in(R_{0}\setminus S^{\prime})$ and $(W,(R_{0}\setminus S^{\prime}),V),V(\mathbf{j})\Vdash\alpha$ , so $(W,(R_{0}\setminus S^{\prime}),V),V(\mathbf{i})\Vdash\Diamond\alpha$ , therefore $(\mathbb{F},V)\Vdash\mathbf{i}\leq^{S}_{S^{\prime}}\Diamond\alpha$ . ∎

Lemma 17.

The approximation rules for $\Diamondblack,\blacksquare$ in Substage 1 are sound in $\mathbb{F}$ .

Proof.

We prove for $\Diamondblack$ , the case for $\blacksquare$ is similar. For the soundness of the approximation rule for $\Diamondblack$ , it suffices to show that for any Kripke frame $\mathbb{F}=(W,R_{0})$ , any valuation $V$ on $\mathbb{F}$ ,

1.

if $(\mathbb{F},V)\Vdash\mathbf{i}\leq^{S}_{S^{\prime}}\Diamondblack\alpha$ , then there is a valuation $V^{\mathbf{i}_{m0},\mathbf{i}_{m1}}$ such that $V^{\mathbf{i}_{m0},\mathbf{i}_{m1}}$ is the same as $V$ except $V^{\mathbf{i}_{m0},\mathbf{i}_{m1}}(\mathbf{i}_{m0})$ and $V^{\mathbf{i}_{m0},\mathbf{i}_{m1}}(\mathbf{i}_{m1})$ , and $(\mathbb{F},V^{\mathbf{i}_{m0},\mathbf{i}_{m1}})\Vdash\mathbf{i}_{m0}\leq^{S^{\prime}}_{S^{\prime}}\Diamond^{S^{\prime}}\mathbf{i}_{m1}$ and $(\mathbb{F},V^{\mathbf{i}_{m0},\mathbf{i}_{m1}})\Vdash\mathbf{i}\leq^{S}_{S^{\prime}\cup\{(\mathbf{i}_{m0},\mathbf{i}_{m1})\}}\alpha$ ;
2.

if $(\mathbb{F},V)\Vdash\mathbf{i}_{m0}\leq^{S^{\prime}}_{S^{\prime}}\Diamond^{S^{\prime}}\mathbf{i}_{m1}$ and $(\mathbb{F},V)\Vdash\mathbf{i}\leq^{S}_{S^{\prime}\cup\{(\mathbf{i}_{m0},\mathbf{i}_{m1})\}}\alpha$ , then $(\mathbb{F},V)\Vdash\mathbf{i}\leq^{S}_{S^{\prime}}\Diamondblack\alpha$ .

For item 1, if $(\mathbb{F},V)\Vdash\mathbf{i}\leq^{S}_{S^{\prime}}\Diamondblack\alpha$ , then $(W,(R_{0}\setminus S^{\prime}),V),V(\mathbf{i})\Vdash\Diamondblack\alpha$ , therefore there are $(w,v)\in(R_{0}\setminus S^{\prime})$ such that $(W,((R_{0}\setminus S^{\prime})\setminus\{(w,v)\}),V),V(\mathbf{i})\Vdash\alpha$ . Now take $V^{\mathbf{i}_{m0},\mathbf{i}_{m1}}$ such that $V^{\mathbf{i}_{m0},\mathbf{i}_{m1}}$ is the same as $V$ except $V^{\mathbf{i}_{m0},\mathbf{i}_{m1}}(\mathbf{i}_{m0})=\{w\}$ and $V^{\mathbf{i}_{m0},\mathbf{i}_{m1}}(\mathbf{i}_{m1})=\{v\}$ , then by $(w,v)\in(R_{0}\setminus S^{\prime})$ , we have that $(W,R_{0},V^{\mathbf{i}_{m0},\mathbf{i}_{m1}})\Vdash\mathbf{i}_{m0}\leq^{S^{\prime}}_{S^{\prime}}\Diamond^{S^{\prime}}\mathbf{i}_{m1}$ , and from $(W,((R_{0}\setminus S^{\prime})\setminus\{(w,v)\}),V),V(\mathbf{i})\Vdash\alpha$ we have that $(W,((R_{0}\setminus S^{\prime})\setminus\{(V^{\mathbf{i}_{m0},\mathbf{i}_{m1}}(\mathbf{i}_{m0}),V^{\mathbf{i}_{m0},\mathbf{i}_{m1}}(\mathbf{i}_{m1}))\}),V^{\mathbf{i}_{m0},\mathbf{i}_{m1}}),V^{\mathbf{i}_{m0},\mathbf{i}_{m1}}(\mathbf{i})\Vdash\alpha$ , so $(\mathbb{F},V^{\mathbf{i}_{m0},\mathbf{i}_{m1}})\Vdash\mathbf{i}\leq^{S}_{S^{\prime}\cup\{(\mathbf{i}_{m0},\mathbf{i}_{m1})\}}\alpha$ .

For item 2, if $(\mathbb{F},V)\Vdash\mathbf{i}_{m0}\leq^{S^{\prime}}_{S^{\prime}}\Diamond^{S^{\prime}}\mathbf{i}_{m1}$ and $(\mathbb{F},V)\Vdash\mathbf{i}\leq^{S}_{S^{\prime}\cup\{(\mathbf{i}_{m0},\mathbf{i}_{m1})\}}\alpha$ , then $(V(\mathbf{i}_{m0}),V(\mathbf{i}_{m1}))\in(R_{0}\setminus S^{\prime})$ , and $(W,(R_{0}\setminus(S^{\prime}\cup\{(\mathbf{i}_{m0},\mathbf{i}_{m1})\})),V),V(\mathbf{i})\Vdash\alpha$ , so $(W,(R_{0}\setminus S^{\prime}),V),V(\mathbf{i})\Vdash\Diamondblack\alpha$ , therefore $(\mathbb{F},V)\Vdash\mathbf{i}\leq^{S}_{S^{\prime}}\Diamondblack\alpha$ . ∎

Lemma 18.

The approximation rule for $\to$ in Substage 1 is sound in $\mathbb{F}$ .

Proof.

For the soundness of the approximation rule for $\to$ , it suffices to show that for any Kripke frame $\mathbb{F}=(W,R_{0})$ , any valuation $V$ on $\mathbb{F}$ ,

1.

if $(\mathbb{F},V)\Vdash\alpha\to\beta\leq^{S}_{S^{\prime}}\neg\mathbf{i}$ , then there is a valuation $V^{\mathbf{j},\mathbf{k}}$ such that $V^{\mathbf{j},\mathbf{k}}$ is the same as $V$ except $V^{\mathbf{j},\mathbf{k}}(\mathbf{j})$ and $V^{\mathbf{j},\mathbf{k}}(\mathbf{k})$ , and $(\mathbb{F},V^{\mathbf{j},\mathbf{k}})\Vdash\mathbf{j}\leq^{S}_{S}\alpha$ , $(\mathbb{F},V^{\mathbf{j},\mathbf{k}})\Vdash\beta\leq^{S}_{S}\neg\mathbf{k}$ and $(\mathbb{F},V^{\mathbf{j},\mathbf{k}})\Vdash\mathbf{j}\to\neg\mathbf{k}\leq^{S}_{S^{\prime}}\neg\mathbf{i}$ ;
2.

if $(\mathbb{F},V)\Vdash\mathbf{j}\leq^{S}_{S}\alpha$ , $(\mathbb{F},V)\Vdash\beta\leq^{S}_{S}\neg\mathbf{k}$ and $(\mathbb{F},V)\Vdash\mathbf{j}\to\neg\mathbf{k}\leq^{S}_{S^{\prime}}\neg\mathbf{i}$ , then $(\mathbb{F},V)\Vdash\alpha\to\beta\leq^{S}_{S^{\prime}}\neg\mathbf{i}$ .

For item 1, if $(\mathbb{F},V)\Vdash\alpha\to\beta\leq^{S}_{S^{\prime}}\neg\mathbf{i}$ , then $(W,(R_{0}\setminus S),V),V(\mathbf{i})\Vdash\alpha$ and $(W,(R_{0}\setminus S),V),V(\mathbf{i})\Vdash\neg\beta$ . Now take $V^{\mathbf{j},\mathbf{k}}$ such that $V^{\mathbf{j},\mathbf{k}}$ is the same as $V$ except that $V^{\mathbf{j},\mathbf{k}}(\mathbf{j})=V^{\mathbf{j},\mathbf{k}}(\mathbf{k})=V(\mathbf{i})$ , we have that $(W,(R_{0}\setminus S),V^{\mathbf{j},\mathbf{k}}),V^{\mathbf{j},\mathbf{k}}(\mathbf{j})\Vdash\alpha$ and $(W,(R_{0}\setminus S),V^{\mathbf{j},\mathbf{k}}),V^{\mathbf{j},\mathbf{k}}(\mathbf{k})\Vdash\neg\beta$ , so $(\mathbb{F},V^{\mathbf{j},\mathbf{k}})\Vdash\mathbf{j}\leq^{S}_{S}\alpha$ , $(\mathbb{F},V^{\mathbf{j},\mathbf{k}})\Vdash\beta\leq^{S}_{S}\neg\mathbf{k}$ . Since $V^{\mathbf{j},\mathbf{k}}(\mathbf{j})=V^{\mathbf{j},\mathbf{k}}(\mathbf{k})=V^{\mathbf{j},\mathbf{k}}(\mathbf{i})=V(\mathbf{i})$ , it is easy to see that $V^{\mathbf{j},\mathbf{k}}(\mathbf{j}\to\neg\mathbf{k})=V^{\mathbf{j},\mathbf{k}}(\neg\mathbf{i})$ , so $(\mathbb{F},V^{\mathbf{j},\mathbf{k}})\Vdash\mathbf{j}\to\neg\mathbf{k}\leq^{S}_{S^{\prime}}\neg\mathbf{i}$ .

For item 2, if $(\mathbb{F},V)\Vdash\mathbf{j}\leq^{S}_{S}\alpha$ , $(\mathbb{F},V)\Vdash\beta\leq^{S}_{S}\neg\mathbf{k}$ and $(\mathbb{F},V)\Vdash\mathbf{j}\to\neg\mathbf{k}\leq^{S}_{S^{\prime}}\neg\mathbf{i}$ , then $V(\mathbf{j}\to\neg\mathbf{k})\subseteq V(\neg\mathbf{i})$ , so $V(\mathbf{i})\subseteq V(\mathbf{j}\land\mathbf{k})$ , since $\mathbf{i},\mathbf{j},\mathbf{k}$ are nominals, there interpretations are singletons, so $V(\mathbf{i})=V(\mathbf{j})=V(\mathbf{k})$ . Now from $(\mathbb{F},V)\Vdash\mathbf{j}\leq^{S}_{S}\alpha$ we have that $(W,(R_{0}\setminus S),V),V(\mathbf{j})\Vdash\alpha$ , and from $(\mathbb{F},V)\Vdash\beta\leq^{S}_{S}\neg\mathbf{k}$ we have that $(W,(R_{0}\setminus S),V),V(\mathbf{k})\Vdash\neg\beta$ , so $(W,(R_{0}\setminus S),V),V(\mathbf{i})\Vdash\alpha$ and $(W,(R_{0}\setminus S),V),V(\mathbf{i})\Vdash\neg\beta$ , so $(\mathbb{F},V)\Vdash\alpha\to\beta\leq^{S}_{S^{\prime}}\neg\mathbf{i}$ .

∎

Lemma 19.

The residuation rules for $\neg$ in Substage 1 and 2 are sound in $\mathbb{F}$ .

Proof.

It is easy to see that the residuation rules for $\neg$ in Substage 1 are special cases of the residuation rules for $\neg$ in Substage 2 (modulo double negation elimination). Now we only prove it for the residuation rule in Substage 2 where negation symbols occur on the right-hand side of the inequalities, the other rule is similar.

For the soundness of the residuation rule for $\neg$ , it suffices to show that for any Kripke frame $\mathbb{F}=(W,R_{0})$ , any valuation $V$ on $\mathbb{F}$ , $(\mathbb{F},V)\Vdash\alpha\leq^{S}_{S^{\prime}}\neg\beta$ iff $(\mathbb{F},V)\Vdash\beta\leq^{S^{\prime}}_{S}\neg\alpha$ . Indeed, it follows from the following equivalence:

	$(\mathbb{F},V)\Vdash\alpha\leq^{S}_{S^{\prime}}\neg\beta$
iff	for all $w\in W$ , if $(W,(R_{0}\setminus S),V),w\Vdash\alpha$ , then $(W,(R_{0}\setminus S^{\prime}),V),w\nVdash\beta$
iff	for all $w\in W$ , if $(W,(R_{0}\setminus S^{\prime}),V),w\Vdash\beta$ , then $(W,(R_{0}\setminus S),V),w\nVdash\alpha$
iff	$(\mathbb{F},V)\Vdash\beta\leq^{S^{\prime}}_{S}\neg\alpha$ .

∎

Proposition 20.

The splitting rules, the residuation rules for $\neg,\Diamond,\Box,\Diamondblack,\blacksquare$ , the second splitting rule in Substage 2 are sound in $\mathbb{F}$ .

Proof.

By Lemma 15, 19, 21, 22 and 23. ∎

Lemma 21.

The residuation rules for $\Diamond,\Box$ in Substage 2 are sound in $\mathbb{F}$ .

Proof.

We prove it for $\Diamond$ , and the rule for $\Box$ is similar.

To show the soundness of the residuation rule for $\Diamond$ in Substage 2, it suffices to show that for any Kripke frame $\mathbb{F}=(W,R_{0})$ , any valuation $V$ on $\mathbb{F}$ , $(\mathbb{F},V)\Vdash\Diamond\alpha\leq^{S}_{S^{\prime}}\beta$ iff $(\mathbb{F},V)\Vdash\alpha\leq^{S}_{S^{\prime}}(\Box^{S})^{-1}\beta$ .

$\Rightarrow$ : if $(\mathbb{F},V)\Vdash\Diamond\alpha\leq^{S}_{S^{\prime}}\beta$ , then for all $w\in W$ , if $(W,(R_{0}\setminus S),V),w\Vdash\Diamond\alpha$ , then $(W,(R_{0}\setminus S^{\prime}),V),w\Vdash\beta$ . Our aim is to show that for all $v\in W$ , if $(W,(R_{0}\setminus S),V),v\Vdash\alpha$ , then $(W,(R_{0}\setminus S^{\prime}),V),v\Vdash(\Box^{S})^{-1}\beta$ .

Consider any $v\in W$ such that $(W,(R_{0}\setminus S),V),v\Vdash\alpha$ . Then for any $u\in W$ such that $(u,v)\in(R_{0}\setminus S)$ , $(W,(R_{0}\setminus S),V),u\Vdash\Diamond\alpha$ . Since $(\mathbb{F},V)\Vdash\Diamond\alpha\leq^{S}_{S^{\prime}}\beta$ , we have that $(W,(R_{0}\setminus S^{\prime}),V),u\Vdash\beta$ , so for any $u\in W$ such that $(v,u)\in(R_{0}\setminus S)^{-1}$ , $(W,(R_{0}\setminus S^{\prime}),V),u\Vdash\beta$ , so $(W,(R_{0}\setminus S^{\prime}),V),v\Vdash(\Box^{S})^{-1}\beta$ .

$\Leftarrow$ : if $(\mathbb{F},V)\Vdash\alpha\leq^{S}_{S^{\prime}}(\Box^{S})^{-1}\beta$ , then for all $w\in W$ , if $(W,(R_{0}\setminus S),V),w\Vdash\alpha$ , then $(W,(R_{0}\setminus S^{\prime}),V),w\Vdash(\Box^{S})^{-1}\beta$ . Our aim is to show that for all $v\in W$ , if $(W,(R_{0}\setminus S),V),v\Vdash\Diamond\alpha$ , then $(W,(R_{0}\setminus S^{\prime}),V),v\Vdash\beta$ .

Now assume that $(W,(R_{0}\setminus S),V),v\Vdash\Diamond\alpha$ . Then there is a $u\in W$ such that $(v,u)\in(R_{0}\setminus S)$ and $(W,(R_{0}\setminus S),V),u\Vdash\alpha$ . By $(\mathbb{F},V)\Vdash\alpha\leq^{S}_{S^{\prime}}(\Box^{S})^{-1}\beta$ , we have that $(W,(R_{0}\setminus S^{\prime}),V),u\Vdash(\Box^{S})^{-1}\beta$ . Therefore, for $v\in W$ , we have $(u,v)\in(R_{0}\setminus S)^{-1}$ , thus $(W,(R_{0}\setminus S^{\prime}),V),v\Vdash\beta$ . ∎

Lemma 22.

The residuation rules for $\Diamondblack,\blacksquare$ in Substage 2 are sound in $\mathbb{F}$ .

Proof.

We prove it for $\blacksquare$ , and the rule for $\Diamondblack$ is similar.

For the residuation rule for $\blacksquare$ , it suffices to show that for any Kripke frame $\mathbb{F}=(W,R_{0})$ , any valuation $V$ on $\mathbb{F}$ , $(\mathbb{F},V)\Vdash\alpha\leq^{S}_{S^{\prime}}\blacksquare\beta$ iff $(\mathbb{F},V)\Vdash\forall\mathbf{i}_{m0}\forall\mathbf{i}_{m1}(\mathbf{i}_{m0}\leq^{S^{\prime}}_{S^{\prime}}\Diamond^{S^{\prime}}\mathbf{i}_{m1}\ \Rightarrow\ \alpha\leq^{S}_{S^{\prime}\cup\{(\mathbf{i}_{m0},\mathbf{i}_{m1})\}}\beta)$ . Indeed,

$(\mathbb{F},V)\Vdash\forall\mathbf{i}_{m0}\forall\mathbf{i}_{m1}(\mathbf{i}_{m0}\leq^{S^{\prime}}_{S^{\prime}}\Diamond^{S^{\prime}}\mathbf{i}_{m1}\ \Rightarrow\ \alpha\leq^{S}_{S^{\prime}\cup\{(\mathbf{i}_{m0},\mathbf{i}_{m1})\}}\beta)$ ,

iff for all $w,v\in W$ , if $(w,v)\in(R_{0}\setminus S^{\prime})$ then $(W,R_{0},V^{\mathbf{i}_{m0},\mathbf{i}_{m1}}_{w,v})\Vdash\alpha\leq^{S}_{S^{\prime}\cup\{(\mathbf{i}_{m0},\mathbf{i}_{m1})\}}\beta$ , where $V^{\mathbf{i}_{m0},\mathbf{i}_{m1}}_{w,v}$ is the same as $V$ except that $V^{\mathbf{i}_{m0},\mathbf{i}_{m1}}_{w,v}(\mathbf{i}_{m0})=\{w\}$ , $V^{\mathbf{i}_{m0},\mathbf{i}_{m1}}_{w,v}(\mathbf{i}_{m1})=\{v\}$ ,

iff for all $u,v,w\in W$ , if $(w,v)\in(R_{0}\setminus S^{\prime})$ and $(W,(R_{0}\setminus S),V^{\mathbf{i}_{m0},\mathbf{i}_{m1}}_{w,v}),u\Vdash\alpha$ , then $(W,(R_{0}\setminus(S^{\prime}\cup\{(\mathbf{i}_{m0},\mathbf{i}_{m1})\})),V^{\mathbf{i}_{m0},\mathbf{i}_{m1}}_{w,v}),u\Vdash\beta$ ,

iff for all $u\in W$ , if $(W,(R_{0}\setminus S),V^{\mathbf{i}_{m0},\mathbf{i}_{m1}}_{w,v}),u\Vdash\alpha$ , then for all $v,w\in W$ , if $(w,v)\in(R_{0}\setminus S^{\prime})$ then $(W,(R_{0}\setminus(S^{\prime}\cup\{(\mathbf{i}_{m0},\mathbf{i}_{m1})\})),V^{\mathbf{i}_{m0},\mathbf{i}_{m1}}_{w,v}),u\Vdash\beta$ ,

iff for all $u\in W$ , if $(W,(R_{0}\setminus S),V^{\mathbf{i}_{m0},\mathbf{i}_{m1}}_{w,v}),u\Vdash\alpha$ , then $(W,(R_{0}\setminus S^{\prime}),V^{\mathbf{i}_{m0},\mathbf{i}_{m1}}_{w,v}),u\Vdash\blacksquare\beta$ ,

iff for all $u\in W$ , if $(W,(R_{0}\setminus S),V),u\Vdash\alpha$ , then $(W,(R_{0}\setminus S^{\prime}),V),u\Vdash\blacksquare\beta$ (since $\mathbf{i}_{m0}$ and $\mathbf{i}_{m1}$ do not occur in $\alpha$ and $\beta$ ),

iff $(\mathbb{F},V)\Vdash\alpha\leq^{S}_{S^{\prime}}\blacksquare\beta$ . ∎

Lemma 23.

The second splitting rule in Substage 2 is sound in $\mathbb{F}$ .

Proof.

It follows immediately from the meta-equivalence that $\forall x\forall y(\alpha\rightarrow\beta\land\gamma)\leftrightarrow\forall x\forall y(\alpha\rightarrow\beta)\land\forall x\forall y(\alpha\rightarrow\gamma)$ . ∎

Proposition 24.

The packing rules in Substage 3 are sound in $\mathbb{F}$ .

Proof.

We only prove the soundness of the first packing rule, the others are similar.

It is easy to see that in the mega-inequality of the premise and in the conclusion, contextual connectives $\Box,\Diamond,\blacksquare,\Diamondblack$ do not occur, so we can ignore the superscripts and subscripts in the inequalities occuring in the rule.

Therefore, for any Kripke frame $\mathbb{F}=(W,R_{0})$ and any valuation $V$ on it,

$(\mathbb{F},V)\Vdash\forall\mathbf{i}_{m_{0}0}\forall\mathbf{i}_{m_{0}1}(\mathbf{i}_{m_{0}0}\leq^{S_{0}}_{S_{0}}\Diamond^{S_{0}}\mathbf{i}_{m_{0}1}\Rightarrow\ldots\forall\mathbf{i}_{m_{k}0}\forall\mathbf{i}_{m_{k}1}(\mathbf{i}_{m_{k}0}\leq^{S_{k}}_{S_{k}}\Diamond^{S_{k}}\mathbf{i}_{m_{k}1}\ \Rightarrow\ \alpha\leq^{S}_{S^{\prime}}p)\ldots)$ ,

iff for all $w_{m_{0}0},w_{m_{0}1},\ldots,w_{m_{k}0},w_{m_{k}1}\in W$ , if $(w_{m_{0}0},w_{m_{0}1})\in(R_{0}\setminus S_{0})$ , …, $(w_{m_{k}0},w_{m_{k}1})\in(R_{0}\setminus S_{k})$ , then $(\mathbb{F},V^{\mathbf{i}_{m_{0}0},\mathbf{i}_{m_{0}1},\ldots,\mathbf{i}_{m_{k}0},\mathbf{i}_{m_{k}1}}_{w_{m_{0}0},w_{m_{0}1},\ldots,w_{m_{k}0},w_{m_{k}1}})\Vdash\alpha\leq^{S}_{S^{\prime}}p$ ,

iff for all $w_{m_{0}0},w_{m_{0}1},\ldots,w_{m_{k}0},w_{m_{k}1},v\in W$ , if $(w_{m_{0}0},w_{m_{0}1})\in(R_{0}\setminus S_{0})$ , …, $(w_{m_{k}0},w_{m_{k}1})\in(R_{0}\setminus S_{k})$ , $(\mathbb{F},V^{\mathbf{i}_{m_{0}0},\mathbf{i}_{m_{0}1},\ldots,\mathbf{i}_{m_{k}0},\mathbf{i}_{m_{k}1}}_{w_{m_{0}0},w_{m_{0}1},\ldots,w_{m_{k}0},w_{m_{k}1}}),v\Vdash\alpha$ , then $(\mathbb{F},V^{\mathbf{i}_{m_{0}0},\mathbf{i}_{m_{0}1},\ldots,\mathbf{i}_{m_{k}0},\mathbf{i}_{m_{k}1}}_{w_{m_{0}0},w_{m_{0}1},\ldots,w_{m_{k}0},w_{m_{k}1}}),v\Vdash p$ ,

iff for all $w_{m_{0}0},w_{m_{0}1},\ldots,w_{m_{k}0},w_{m_{k}1},v\in W$ , if $(\mathbb{F},V^{\mathbf{i}_{m_{0}0},\mathbf{i}_{m_{0}1},\ldots,\mathbf{i}_{m_{k}0},\mathbf{i}_{m_{k}1}}_{w_{m_{0}0},w_{m_{0}1},\ldots,w_{m_{k}0},w_{m_{k}1}})\Vdash A(\mathbf{i}_{m_{0}0}\to\mathbf{i}_{m_{0}1}),\ldots,A(\mathbf{i}_{m_{k}0}\to\mathbf{i}_{m_{k}1})$ , $(\mathbb{F},V^{\mathbf{i}_{m_{0}0},\mathbf{i}_{m_{0}1},\ldots,\mathbf{i}_{m_{k}0},\mathbf{i}_{m_{k}1}}_{w_{m_{0}0},w_{m_{0}1},\ldots,w_{m_{k}0},w_{m_{k}1}}),v\Vdash\alpha$ , then $(\mathbb{F},V),v\Vdash p$ ,

iff for all $w_{m_{0}0},w_{m_{0}1},\ldots,w_{m_{k}0},w_{m_{k}1},v\in W$ , if $(\mathbb{F},V^{\mathbf{i}_{m_{0}0},\mathbf{i}_{m_{0}1},\ldots,\mathbf{i}_{m_{k}0},\mathbf{i}_{m_{k}1}}_{w_{m_{0}0},w_{m_{0}1},\ldots,w_{m_{k}0},w_{m_{k}1}}),v\Vdash A(\mathbf{i}_{m_{0}0}\to\mathbf{i}_{m_{0}1})\land\ldots\land A(\mathbf{i}_{m_{k}0}\to\mathbf{i}_{m_{k}1})\land\alpha$ , then $(\mathbb{F},V),v\Vdash p$ ,

iff for all $v\in W$ , if there exists $w_{m_{0}0},w_{m_{0}1},\ldots,w_{m_{k}0},w_{m_{k}1}\in W$ such that $(\mathbb{F},V^{\mathbf{i}_{m_{0}0},\mathbf{i}_{m_{0}1},\ldots,\mathbf{i}_{m_{k}0},\mathbf{i}_{m_{k}1}}_{w_{m_{0}0},w_{m_{0}1},\ldots,w_{m_{k}0},w_{m_{k}1}}),v\Vdash A(\mathbf{i}_{m_{0}0}\to\mathbf{i}_{m_{0}1})\land\ldots\land A(\mathbf{i}_{m_{k}0}\to\mathbf{i}_{m_{k}1})\land\alpha$ , then $(\mathbb{F},V),v\Vdash p$ ,

iff for all $v\in W$ , if $(\mathbb{F},V),v\Vdash\exists\mathbf{i}_{m_{0}0}\exists\mathbf{i}_{m_{0}1}\ldots\exists\mathbf{i}_{m_{k}0}\exists\mathbf{i}_{m_{k}1}(A(\mathbf{i}_{m_{0}0}\to\mathbf{i}_{m_{0}1})\land\ldots\land A(\mathbf{i}_{m_{k}0}\to\mathbf{i}_{m_{k}1})\land\alpha)$ , then $(\mathbb{F},V),v\Vdash p$ ,

iff $(\mathbb{F},V)\Vdash\exists\mathbf{i}_{m_{0}0}\exists\mathbf{i}_{m_{0}1}\ldots\exists\mathbf{i}_{m_{k}0}\exists\mathbf{i}_{m_{k}1}(A(\mathbf{i}_{m_{0}0}\to\Diamond^{S_{0}}\mathbf{i}_{m_{0}1})\land A(\mathbf{i}_{m_{k}0}\to\Diamond^{S_{k}}\mathbf{i}_{m_{k}1})\land\alpha)\leq^{\varnothing}_{\varnothing}p$ . ∎

Proposition 25.

The Ackermann rules in Substage 4 are sound in $\mathbb{F}$ .

Proof.

We only prove it for the right-handed Ackermann rule, the other rule is similar.

Without loss of generality we assume that $n=m=1$ . It suffices to show the following right-handed Ackermann lemma:

Lemma 26.

Assume $\alpha$ is pure and contains no contextual modalities $\Box,\Diamond,\blacksquare,\Diamondblack$ and does not contain nominals in $\vec{\mathbf{i}}$ , $\beta$ is positive in $p$ and $\gamma$ is negative in $p$ , then for any Kripke frame $\mathbb{F}=(W,R_{0})$ and any valuation $V$ on it,

$(\mathbb{F},V)\Vdash\forall\vec{\mathbf{i}}(\beta(\alpha/p)\leq^{T}_{T^{\prime}}\gamma(\alpha/p))$ iff there exists a valuation $V^{p}$ such that $(\mathbb{F},V^{p})\Vdash\alpha\leq^{\varnothing}_{\varnothing}p$ and $(\mathbb{F},V^{p})\Vdash\forall\vec{\mathbf{i}}(\beta\leq^{T}_{T^{\prime}}\gamma)$ , where $V^{p}$ is the same as $V$ except $V^{p}(p)$ .

Notice that $\alpha$ and $p$ do not contain contextual modalities, so their valuation do not change when the context is different.

$\Rightarrow$ : Take $V^{p}$ such that $V^{p}$ is the same as $V$ except that $V^{p}(p)=V(\alpha)$ . Since $\alpha$ does not contain $p$ , it is easy to see that $V^{p}(\alpha)=V(\alpha)=V^{p}(p)$ . Therefore $(\mathbb{F},V^{p})\Vdash\alpha\leq^{\varnothing}_{\varnothing}p$ . Since the valuation of $\alpha$ and $p$ do not change when the context is different, so for any $w\in W$ ,

$(W,(R_{0}\setminus T),V^{p}),w\Vdash\beta$ iff $(W,(R_{0}\setminus T),V),w\Vdash\beta(\alpha/p)$ , and

$(W,(R_{0}\setminus T^{\prime}),V^{p}),w\Vdash\gamma$ iff $(W,(R_{0}\setminus T^{\prime}),V),w\Vdash\gamma(\alpha/p)$ , so

from $(\mathbb{F},V)\Vdash\forall\vec{\mathbf{i}}(\beta(\alpha/p)\leq^{T}_{T^{\prime}}\gamma(\alpha/p))$ one can get $(\mathbb{F},V^{p})\Vdash\forall\vec{\mathbf{i}}(\beta\leq^{T}_{T^{\prime}}\gamma)$ .

$\Leftarrow$ : This direction follows from the monotonicity of $\beta$ in $p$ and the antitonicity of $\gamma$ in $p$ , and that the valuation of $\alpha$ and $p$ do not change when the context is different. ∎

3.5 Success of $\mathsf{ALBA}^{\mathsf{SML}}$ on Sahlqvist inequalities

In the present subsection we show that $\mathsf{ALBA}^{\mathsf{SML}}$ succeeds on all Sahlqvist inequalities:

Theorem 3.2.

$\mathsf{ALBA}^{\mathsf{SML}}$ succeeds on all Sahlqvist inequalities.

Definition 27 (Definite $\varepsilon$ -Sahlqvist inequality).

Given an order type $\varepsilon$ , $*\in\{-,+\}$ , the signed generation tree $*\varphi$ of the term $\varphi(p_{1},\ldots,p_{n})$ is definite $\varepsilon$ -Sahlqvist if there is no $+\lor,-\land$ occurring in the outer part on an $\varepsilon$ -critical branch. An inequality $\varphi\leq\psi$ is definite $\varepsilon$ -Sahlqvist if the trees $+\varphi$ and $-\psi$ are both definite $\varepsilon$ -Sahlqvist.

Lemma 28.

Let $\{\varphi_{i}\leq\psi_{i}\}_{i\in I}=\mathsf{Preprocess}(\varphi\leq\psi)$ obtained by exhaustive application of the rules in Stage 1 on an input $\varepsilon$ -Sahlqvist inequality $\varphi\leq\psi$ . Then each $\varphi_{i}\leq\psi_{i}$ is a definite $\varepsilon$ -Sahlqvist inequality.

Proof.

It is easy to see that by applying the distribution rules, all occurrences of $+\lor$ and $-\land$ in the outer part of an $\varepsilon$ -critical branch have been pushed up towards the root of the signed generation trees $+\varphi$ and $-\psi$ . Then by exhaustively applying the splitting rules, all such $+\lor$ and $-\land$ are eliminated. Since by applying the distribution rules, the splitting rules and the monotone/antitone variable elimination rules do not change the $\varepsilon$ -Sahlqvistness of a signed generation tree, in $\mathsf{Preprocess}(\varphi\leq\psi)$ , each signed generation tree $+\varphi_{i}$ and $-\psi_{i}$ are $\varepsilon$ -Sahlqvist, and since they do not have $+\lor$ and $-\land$ in the outer part in the $\varepsilon$ -critical branches, they are definite. ∎

Definition 29 (Inner $\varepsilon$ -Sahlqvist signed generation tree).

Given an order type $\varepsilon$ , $*\in\{-,+\}$ , the signed generation tree $*\varphi$ of the term $\varphi(p_{1},\ldots,p_{n})$ is inner $\varepsilon$ -Sahlqvist if its outer part $P_{2}$ on an $\varepsilon$ -critical branch is always empty, i.e. its $\varepsilon$ -critical branches have inner nodes only.

Lemma 30.

Given inequalities $\mathbf{i}_{0}\leq^{\varnothing}_{\varnothing}\varphi_{i}$ and $\psi_{i}\leq^{\varnothing}_{\varnothing}\neg\mathbf{i}_{1}$ obtained from Stage 1 where $+\varphi_{i}$ and $-\psi_{i}$ are definite $\varepsilon$ -Sahlqvist, by applying the rules in Substage 1 of Stage 2 exhaustively, the inequalities that we get are in one of the following forms:

1.

pure inequalities which does not have occurrences of propositional variables;
2.

inequalities of the form $\mathbf{i}\leq^{S}_{S^{\prime}}\alpha$ where $+\alpha$ is inner $\varepsilon$ -Sahlqvist;
3.

inequalities of the form $\beta\leq^{S}_{S^{\prime}}\neg\mathbf{i}$ where $-\beta$ is inner $\varepsilon$ -Sahlqvist.

Proof.

Indeed, the rules in the Substage 1 of Stage 2 deal with outer nodes in the signed generation trees $+\varphi_{i}$ and $-\psi_{i}$ except $+\lor$ , $-\land$ . For each rule, without loss of generality assume we start with an inequality of the form $\mathbf{i}\leq^{S}_{S^{\prime}}\alpha$ , then by applying the rules in Substage 1 of Stage 2, the inequalities we get are either a pure inequality without propositional variables, or an inequality where the left-hand side (resp. right-hand side) is $\mathbf{i}$ (resp. $\neg\mathbf{i}$ ), and the other side is a formula $\alpha^{\prime}$ which is a subformula of $\alpha$ , such that $\alpha^{\prime}$ has one root connective less than $\alpha$ . Indeed, if $\alpha^{\prime}$ is on the left-hand side (resp. right-hand side) then $-\alpha^{\prime}$ ( $+\alpha^{\prime}$ ) is definite $\varepsilon$ -Sahlqvist.

By applying the rules in the Substage 1 of Stage 2 exhaustively, we can eliminate all the outer connectives in the critical branches, so for non-pure inequalities, they become of form 2 or form 3. ∎

Lemma 31.

Assume we have an inequality $\mathbf{i}\leq^{S}_{S^{\prime}}\alpha$ or $\beta\leq^{S}_{S^{\prime}}\neg\mathbf{i}$ where $+\alpha$ and $-\beta$ are inner $\varepsilon$ -Sahlqvist, by applying the rules in Substage 2 of Stage 2, we have (mega-)inequalities ( $k$ can be 0 where a mega-inequality becomes an inequality) of the following form:

1.

$\forall\mathbf{i}_{m_{0}0}\forall\mathbf{i}_{m_{0}1}(\mathbf{i}_{m_{0}0}\leq^{S_{0}}_{S_{0}}\Diamond^{S_{0}}\mathbf{i}_{m_{0}1}\Rightarrow\ldots\forall\mathbf{i}_{m_{k}0}\forall\mathbf{i}_{m_{k}1}(\mathbf{i}_{m_{k}0}\leq^{S_{k}}_{S_{k}}\Diamond^{S_{k}}\mathbf{i}_{m_{k}1}\Rightarrow\alpha\leq^{S}_{S^{\prime}}p)\ldots)$ , where $\varepsilon(p)=1$ , $\alpha$ is pure and does not contain contextual connectives $\Box,\Diamond,\blacksquare,\Diamondblack$ ;
2.

$\forall\mathbf{i}_{m_{0}0}\forall\mathbf{i}_{m_{0}1}(\mathbf{i}_{m_{0}0}\leq^{S_{0}}_{S_{0}}\Diamond^{S_{0}}\mathbf{i}_{m_{0}1}\Rightarrow\ldots\forall\mathbf{i}_{m_{k}0}\forall\mathbf{i}_{m_{k}1}(\mathbf{i}_{m_{k}0}\leq^{S_{k}}_{S_{k}}\Diamond^{S_{k}}\mathbf{i}_{m_{k}1}\Rightarrow p\leq^{S}_{S^{\prime}}\beta)\ldots)$ , where $\varepsilon(p)=\partial$ , $\beta$ is pure and does not contain contextual connectives $\Box,\Diamond,\blacksquare,\Diamondblack$ ;
3.

$\forall\mathbf{i}_{m_{0}0}\forall\mathbf{i}_{m_{0}1}(\mathbf{i}_{m_{0}0}\leq^{S_{0}}_{S_{0}}\Diamond^{S_{0}}\mathbf{i}_{m_{0}1}\Rightarrow\ldots\forall\mathbf{i}_{m_{k}0}\forall\mathbf{i}_{m_{k}1}(\mathbf{i}_{m_{k}0}\leq^{S_{k}}_{S_{k}}\Diamond^{S_{k}}\mathbf{i}_{m_{k}1}\Rightarrow\alpha\leq^{S}_{S^{\prime}}\gamma)\ldots)$ , where $\alpha$ is pure and does not contain contextual connectives $\Box,\Diamond,\blacksquare,\Diamondblack$ , and $+\gamma$ is $\varepsilon^{\partial}$ -uniform;
4.

$\forall\mathbf{i}_{m_{0}0}\forall\mathbf{i}_{m_{0}1}(\mathbf{i}_{m_{0}0}\leq^{S_{0}}_{S_{0}}\Diamond^{S_{0}}\mathbf{i}_{m_{0}1}\Rightarrow\ldots\forall\mathbf{i}_{m_{k}0}\forall\mathbf{i}_{m_{k}1}(\mathbf{i}_{m_{k}0}\leq^{S_{k}}_{S_{k}}\Diamond^{S_{k}}\mathbf{i}_{m_{k}1}\Rightarrow\gamma\leq^{S}_{S^{\prime}}\beta)\ldots)$ , where $\beta$ is pure and does not contain contextual connectives $\Box,\Diamond,\blacksquare,\Diamondblack$ , and $-\gamma$ is $\varepsilon^{\partial}$ -uniform.

Proof.

First of all, from the rules of the Substage 2 of Stage 2, it is easy to see that from the given inequality, what we will obtain would be a set of mega-inequalities, and by the second splitting rule those mega-inequalities are built up from inequalities by $\forall\mathbf{i}\forall\mathbf{j}(\mathbf{i}\leq^{S}_{S}\Diamond^{S}\mathbf{j}\Rightarrow\mathsf{Mega})$ , so we will have mega-inequalities of the form $\forall\mathbf{i}_{m_{0}0}\forall\mathbf{i}_{m_{0}1}(\mathbf{i}_{m_{0}0}\leq^{S_{0}}_{S_{0}}\Diamond^{S_{0}}\mathbf{i}_{m_{0}1}\Rightarrow\ldots\forall\mathbf{i}_{m_{k}0}\forall\mathbf{i}_{m_{k}1}(\mathbf{i}_{m_{k}0}\leq^{S_{k}}_{S_{k}}\Diamond^{S_{k}}\mathbf{i}_{m_{k}1}\Rightarrow\gamma\leq^{S}_{S^{\prime}}\delta)\ldots)$ . Now it suffices to check the shape of $\gamma$ and $\delta$ . (From now on we call $\gamma\leq^{S}_{S^{\prime}}\delta$ the head of the mega-inequality.)

Notice that for each input inequality, it is of the form $\mathbf{i}\leq^{S}_{S^{\prime}}\alpha$ or $\beta\leq^{S}_{S^{\prime}}\neg\mathbf{i}$ , where $+\alpha$ and $-\beta$ are inner $\varepsilon$ -Sahlqvist. By applying the splitting rules and the residuation rules in this substage, it is easy to see that the head of the (mega-)inequality will have one side of the inequality pure and have no contextual connectives $\Box,\Diamond,\blacksquare,\Diamondblack$ , and the other side still inner $\varepsilon$ -Sahlqvist. By applying these rules exhaustively, one will either have $p$ as the non-pure side (with this $p$ on a critical branch), or have an inner $\varepsilon$ -Sahlqvist signed generation tree with no critical branch, i.e., $\varepsilon^{\partial}$ -uniform. ∎

Lemma 32.

Assume we have ( $mega$ -)inequalities of the form as described in Lemma 31. Then we can get inequalities of the following form:

1.

$\alpha\leq^{\varnothing}_{\varnothing}p$ where $\varepsilon(p)=1$ , $\alpha$ is pure and do not contain contextual connectives $\Box,\Diamond,\blacksquare,\Diamondblack$ ;
2.

$p\leq^{\varnothing}_{\varnothing}\alpha$ where $\varepsilon(p)=\partial$ , $\alpha$ is pure and do not contain contextual connectives $\Box,\Diamond,\blacksquare,\Diamondblack$ ;
3.

$\forall\mathbf{i}_{1}\ldots\forall\mathbf{i}_{n}(\top\leq^{\varnothing}_{S}\gamma)$ where $+\gamma$ is $\varepsilon^{\partial}$ -uniform.

Proof.

From the shape of the mega-inequalities, we can see that for all the mega-inequalities we can apply the corresponding packing rules so that we can get the inequalities as described in the lemma. ∎

Lemma 33.

Assume we have inequalities of the form as described in Lemma 32, the Ackermann lemmas are applicable and therefore all propositional variables can be eliminated.

Proof.

Immediate observation from the requirements of the Ackermann lemmas. ∎

Proof of Theorem 3.2.

Assume we have an $\varepsilon$ -Sahlqvist inequality $\varphi\leq\psi$ as input. By Lemma 28, we get a set of definite $\varepsilon$ -Sahlqvist inequalities. Then by Lemma 30, we get inequalities as described in Lemma 30. By Lemma 31, we get the mega-inequalities as described. Therefore by Lemma 32, we can apply the packing rules to get inequalities and universally quantified inequalities as described in the lemma. Finally by Lemma 33, the (universally quantified) inequalities are in the right shape to apply the Ackermann rules, and thus we can eliminate all the propositional variables and the algorithm succeeds on the input. ∎

4 Discussions and further directions

4.1 Completeness and canonicity issues

One issue that is not treated in the present paper is the completeness and canonicity theory of sabotage modal logic. For completeness theory, as is discussed in [5], there is not yet natural Hilbert-style axiomatization system for the basic sabotage modal logic, and there is no canonical model for sabotage modal logic, so it is not yet ready to provide a Sahlqvist-type completeness theorem for the current state-of-art. Regarding canonicity theory, one possible approach is to reduce the canonicity problem for formulas in sabotage modal logic to canonicity problems for formulas in hybrid logic with binders, since sabotage modal logic is a fragment of hybrid logic with binders (for more details, see [3]), for which the Sahlqvist theory is still in development (see [25]). For the algebraic approach of canonicity, one needs to first define the algebraic semantics for sabotage modal logic.

4.2 Other questions

Other interesting questions include the following:

•

Extending the Sahlqvist sabotage formulas to inductive sabotage formulas as well as to the language of sabotage modal logic with fixpoint operators;
•

A Kracht-type theorem characterizing the first-order correspondents of Sahlqvist sabotage formulas;
•

A Goldblatt-Thomason-type theorem characterizing the sabotage modally definable classes of Kripke frames;
•

Extend results on sabotage modal logic to the class of relation changing modal logics [3];
•

Since sabotage modal logic can be treated as a fragment of very expressive hybrid logics (see [3]), therefore a relevant interesting question would be to have a Sahlqvist-type correspondence theory for very expressive hybrid logics. For other existing works of correspondence theory for hybrid logic, see [7, 9, 13, 14, 21, 22].

Acknowledgement

The research of the author is supported by Taishan University Starting Grant “Studies on Algebraic Sahlqvist Theory” and the Taishan Young Scholars Program of the Government of Shandong Province, China (No.tsqn201909151).

References

[1] C. Areces, R. Fervari, and G. Hoffmann. Swap logic. Logic Journal of IGPL, 22(2):309–332, 2014.
[2] C. Areces, R. Fervari, and G. Hoffmann. Relation-changing modal operators. Logic Journal of the IGPL, 23(4):601–627, 2015.
[3] C. Areces, R. Fervari, G. Hoffmann, and M. Martel. Relation-changing logics as fragments of hybrid logics. In D. Cantone and G. Delzanno, editors, Proceedings of the Seventh International Symposium on Games, Automata, Logics and Formal Verification, volume 226 of Electronic Proceedings in Theoretical Computer Science, pages 16–29. Open Publishing Association, 2016.
[4] G. Aucher, P. Balbiani, L. F. del Cerro, and A. Herzig. Global and local graph modifiers. Electronic Notes in Theoretical Computer Science, 231:293–307, 2009.
[5] G. Aucher, J. Van Benthem, and D. Grossi. Modal logic of sabotage revisited. Journal of Logic and Computation, 28:269–303, 2018.
[6] P. Blackburn, J. F. van Benthem, and F. Wolter. Handbook of modal logic, volume 3. Elsevier, 2006.
[7] W. Conradie. Completeness and correspondence in hybrid logic via an extension of SQEMA. Electronic Notes in Theoretical Computer Science, 231:175–190, 2009.
[8] W. Conradie, V. Goranko, and D. Vakarelov. Algorithmic correspondence and completeness in modal logic. I. The core algorithm SQEMA. Logical Methods in Computer Science, 2:1–26, 2006.
[9] W. Conradie, V. Goranko, and D. Vakarelov. Algorithmic correspondence and completeness in modal logic. II. polyadic and hybrid extensions of the algorithm SQEMA. Journal of Logic and Computation, 16(5):579–612, 2006.
[10] W. Conradie and A. Palmigiano. Algorithmic correspondence and canonicity for distributive modal logic. Annals of Pure and Applied Logic, 163(3):338 – 376, 2012.
[11] W. Conradie, A. Palmigiano, S. Sourabh, and Z. Zhao. Canonicity and relativized canonicity via pseudo-correspondence: an application of ALBA. Submitted. ArXiv preprint 1511.04271.
[12] W. Conradie, A. Palmigiano, and Z. Zhao. Sahlqvist via translation. Logical Methods in Computer Science, 15, 2019.
[13] W. Conradie and C. Robinson. On Sahlqvist theory for hybrid logic. Journal of Logic and Computation, 27(3):867–900, 2017.
[14] V. Goranko and D. Vakarelov. Sahlqvist formulas unleashed in polyadic modal languages. Advances in Modal Logic 3, pages 221–240, 2000.
[15] B. Kooi and B. Renne. Arrow update logic. The Review of Symbolic Logic, 4(04):536–559, 2011.
[16] D. Li. Losing connection: the modal logic of definable link deletion. Journal of Logic and Computation, 30(3):715–743, 2020.
[17] C. Löding and P. Rohde. Model checking and satisfiability for sabotage modal logic. In International Conference on Foundations of Software Technology and Theoretical Computer Science, pages 302–313. Springer, 2003.
[18] C. Löding and P. Rohde. Solving the sabotage game is pspace-hard. In International Symposium on Mathematical Foundations of Computer Science, pages 531–540. Springer, 2003.
[19] A. Palmigiano, S. Sourabh, and Z. Zhao. Sahlqvist theory for impossible worlds. Journal of Logic and Computation, 27(3):775–816, 2017.
[20] H. Sahlqvist. Completeness and correspondence in the first and second order semantics for modal logic. In Studies in Logic and the Foundations of Mathematics, volume 82, pages 110–143. 1975.
[21] K. Tamura. Hybrid logic with pure and Sahlqvist axioms. http://www.st.nanzan-u.ac.jp/info/sasaki/2005mlg/43-45.pdf.
[22] B. ten Cate, M. Marx, and J. P. Viana. Hybrid logics with Sahlqvist axioms. Logic Journal of the IGPL, (3):293–300, 2006.
[23] J. van Benthem. An essay on sabotage and obstruction. In Mechanizing Mathematical Reasoning, pages 268–276. Springer, 2005.
[24] J. van Benthem, K. Mierzewski, and F. Zaffora Blando. The modal logic of stepwise removal. Reports on Symbolic Logic, 2019.
[25] Z. Zhao. Algorithmic correspondence for hybrid logic with binder. In preparation.

Sahlqvist Correspondence Theory for Sabotage Modal Logic

Abstract

1 Introduction

2 Preliminaries on sabotage modal logic

Definition 1.

Theorem 2.1.

3 Algorithmic correspondence for sabotage modal logic

3.1 The expanded sabotage modal language ℒ■+\mathcal{L}_{\blacksquare}^{+}, the first-order correspondence language and the standard translation

3.1.1 The expanded sabotage modal language ℒ■+\mathcal{L}_{\blacksquare}^{+}

Definition 2.

Proposition 3.

3.1.2 The first-order correspondence language and the standard translation

Definition 4.

Proposition 5.

Definition 6.

Proposition 7.

3.2 Sahlqvist inequalities

Definition 8 (Order-type of propositional variables).

Definition 9 (Signed generation tree).

Definition 10.

Definition 11 (Sahlqvist and inequalities).

3.3 The algorithm 𝖠𝖫𝖡𝖠𝖲𝖬𝖫\mathsf{ALBA}^{\mathsf{SML}} for the sabotage modal language

3.4 Soundness of 𝖠𝖫𝖡𝖠𝖲𝖬𝖫\mathsf{ALBA}^{\mathsf{SML}}

Theorem 3.1 (Soundness).

Proof.

Proposition 12 (Soundness of the rules in Stage 1).

Proof.

Proposition 13.

Proof.

Proposition 14.

Proof.

Lemma 15.

Proof.

Lemma 16.

Proof.

Lemma 17.

Proof.

Lemma 18.

Proof.

Lemma 19.

Proof.

Proposition 20.

Proof.

Lemma 21.

Proof.

Lemma 22.

Proof.

Lemma 23.

Proof.

Proposition 24.

Proof.

Proposition 25.

Proof.

Lemma 26.

3.5 Success of 𝖠𝖫𝖡𝖠𝖲𝖬𝖫\mathsf{ALBA}^{\mathsf{SML}} on Sahlqvist inequalities

Theorem 3.2.

Definition 27 (Definite ε\varepsilon-Sahlqvist inequality).

Lemma 28.

Proof.

Definition 29 (Inner ε\varepsilon-Sahlqvist signed generation tree).

Lemma 30.

Proof.

Lemma 31.

Proof.

Lemma 32.

Proof.

Lemma 33.

Proof.

Proof of Theorem 3.2.

4 Discussions and further directions

4.1 Completeness and canonicity issues

4.2 Other questions

Acknowledgement

References

3.1 The expanded sabotage modal language $\mathcal{L}_{\blacksquare}^{+}$ , the first-order correspondence language and the standard translation

3.1.1 The expanded sabotage modal language $\mathcal{L}_{\blacksquare}^{+}$

3.3 The algorithm $\mathsf{ALBA}^{\mathsf{SML}}$ for the sabotage modal language

3.4 Soundness of $\mathsf{ALBA}^{\mathsf{SML}}$

3.5 Success of $\mathsf{ALBA}^{\mathsf{SML}}$ on Sahlqvist inequalities

Definition 27 (Definite $\varepsilon$ -Sahlqvist inequality).

Definition 29 (Inner $\varepsilon$ -Sahlqvist signed generation tree).