Relational Companions of Logics¹¹1A version of this article has been submitted to the Indian Conference on Logic and its Applications 2025

Sankha S. Basu Department of Mathematics
Indraprastha Institute of Information Technology-Delhi
New Delhi, India. Sayantan Roy Department of Mathematics
Indraprastha Institute of Information Technology-Delhi
New Delhi, India.

(August 30, 2024)

Abstract

The variable inclusion companions of logics have lately been thoroughly studied by multiple authors. There are broadly two types of these companions: the left and the right variable inclusion companions. Another type of companions of logics induced by Hilbert-style presentations (Hilbert-style logics) were introduced in [1]. A sufficient condition for the restricted rules companion of a Hilbert-style logic to coincide with its left variable inclusion companion was proved there, while a necessary condition remained elusive. The present article has two parts. In the first part, we give a necessary and sufficient condition for the left variable inclusion and the restricted rules companions of a Hilbert-style logic to coincide. In the rest of the paper, we recognize that the variable inclusion restrictions used to define variable inclusion companions of a logic $\langle\mathcal{L},\vdash\rangle$ are relations from $\mathcal{P}(\mathcal{L})$ to $\mathcal{L}$ . This leads to a more general idea of a relational companion of a logical structure, a framework that we borrow from the field of universal logic. We end by showing that even Hilbert-style logics and the restricted rules companions of these can be brought under the umbrella of the general notions of logical structures and their relational companions that are discussed here.

Keywords: Companion logics; Universal logic; Logics of variable inclusion.

1 Introduction

The logics of variable inclusion have recently been rigorously studied, e.g., in [7, 8, 13]. These companion logics come in four flavors, viz., the left, the right, the pure left, and the pure right variable inclusion companion logics. The definitions and various examples of each of these classes can be found in the above references. It is well-known that the left variable inclusion companion of classical propositional logic (CPC) is the paraconsistent weak Kleene logic (PWK). A simple Hilbert-style presentation of PWK, consisting of the same set of axioms as CPC and a restricted version of the classical rule of modus ponens, was presented in [6]. This led to the following natural question. Can we always obtain a Hilbert-style presentation of the left variable inclusion companion logic from that of the original logic (if it has one, of course) by just restricting the rules of inference? The answer to this question was shown to be negative in [1]. In the course of the argument, the restricted rules companion of a Hilbert-style logic, i.e., a logic induced syntactically by a Hilbert-style presentation, was introduced. A sufficient condition for the restricted rules companion to coincide with the left variable inclusion companion of a Hilbert-style logic was proved as well. However, a necessary condition for the same remained unattained.

The present article has two main parts. In the first, a necessary and sufficient condition for the left variable inclusion and the restricted rules companions of a Hilbert-style logic to coincide, is presented.

In the second part, we generalize the notions of variable inclusion companion and restricted rules companion logics. This is done using the framework of logical structures from universal logic [4, 5].

A logical structure is a pair $\mathcal{S}=\langle\mathcal{L},\vdash\rangle$ , where $\mathcal{L}$ is a set and $\vdash\,\subseteq\mathcal{P}(\mathcal{L})\times\mathcal{L}$ . A logic is a logical structure $\mathcal{S}=\langle\mathcal{L},\vdash\rangle$ , where $\mathcal{L}$ is the set of formulas defined inductively, in the usual way, over a set of variables $V$ , using a finite set of connectives/operators called the signature/type. In other words, $\mathcal{L}$ is the formula algebra over $V$ of some type. The formula algebra has the universal mapping property for the class of all algebras of the same type as $\mathcal{L}$ over $V$ , i.e., any function $f:V\to A$ , where $A$ is the universe of an algebra $\mathbf{A}$ of the same type as $\mathcal{L}$ , can be uniquely extended to a homomorphism from $\mathcal{L}$ to $\mathbf{A}$ (see [12, 11] for more details). We, however, do not assume any condition on the $\vdash$ -relation. For any $\alpha\in\mathcal{L}$ , $\mathrm{var}(\alpha)$ denotes the set of all the variables occurring in $\alpha$ , and for any $\Delta\subseteq\mathcal{L}$ , $\mathrm{var}(\Delta)=\displaystyle\bigcup_{\alpha\in\Delta}\mathrm{var}(\alpha)$ .

2 Left variable inclusion and restricted rules companions

In this section, we will deal exclusively with logics, in the usual sense, as described in the previous section. As mentioned earlier, the logics of variable inclusion have recently been rigorously studied, e.g., in [7, 8, 13]. The following definition of a left variable inclusion companion can be found in these.

Definition 2.1.

Suppose $\mathcal{S}=\langle\mathcal{L},\vdash\rangle$ is a logic. The left variable inclusion companion of $\mathcal{S}$ , denoted by $\mathcal{S}^{l}=\langle\mathcal{L},\vdash^{l}\rangle$ , is defined as follows. For any $\Gamma\cup\{\alpha\}\subseteq\mathcal{L}$ ,

\Gamma\vdash^{l}\alpha\;\hbox{iff there is a}\;\Delta\subseteq\Gamma\;\hbox{such that}\;\mathrm{var}(\Delta)\subseteq\mathrm{var}(\alpha)\;\hbox{and}\;\Delta\vdash\alpha.

The restricted rules companion of a Hilbert-style logic, i.e., a logic induced syntactically by a Hilbert-style presentation, was introduced in [1] as follows.

Definition 2.2.

Suppose $\mathcal{S}=\langle\mathcal{L},\vdash\rangle$ is a Hilbert-style logic with $A\subseteq\mathcal{L}$ as the set of axioms and $R_{\mathcal{S}}\subseteq\mathcal{P}(\mathcal{L})\times\mathcal{L}$ as the set of rules of inference. The restricted rules companion of $\mathcal{S}$ , denoted by $\mathcal{S}^{re}=\langle\mathcal{L},\vdash^{re}\rangle$ , is then defined as the Hilbert-style logic with the following sets of axioms and rules.

Set of axioms	=	$A$ , and
set of rules of inference	=	$R_{\mathcal{S}^{re}}=\left\{\dfrac{\Gamma}{\alpha}\in R_{\mathcal{S}}\mid\,\mathrm{var}(\Gamma)\subseteq\mathrm{var}(\alpha)\right\}$ .

Suppose $\mathcal{S}=\langle\mathcal{L},\vdash\rangle$ is a Hilbert-style logic and $\mathcal{S}^{l}=\langle\mathcal{L},\vdash^{l}\rangle$ , $\mathcal{S}^{re}=\langle\mathcal{L},\vdash^{re}\rangle$ be its left variable inclusion and restricted rules companion logics, respectively. It was established that, $\vdash^{re}\,\subseteq\,\vdash^{l}$ ([1, Theorem 3.6]), but the reverse inclusion, i.e., $\vdash^{l}\,\subseteq\,\vdash^{re}$ is not guaranteed ([1, Remark 3.7]). The following sufficient condition for the latter inclusion was also given in this paper.

Theorem 2.3 ([1, Theorem 4.3]).

Suppose $\mathcal{S}=\langle\mathcal{L},\vdash\rangle$ is a finitary Hilbert-style logic such that $\dfrac{\alpha,\alpha\longrightarrow\beta}{\beta}$ (modus ponens [MP]) is a rule of inference in $\mathcal{S}$ . Suppose further that the Deduction theorem holds in $\mathcal{S}$ . Then the restricted rules companion of $\mathcal{S}$ coincides with the left variable inclusion companion of $\mathcal{S}$ , i.e., $\vdash^{re}\,=\,\vdash^{l}$ .

However, a necessary condition for $\vdash^{l}\,=\,\vdash^{re}$ remained elusive. In the rest of this section, we investigate this further and provide a necessary and sufficient condition for the two companion logics to coincide. The following lemmas list some straightforward inferences that can be drawn from the definitions of left variable inclusion and restricted rules companions.

Lemma 2.4.

Suppose $\mathcal{S}=\langle\mathcal{L},\vdash\rangle$ is a logic.

(i)

$\mathcal{S}^{l}=\langle\mathcal{L},\vdash^{l}\rangle$ is monotonic. Moreover, if $\mathcal{S}$ is monotonic, then $\vdash^{l}\,\subseteq\,\vdash$ .
(ii)

$(\mathcal{S}^{l})^{l}=\mathcal{S}^{l}$ , i.e., $(\vdash^{l})^{l}\,=\,\vdash^{l}$ .
(iii)

Suppose $\mathcal{S}$ is a Hilbert-style logic. Then, $\mathcal{S}^{re}$ is monotonic and moreover, $\vdash^{re}\,\subseteq\,\vdash$ .
(iv)

Suppose $\mathcal{S}$ is a Hilbert-style logic. Then, $(\mathcal{S}^{re})^{re}=\mathcal{S}^{re}$ , i.e., $(\vdash^{re})^{re}\,=\,\vdash^{re}$ .

Proof.

Parts (i) and (ii) follow straightforwardly from the definition of left variable inclusion companions. For part (iii), we recall that every Hilbert-style logic is monotonic. Thus, in fact, $\mathcal{S}$ and $\mathcal{S}^{re}$ , being Hilbert-style logics, are both monotonic. That $\vdash^{re}\,\subseteq\,\vdash$ , follows from the definition of $\mathcal{S}^{re}$ .

For part (iv), let $A$ and $R_{\mathcal{S}}$ as its sets of axioms and rules of inference, respectively, of $\mathcal{S}$ . Then $\mathcal{S}^{re}$ has $A$ and $R_{\mathcal{S}^{re}}$ , as its sets of axioms and rules, where $R_{\mathcal{S}^{re}}$ is as described in the definition of a restricted rules companion. Now, since any rule in $R_{\mathcal{S}^{re}}$ is already restricted, $A$ and $R_{\mathcal{S}^{re}}$ also comprise a Hilbert-style presentation for $(\mathcal{S}^{re})^{re}$ . Thus, $(\mathcal{S}^{re})^{re}=\mathcal{S}^{re}$ , i.e., $(\vdash^{re})^{re}\,=\,\vdash^{re}$ . ∎

Theorem 2.5.

Suppose $\mathcal{S}_{1}=\langle\mathcal{L},\vdash_{1}\rangle$ and $\mathcal{S}_{2}=\langle\mathcal{L},\vdash_{2}\rangle$ are two logics such that $\vdash_{1}\,\subseteq\,\vdash_{2}$ . Then, $\vdash_{1}^{l}\,\subseteq\,\vdash_{2}^{l}$ . Moreover, if $\mathcal{S}_{1}$ and $\mathcal{S}_{2}$ are Hilbert-style logics, such that for any $\dfrac{\Gamma}{\alpha}\in R_{\mathcal{S}_{1}^{re}}$ , $\Gamma\vdash^{re}_{2}\alpha$ , then $\vdash^{re}_{1}\,\subseteq\,\vdash^{re}_{2}$ .

Proof.

Suppose $\Sigma\cup\{\alpha\}\subseteq\mathcal{L}$ such that $\Sigma\vdash_{1}^{l}\alpha$ . Then there exists $\Delta\subseteq\Sigma$ with $\mathrm{var}(\Delta)\subseteq\mathrm{var}(\alpha)$ such that $\Delta\vdash_{1}\alpha$ . Since $\vdash_{1}\,\subseteq\,\vdash_{2}$ , $\Delta\vdash_{2}\alpha$ . Thus, $\Sigma\vdash_{2}^{l}\alpha$ . Hence, $\vdash_{1}^{l}\,\subseteq\,\vdash_{2}^{l}$ .

Next, suppose $\mathcal{S}_{1},\mathcal{S}_{2}$ are Hilbert-style logics such that for any $\dfrac{\Gamma}{\alpha}\in R_{\mathcal{S}_{1}^{re}}$ , $\Gamma\vdash^{re}_{2}\alpha$ . Now, let $\Sigma\cup\{\alpha\}\subseteq\mathcal{L}$ such that $\Sigma\vdash^{re}_{1}\alpha$ . Then, there exists a derivation $D=\langle\alpha_{1},\ldots,\alpha_{n}=\alpha\rangle$ of $\alpha$ from $\Sigma$ , where for each $1\leq i\leq n$ , $\alpha_{i}$ is either an axiom of $\mathcal{S}_{1}$ , or an element of $\Sigma$ , or is obtained by applying a rule of inference in $R_{\mathcal{S}_{1}^{re}}$ . If $\alpha_{i}$ is an axiom, then $\vdash_{1}\alpha_{i}$ , and since $\vdash_{1}\,\subseteq\,\vdash_{2}$ , $\vdash_{2}\alpha_{i}$ . Then, by [1, Theorem 3.4], $\vdash^{re}_{2}\alpha_{i}$ . So, there exists a derivation of $\alpha_{i}$ in $\mathcal{S}_{2}^{re}$ . Now, suppose $\alpha_{i}$ is obtained by applying a rule of inference $\dfrac{\Delta}{\alpha_{i}}\in R_{\mathcal{S}_{1}^{re}}$ , where $\Delta\subseteq\{\alpha_{1},\ldots,\alpha_{i-1}\}$ . Then, by assumption, $\Delta\vdash^{re}_{2}\alpha_{i}$ , and hence, there exists a derivation of $\alpha_{i}$ from $\Delta$ in $\mathcal{S}_{2}^{re}$ . So, we can translate the derivation $D$ of $\alpha$ from $\Sigma$ as follows. For each $1\leq i\leq n$ , if $\alpha_{i}$ is an axiom, then we replace $\alpha_{i}$ by the elements of a derivation of $\alpha_{i}$ in $\mathcal{S}_{2}^{re}$ . If $\alpha_{i}$ is obtained from $\Delta\subseteq\{\alpha_{1},\ldots,\alpha_{i-1}\}$ , by using a rule of inference in $\mathcal{S}_{1}^{re}$ , then we replace $\alpha_{i}$ by the elements of a derivation of $\alpha_{i}$ from $\Delta$ in $\mathcal{S}_{2}^{re}$ . Finally, if $\alpha_{i}\in\Sigma$ , then we keep it unchanged. Let $D^{\prime}$ be the resulting sequence of formulas. Clearly, $D^{\prime}$ is a derivation of $\alpha$ from $\Sigma$ in $\mathcal{S}_{2}^{re}$ . Thus, $\Sigma\vdash^{re}_{2}\alpha$ . Hence, $\vdash^{re}_{1}\,\subseteq\,\vdash^{re}_{2}$ . ∎

Remark 2.6.

It is not true, in general, that if $\mathcal{S}_{1}=\langle\mathcal{L},\vdash_{1}\rangle$ and $\mathcal{S}_{2}=\langle\mathcal{L},\vdash_{2}\rangle$ are two Hilbert-style logics with $\vdash_{1}\,\subseteq\,\vdash_{2}$ , then $\vdash^{re}_{1}\,\subseteq\,\vdash^{re}_{2}$ . This can be seen from the following example.

Suppose $\mathcal{L}$ is the formula algebra over a countable set of variables $V$ of type $\{\land,\lor\}$ . Let $\mathcal{S}_{1}=\langle\mathcal{L},\vdash_{1}\rangle$ be the Hilbert-style logic with an empty set of axioms and the following two rules of inference.

R_{1}:\,\dfrac{\alpha\land\beta}{\alpha}\quad\hbox{and}\quad R_{2}:\,\dfrac{\alpha}{\alpha\lor\beta},\quad\hbox{where }\alpha,\beta\in\mathcal{L}.

$\mathcal{S}_{1}$ is the same logic that was used in [1, Remark 3.7] to show that the left variable inclusion companion of a Hilbert-style logic can differ from its restricted rules companion.

Let $\mathcal{S}_{2}=\langle\mathcal{L},\vdash_{2}\rangle$ be the Hilbert-style logic with an empty set of axioms and the following rule of inference in addition to $R_{1},R_{2}$ above.

R_{3}:\,\dfrac{\alpha\land\beta}{\alpha\lor\beta},\quad\hbox{where }\alpha,\beta\in\mathcal{L}.

Clearly, $\vdash_{2}\,\subseteq\,\vdash_{1}$ , since $R_{3}$ can be derived in $\mathcal{S}_{1}$ as follows. For any $\alpha,\beta\in\mathcal{L}$ ,

\begin{array}[]{lcl}\alpha\land\beta&\vdash_{1}&1.\,\alpha\land\beta\\ &&2.\,\alpha\qquad[R_{1}\hbox{ on (1)}]\\ &&3.\,\alpha\lor\beta\qquad[R_{2}\hbox{ on (2)}]\end{array}

We note that $\mathcal{S}_{1}^{re}=\langle\mathcal{L},\vdash^{re}_{1}\rangle$ , is the logic induced by the same set of axioms and the following two rules of inference.

\begin{array}[]{ll}R_{1}^{\prime}:\,\dfrac{\alpha\land\beta}{\alpha}&\hbox{such that }\mathrm{var}(\alpha\land\beta)\subseteq\mathrm{var}(\alpha),\hbox{ i.e., }\mathrm{var}(\beta)\subseteq\mathrm{var}(\alpha),\hbox{ and}\\ &\\ R_{2}:\,\dfrac{\alpha}{\alpha\lor\beta},&\end{array}

while $\mathcal{S}_{2}^{re}=\langle\mathcal{L},\vdash^{re}_{1}\rangle$ , is the logic induced by the same set of axioms and the rules $R_{1}^{\prime},R_{2}$ , and $R_{3}$ . ( $R_{2}$ and $R_{3}$ do not need to be restricted as $\mathrm{var}(\alpha)\subseteq\mathrm{var}(\alpha\lor\beta)$ and $\mathrm{var}(\alpha\land\beta)=\mathrm{var}(\alpha\lor\beta)$ for any $\alpha,\beta\in\mathcal{L}$ .)

Now, suppose $p,q$ are distinct variables. Then, while $p\land q\vdash^{re}_{2}p\lor q$ , $p\land q\not\vdash^{re}_{1}p\lor q$ , since we cannot apply $R_{1}^{\prime}$ and $R_{2}$ to derive $p\lor q$ from $p\land q$ in $\mathcal{S}_{1}$ , as shown in [1, Remark 3.7].

Thus, $\vdash^{re}_{2}\,\not\subseteq\,\vdash^{re}_{1}$ although $\vdash_{2}\,\subseteq\,\vdash_{1}$ .

Theorem 2.7.

Suppose $\mathcal{S}=\langle\mathcal{L},\vdash\rangle$ is a Hilbert-style logic. Then, $\mathcal{S}^{l}=\mathcal{S}^{re}$ iff $(\mathcal{S}^{re})^{l}=\mathcal{S}^{l}$ . In other words, $\vdash^{l}\,=\,\vdash^{re}$ iff $(\vdash^{re})^{l}\,=\,\vdash^{l}$ , i.e., for all $\Gamma\cup\{\alpha\}\subseteq\mathcal{L}$ , $\Gamma\vdash^{l}\alpha$ iff there exists $\Delta\subseteq\Gamma$ such that $\mathrm{var}(\Delta)\subseteq\mathrm{var}(\alpha)$ and $\Delta\vdash^{re}\alpha$ .

Proof.

Suppose $\mathcal{S}^{l}=\mathcal{S}^{re}$ , i.e., $\vdash^{l}\,=\,\vdash^{re}$ . Now, by Lemma 2.4 (iii), $\vdash^{re}\,\subseteq\,\vdash$ . So, by Theorem 2.5, $(\vdash^{re})^{l}\,\subseteq\,\vdash^{l}$ . Now, suppose $\Gamma\cup\{\alpha\}\subseteq\mathcal{L}$ such that $\Gamma\vdash^{l}\alpha$ . Then, there exists $\Delta\subseteq\Gamma$ such that $\mathrm{var}(\Delta)\subseteq\mathrm{var}(\alpha)$ and $\Delta\vdash\alpha$ . Clearly, $\Delta\vdash^{l}\alpha$ as well. This implies that $\Delta\vdash^{re}\alpha$ , since $\vdash^{l}\,=\,\vdash^{re}$ . Now, as $\Delta\subseteq\Gamma$ , $\mathrm{var}(\Delta)\subseteq\mathrm{var}(\alpha)$ , and $\Delta\vdash^{re}\alpha$ , $\Gamma(\vdash^{re})^{l}\alpha$ . Thus, $\vdash^{l}\,\subseteq\,(\vdash^{re})^{l}$ . Hence, $(\vdash^{re})^{l}\,=\,\vdash^{l}$ .

Conversely, suppose $(\vdash^{re})^{l}\,=\,\vdash^{l}$ . We know that $\vdash^{re}\,\subseteq\,\vdash^{l}$ . Thus, we only need to show that $\vdash^{l}\,\subseteq\,\vdash^{re}$ . Suppose $\Gamma\cup\{\alpha\}\subseteq\mathcal{L}$ such that $\Gamma\vdash^{l}\alpha$ . Then, by our assumption, $\Gamma(\vdash^{re})^{l}\alpha$ . So, there exists $\Delta\subseteq\Gamma$ such that $\mathrm{var}(\Delta)\subseteq\mathrm{var}(\alpha)$ and $\Delta\vdash^{re}\alpha$ . Now, as $\mathcal{S}^{re}$ is a Hilbert-style logic, it is monotonic. This implies that $\Gamma\vdash^{re}\alpha$ . Thus, $\vdash^{l}\,\subseteq\,\vdash^{re}$ . Hence $\vdash^{l}\,=\,\vdash^{re}$ . ∎

3 Relational companions of a logical structure

We now let go of the formula algebras and land in the arena of logical structures that were described in the introduction. The attempt here would be to generalize the notion of a logic of variable inclusion. In doing so, we will be able to capture a lot more than just the logics of left variable inclusion.

Definition 3.1.

Suppose $\mathcal{S}=\langle\mathcal{L},\vdash\rangle$ is a logical structure and $\varrho\subseteq\mathcal{P}(\mathcal{L})\times\mathcal{L}$ .

(i)

The $\varrho$ -companion of $\mathcal{S}$ is the logical structure $\mathcal{S}^{\varrho}=\langle\mathcal{L},\vdash^{\varrho}\rangle$ , where $\vdash^{\varrho}\,\subseteq\mathcal{P}(\mathcal{L})\times\mathcal{L}$ is defined as follows. For any $\Gamma\cup\{\alpha\}\subseteq\mathcal{L}$ ,

\Gamma\vdash^{\varrho}\alpha\hbox{ iff there is a }\Delta\subseteq\Gamma\hbox{ such that }(\Delta,\alpha)\in\varrho\hbox{ and }\Delta\vdash\alpha.

(ii)

The pure $\varrho$ -companion of $\mathcal{S}$ is the logical structure $\mathcal{S}^{p\varrho}=\langle\mathcal{L},\vdash^{p\varrho}\rangle$ , where $\vdash^{p\varrho}\,\subseteq\mathcal{P}(\mathcal{L})\times\mathcal{L}$ is defined as follows. For any $\Gamma\cup\{\alpha\}\subseteq\mathcal{L}$ ,

\Gamma\vdash^{p\varrho}\alpha\hbox{ iff there is a }\Delta\subseteq\Gamma\hbox{ such that }\Delta\neq\emptyset,(\Delta,\alpha)\in\varrho\hbox{ and }\Delta\vdash\alpha.

Any such $\varrho$ -companion ( $p\varrho$ -companion) $\mathcal{S}^{\varrho}$ ( $\mathcal{S}^{p\varrho}$ ) is called a relational companion (pure relational companion) of $\mathcal{S}$ .

Example 3.2.

Suppose $\mathcal{S}=\langle\mathcal{L},\vdash\rangle$ is a logic (in the usual sense).

(i)

The left variable inclusion companion $\mathcal{S}^{l}$ is the relational companion $\mathcal{S}^{L}=\langle\mathcal{L},\vdash^{L}\rangle$ of $\mathcal{S}$ , where the relation $L\subseteq\mathcal{P}(\mathcal{L})\times\mathcal{L}$ is defined by variable inclusion from left to right, i.e., $(\Delta,\alpha)\in L$ iff $\mathrm{var}(\Delta)\subseteq\mathrm{var}(\alpha)$ . Thus, $\mathcal{S}^{l}=\mathcal{S}^{L}$ , the $L$ -companion of $\mathcal{S}$ .

(ii)

The pure left variable inclusion companion of $\mathcal{S}$ , denoted by $\mathcal{S}^{pl}=\langle\mathcal{L},\vdash^{pl}\rangle$ , is defined (e.g., in [8, 13]) as follows. For any $\Gamma\cup\{\alpha\}\subseteq\mathcal{L}$ ,

\Gamma\vdash^{pl}\alpha\;\hbox{iff there is a}\;\Delta\subseteq\Gamma\;\hbox{such that}\;\Delta\neq\emptyset,\mathrm{var}(\Delta)\subseteq\mathrm{var}(\alpha),\;\hbox{and}\;\Delta\vdash\alpha.

Clearly, $\mathcal{S}^{pl}$ is the pure $L$ -companion of $\mathcal{S}$ , where the relation $L$ is as defined in (i), i.e., $\mathcal{S}^{pl}=\mathcal{S}^{pL}$ .

Example 3.3.

Suppose $\mathcal{S}=\langle\mathcal{L},\vdash\rangle$ is a monotonic logic (in the usual sense).

(i)

The right variable inclusion companion of $\mathcal{S}$ , denoted by $\mathcal{S}^{r}=\langle\mathcal{L},\vdash^{r}\rangle$ is defined (e.g., in [13]) as follows. For any $\Gamma\cup\{\alpha\}\subseteq\mathcal{L}$ ,

\Gamma\vdash^{r}\alpha\;\hbox{iff }\;\Gamma\;\hbox{contains an \emph{$\mathcal{S}$-antitheorem}, or}\;\Gamma\vdash\alpha\;\hbox{and}\;\mathrm{var}(\alpha)\subseteq\mathrm{var}(\Gamma).

An $\mathcal{S}$ -antitheorem is a set $\Sigma\subseteq\mathcal{L}$ such that for every substitution $\sigma$ , $\sigma(\Sigma)\vdash\varphi$ for all $\varphi\in\mathcal{L}$ , i.e., $\sigma(\Sigma)$ explodes in $\mathcal{S}$ for every $\sigma$ ²²2Suppose $\mathcal{L}$ is a formula algebra over a set of variables $V$ (which is the case when discussing variable inclusion logics). A substitution is any function $\sigma:V\to\mathcal{L}$ that extends to a unique endomorphism (also denoted by $\sigma$ ) from $\mathcal{L}$ to itself via the universal mapping property..

$\mathcal{S}^{r}$ can be seen as the relational companion $\mathcal{S}^{R}=\langle\mathcal{L},\vdash^{R}\rangle$ of $\mathcal{S}$ , where the relation $R\subseteq\mathcal{P}(\mathcal{L})\times\mathcal{L}$ is defined as follows. $(\Delta,\alpha)\in R$ iff either $\Delta$ is an $\mathcal{S}$ -antitheorem or $\mathrm{var}(\alpha)\subseteq\mathrm{var}(\Delta)$ .

The proof that $\mathcal{S}^{r}=\mathcal{S}^{R}$ can be given as follows. Let $\Gamma\cup\{\alpha\}\subseteq\mathcal{L}$ .

Suppose $\Gamma\vdash^{R}\alpha$ . Then there exists a $\Delta\subseteq\Gamma$ such that $(\Delta,\alpha)\in R$ and $\Delta\vdash\alpha$ . Now, since $(\Delta,\alpha)\in R$ , either $\Delta$ is an $\mathcal{S}$ -antitheorem, in which case $\Gamma$ contains an $\mathcal{S}$ -antitheorem, or $\mathrm{var}(\alpha)\subseteq\mathrm{var}(\Delta)$ and $\Delta\vdash\alpha$ . In the latter case, as $\Delta\subseteq\Gamma$ , $\mathrm{var}(\alpha)\subseteq\mathrm{var}(\Gamma)$ and since $\mathcal{S}$ is monotonic, $\Gamma\vdash\alpha$ as well. Thus, $\Gamma\vdash^{r}\alpha$ .

Conversely, suppose $\Gamma\vdash^{r}\alpha$ . Then, either $\Gamma$ contains an $\mathcal{S}$ -antitheorem or $\mathrm{var}(\alpha)\subseteq\mathrm{var}(\Gamma)$ and $\Gamma\vdash\alpha$ . If $\Gamma$ contains an $\mathcal{S}$ -antitheorem $\Delta$ , then $\Delta\subseteq\Gamma$ such that $(\Delta,\alpha)\in R$ and $\Delta\vdash\alpha$ as $\Delta$ is an $\mathcal{S}$ -antitheorem. On the other hand, if $\Gamma\vdash\alpha$ and $\mathrm{var}(\alpha)\subseteq\mathrm{var}(\Gamma)$ , then $\Gamma$ is its own subset such that $(\Gamma,\alpha)\in R$ and $\Gamma\vdash\alpha$ . Thus, in either case, there exists $\Delta\subseteq\Gamma$ such that $(\Delta,\alpha)\in R$ and $\Delta\vdash\alpha$ , and so, $\Gamma\vdash^{R}\alpha$ . Hence $\vdash^{r}\,=\,\vdash^{R}$ , i.e., $\mathcal{S}^{r}=\mathcal{S}^{R}$ .

(ii)

The pure right variable inclusion companion of $\mathcal{S}$ , denoted by $\mathcal{S}^{pr}=\langle\mathcal{L}\vdash^{pr}\rangle$ , is defined (e.g., in [8, 13]) as follows. For any $\Gamma\cup\{\alpha\}\subseteq\mathcal{L}$ ,

$\Gamma\vdash^{pr}\alpha\;\hbox{iff}\;\Gamma\vdash\alpha\;\hbox{and}\;\mathrm{var}(\alpha)\subseteq\mathrm{var}(\Gamma).$

$\mathcal{S}^{pr}$ can be seen as a relational companion $\mathcal{S}^{PR}=\langle\mathcal{L},\vdash^{PR}\rangle$ of $\mathcal{S}$ , where the relation $PR\subseteq\mathcal{P}(\mathcal{L})\times\mathcal{L}$ is defined by variable inclusion from right to left, i.e., $(\Delta,\alpha)\in PR$ iff $\mathrm{var}(\alpha)\subseteq\mathrm{var}(\Delta)$ . This can be shown with a similar argument as for the right variable inclusion companions above. The monotonicity of $\mathcal{S}$ is required for showing that $\vdash^{PR}\,\subseteq\,\vdash^{pr}$ .

Although $\mathcal{S}^{pr}$ can be seen as a relational companion of $\mathcal{S}$ , it cannot be described as a pure relational companion of $\mathcal{S}$ , unless $\mathcal{S}$ is a logic without antitheorems. However, if $\mathcal{S}$ is a logic without antitheorems, then $\mathcal{S}^{pr}=\mathcal{S}^{pR}$ , where $R$ is the relation used in (i).

Example 3.4.

Some more inclusion logics have been introduced in [9] as generalizations of the left and right variable inclusion logics. In these companion logics, the containment requirement is extended to classes of subformulas. We might call these the left and right subformula inclusion companion logics (the actual names require some additional machinery and hence we avoid these). While the left subformula inclusion companions of a logic can be seen as relational companions of it, the right subformula inclusion companions of a monotonic logic can be seen as relational companions of it. This is much like the case for left and right variable inclusion companions.

It is easy to see that the left, pure left, and pure right variable inclusion companions of a logic $\mathcal{S}=\langle\mathcal{L},\vdash\rangle$ , with a unary (negation) operator $\neg$ in the signature, are all paraconsistent with respect to $\neg$ , i.e., there exists $\alpha,\beta\in\mathcal{L}$ such that $\{\alpha,\neg\alpha\}\not\vdash\beta$ . In other words, the principle of explosion, ECQ, with respect to $\neg$ (we call this $\neg$ -ECQ), fails in these companion logics (see [3] for more on the paraconsistency of these companion logics). The right variable inclusion companion of a logic is, however, not necessarily paraconsistent with respect to a $\neg$ . Thus, not all relational companions of a logic, with such a unary operator $\neg$ , are paraconsistent with respect to $\neg$ . It can also be observed from the definition of a relational companion that the matter of paraconsistency depends on the relation. The following example from [10] can be seen as a relational companion created with the intention of obtaining a paraconsistent logical structure. The authors have called this process paraconsistentization.

Example 3.5.

Suppose $\mathcal{S}=\langle\mathcal{L},\vdash\rangle$ is a logical structure. Then $\mathcal{S}^{\mathbb{P}}=\langle\mathcal{L},\vdash^{\mathbb{P}}\rangle$ is the logical structure, where $\vdash^{\mathbb{P}}\subseteq\mathcal{P}(\mathcal{L})\times\mathcal{L}$ is defined as follows. For any $\Gamma\cup\{\alpha\}\subseteq\mathcal{L}$ ,

\Gamma\vdash^{\mathbb{P}}\alpha\hbox{ iff there is a }\Delta\subseteq\Gamma\hbox{ such that }\Delta\hbox{ is }\mathcal{S}\hbox{-nontrivial and }\Delta\vdash\alpha.

A set $\Delta$ is $\mathcal{S}$ -nontrivial, if there exists $\varphi\in\mathcal{L}$ such that $\Delta\not\vdash\varphi$ .

Theorem 3.6.

Suppose $\mathcal{S}=\langle\mathcal{L},\vdash\rangle$ is a logical structure and $\varrho\subseteq\mathcal{P}(\mathcal{L})\times\mathcal{L}$ .

(i)

Then, $\mathcal{S}^{\varrho}=\langle\mathcal{L},\vdash^{\varrho}\rangle$ and $\mathcal{S}^{p\varrho}=\langle\mathcal{L},\vdash^{p\varrho}\rangle$ are monotonic.
(ii)

If $\mathcal{S}$ is monotonic, then $\vdash^{\varrho},\vdash^{p\varrho}\,\subseteq\,\vdash$ .
(iii)

$(\mathcal{S}^{\varrho})^{\varrho}=\mathcal{S}^{\varrho}$ , i.e., $(\vdash^{\varrho})^{\varrho}\,=\,\vdash^{\varrho}$ , and $(\mathcal{S}^{p\varrho})^{p\varrho}=\mathcal{S}^{p\varrho}$ , i.e., $(\vdash^{p\varrho})^{p\varrho}\,=\,\vdash^{p\varrho}$ .

Proof.

(i)

Suppose $\Gamma\cup\Sigma\cup\{\alpha\}\subseteq\mathcal{L}$ such that $\Gamma\subseteq\Sigma$ and $\Gamma\vdash^{\varrho}\alpha$ . Then, there exists $\Delta\subseteq\Gamma$ such that $(\Delta,\alpha)\in\varrho$ and $\Delta\vdash\alpha$ . So, $\Delta\subseteq\Sigma$ as well. Thus, $\Sigma\vdash^{\varrho}\alpha$ . Hence, $\mathcal{S}^{\varrho}$ is monotonic.

An almost identical argument can be used to show that $\mathcal{S}^{p\varrho}$ is monotonic.
(ii)

Suppose $\mathcal{S}$ is monotonic. Let $\Gamma\cup\{\alpha\}\subseteq\mathcal{L}$ and $\Gamma\vdash^{\varrho}\alpha$ . Then, there exists $\Delta\subseteq\Gamma$ such that $(\Delta,\alpha)\in\varrho$ and $\Delta\vdash\alpha$ . So, by monotonicity, $\Gamma\vdash\alpha$ . Hence, $\vdash^{\varrho}\,\subseteq\,\vdash$ . It is easy to see that $\vdash^{p\varrho}\,\subseteq\,\vdash^{\varrho}$ . Thus, if $\vdash^{\varrho}\,\subseteq\,\vdash$ , then $\vdash^{p\varrho}\,\subseteq\,\vdash$ as well.
(iii)

By (i), $\mathcal{S}^{\varrho}$ is monotonic. So, by (ii), $(\vdash^{\varrho})^{\varrho}\,\subseteq\,\vdash^{\varrho}$ .

Suppose $\Gamma\cup\{\alpha\}\subseteq\mathcal{L}$ and $\Gamma\vdash^{\varrho}\alpha$ . Then, there exists $\Delta\subseteq\Gamma$ such that $(\Delta,\alpha)\in\varrho$ and $\Delta\vdash\alpha$ . Clearly, $\Delta\vdash^{\varrho}\alpha$ as well. Thus, $\Gamma(\vdash^{\varrho})^{\varrho}\alpha$ , and so, $\vdash^{\varrho}\,\subseteq\,(\vdash^{\varrho})^{\varrho}$ . Hence, $(\vdash^{\varrho})^{\varrho}\,=\,\vdash^{\varrho}$ .

The argument for $\mathcal{S}^{p\varrho}$ is identical, except for the non-emptiness requirement on the $\Delta$ in the converse part.

∎

Remark 3.7.

The above theorem generalizes the results concerning the left variable inclusion companion of a logic in Lemma 2.4.

Theorem 3.8.

Suppose $\mathcal{S}_{1}=\langle\mathcal{L},\vdash_{1}\rangle,\mathcal{S}_{2}=\langle\mathcal{L},\vdash_{2}\rangle$ are logical structures such that $\vdash_{1}\,\subseteq\,\vdash_{2}$ , and $\varrho,\sigma\subseteq\mathcal{P}(\mathcal{L})\times\mathcal{L}$ such that $\varrho\subseteq\sigma$ . Then, $\vdash_{1}^{\varrho}\,\subseteq\,\vdash_{2}^{\sigma}$ and $\vdash_{1}^{p\varrho}\,\subseteq\,\vdash_{2}^{p\sigma}$ .

Proof.

Suppose $\Gamma\cup\{\alpha\}\subseteq\mathcal{L}$ such that $\Gamma\vdash_{1}^{\varrho}\alpha$ . Then, there exists $\Delta\subseteq\Gamma$ such that $(\Delta,\alpha)\in\varrho$ and $\Delta\vdash_{1}\alpha$ . Since $\varrho\subseteq\sigma$ , $(\Delta,\alpha)\in\sigma$ and as $\vdash_{1}\,\subseteq\,\vdash_{2}$ , $\Delta\vdash_{2}\alpha$ . Thus, $\Gamma\vdash_{2}^{\sigma}\alpha$ . Hence, $\vdash_{1}^{\varrho}\,\subseteq\,\vdash_{2}^{\sigma}$ .

It can be proved that $\vdash_{1}^{p\varrho}\,\subseteq\,\vdash_{2}^{p\sigma}$ with similar arguments. ∎

Corollary 3.9.

The following are some immediate observations from the above theorem.

(i)

Suppose $\mathcal{S}_{1}=\langle\mathcal{L},\vdash_{1}\rangle,\mathcal{S}_{2}=\langle\mathcal{L},\vdash_{2}\rangle$ are logical structures such that $\vdash_{1}\,\subseteq\,\vdash_{2}$ and $\varrho\subseteq\mathcal{P}(\mathcal{L})\times\mathcal{L}$ . Then, $\vdash_{1}^{\varrho}\,\subseteq\,\vdash_{2}^{\varrho}$ and $\vdash_{1}^{p\varrho}\,\subseteq\,\vdash_{2}^{p\varrho}$ .
(ii)

Suppose $\mathcal{S}=\langle\mathcal{L},\vdash\rangle$ is a logical structure and $\varrho,\sigma\subseteq\mathcal{P}(\mathcal{L})\times\mathcal{L}$ . Then $\vdash^{\varrho},\vdash^{\sigma}\,\subseteq\,\vdash^{\varrho\,\cup\,\sigma}$ and $\vdash^{\varrho\,\cap\,\sigma}\,\subseteq\,\vdash^{\varrho},\vdash^{\sigma}$ .

Theorem 3.10.

Suppose $\mathcal{S}=\langle\mathcal{L},\vdash\rangle$ is a logical structure and $\varrho,\sigma\subseteq\mathcal{P}(\mathcal{L})\times\mathcal{L}$ .

(i)

$(\vdash^{\varrho})^{\sigma}\,\subseteq\,\vdash^{\varrho}$ . The equality holds if $\varrho\subseteq\sigma$ .
(ii)

If $\mathcal{S}$ is monotonic, then $(\vdash^{\varrho})^{\sigma}\,\subseteq\,\vdash^{\sigma}$ .
(iii)

If $\varrho\subseteq\sigma$ , then $(\vdash^{\varrho})^{\sigma}\,\subseteq\,\vdash^{\sigma}$ .
(iv)

If $\vdash^{\sigma}\,\subseteq\,\vdash^{\varrho}$ , then $\vdash^{\sigma}\,\subseteq\,(\vdash^{\varrho})^{\sigma}$ .
(v)

If $\varrho\subseteq\sigma$ , then $\vdash^{\varrho}\,=\,\vdash^{\sigma}$ iff $(\vdash^{\varrho})^{\sigma}\,=\,\vdash^{\sigma}$ .

Analogous statements hold for pure relational companions of $\mathcal{S}$ .

Proof.

(i)

The $\varrho$ -companion of $\mathcal{S}$ , $\mathcal{S}^{\varrho}$ is monotonic, by Theorem 3.6(i). So, by Theorem 3.6(ii), $(\vdash^{\varrho})^{\sigma}\,\subseteq\,\vdash^{\varrho}$ .

Now, suppose $\varrho\subseteq\sigma$ and $\Gamma\cup\{\alpha\}\subseteq\mathcal{L}$ such that $\Gamma\vdash^{\varrho}\alpha$ . Then, there exists $\Delta\subseteq\Gamma$ such that $(\Delta,\alpha)\in\varrho$ and $\Delta\vdash\alpha$ . Clearly, $\Delta\vdash^{\varrho}\alpha$ . Since $\varrho\subseteq\sigma$ , $(\Delta,\alpha)\in\sigma$ . Thus, $\Gamma(\vdash^{\varrho})^{\sigma}\alpha$ . So, $\vdash^{\sigma}\,\subseteq\,(\vdash^{\varrho})^{\sigma}$ . Hence, $(\vdash^{\varrho})^{\sigma}\,=\,\vdash^{\varrho}$ .
(ii)

Suppose $\mathcal{S}$ is monotonic. Then, by Theorem 3.6(ii), $\vdash^{\varrho}\,\subseteq\,\vdash$ . Hence, by Corollary 3.9(i), $(\vdash^{\varrho})^{\sigma}\,\subseteq\,\vdash^{\sigma}$ .
(iii)

Suppose $\varrho\subseteq\sigma$ and $\Gamma\cup\{\alpha\}\subseteq\mathcal{L}$ such that $\Gamma(\vdash^{\varrho})^{\sigma}\alpha$ . Then, there exists $\Delta\subseteq\Gamma$ such that $(\Delta,\alpha)\in\sigma$ and $\Delta\vdash^{\varrho}\alpha$ . So, there exists $\Delta^{\prime}\subseteq\Delta$ such that $(\Delta^{\prime},\alpha)\in\varrho$ and $\Delta^{\prime}\vdash\alpha$ . Now, $\Delta^{\prime}\subseteq\Gamma$ , and as $\varrho\subseteq\sigma$ , $(\Delta^{\prime},\alpha)\in\sigma$ . So, $\Gamma\vdash^{\sigma}\alpha$ . Thus, $(\vdash^{\varrho})^{\sigma}\,\subseteq\,\vdash^{\sigma}$ .
(iv)

Suppose $\vdash^{\sigma}\,\subseteq\,\vdash^{\varrho}$ and $\Gamma\cup\{\alpha\}\subseteq\mathcal{L}$ such that $\Gamma\vdash^{\sigma}\alpha$ . Then, there exists $\Delta\subseteq\Gamma$ such that $(\Delta,\alpha)\in\sigma$ and $\Delta\vdash\alpha$ . Clearly, $\Delta\vdash^{\sigma}\alpha$ . Now, as $\vdash^{\sigma}\,\subseteq\,\vdash^{\varrho}$ , $\Delta\vdash^{\varrho}\alpha$ as well. Thus, $\Gamma(\vdash^{\varrho})^{\sigma}\alpha$ . Hence, $\vdash^{\sigma}\,\subseteq\,(\vdash^{\varrho})^{\sigma}$ .
(v)

Suppose $\varrho\subseteq\sigma$ . Moreover, suppose $\vdash^{\varrho}\,=\,\vdash^{\sigma}$ . Then, using parts (iii) and (iv) above, we have $(\vdash^{\varrho})^{\sigma}\,=\,\vdash^{\sigma}$ .

Conversely, suppose $(\vdash^{\varrho})^{\sigma}\,=\,\vdash^{\sigma}$ . Let $\Gamma\cup\{\alpha\}\subseteq\mathcal{L}$ such that $\Gamma\vdash^{\sigma}\alpha$ . So, $\Gamma(\vdash^{\varrho})^{\sigma}\alpha$ . Then, there exists $\Delta\subseteq\Gamma$ such that $(\Delta,\alpha)\in\sigma$ and $\Delta\vdash^{\varrho}\alpha$ . This implies that there exists $\Delta^{\prime}\subseteq\Delta$ such that $(\Delta^{\prime},\alpha)\in\varrho$ and $\Delta^{\prime}\vdash\alpha$ . Since $\Delta^{\prime}\subseteq\Gamma$ , $\Gamma\vdash^{\varrho}\alpha$ . Thus. $\vdash^{\sigma}\,\subseteq\,\vdash^{\varrho}$ . Now, as $\varrho\subseteq\sigma$ , $\vdash^{\varrho}\,\subseteq\,\vdash^{\sigma}$ , by Theorem 3.8. Hence, $\vdash^{\varrho}\,=\,\vdash^{\sigma}$ .

The proofs for the pure relational companions of $\mathcal{S}$ can be constructed with similar arguments. ∎

Definition 3.11.

Suppose $A$ is a set and $\varrho\subseteq\mathcal{P}(A)\times A$ . Then, $\varrho$ is said to be downward directed if for any $\Delta\cup\{\alpha\}\subseteq\mathcal{L}$ , $(\Delta,\alpha)\in\varrho$ implies that $(\Delta^{\prime},\alpha)\in\varrho$ for all $\Delta^{\prime}\subseteq\Delta$ .

Theorem 3.12.

Suppose $\mathcal{S}=\langle\mathcal{L},\vdash\rangle$ is a logical structure and $\varrho,\sigma\subseteq\mathcal{P}(\mathcal{L})\times\mathcal{L}$ . If $\sigma$ is downward directed, then $(\vdash^{\varrho})^{\sigma}\,\subseteq\,(\vdash^{\sigma})^{\varrho}$ . Hence, if $\varrho,\sigma$ are both downward directed, then $(\vdash^{\varrho})^{\sigma}\,=\,(\vdash^{\sigma})^{\varrho}$ .

Proof.

Suppose $\sigma$ is downward directed. Let $\Gamma\cup\{\alpha\}\subseteq\mathcal{L}$ such that $\Gamma(\vdash^{\varrho})^{\sigma}\alpha$ . Then, there exists $\Delta\subseteq\Gamma$ such that $(\Delta,\alpha)\in\sigma$ and $\Delta\vdash^{\varrho}\alpha$ . This implies that there exists $\Delta^{\prime}\subseteq\Delta$ such that $(\Delta^{\prime},\alpha)\in\varrho$ and $\Delta^{\prime}\vdash\alpha$ . Now, as $\sigma$ is downward directed, $(\Delta^{\prime},\alpha)\in\sigma$ . Then, $\Delta^{\prime}\vdash^{\sigma}\alpha$ . Now, since $(\Delta^{\prime},\alpha)\in\varrho$ and $\Delta^{\prime}\subseteq\Gamma$ , this implies that $\Gamma(\vdash^{\sigma})^{\varrho}\alpha$ . Hence, $(\vdash^{\varrho})^{\sigma}\,\subseteq\,(\vdash^{\sigma})^{\varrho}$ .

Thus, if $\varrho$ is also downward directed, then $(\vdash^{\sigma})^{\varrho}\,\subseteq\,(\vdash^{\varrho})^{\sigma}$ , and hence, in that case, $(\vdash^{\varrho})^{\sigma}\,=\,(\vdash^{\sigma})^{\varrho}$ . ∎

It is not hard to see that, for any logic $\mathcal{S}=\langle\mathcal{L},\vdash\rangle$ , $\vdash\alpha$ iff $\vdash^{l}\alpha$ for all $\alpha\in\mathcal{L}$ . The following theorem generalizes this to relational companions of logical structures.

Theorem 3.13.

Suppose $\mathcal{S}=\langle\mathcal{L},\vdash\rangle$ is a logical structure and $\varrho\subseteq\mathcal{P}(\mathcal{L})\times\mathcal{L}$ such that $(\emptyset,\alpha)\in\varrho$ for all $\alpha\in\mathcal{L}$ . Then, for any $\alpha\in\mathcal{L}$ , $\emptyset\vdash\alpha$ (written as $\vdash\alpha$ ) iff $\emptyset\vdash^{\varrho}\alpha$ (written as $\vdash^{\varrho}\alpha$ ).

Proof.

Suppose $\alpha\in\mathcal{L}$ such that $\vdash\alpha$ . Then, as $(\emptyset,\alpha)\in\varrho$ , $\vdash^{\varrho}\alpha$ . Conversely, suppose $\vdash^{\varrho}\alpha$ . Then, there exists $\Delta\subseteq\emptyset$ such that $(\Delta,\alpha)\in\varrho$ and $\Delta\vdash\alpha$ . Clearly, $\Delta=\emptyset$ . Thus, $\vdash\alpha$ . ∎

As discussed above, the left, pure left, and pure right variable inclusion companions of a logic are paraconsistent (see [3] for a detailed study on this). The following theorem generalizes this to certain relational companions of logical structures.

Definition 3.14.

Suppose $A,B$ are sets and $\varrho\subseteq A\times B$ . Then, $\varrho$ is said to have finite reach if for every $a\in A$ , the set $\varrho_{a}=\{b\in B\mid\,(a,b)\in\varrho\}$ is finite.

Theorem 3.15.

Suppose $\mathcal{S}=\langle\mathcal{L},\vdash\rangle$ is a logical structure such that $\mathcal{L}$ is infinite and $\varrho\subseteq\mathcal{P}(\mathcal{L})\times\mathcal{L}$ has finite reach. Then, for every finite $\Gamma\subseteq\mathcal{L}$ , there exists $\beta\in\mathcal{L}$ such that $\Gamma\not\vdash^{\varrho}\beta$ , i.e., every finite $\Gamma\subseteq\mathcal{L}$ is nontrivial in $\mathcal{S}^{\varrho}$ . The same is true for the pure $\varrho$ -companion of $\mathcal{S}$ .

Proof.

Suppose $\varrho$ has finite reach. Let $\Gamma$ be a finite subset of $\mathcal{L}$ . So, $\mathcal{P}(\Gamma)$ is finite. Now, as $\varrho$ has finite reach, $\varrho_{\Delta}=\{\alpha\in\mathcal{L}\mid\,(\Delta,\alpha)\in\varrho\}$ is finite for every $\Delta\in\mathcal{P}(\Gamma)$ . Thus, $\displaystyle\bigcup_{\Delta\in\mathcal{P}(\Gamma)}\varrho_{\Delta}$ , being a finite union of finite sets, is finite. Let $\beta\in\mathcal{L}\setminus\displaystyle\bigcup_{\Delta\in\mathcal{P}(\Gamma)}\varrho_{\Delta}$ (such a $\beta$ exists since $\mathcal{L}$ is infinite). Then, $(\Delta,\beta)\notin\varrho$ for every $\Delta\subseteq\Gamma$ . Thus, $\Gamma\not\vdash^{\varrho}\beta$ . Hence, every finite subset of $\mathcal{L}$ is non-trivial.

An almost identical argument proves the same result for $\mathcal{S}^{p\varrho}=\langle\mathcal{L},\vdash^{p\varrho}\rangle$ . ∎

Corollary 3.16.

Suppose $\mathcal{S}=\langle\mathcal{L},\vdash\rangle$ is a logic (in the usual sense) such that there is a unary (negation) operator $\neg$ in the signature. Moreover, let $\varrho\subseteq\mathcal{P}(\mathcal{L})\times\mathcal{L}$ be a relation with finite reach. Then, $\neg$ -ECQ fails in $\mathcal{S}^{\varrho}$ and $\mathcal{S}^{p\varrho}$ . Thus, $\mathcal{S}^{\varrho}$ and $\mathcal{S}^{p\varrho}$ are paraconsistent with respect to $\neg$ .

Definition 3.17.

A logical structure $\mathcal{S}=\langle\mathcal{L},\vdash\rangle$ is said to be finitely trivializable if there exists a finite $\Gamma\subseteq\mathcal{L}$ such that $\Gamma\vdash\alpha$ for all $\alpha\in\mathcal{L}$ , i.e., there is a finite trivial subset of $\mathcal{L}$ .

Remark 3.18.

Suppose $\mathcal{S}=\langle\mathcal{L},\vdash\rangle$ is a logical structure such that $\mathcal{L}$ is infinite and $\varrho\subseteq\mathcal{P}(\mathcal{L})\times\mathcal{L}$ is a relation with finite reach. Then, by Theorem 3.15, $\mathcal{S}^{\varrho}$ and $\mathcal{S}^{p\varrho}$ are not finitely trivializable.

Suppose $\mathcal{S}=\langle\mathcal{L},\vdash\rangle$ is a logical structure. The generalized principle of explosion (gECQ) was introduced in [2] as follows. For every $\alpha\in\mathcal{L}$ , there exists $\beta\in\mathcal{L}$ such that $\{\alpha,\beta\}\vdash\gamma$ for all $\gamma\in\mathcal{L}$ . A logic or logical structure in which gECQ fails is called NF-paraconsistent (NF stands for Negation-Free).

spECQ (where sp stands for set-point), a principle of explosion introduced in [3], can be described as follows. For each $\Gamma\subsetneq\mathcal{L}$ , there exists $\alpha\in\mathcal{L}$ such that $\Gamma\cup\{\alpha\}\subsetneq\mathcal{L}$ and $\Gamma\cup\{\alpha\}\vdash\beta$ for all $\beta\in\mathcal{L}$ .

It is easy to see that, if $\mathcal{S}=\langle\mathcal{L},\vdash\rangle$ is a logical structure that is not finitely trivializable, then gECQ and spECQ fail in it. This is also discussed in [3].

Corollary 3.19.

Suppose $\mathcal{S}=\langle\mathcal{L},\vdash\rangle$ is a logical structure such that $\mathcal{L}$ is infinite and $\varrho\subseteq\mathcal{P}(\mathcal{L})\times\mathcal{L}$ is a relation with finite reach. Then, by Remark 3.18, gECQ and spECQ fail in $\mathcal{S}^{\varrho}$ and $\mathcal{S}^{p\varrho}$ .

3.1 Hilbert-type logical structures and their restrictions

In this subsection, we first generalize Hilbert-style logics to logical structures and then discuss ‘restricted’ companions of these as generalizations of the restricted rules companions of Hilbert-style logics discussed in Section 2. We first note that any axiom in a Hilbert-style logic can also be regarded as a rule with an empty set of hypotheses. Thus, it is sufficient to deal with Hilbert-style logics induced by only a set of rules. Secondly, for the restricted rules companion of a logic, we used the variable inclusion restriction only to restrict all the rules of inference. This can be generalized to a situation where different rules are restricted in different ways.

Definition 3.20.

Suppose $\mathcal{L}$ is a set and $\mathcal{R}\subseteq\mathcal{P}(\mathcal{L})\times\mathcal{L}$ . Let $\vdash\,\subseteq\,\mathcal{P}(\mathcal{L})\times\mathcal{L}$ be defined as follows. For any $\Gamma\cup\{\alpha\}\subseteq\mathcal{L}$ , $\Gamma\vdash\alpha$ if there exists a finite sequence $(\beta_{0},\ldots,\beta_{n})$ of elements of $\mathcal{L}$ with $\beta_{n}=\alpha$ , and for each $0\leq i\leq n$ , either $\beta_{i}\in\Gamma$ , or there exists $\Gamma^{\prime}\subseteq\{\beta_{0}\ldots,\beta_{i-1}\}$ such that $(\Gamma^{\prime},\beta_{i})\in\mathcal{R}$ . Then $\mathcal{S}=\langle\mathcal{L},\vdash\rangle$ is called the Hilbert-type logical structure induced by $\mathcal{R}$ .

A Hilbert-type logical structure $\langle\mathcal{L},\vdash\rangle$ is any logical structure that is induced by some $\mathcal{R}\subseteq\mathcal{P}(\mathcal{L})\times\mathcal{L}$ .

Remark 3.21.

It is clear from the above definition that a Hilbert-type logical structure $\mathcal{S}=\langle\mathcal{L},\vdash\rangle$ is finitary and Tarski-type, i.e., reflexive, monotonic, and transitive (see [14] for the definitions).

Definition 3.22.

Suppose $\mathcal{S}=\langle\mathcal{L},\vdash\rangle$ is a Hilbert-type logical structure induced by $\mathcal{R}\subseteq\mathcal{P}(\mathcal{L})\times\mathcal{L}$ and $\Pi$ is a collection of relations from $\mathcal{P}(\mathcal{L})$ to $\mathcal{L}$ , i.e., for any $\sigma\in\Pi$ , $\sigma\subseteq\mathcal{P}(\mathcal{L})\times\mathcal{L}$ . Let $\mathcal{R}^{\Pi}=\{(\Gamma,\alpha)\in\mathcal{R}\mid\,\hbox{there exists }\sigma\in\Pi\hbox{ such that }(\Gamma,\alpha)\in\sigma\}$ . Then, the logical structure induced by $\mathcal{R}^{\Pi}$ , denoted by $\mathcal{S}^{\Pi}=\langle\mathcal{L},\vdash^{\Pi}\rangle$ , is called the $\Pi$ -restricted companion of $\mathcal{S}$ .

Remark 3.23.

Suppose $\mathcal{S}=\langle\mathcal{L},\vdash\rangle$ is a Hilbert-style logic with $\mathcal{R}$ as the set of rules of inference. Let $\Pi=\{\sigma\}$ , where $\sigma\subseteq\mathcal{P}(\mathcal{L})\times\mathcal{L}$ is defined by $(\Gamma,\alpha)\in\sigma$ iff $\mathrm{var}(\Gamma)\subseteq\mathrm{var}(\alpha)$ . Then, $\mathcal{R}^{\Pi}=\{(\Gamma,\alpha)\in\mathcal{R}\mid\,\mathrm{var}(\Gamma)\subseteq\mathrm{var}(\alpha)\}$ , and hence $\mathcal{S}^{\Pi}=\langle\mathcal{L},\vdash^{\Pi}\rangle$ , the $\Pi$ -restricted companion of $\mathcal{S}$ , is the restricted rules companion of $\mathcal{S}$ , $\mathcal{S}^{re}=\langle\mathcal{L},\vdash^{re}\rangle$ .

We can also see a $\Pi$ -restricted companion of a Hilbert-type logical structure as a relational companion of a logical structure as follows.

Suppose $\mathcal{S}=\langle\mathcal{L},\vdash\rangle$ is a logical structure induced by $\mathcal{R}\subseteq\mathcal{P}(\mathcal{L})\times\mathcal{L}$ and $\Pi$ is a collection of relations from $\mathcal{P}(\mathcal{L})$ to $\mathcal{L}$ . Then, $\mathcal{S}^{\Pi}=\langle\mathcal{L},\vdash^{\Pi}\rangle$ is the Hilbert-type logical structure induced by $\mathcal{R}^{\Pi}$ , where $\mathcal{R}^{\Pi}$ is as described in the above definition. Let $\varrho\subseteq\mathcal{P}(\mathcal{L})\times\mathcal{L}$ be defined as follows. $(\Delta,\alpha)\in\varrho$ iff $\Delta\vdash^{\Pi}\alpha$ . Then, $\mathcal{S}^{\varrho}=\langle\mathcal{L},\vdash^{\varrho}\rangle$ is the $\varrho$ -companion of $\mathcal{S}$ .

Now, suppose $\Gamma\cup\{\alpha\}\subseteq\mathcal{L}$ and $\Gamma\vdash^{\Pi}\alpha$ . So, there exists a finite sequence $(\beta_{0},\ldots,\beta_{n})$ of elements of $\mathcal{L}$ with $\beta_{n}=\alpha$ , and for each $0\leq i\leq n$ , either $\beta_{i}\in\Gamma$ , or there exists $\Gamma^{\prime}\subseteq\{\beta_{0}\ldots,\beta_{i-1}\}$ such that $(\Gamma^{\prime},\beta_{i})\in\mathcal{R}^{\Pi}$ . Let $\Delta=\Gamma\cap\{\beta_{0},\ldots,\beta_{n}\}$ . Clearly, $\Delta\vdash^{\Pi}\alpha$ , i.e., $(\Delta,\alpha)\in\varrho$ . So, $\Gamma\vdash^{\varrho}\alpha$ . Conversely, suppose $\Gamma\vdash^{\varrho}\alpha$ . Then, there exists a $\Delta\subseteq\Gamma$ such that $(\Delta,\alpha)\in\varrho$ , i.e., $\Delta\vdash^{\Pi}\alpha$ and $\Delta\vdash\alpha$ . Now, since $\mathcal{S}^{\Pi}$ is a Hilbert-type logical structure, and hence, monotonic by Remark 3.21, $\Delta\vdash^{\Pi}\alpha$ implies $\Gamma\vdash^{\Pi}\alpha$ . Hence, $\vdash^{\Pi}\,=\,\vdash^{\varrho}$ .

Thus, the restricted rules companions of a logic can also be seen as relational companions of the logic.

4 Conclusions and future directions

In this article, we have proposed the relational companions of logical structures as generalizations of the variable inclusion companions of logics and the restricted rules companions of Hilbert-style logics. More properties of these companion logics, especially those of the $\Pi$ -restricted companions of Hilbert-type logics, could be investigated further.

Another, perhaps interesting, observation is the possibility of using a logical structure $\mathcal{S}_{1}=\langle\mathcal{L},\vdash_{1}\rangle$ to define a companion to another logical structure $\mathcal{S}_{2}=\langle\mathcal{L},\vdash_{2}\rangle$ in the following way. Since $\vdash_{1}\subseteq\mathcal{P}(\mathcal{L})\times\mathcal{L}$ is also a relation from $\mathcal{P}(\mathcal{L})$ to $\mathcal{L}$ , we can define the $\vdash_{1}$ -companion of $\mathcal{S}_{2}$ . This is already the case in the way we have described a $\Pi$ -restricted companion of a Hilbert-type logical structure as a relational companion at the end of the previous section. This line of investigation can be interesting from the perspective of combining logical structures as well, since this is, in a way, merging the two relations $\vdash_{1}$ and $\vdash_{2}$ .

References

[1] S.S̃. Basu and M.K̃. Chakraborty, Restricted rules of inference and paraconsistency, Logic Journal of the IGPL 30 (2021), no. 3, 534–560.
[2] S.S̃. Basu and S. Roy, Negation-free definitions of paraconsistency, Proceedings of the 10th International Conference on Non-Classical Logics. Theory and Applications, Łódź, Poland, 14-18 March 2022 (Andrzej Indrzejczak and Michał Zawidzki, eds.), Electronic Proceedings in Theoretical Computer Science, vol. 358, Open Publishing Association, 2022, pp. 150–159.
[3] S.S̃. Basu and S. Roy, Generalized explosion principles, http://arxiv.org/abs/2307.15358 (2023), 28.
[4] J.Ỹ. Béziau, Universal logic, Logica’94 - Proceedings of the 8th International Symposium (Prague) (T.Childers and O.Majer, eds.), 1994, pp. 73–93.
[5] J.Ỹ. Béziau, 13 questions about universal logic, University of Łódź. Department of Logic. Bulletin of the Section of Logic 35 (2006), no. 2-3, 133–150, Questions by Linda Eastwood.
[6] S. Bonzio, J. Gil-Férez, F. Paoli, and L. Peruzzi, On paraconsistent weak Kleene logic: Axiomatisation and algebraic analysis, Studia Logica 105 (2017), no. 2, 253–297.
[7] S. Bonzio, T. Moraschini, and M. Pra Baldi, Logics of left variable inclusion and Płonka sums of matrices, Archive for Mathematical Logic 60 (2021), no. 1-2, 49–76.
[8] S. Bonzio, F. Paoli, and M. Pra Baldi, Logics of variable inclusion, Trends in Logic—Studia Logica Library, vol. 59, Springer, Cham, 2022.
[9] C. Caleiro, S. Marcelino, and P. Filipe, Infectious semantics and analytic calculi for even more inclusion logics, 2020 IEEE 50th International Symposium on Multiple-Valued Logic—ISMVL 2020, IEEE Computer Soc., Los Alamitos, CA, 2020, pp. 224–229.
[10] E.G̃. de Souza, A. Costa-Leite, and D. H.B̃. Dias, Paraconsistent orbits of logics, Logica Universalis 15 (2021), no. 3, 271–289.
[11] J.M̃. Font, Abstract algebraic logic: An introductory textbook, Studies in Logic and the Foundations of Mathematics, College Publications, 2016.
[12] J.M̃. Font, R. Jansana, and D. Pigozzi, A survey of abstract algebraic logic, Studia Logica 74 (2003), no. 1, 13–97.
[13] F. Paoli, M. Pra Baldi, and D. Szmuc, Pure variable inclusion logics, Logic and Logical Philosophy 30 (2021), no. 4, 631–652.
[14] S. Roy, S.S̃. Basu, and M.K̃. Chakraborty, Lindenbaum-type logical structures, Logica Universalis 17 (2023), no. 1, 69–102.

Relational Companions of Logics111A version of this article has been submitted to the Indian Conference on Logic and its Applications 2025

Abstract

1 Introduction

2 Left variable inclusion and restricted rules companions

Definition 2.1.

Definition 2.2.

Theorem 2.3 ([1, Theorem 4.3]).

Lemma 2.4.

Proof.

Theorem 2.5.

Proof.

Remark 2.6.

Theorem 2.7.

Proof.

3 Relational companions of a logical structure

Definition 3.1.

Example 3.2.

Example 3.3.

Example 3.4.

Example 3.5.

Theorem 3.6.

Proof.

Remark 3.7.

Theorem 3.8.

Proof.

Corollary 3.9.

Theorem 3.10.

Proof.

Definition 3.11.

Theorem 3.12.

Proof.

Theorem 3.13.

Proof.

Definition 3.14.

Theorem 3.15.

Proof.

Corollary 3.16.

Definition 3.17.

Remark 3.18.

Corollary 3.19.

3.1 Hilbert-type logical structures and their restrictions

Definition 3.20.

Remark 3.21.

Definition 3.22.

Remark 3.23.

4 Conclusions and future directions

References

Relational Companions of Logics¹¹1A version of this article has been submitted to the Indian Conference on Logic and its Applications 2025