Proof. We begin by proving the “if” part. Define

$$ \begin{align*} \mathsf{K} := \{ \boldsymbol{Fm}/ \theta(\varGamma, \boldsymbol{\tau}) \colon \varGamma \subseteq Fm \text{ and }\textrm{Cn}_{\vdash}(\varGamma) = \varGamma \}. \end{align*} $$

By assumption, for every $\varphi \in Fm$ and $\varGamma \subseteq Fm$ such that $\textrm {Cn}_{\vdash }(\varGamma ) = \varGamma $ ,

$$ \begin{align*} \varphi / \theta(\varGamma, \boldsymbol{\tau}) \in \boldsymbol{\tau}(\boldsymbol{Fm}/ \theta(\varGamma, \boldsymbol{\tau})) \Longleftrightarrow \boldsymbol{\tau}(\varphi) \subseteq \theta(\varGamma, \boldsymbol{\tau}) \Longleftrightarrow \varphi \in \varGamma. \end{align*} $$

Consequently, for every $\varGamma \subseteq Fm$ such that $\textrm {Cn}_{\vdash }(\varGamma ) = \varGamma $ ,

$$ \begin{align*} \langle \boldsymbol{Fm}, \varGamma \rangle \in {\mathbb{H}_{\textrm{s}}^{-1}}(\langle \boldsymbol{Fm} / \theta(\varGamma, \boldsymbol{\tau}), \boldsymbol{\tau}(\boldsymbol{Fm}/ \theta(\varGamma, \boldsymbol{\tau})) \rangle). \end{align*} $$

Hence, by Lemma 2.3, the following classes of matrices induce the same logic:

$$ \begin{align*} \mathsf{M}_{1} &:= \{ \langle \boldsymbol{Fm}, \varGamma \rangle \colon \varGamma \subseteq Fm \text{ and }\textrm{Cn}_{\vdash}(\varGamma) = \varGamma \},\\ \mathsf{M}_{2} & := \{ \langle \boldsymbol{A}, \boldsymbol{\tau}(\boldsymbol{A}) \rangle \colon \boldsymbol{A} \in \mathsf{K} \}. \end{align*} $$

As $\mathsf {M}_{1}$ is a matrix semantics for $\vdash $ , so is $\mathsf {M}_{2}$ . By Proposition 3.2 we conclude that $\mathsf {K}$ is a $\boldsymbol {\tau }$ -algebraic semantics for $\vdash $ .

To prove the “only if” part, let $\mathsf {K}$ be a $\boldsymbol {\tau }$ -algebraic semantics for $\vdash $ . Then consider $\varGamma \cup \{ \varphi \} \subseteq Fm$ such that $\boldsymbol {\tau }(\varphi ) \subseteq \theta (\varGamma , \boldsymbol {\tau })$ . In order to prove that $\varGamma \vdash \varphi $ , it suffices to show that for every $\boldsymbol {A} \in \mathsf {K}$ and homomorphism $h \colon \boldsymbol {Fm} \to \boldsymbol {A}$ , if $h[\varGamma ] \subseteq \boldsymbol {\tau }(\boldsymbol {A})$ , then $h(\varphi ) \in \boldsymbol {\tau }(\boldsymbol {A})$ . To this end, consider $\boldsymbol {A} \in \mathsf {K}$ and a homomorphism $h \colon \boldsymbol {Fm} \to \boldsymbol {A}$ such that $h[\varGamma ] \subseteq \boldsymbol {\tau }(\boldsymbol {A})$ . Observe that the kernel $\textrm {Ker}(h)$ of h contains the generators of $\theta (\varGamma , \boldsymbol {\tau })$ , whence

$$ \begin{align*} \boldsymbol{\tau}(\varphi) \subseteq \theta(\varGamma, \boldsymbol{\tau}) \subseteq \textrm{Ker}(h). \end{align*} $$

But this amounts to $h(\varphi ) \in \boldsymbol {\tau }(\boldsymbol {A})$ . Thus, we conclude that $\varGamma \vdash \varphi $ , as desired.⊣

Proof. This is attributed to Suszko in [Reference Rautenberg40, p. 67]. For a detailed argument, however, the reader may consult the proof of [Reference Albuquerque, Font, Jansana and Moraschini1, Theorem 10].⊣

Proof. Let $\vdash $ be an almost assertional logic. Then $\vdash $ has a matrix semantics $\mathsf {M}$ for which there is a formula $\varphi (x)$ such that $\varphi ^{\boldsymbol {A}} \colon A \to A$ is a constant function and $F = \{ \varphi ^{\boldsymbol {A}} \}$ , for all $\langle \boldsymbol {A}, F \rangle \in \mathsf {M}$ with $F \ne \emptyset $ . Since $\mathsf {M}$ is a matrix semantics for $\vdash $ , we get

(3) $$ \begin{align} y \vdash \varphi(x). \end{align} $$

To prove the “only if” part, suppose that $\vdash $ has a $\boldsymbol {\tau }$ -algebraic semantics $\mathsf {K}$ . As $\vdash $ lacks theorems, there are $\boldsymbol {A} \in \mathsf {K}$ and $a \in A$ such that $\varphi ^{\boldsymbol {A}}(a) \notin \boldsymbol {\tau }(\boldsymbol {A})$ . Together with (5), this implies $\boldsymbol {\tau }(\boldsymbol {A}) = \emptyset $ . Consequently, $\boldsymbol {\tau }$ satisfies condition (i). Moreover, $\boldsymbol {\tau }$ satisfies condition (ii) by Proposition 3.3.

Then we turn to prove the “if” part. As $\mathsf {M}$ is a matrix semantics for $\vdash $ , the same holds for $\mathsf {M}^{\ast }$ by Corollary 2.4. Furthermore, for every $\langle \boldsymbol {A}, F \rangle \in \mathsf {M}^{\ast }$ ,

(4) $$ \begin{align} \text{if }a \in F \text{, then }a \in \boldsymbol{\tau}(\boldsymbol{A}). \end{align} $$

To prove this, consider $\langle \boldsymbol {A}, F \rangle \in \mathsf {M}^{\ast }$ , $a \in F$ , and $\varepsilon \thickapprox \delta \in \boldsymbol {\tau }$ . From condition (ii) it follows that for every formula $\varphi (v,\vec {z})$ and $\vec {c} \in A$ ,

$$ \begin{align*} \varphi^{\boldsymbol{A}}(\varepsilon^{\boldsymbol{A}}(a), \vec{c}) \in F \Longleftrightarrow \varphi^{\boldsymbol{A}}(\delta^{\boldsymbol{A}}(a), \vec{c}) \in F. \end{align*} $$

This means that for every unary polynomial function p of $\boldsymbol {A}$ ,

$$ \begin{align*} p(\varepsilon^{\boldsymbol{A}}(a)) \in F \Longleftrightarrow p(\delta^{\boldsymbol{A}}(a)) \in F. \end{align*} $$

By Proposition 2.2, we conclude that $\langle \varepsilon ^{\boldsymbol {A}}(a), \delta ^{\boldsymbol {A}}(a) \rangle \in \boldsymbol {\varOmega }^{\boldsymbol {A}}F$ . Since $\langle \boldsymbol {A}, F \rangle \in \mathsf {M}^{\ast }$ , the matrix $\langle \boldsymbol {A}, F \rangle $ is reduced, i.e., $\boldsymbol {\varOmega }^{\boldsymbol {A}}F$ is the identity relation on A. Consequently, $\varepsilon ^{\boldsymbol {A}}(a) = \delta ^{\boldsymbol {A}}(a)$ , establishing (4).

Then set

$$ \begin{align*} \boldsymbol{\rho} := \boldsymbol{\tau} \cup \{ x \thickapprox \varphi(x) \}, \end{align*} $$

and observe that for every $\langle \boldsymbol {A}, F \rangle \in \mathsf {M}^{\ast }$ ,

(5) $$ \begin{align} \text{if }F \ne \emptyset, \text{ then }\boldsymbol{\rho}(\boldsymbol{A}) = F. \end{align} $$

To prove this, consider $\langle \boldsymbol {A}, F \rangle \in \mathsf {M}^{\ast }$ such that $F \ne \emptyset $ . Then $\langle \boldsymbol {A}, F \rangle = \langle \boldsymbol {B} / \boldsymbol {\varOmega }^{\boldsymbol {B}}G, G / \boldsymbol {\varOmega }^{\boldsymbol {B}}G\rangle $ for some $\langle \boldsymbol {B}, G \rangle \in \mathsf {M}$ such that $G = \emptyset $ . By assumption, $\varphi ^{\boldsymbol {B}} \colon B \to B$ is a constant function and $G = \{ \varphi ^{\boldsymbol {B}} \}$ . This easily implies

$$ \begin{align*} F = \{ a \in A \colon a = \varphi^{\boldsymbol{A}}(a) \}. \end{align*} $$

Together with (4), the above display implies (5).

Recall that $\mathsf {M}^{\ast }$ is a matrix semantics for $\vdash $ and that $\vdash $ lacks theorems. Then by Lemma 4.8 the following is also a matrix semantics for $\vdash $ :

$$ \begin{align*} \mathsf{N} := \{ \langle \boldsymbol{A}, F \rangle \in \mathsf{M}^{\ast} \colon F \ne \emptyset \} \cup \{ \langle \boldsymbol{Fm}, \emptyset \rangle \}. \end{align*} $$

Moreover,

(6) $$ \begin{align} \text{if }\langle \boldsymbol{A}, F \rangle \in \mathsf{N}\text{, then }F = \boldsymbol{\rho}(\boldsymbol{A}). \end{align} $$

To prove this, consider $\langle \boldsymbol {A}, F \rangle \in \mathsf {N}$ . If $F \ne \emptyset $ , then $F = \boldsymbol {\rho }(\boldsymbol {A})$ by (5). Then we consider the case where $F = \emptyset $ . By definition of $\mathsf {N}$ , in this case $\langle \boldsymbol {A}, F \rangle = \langle \boldsymbol {Fm}, \emptyset \rangle $ . By condition (i) we get $\boldsymbol {\rho }(\boldsymbol {Fm}) \subseteq \boldsymbol {\tau }(\boldsymbol {Fm}) = \emptyset $ , whence $\boldsymbol {\rho }(\boldsymbol {Fm}) = \emptyset $ as desired. This establishes (6).

As a consequence,

$$ \begin{align*} \mathsf{N} = \{ \langle \boldsymbol{A}, \boldsymbol{\rho}(\boldsymbol{A}) \rangle \colon \boldsymbol{A} \in \mathsf{K} \}, \end{align*} $$

where $\mathsf {K}$ is the class of algebraic reducts of matrices in $\mathsf {N}$ . Since $\mathsf {N}$ is a matrix semantics for $\vdash $ , we can apply Proposition 3.2 obtaining that $\mathsf {K}$ is a $\boldsymbol {\rho }$ -algebraic semantics for $\vdash $ .⊣

Proof. Observe that a logic $\vdash $ is either assertional or almost assertional if and only if it has a matrix semantics $\mathsf {M}$ for which there is a formula $\psi (x)$ such that $\psi ^{\boldsymbol {A}} \colon A \to A$ is a constant function and $F = \{ \psi ^{\boldsymbol {A}} \}$ , for all $\langle \boldsymbol {A}, F \rangle \in \mathsf {M}$ with $F \ne \emptyset $ .

To prove the “only if’ part, consider a logic $\vdash $ that is either assertional or almost assertional. By the above remarks, $\vdash $ has a unital matrix semantics $\mathsf {M}$ and a formula $\psi (x)$ such that $y \vdash \psi (x)$ . Hence, with an application of Proposition 4.2, we obtain $x, y, \varphi (x, \vec {z}) \vdash \varphi (y, \vec {z})$ for every $\varphi (v, \vec {z}) \in Fm$ , as desired.

Then we turn to prove the “if’ part. Consider a logic $\vdash $ for which there is a formula $\psi (x)$ such that $y \vdash \psi (x)$ and $x, y, \varphi (x, \vec {z}) \vdash \varphi (y, \vec {z})$ for every $\varphi (v, \vec {z}) \in Fm$ . By Proposition 4.2, $\vdash $ has a unital matrix semantics $\mathsf {M}$ . The fact that $\mathsf {M}$ is unital and $y \vdash \psi (x)$ imply that $\psi ^{\boldsymbol {A}} \colon A \to A$ is a constant function and $F = \{ \psi ^{\boldsymbol {A}} \}$ , for all $\langle \boldsymbol {A}, F \rangle \in \mathsf {M}$ with $F \ne \emptyset $ . Thus, by the remark at the beginning of the proof, $\vdash $ is either assertional or almost assertional.⊣

Proof. (i): Observe that if $\vdash $ is inconsistent, then any class of algebras $\mathsf {K}$ is an $\boldsymbol {\tau }$ -algebraic semantics for $\vdash $ where $\boldsymbol {\tau } = \emptyset $ .

(ii): Let $\vdash $ be almost inconsistent. To prove the “only if” part, suppose, with a view to contradiction, that $\vdash $ has a $\boldsymbol {\tau }$ -algebraic semantics $\mathsf {K}$ , but that $\mathscr {L}_{\vdash }$ is either empty or comprises only a constant symbol $1$ . Due to the poor language in which $\vdash $ is formulated,

$$ \begin{align*} \boldsymbol{\tau} \subseteq \{ x \thickapprox x, x \thickapprox 1, 1 \thickapprox x, 1 \thickapprox 1 \}. \end{align*} $$

We can assume without loss of generality that $\boldsymbol {\tau }$ does not contain any trivially valid equation, whence $\boldsymbol {\tau } \subseteq \{ x \thickapprox 1, 1 \thickapprox x \}$ . Furthermore, by symmetry we can assume that $\boldsymbol {\tau } \subseteq \{ x \thickapprox 1 \}$ . Thus, either $\boldsymbol {\tau } = \emptyset $ or $\boldsymbol {\tau } = \{ x \thickapprox 1 \}$ . In both cases, the fact that $\mathsf {K}$ is a $\boldsymbol {\tau }$ -algebraic semantics for $\vdash $ implies $\emptyset \vdash 1$ , contradicting the fact that $\vdash $ lacks theorems.

To prove the “if” part, suppose first that $\mathscr {L}_{\vdash }$ comprises a non-constant connective $f(x_{1}, \dots , x_{n})$ . Then define

$$ \begin{align*} \boldsymbol{\tau} := \{ f(x, \dots, x) \thickapprox f(f(x, \dots, x), \dots, f(x, \dots, x)) \}. \end{align*} $$

Clearly, $\boldsymbol {\tau }(\boldsymbol {Fm}) = \emptyset $ . As $\vdash $ is almost inconsistent, this implies that $\mathsf {K} := \{ \boldsymbol {Fm} \}$ is a $\boldsymbol {\tau }$ -algebraic semantics for $\vdash $ .

The case where $\mathscr {L}_{\vdash }$ comprises two constant symbols $1$ and $0$ is treated similarly, taking $\boldsymbol {\tau } := \{ 1 \thickapprox 0 \}$ .⊣

Proof. Consider an arbitrary logic $\vdash $ . Furthermore, let $\mathsf {M}$ be a matrix semantics for $\vdash $ (it exists by Theorem 2.1). For every $\langle \boldsymbol {A}, F \rangle \in \mathsf {M}$ , let also $\boldsymbol {A}^{+}$ be the expansion of $\boldsymbol {A}$ with a new binary operation $+ \colon A^{2} \to A$ that is interpreted as the projection of the first coordinate, i.e.,

$$ \begin{align*} a + c := a,\quad \text{for all }a, c \in A. \end{align*} $$

Then let $\vdash ^{+}$ be the logic induced by the class of matrices

$$ \begin{align*} \mathsf{M}^{+} := \{ \langle \boldsymbol{A}^{+}, F \rangle : \langle \boldsymbol{A}, F \rangle \in \mathsf{M} \}. \end{align*} $$

From the definition of $\mathsf {M}^{+}$ it follows that $\vdash $ and $\vdash ^{+}$ are term-equivalent.

Now, from the definition of $\vdash ^{+}$ it follows that the formulas x and $x + x$ are logically equivalent in $\vdash ^{+}$ . Since $\vdash ^{+}$ is not graph-based, we can apply Theorem 6.2 obtaining that it has an algebraic semantics.⊣

Convention 6.5. Given a formula $\gamma $ , we denote by $T(\gamma )^{-x}$ the tree obtained by removing from $T(\gamma )$ the leaves labeled by the variable x.

Proof of Theorem 6.2. Since $\vdash $ is not graph-based, either $\mathscr {L}_{\vdash }$ comprises two distinct unary connectives $\square $ and $\Diamond $ or it comprises at least an n-ary connective with $n \geqslant 2$ . We shall detail the case where $\mathscr {L}_{\vdash }$ comprises $\square x$ and $\Diamond x$ , as the other one is analogous.

Suppose that $\vdash $ has two distinct logically equivalent formulas $\varphi $ and $\psi $ such that $\textit {Var}(\varphi ) \cup \textit {Var}(\psi ) = \{ x \}$ . By Lemma 2.7, the logic $\vdash $ has a matrix semantics $\mathsf {M}$ validating the equation $\varphi \thickapprox \psi $ . Notice that we can safely assume that

(7) $$ \begin{align} \textit{Var}(\varphi) = \textit{Var}(\psi) = \{ x \}. \end{align} $$

For suppose that (7) does not hold. Then by symmetry we can assume that $\textit {Var}(\varphi ) = \{ x \}$ and $\textit {Var}(\psi ) = \emptyset $ . Now, from $\mathsf {M} \vDash \varphi (x) \thickapprox \psi (x)$ it follows $\mathsf {M}\vDash \varphi (\varphi (x)) \thickapprox \psi (\varphi (x))$ . Since $\textit {Var}(\psi ) = \emptyset $ , the formula $\psi $ is closed, whence $\psi (\varphi (x)) = \psi (x)$ . Thus, $\mathsf {M}\vDash \varphi (\varphi (x)) \thickapprox \psi (x)$ . Together with $\mathsf {M} \vDash \varphi (x) \thickapprox \psi (x)$ , this implies

$$ \begin{align*} \mathsf{M} \vDash \varphi(x) \thickapprox \varphi(\varphi(x)). \end{align*} $$

We have two cases: either $\varphi = x$ or $\varphi \ne x$ . First suppose that $\varphi = x$ . As $\psi $ is a closed formula, $\mathsf {M} \vDash x \thickapprox \psi $ implies that algebraic reducts of the matrices in $\mathsf {M}$ are trivial. Because $\mathsf {M}$ is a matrix semantics for $\vdash $ , this yields $x \vdash y$ which, in turn, means that $\vdash $ is trivial. As the language of $\vdash $ comprises a non-constant symbol, from Proposition 5.2 it follows that $\vdash $ has an algebraic semantics, thus concluding the proof of the theorem. Then it only remains to consider the case where $\varphi \ne x$ . In this case, $\varphi (\varphi (x)) \ne \varphi (x)$ . Thus we can replace $\psi $ by $\varphi (\varphi (x))$ , validating both the assumption of the theorem and (7). Accordingly, from now we shall assume that (7) holds.

Let $k \in \omega $ be greater than the length of all branches in $T(\varphi )$ and $T(\psi )$ . As $\varphi = \varphi (x)$ and $\psi = \psi (x)$ , it makes sense to define

$$ \begin{align*} \varphi' := \square^{2k}\Diamond \varphi(\square^{k} \Diamond x) \text{ and }\psi':= \square^{2k}\Diamond \psi(\square^{k} \Diamond x). \end{align*} $$

Furthermore, since $\mathsf {M} \vDash \varphi \thickapprox \psi $ ,

(8) $$ \begin{align} \mathsf{M} \vDash \varphi' \thickapprox \psi'. \end{align} $$

Now, let m be the number of occurrences of x in $\varphi '(x)$ . Then, consider distinct variables $x_{1}, \dots , x_{m}$ and let $\hat {\varphi }'(x_{1}, \dots , x_{m})$ be the formula obtained by replacing the j-th occurrence of x in $\varphi '$ by $x_{j}$ for all $j \leqslant m$ . Clearly,

$$ \begin{align*} \varphi' = \hat{\varphi}'(x, \dots, x). \end{align*} $$

Claim 6.6. There are no $\alpha _{1}, \dots , \alpha _{m}, \beta \in Fm$ such that

$$ \begin{align*} \hat{\varphi}'(\alpha_{1}, \dots, \alpha_{m}) = \psi'(\beta). \end{align*} $$

Proof. Given a tree T and two nodes $w < u$ , we denote by $[w, u]$ the set of nodes of T in between $w$ and u (including $w$ and u). Bearing this in mind, suppose, with a view to contradiction, that $\hat {\varphi }'(\alpha _{1}, \dots , \alpha _{m}) = \psi '(\beta )$ for some $\alpha _{1}, \dots , \alpha _{m}, \beta \in Fm$ . Consequently,

(9) $$ \begin{align} T(\hat{\varphi}'(\alpha_{1}, \dots, \alpha_{m})) = T(\psi'(\beta)). \end{align} $$

Notice that, because of $\varphi ' = \square ^{2k}\Diamond \varphi (\square ^{k} \Diamond x)$ , the tree $T(\varphi )^{-x}$ can be identified with a unique downset of the tree obtained by removing the smallest $2k+1$ nodes from $T(\hat {\varphi }'(\alpha _{1}, \dots , \alpha _{m}))$ . Working under this identification, a node $w$ of $T(\hat {\varphi }'(\alpha _{1}, \dots , \alpha _{m}))$ belongs to $T(\varphi )^{-x}$ if and only if it satisfies the following conditions:

1. (i) The downset of $w$ in $T(\hat {\varphi }'(\alpha _{1}, \dots , \alpha _{m}))$ has at least $2k+2$ and at most $3k$ elements;

2. (ii) There are no nodes $u < v$ in $T(\hat {\varphi }'(\alpha _{1}, \dots , \alpha _{m}))$ such that $w \in [u, v]$ and $[u, v] = \{ b_{1}, \dots , b_{k}, d \}$ , where

   $$ \begin{align*} b_{1} < \dots < b_{k} < d \end{align*} $$
   and the nodes $b_{i}$ and d are labeled, respectively, with $\square $ and $\Diamond $ .

This observation is a consequence of the fact that k is greater than the length of branches in $T(\varphi )$ and $\varphi ' = \square ^{2k}\Diamond \varphi (\square ^{k}\Diamond x)$ .

A similar argument shows that $T(\psi )^{-x}$ can be identified with the subtree of $T(\psi '(\beta ))$ comprising the nodes $w$ of $T(\psi '(\beta ))$ satisfying conditions (i) and (ii). Together with (9), this implies $T(\varphi )^{-x} = T(\psi )^{-x}$ and, therefore, $\varphi = \psi $ . But this contradicts the assumption that the formulas $\varphi $ and $\psi $ are distinct.⊣

Our aim is to show that $\vdash $ has a $\boldsymbol {\tau }$ -algebraic semantics, where

$$ \begin{align*} \boldsymbol{\tau}(x) := \{ \varphi' \thickapprox \psi' \}. \end{align*} $$

Suppose the contrary, with a view to contradiction. By Proposition 3.5 there is $\varGamma \cup \{ \gamma \} \subseteq Fm$ such that $\boldsymbol {\tau }(\gamma ) \subseteq \theta (\varGamma , \boldsymbol {\tau })$ and $\varGamma \nvdash \gamma $ . We can assume without loss of generality $\varGamma = \textrm {Cn}_{\vdash }(\varGamma )$ .

Since $\boldsymbol {\tau }(\gamma ) \subseteq \theta (\varGamma , \boldsymbol {\tau })$ , by Theorem 6.4 there are

$$ \begin{align*} \alpha_{0}, \dots, \alpha_{n} &\in Fm,\\ \beta_{0}, \dots \beta_{n-1} &\in \varGamma,\\ \delta_{0}(x, \vec{z}), \dots, \delta_{n-1}(x, \vec{z}) &\in Fm, \end{align*} $$

such that $\varphi '(\gamma ) = \alpha _{0}$ , $\psi '(\gamma ) = \alpha _{n}$ , and

(10) $$ \begin{align} \{ \alpha_{i}, \alpha_{i+1} \} = \{ \delta_{i}(\varphi'(\beta_{i}), \vec{z}), \delta_{i}(\psi'(\beta_{i}), \vec{z}) \},\quad \text{for every }i < n. \end{align} $$

We shall prove by induction on i that for all $\alpha _{i}$ there are $\gamma _{1}^{i}, \dots , \gamma _{m}^{i} \in Fm$ such that

(11) $$ \begin{align} \alpha_{i} = \hat{\varphi}'(\gamma_{1}^{i}, \dots, \gamma_{m}^{i}) \text{ and }\gamma \equiv \gamma_{1}^{i} \equiv \cdots \equiv \gamma_{m}^{i} \quad\mod \theta(\varGamma, \boldsymbol{\tau}). \end{align} $$

For the base case, it suffices to take

$$ \begin{align*} \gamma = \gamma_{1}^{0} = \cdots = \gamma_{m}^{0}. \end{align*} $$

For the induction step, suppose that $\alpha _{i} = \hat {\varphi }'(\gamma _{1}^{i}, \dots , \gamma _{m}^{i})$ for some $\gamma _{1}^{i}, \dots , \gamma _{m}^{i} \in Fm$ such that $\gamma \equiv \gamma _{1}^{i}\equiv \cdots \equiv \gamma _{m}^{i} \quad\mod \theta (\varGamma , \boldsymbol {\tau })$ . Moreover, from (10) it follows $\{ \alpha _{i}, \alpha _{i+1} \} = \{ \delta _{i}(\varphi '(\beta _{i}), \vec {z}), \delta _{i}(\psi '(\beta _{i}), \vec {z}) \}$ . There are two cases:

1. (i) either $\hat {\varphi }'(\gamma _{1}^{i}, \dots , \gamma _{m}^{i}) = \alpha _{i} = \delta _{i}(\varphi '(\beta _{i}), \vec {z})$ and $\alpha _{i+1} = \delta _{i}(\psi '(\beta _{i}), \vec {z})$ , or

2. (ii) $\hat {\varphi }'(\gamma _{1}^{i}, \dots , \gamma _{m}^{i}) = \alpha _{i} = \delta _{i}(\psi '(\beta _{i}), \vec {z})$ and $\alpha _{i+1} = \delta _{i}(\varphi '(\beta _{i}), \vec {z})$ .

(i): We shall prove that there exist $\varepsilon _{1}(x, \vec {z}), \dots , \varepsilon _{m}(x, \vec {z}) \in Fm$ such that

(12) $$ \begin{align} \delta_{i}(x, \vec{z}) = \hat{\varphi}'(\varepsilon_{1}(x, \vec{z}), \dots, \varepsilon_{m}(x, \vec{z})). \end{align} $$

Suppose the contrary, with a view to contradiction. By (i), $\hat {\varphi }'(\gamma _{1}^{i}, \dots , \gamma _{m}^{i}) = \delta _{i}(\varphi '(\beta _{i}), \vec {z})$ . Thus, $T(\delta _{i}(x, \vec {z}))^{-x}$ and $T(\varphi ')^{-x}$ can be identified with two unique (possibly empty) downsets of $T(\hat {\varphi }'(\gamma _{1}^{i}, \dots , \gamma _{m}^{i}) )$ . Accordingly, from now on we shall work under this identification.

As $\delta _{i}(x, \vec {z}) \ne \hat {\varphi }'(\varepsilon _{1}, \dots , \varepsilon _{m})$ for any $\varepsilon _{1}, \dots , \varepsilon _{m} \in Fm$ , the tree $T(\varphi ')^{-x}$ is not a downset of $T(\delta _{i}(x, \vec {z}))^{-x}$ . Let then $w$ be a node of $T(\varphi ')^{-x}$ that is minimal in $T(\varphi ')^{-x} \smallsetminus T(\delta _{i}(x, \vec {z}))^{-x}$ . Let also $\chi $ be the unique formula such that $T(\chi )$ is the upset of $w$ in $T(\hat {\varphi }'(\gamma _{1}^{i}, \dots , \gamma _{m}^{i}))$ . As $\delta _{i}(\varphi '(\beta _{i}), \vec {z}) = \hat {\varphi }'(\gamma _{1}^{i}, \dots , \gamma _{m}^{i})$ , the minimality of $w$ implies that

(13) $$ \begin{align} \chi = \varphi'(\beta_{i}) = \square^{2k}\Diamond \varphi(\square^{k} \Diamond \beta_{i}). \end{align} $$

As k is greater than the length of all branches in $T(\varphi )$ and $\varphi ' = \square ^{2k}\Diamond \varphi (\square ^{k} \Diamond x)$ , there cannot be any point u in $T(\varphi ')^{-x}$ other than the root whose upset in $T(\hat {\varphi }'(\gamma _{1}^{i}, \dots , \gamma _{m}^{i}))$ is the subformula tree of a formula starting with the prefix $\square ^{2k}$ . Thus we conclude that $w$ is the root of $T(\varphi ')^{-x}$ and, therefore, of $T(\hat {\varphi }'(\gamma _{1}^{i}, \dots , \gamma _{m}^{i}))$ . As $T(\chi )$ is the upset of the root $w$ of $T(\hat {\varphi }'(\gamma _{1}^{i}, \dots , \gamma _{m}^{i}))$ , together with (13), this implies

(14) $$ \begin{align} \hat{\varphi}'(\gamma_{1}^{i}, \dots, \gamma_{m}^{i}) = \chi = \varphi'(\beta_{i}). \end{align} $$

Since $\textit {Var}(\varphi ') = \{ x \}$ by (7), this yields

$$ \begin{align*} \beta_{i} = \gamma_{1}^{i} = \cdots = \gamma_{m}^{i}. \end{align*} $$

As by inductive hypothesis $\gamma \equiv \gamma _{1}^{i}\equiv \cdots \equiv \gamma _{m}^{i} \quad\mod \theta (\varGamma , \boldsymbol {\tau })$ , the above display guarantees $\langle \gamma , \beta _{i} \rangle \in \theta (\varGamma , \boldsymbol {\tau })$ . Lastly, since $\beta _{i} \in \varGamma $ and $\theta (\varGamma , \boldsymbol {\tau })$ is compatible with $\varGamma $ by Claim 6.7, this implies $\gamma \in \varGamma $ , a contradiction. This establishes that there exist $\varepsilon _{1}(x, \vec {z}), \dots , \varepsilon _{m}(x, \vec {z}) \in Fm$ validating (12).

From (12) it follows

$$ \begin{align*} \hat{\varphi}'(\gamma_{1}^{i}, \dots, \gamma_{m}^{i}) = \delta_{i}(\varphi'(\beta_{i}), \vec{z}) = \hat{\varphi}'(\varepsilon_{1}(\varphi'(\beta_{i}), \vec{z}), \dots, \varepsilon_{m}(\varphi'(\beta_{i}), \vec{z})). \end{align*} $$

Consequently,

$$ \begin{align*} \gamma_{1}^{i} = \varepsilon_{1}(\varphi'(\beta_{i}), \vec{z}), \dots, \gamma_{m}^{i} = \varepsilon_{m}(\varphi'(\beta_{i}), \vec{z}). \end{align*} $$

Thus, defining

$$ \begin{align*} \gamma_{1}^{i+1} := \varepsilon_{1}(\psi'(\beta_{i}), \vec{z}), \dots, \gamma_{m}^{i+1} := \varepsilon_{m}(\psi'(\beta_{i}), \vec{z}), \end{align*} $$

we obtain

$$ \begin{align*} \alpha_{i+1} = \delta_{i}(\psi'(\beta_{i}), \vec{z}) &= \hat{\varphi}'(\varepsilon_{1}(\psi'(\beta_{i}), \vec{z}), \dots, \varepsilon_{m}(\psi'(\beta_{i}), \vec{z}))\\ &= \hat{\varphi}'(\gamma_{1}^{i+1}, \dots, \gamma_{m}^{i+1}). \end{align*} $$

Furthermore, for every $m \geqslant j \in \omega $ ,

$$ \begin{align*} \gamma \equiv \gamma_{j}^{i} = \varepsilon_{j}(\varphi'(\beta_{i}), \vec{z}) \equiv \varepsilon_{j}(\psi'(\beta_{i}), \vec{z}) = \gamma_{j}^{i+1} \quad\mod \theta(\varGamma, \boldsymbol{\tau}). \end{align*} $$

The first equivalence above follows from the inductive hypothesis, while the third from $\beta _{i} \in \varGamma $ . This concludes the proof of the induction step in case (i).

(ii): Replicating the proof described for case (i) up to (14), we obtain

$$ \begin{align*} \hat{\varphi}'(\gamma_{1}^{i}, \dots, \gamma_{m}^{i}) = \psi'(\beta_{i}), \end{align*} $$

a contradiction with Claim 6.6. This concludes the inductive proof.

Finally, taking $i=n$ in (11), we obtain

$$ \begin{align*} \hat{\varphi}'(\gamma_{1}^{n}, \dots, \gamma_{m}^{n}) = \alpha_{n} = \psi'(\gamma). \end{align*} $$

But this is impossible by Claim 6.6. Hence we reached the desired contradiction. We conclude that $\vdash $ has a $\boldsymbol {\tau }$ -algebraic semantics.

This establishes the theorem for logics whose language comprises two distinct unary symbols. To conclude the proof, suppose that $\mathscr {L}_{\vdash }$ comprises an n-ary connective f with $ n \geqslant 2$ . Then define

$$ \begin{align*} \square x := f(f(x, \dots, x), x, \dots, x) \text{ and }\Diamond x := f(x, f(x, \dots, x), x \dots, x). \end{align*} $$

Using this definition of $\square $ and $\Diamond $ , it is possible to reproduce the argument detailed in the case where $\mathscr {L}_{\vdash }$ comprises two distinct unary connectives.⊣

Proof. We detail the proof of (ii) only, as that of (i) is analogous. By Corollary 3.6 it suffices to show that fragments of substructural logics with exchange in which a connective among $\{ \land , \lor , \cdot , \to \}$ is term-definable have an algebraic semantics. Accordingly, let $\vdash $ be one of these fragments. Then there is a variety $\mathsf {K}$ of commutative FL-algebras such that $\vdash $ is the logic induced by the class of matrices

$$ \begin{align*} \mathsf{M} := \{ \langle \boldsymbol{A}, F \rangle \colon \boldsymbol{A} \text{ is the}\ \mathscr{L}_{\vdash}\text{-reduct of an FL-algebra} \boldsymbol{A}^{+} \text{and }F = \boldsymbol{\tau}(\boldsymbol{A}^{+}) \}, \end{align*} $$

where $\boldsymbol {\tau } = \{ x \land 1 \thickapprox 1 \}$ . Thus, by Lemma 2.7 and Theorem 6.2, it only remains to prove that $\mathsf {M}$ validates a nontrivial equation $\varepsilon \thickapprox \delta $ such that $\textit {Var}(\varepsilon ) \cup \textit {Var}(\delta ) = \{ x \}$ . To this end, recall that in $\vdash $ a connective in $\ast \in \{ \land , \lor , \cdot , \to \}$ is term-definable by means of a, possibly complex, formula $x + y$ .

1. (i) If $\ast \in \{ \land , \lor \}$ , take $\varepsilon := x$ and $\delta := x + x$ ;

2. (ii) If $\ast = \cdot $ , take $\varepsilon := x + (x + x)$ and $\delta := (x + x) + x$ ;

3. (iii) If $\ast = {\to }$ , take $\varepsilon := (x + x) + (x + x)$ and $\delta := x + ((x + x) + x)$ .

In all cases, $\varepsilon \thickapprox \delta $ is nontrivial, valid in $\mathsf {M}$ , and such that $\textit {Var}(\varepsilon ) \cup \textit {Var}(\delta ) = \{ x \}$ . ⊣

Convention 8.2. From now on we shall denote by $\square $ the unary connective (if any) of an arbitrary graph-based logic and its set of constants by $\{ \textbf {c}_{i} \colon i < \alpha \}$ where $\alpha $ is a suitable ordinal.

Proof. Let $\vdash $ be a graph-based logic with an algebraic semantics. By Proposition 4.2, to prove that $\vdash $ has a unital matrix semantics, it suffices to show that $x, y, \varphi (x, \vec {z}) \vdash \varphi (y, \vec {z})$ for all $\varphi (v, \vec {z}) \in Fm$ . Since $\vdash $ is graph-based, if it does not have unary connectives, this condition holds vacuously. Then we can assume that $\vdash $ has a unary connective $\square $ . Since $\vdash $ is graph-based, it will be enough to show that for every $n \in \omega $ ,

$$ \begin{align*} x, y, \square^{n}x \vdash \square^{n}y. \end{align*} $$

To this end, consider $n \in \omega $ . By assumption $\vdash $ has an algebraic semantics given by a class of algebras $\mathsf {K}$ and a set of equations $\boldsymbol {\tau }(x)$ . Consider $\boldsymbol {A} \in \mathsf {K}$ and $a, b \in A$ such that

$$ \begin{align*} a, b, \underbrace{\square^{\boldsymbol{A}} \dots \square^{\boldsymbol{A}}}_{n\text{-times}}a \in \boldsymbol{\tau}(\boldsymbol{A}). \end{align*} $$

Then consider $\varepsilon \thickapprox \delta \in \boldsymbol {\tau }$ . We need to prove

(15) $$ \begin{align} \varepsilon^{\boldsymbol{A}}(\underbrace{\square^{\boldsymbol{A}} \dots \square^{\boldsymbol{A}}}_{n\text{-times}}b) = \delta^{\boldsymbol{A}}(\underbrace{\square^{\boldsymbol{A}} \dots \square^{\boldsymbol{A}}}_{n\text{-times}}b). \end{align} $$

As $\vdash $ is graph-based, one of the following conditions holds:

1. (i) $\varepsilon = \square ^{m}x$ and $\delta = \square ^{k}x$ for some $m, k \in \omega $ ;

2. (ii) $\varepsilon = \square ^{m}\textbf {c}_{i}$ and $\delta = \square ^{k}x$ for some $m, k \in \omega $ and $i < \alpha $ ;

3. (iii) $\varepsilon = \square ^{m}x$ and $\delta = \square ^{k}\textbf {c}_{i}$ for some $m, k \in \omega $ and $i < \alpha $ ;

4. (iv) $\varepsilon = \square ^{m} \textbf {c}_{i}$ and $\delta = \square ^{k}\textbf {c}_{j}$ for some $m, k \in \omega $ and $i, j < \alpha $ .

(i): From $b \in \boldsymbol {\tau }(\boldsymbol {A})$ and $\varepsilon \thickapprox \delta \in \boldsymbol {\tau }$ , it follows

$$ \begin{align*} \underbrace{\square^{\boldsymbol{A}} \dots \square^{\boldsymbol{A}}}_{m\text{-times}}b = \underbrace{\square^{\boldsymbol{A}} \dots \square^{\boldsymbol{A}}}_{k\text{-times}}b. \end{align*} $$

In particular, this implies

$$ \begin{align*} \varepsilon^{\boldsymbol{A}}(\underbrace{\square^{\boldsymbol{A}} \dots \square^{\boldsymbol{A}}}_{n\text{-times}}b) = \underbrace{\square^{\boldsymbol{A}} \dots \square^{\boldsymbol{A}}}_{m+n\text{-times}}b = \underbrace{\square^{\boldsymbol{A}} \dots \square^{\boldsymbol{A}}}_{k+n\text{-times}}b = \delta^{\boldsymbol{A}}(\underbrace{\square^{\boldsymbol{A}} \dots \square^{\boldsymbol{A}}}_{n\text{-times}}b). \end{align*} $$

(ii): From $a, \underbrace {\square ^{\boldsymbol {A}} \dots \square ^{\boldsymbol {A}}}_{n\text {-times}}a \in \boldsymbol {\tau }(\boldsymbol {A})$ and $\varepsilon \thickapprox \delta \in \boldsymbol {\tau }$ it follows

$$ \begin{align*} \underbrace{\square^{\boldsymbol{A}} \dots \square^{\boldsymbol{A}}}_{n+m\text{-times}}\textbf{c}_{i}^{\boldsymbol{A}} = \underbrace{\square^{\boldsymbol{A}} \dots \square^{\boldsymbol{A}}}_{n+k\text{-times}}a = \underbrace{\square^{\boldsymbol{A}} \dots \square^{\boldsymbol{A}}}_{k+n\text{-times}}a = \underbrace{\square^{\boldsymbol{A}} \dots \square^{\boldsymbol{A}}}_{m\text{-times}}\textbf{c}_{i}^{\boldsymbol{A}}. \end{align*} $$

Moreover, from $b \in \boldsymbol {\tau }(\boldsymbol {A})$ and $\varepsilon \thickapprox \delta \in \boldsymbol {\tau }$ it follows

$$ \begin{align*} \underbrace{\square^{\boldsymbol{A}} \dots \square^{\boldsymbol{A}}}_{m\text{-times}} \textbf{c}_{i}^{\boldsymbol{A}} = \underbrace{\square^{\boldsymbol{A}} \dots \square^{\boldsymbol{A}}}_{k\text{-times}}b. \end{align*} $$

From the two displays above we obtain

$$ \begin{align*} \varepsilon^{\boldsymbol{A}}(\underbrace{\square^{\boldsymbol{A}} \dots \square^{\boldsymbol{A}}}_{n\text{-times}}b) = \underbrace{\square^{\boldsymbol{A}} \dots \square^{\boldsymbol{A}}}_{m\text{-times}} \textbf{c}_{i}^{\boldsymbol{A}} = \underbrace{\square^{\boldsymbol{A}} \dots \square^{\boldsymbol{A}}}_{n+m\text{-times}}\textbf{c}_{i}^{\boldsymbol{A}} = \underbrace{\square^{\boldsymbol{A}} \dots \square^{\boldsymbol{A}}}_{k+n\text{-times}}b = \delta^{\boldsymbol{A}}(\underbrace{\square^{\boldsymbol{A}} \dots \square^{\boldsymbol{A}}}_{n\text{-times}}b). \end{align*} $$

Case (iii) is handled analogously to case (ii).

(iv): As $\varepsilon $ and $\delta $ are closed formulas, the fact that $\varepsilon ^{\boldsymbol {A}}(a) = \delta ^{\boldsymbol {A}}(a)$ implies

$$ \begin{align*} \varepsilon^{\boldsymbol{A}}(\underbrace{\square^{\boldsymbol{A}} \dots \square^{\boldsymbol{A}}}_{n\text{-times}}b) = \delta^{\boldsymbol{A}}(\underbrace{\square^{\boldsymbol{A}} \dots \square^{\boldsymbol{A}}}_{n\text{-times}}b). \end{align*} $$

This establishes (15) and, therefore, that $\underbrace {\square ^{\boldsymbol {A}} \dots \square ^{\boldsymbol {A}}}_{n\text {-times}}b \in \boldsymbol {\tau }(\boldsymbol {A})$ . As $\mathsf {K}$ is a $\boldsymbol {\tau }$ -algebraic semantics for $\vdash $ , we conclude that $x, y, \square ^{n}x \vdash \square ^{n}y$ , as desired.⊣

Proof. Assertional logics have an algebraic semantics by Proposition 4.4. Then consider a logic $\vdash $ that is graph-based and has an algebraic semantics. By Proposition 8.3 $\vdash $ has a unital matrix semantics. Therefore, if $\vdash $ has theorems, it is also assertional.⊣

Proof. We reason by contraposition. Suppose that $\vdash $ has a $\boldsymbol {\tau }$ -algebraic semantics $\mathsf {K}$ and that $\boldsymbol {\tau }$ contains no nontrivial equation $\varepsilon \thickapprox \delta $ such that $\textit {Var}(\varepsilon ) \cup \textit {Var}(\delta ) = \{ x \}$ . We shall prove that $x \vdash y$ , i.e., that $\vdash $ is trivial. As $\mathsf {K}$ is a $\boldsymbol {\tau }$ -algebraic semantics for $\vdash $ , it suffices to show that for all $\boldsymbol {A} \in \mathsf {K}$ and $a, c \in A$ , if $a \in \boldsymbol {\tau }(\boldsymbol {A})$ , then $c \in \boldsymbol {\tau }(\boldsymbol {A})$ .

To this end, consider $\boldsymbol {A} \in \mathsf {K}$ and $a, c \in A$ such that $a \in \boldsymbol {\tau }(\boldsymbol {A})$ . We need to show that $\varepsilon ^{\boldsymbol {A}}(c) = \delta ^{\boldsymbol {A}}(c)$ for all $\varepsilon \thickapprox \delta \in \boldsymbol {\tau }$ . Then consider an equation $\varepsilon \thickapprox \delta $ in $\boldsymbol {\tau }$ . By the assumption, we have two cases: either $\varepsilon \thickapprox \delta $ is trivial or $\textit {Var}(\varepsilon ) \cup \textit {Var}(\delta ) = \emptyset $ . If $\varepsilon \thickapprox \delta $ is trivial, then $\varepsilon = \delta $ , whence $\varepsilon ^{\boldsymbol {A}}(c) = \delta ^{\boldsymbol {A}}(c)$ . Then we consider the case where $\textit {Var}(\varepsilon ) \cup \textit {Var}(\delta ) = \emptyset $ , i.e., $\varepsilon $ and $\delta $ are closed formulas. In this case, $a \in \boldsymbol {\tau }(\boldsymbol {A})$ implies $\varepsilon ^{\boldsymbol {A}}(a) = \delta ^{\boldsymbol {A}}(a)$ . But, since $\varepsilon $ and $\delta $ are closed formulas, $\varepsilon ^{\boldsymbol {A}}(a) = \varepsilon ^{\boldsymbol {A}}(c)$ and $\delta ^{\boldsymbol {A}}(a) = \delta ^{\boldsymbol {A}}(c)$ , whence $\varepsilon ^{\boldsymbol {A}}(c) = \delta ^{\boldsymbol {A}}(c)$ . We conclude that $c \in \boldsymbol {\tau }(\boldsymbol {A})$ , as desired.⊣

Proof of Theorem 8.1. Let $\vdash $ be a nontrivial logic with a theorem $\varphi $ such that $\textit {Var}(\varphi ) \ne \emptyset $ . As $\vdash $ is substitution invariant, we can assume without loss of generality $\textit {Var}(\varphi ) = \{ x \}$ .

(i) $\Rightarrow $ (iv): Suppose that $\vdash $ has a $\boldsymbol {\tau }$ -algebraic semantics $\mathsf {K}$ . First if $\vdash $ is graph-based, then it is assertional by Corollary 8.4. Then we consider the case where $\vdash $ is not graph-based.

As $\vdash $ is nontrivial, we can apply Lemma 8.5, obtaining that $\boldsymbol {\tau }$ contains a nontrivial equation $\varepsilon \thickapprox \delta $ such that $\textit {Var}(\varepsilon ) \cup \textit {Var}(\delta ) = \{ x \}$ . Recall from Proposition 3.2 that

$$ \begin{align*} \mathsf{M} := \{ \langle \boldsymbol{A}, \boldsymbol{\tau}(\boldsymbol{A}) \rangle \colon \boldsymbol{A} \in \mathsf{K} \} \end{align*} $$

is a matrix semantics for $\vdash $ . As $\varepsilon \thickapprox \delta \in \boldsymbol {\tau }$ and $\varphi $ is a theorem of $\vdash $ ,

$$ \begin{align*} \mathsf{M} \vDash \varepsilon(\varphi) \thickapprox \delta(\varphi). \end{align*} $$

Moreover, as $\textit {Var}(\varepsilon ) \cup \textit {Var}(\delta ) = \{ x \} = \textit {Var}(\varphi )$ ,

$$ \begin{align*} \textit{Var}(\varepsilon(\varphi)) \cup \textit{Var}(\delta(\varphi)) = \{ x \}. \end{align*} $$

In view of the two displays above, since $\mathsf {M}$ is a matrix semantics for $\vdash $ , it only remains to prove that the equation $\varepsilon (\varphi ) \thickapprox \delta (\varphi )$ is nontrivial. Suppose the contrary, with a view to contradiction. As $\textit {Var}(\varphi ) = \{ x \}$ , the tree $T(\varepsilon )^{-x}$ can be identified with the subtree of $T(\varepsilon (\varphi ))$ obtained by removing from $T(\varepsilon (\varphi ))$ the upsets equal to $T(\varphi )$ . Similarly, $T(\delta )^{-x}$ can be identified with the subtree of $T(\delta (\varphi ))$ obtained by removing from $T(\delta (\varphi ))$ the upsets equal to $T(\varphi )$ . Since $\varepsilon (\varphi ) = \delta (\varphi )$ , this implies $T(\varepsilon )^{-x} = T(\delta )^{-x}$ and, therefore, $\varepsilon = \delta $ . But this contradicts the fact that the equation $\varepsilon \thickapprox \delta $ is nontrivial.

(ii) $\Rightarrow $ (i): If $\vdash $ is graph-based, then by assumption it is also assertional. Thus, in this case, $\vdash $ has an algebraic semantics by Proposition 4.4. Then we consider the case where $\vdash $ is not graph-based. Together with the assumption, this implies that $\vdash $ has an algebraic semantics by Theorem 6.2.

Lastly, conditions (ii), (iii), and (iv) are equivalent by Lemma 2.7.⊣

Proof. Let $\vdash $ be a nontrivial protoalgebraic logic. By Lemma 9.2, $\vdash $ has a theorem $\varphi $ such that $\textit {Var}(\varphi ) \ne \emptyset $ and an n-ary connective $f(x_{1}, \dots , x_{n})$ with $n \geqslant 2$ .

(i) $\Rightarrow $ (iv): Suppose that $\vdash $ has an algebraic semantics. As $\vdash $ has a theorem $\varphi $ such that $\textit {Var}(\varphi ) \ne \emptyset $ , it falls in the scope of Theorem 8.1. Therefore, the implication (i) $\Rightarrow $ (iv) in Theorem 8.1 yields that either $\vdash $ is graph-based or it has a matrix semantics validating a nontrivial equation. Thus, to conclude the proof, it suffices to show that $\vdash $ is not graph-based. But this follows from the fact that $\vdash $ has an n-ary connective $f(x_{1}, \dots , x_{n})$ with $n \geqslant 2$ .

(iv) $\Rightarrow $ (i): Suppose that $\vdash $ has a matrix semantics $\mathsf {M}$ validating a nontrivial equation $\varepsilon (x_{1}, \dots , x_{n}) \thickapprox \delta (x_{1}, \dots , x_{n})$ . By the implication (iv) $\Rightarrow $ (i) in Theorem 8.1, to conclude the proof it suffices to show that there are formulas $\varepsilon '$ and $\delta '$ such that $\textit {Var}(\varepsilon ') \cup \textit {Var}(\delta ') = \{ x \}$ and the equation $\varepsilon ' \thickapprox \delta '$ is both nontrivial and valid in $\mathsf {M}$ .

To this end, recall that f is n-ary with $n \geqslant 2$ . Therefore, if $\varepsilon $ and $\delta $ are closed formulas, we are done taking

$$ \begin{align*} \varepsilon' := f(\varepsilon, x, \dots, x) \text{ and }\delta' := f(\delta, x, \dots, x). \end{align*} $$

Then we can assume by symmetry that $x_{1} \in \textit {Var}(\varepsilon )$ . For every $n \in \omega $ , we define recursively a formula $\varphi _{n}(x)$ by the rule

$$ \begin{align*} \varphi_{0}:= f(x, \dots, x) \text{ and }\varphi_{m+1} := f(\varphi_{m}, x, \dots, x). \end{align*} $$

Clearly $\textit {Var}(\varphi _{n}) = \{ x \}$ for all $n \in \omega $ . Let then $k \in \omega $ be greater than the length of all branches in the trees $T(\varepsilon )$ and $T(\delta )$ , and define

$$ \begin{align*} \varepsilon' := \varepsilon(\varphi_{k}, \varphi_{2k}, \dots, \varphi_{nk}) \text{ and }\delta' := \varepsilon(\varphi_{k}, \varphi_{2k}, \dots, \varphi_{nk}). \end{align*} $$

Notice that $\textit {Var}(\varepsilon ') \cup \textit {Var}(\delta ') = \{ x \}$ as $x_{1} \in \textit {Var}(\varepsilon )$ and $\textit {Var}(\varphi _{m}) = \{ x \}$ for all $m \in \omega $ . Furthermore, $\varepsilon ' \thickapprox \delta '$ is valid in $\mathsf {M}$ , because $\varepsilon \thickapprox \delta $ is.

Therefore, it only remains to prove that the equation $\varepsilon ' \thickapprox \delta '$ is nontrivial. To this end, observe that, since k is greater than all branches in $T(\varepsilon )$ , the tree $T(\varepsilon )$ can be obtained as follows. First, let $S_{n}$ be the tree obtained by replacing in $T(\varepsilon )$ the principal upsets whose longest branch has length $nk + 1$ by a point labeled by $x_{n}$ . Then let $S_{n-1}$ be the tree obtained by replacing in $S_{n}$ the principal upsets whose longest branch have length $(n-1)k + 1$ by a point labeled by $x_{n-1}$ . Iterating this process, we eventually get a tree $S_{1}$ which coincides with $T(\varepsilon )$ . Notice that $T(\delta )$ can be obtained by pruning $T(\delta ')$ in exactly the same way. Consequently, if $T(\varepsilon ') = T(\delta ')$ , then $T(\varepsilon ) = T(\delta )$ and, therefore, $\varepsilon = \delta $ . As by assumption $\varepsilon \ne \delta $ , we conclude that $T(\varepsilon ') \ne T(\delta ')$ , i.e., $\varepsilon ' \ne \delta '$ .

(ii) $\Leftrightarrow $ (v): It is easy to see that $\boldsymbol {Fm}(\vdash )$ is isomorphic to $\boldsymbol {Fm}$ if and only if $\equiv _{\vdash }$ is the identity relation on $Fm$ . Bearing this in mind, the equivalence between conditions (ii) and (v) follows from the definition of $\equiv _{\vdash }$ .

Lastly, conditions (ii)–(iv) are equivalent by Lemma 2.7.⊣

Proof. We will make use of the following well-known fact: for all $\varphi , \psi \in Fm$ ,

$$ \begin{align*} \mathsf{Alg}(\vdash^{\ell}_{\mathfrak{F}}) \vDash \varphi \thickapprox \psi \Longleftrightarrow \varphi \mathrel{\dashv\mkern1.5mu\vdash}^{\ell}_{\mathfrak{F}} \psi. \end{align*} $$

Suppose, with a view to contradiction, that $\vdash ^{\ell }_{\mathfrak {F}}$ has a $\boldsymbol {\tau }$ -algebraic semantics based on $\mathsf {Alg}(\vdash ^{\ell }_{\mathfrak {F}})$ . As $\mathfrak {F}$ is nonempty, the logic $\vdash ^{\ell }_{\mathfrak {F}}$ is nontrivial. Together with the fact that $\mathsf {Alg}(\vdash ^{\ell }_{\mathfrak {F}})$ is a $\boldsymbol {\tau }$ -algebraic semantics, this implies that there exists an equation $\varepsilon \thickapprox \delta \in \boldsymbol {\tau }$ such that $\mathsf {Alg}(\vdash ^{\ell }_{\mathfrak {F}}) \nvDash \varepsilon \thickapprox \delta $ . Thus, in view of the above display, we can assume by symmetry that $\varepsilon \nvdash ^{\ell }_{\mathfrak {F}} \delta $ . This means that there are $\mathcal {F} \in \mathfrak {F}$ , a world $w \in \mathcal {F}$ , and an evaluation v in $\mathcal {F}$ such that $w, v \Vdash \varepsilon $ and $w, v \nVdash \delta $ .

Recall that, by the assumptions, $\mathcal {F}^{+} \in \mathfrak {F}$ . Let $v^{+}$ be the unique evaluation on $\mathcal {F}^{+}$ such that for every $y \in \textit {Var}$ and $q \in \mathcal {F}^{+}$ :

$$ \begin{align*} q, v^{+} \Vdash y \Longleftrightarrow \text{ either }(q \in \mathcal{F} \text{ and }q, v \Vdash y)\text{ or }q = w^{+}. \end{align*} $$

From the definition of $\mathcal {F}^{+}$ and $v^{+}$ it follows that

$$ \begin{align*} q, v^{+} \Vdash \varphi \Longleftrightarrow q, v \Vdash \varphi \end{align*} $$

for all $\varphi \in Fm$ and $q \in \mathcal {F}$ . Consequently, as $w, v \Vdash \varepsilon $ and $w, v \nVdash \delta $ ,

$$ \begin{align*} w^{+}, v^{+} \Vdash x \text{ and } w^{+}, v^{+} \nVdash \square(\varepsilon \to \delta). \end{align*} $$

This implies

$$ \begin{align*} x \nvdash^{\ell}_{\mathfrak{F}} \square(\varepsilon \to \delta). \end{align*} $$

On the other hand, clearly $\emptyset \vdash ^{\ell }_{\mathfrak {F}} \square (\delta \to \delta )$ . Consequently,

$$ \begin{align*} x, \square(\delta \to \delta) \nvdash^{\ell}_{\mathfrak{F}} \square(\varepsilon \to \delta). \end{align*} $$

Together with Proposition 3.3 and the fact that $\vdash $ has a $\boldsymbol {\tau }$ -algebraic semantics, this implies $\varepsilon \thickapprox \delta \notin \boldsymbol {\tau }$ , a contradiction.⊣

Proof. We detail the case where $\mathfrak {F}$ is the class of all Kripke frames, as the remaining ones are analogous. First observe that if $\mathcal {F} \in \mathfrak {F}$ , then $\mathcal {F}^{+} \in \mathfrak {F}$ . Hence we can apply Proposition 9.6, obtaining that $\vdash ^{\ell }_{\mathfrak {F}}$ does not have an algebraic semantics based on $\mathsf {Alg}(\vdash ^{\ell }_{\mathfrak {F}})$ . As $\mathsf {Alg}(\vdash ^{\ell }_{\mathfrak {F}})$ is the variety of modal algebras, we are done.⊣

Proof. The implication (ii) $\Rightarrow $ (i) is obvious. To prove the implication (i) $\Rightarrow $ (iii), let $\mathsf {K}$ be the algebraic semantics given by condition (i). To show that $x \vdash \square x$ , it suffices to prove that $\square ^{\boldsymbol {A}}a \in \boldsymbol {\tau }(\boldsymbol {A})$ for all $\boldsymbol {A} \in \mathsf {K}$ and $a \in \boldsymbol {\tau }(\boldsymbol {A})$ . To this end, consider $\boldsymbol {A} \in \mathsf {K}$ , $a \in \boldsymbol {\tau }(\boldsymbol {A})$ , and an equation $\varepsilon \thickapprox \delta $ in $\boldsymbol {\tau }$ . We need to establish

(17) $$ \begin{align} \varepsilon^{\boldsymbol{A}}(\square^{\boldsymbol{A}}a) = \delta^{\boldsymbol{A}}(\square^{\boldsymbol{A}}a). \end{align} $$

Now, recall from the assumption that either $\varepsilon = \square ^{n}\textbf {c}_{i}$ and $\delta = \square ^{m}\textbf {c}_{j}$ for some $i, j < \alpha $ and $n, m \in \omega $ , or $\varepsilon = \square ^{n}x$ and $\delta = \square ^{m}x$ for some $n, m \in \omega $ . Observe that if $\varepsilon = \square ^{n}\textbf {c}_{i}$ and $\delta = \square ^{m}\textbf {c}_{j}$ , then $a \in \boldsymbol {\tau }(\boldsymbol {A})$ implies $\underbrace {\square ^{\boldsymbol {A}} \dots \square ^{\boldsymbol {A}}}_{n\text {-times}}\textbf {c}_{i}^{\boldsymbol {A}} = \underbrace {\square ^{\boldsymbol {A}} \dots \square ^{\boldsymbol {A}}}_{m\text {-times}}\textbf {c}_{j}^{\boldsymbol {A}}$ and, therefore,

$$ \begin{align*} \varepsilon^{\boldsymbol{A}}(\square^{\boldsymbol{A}} a) = \underbrace{\square^{\boldsymbol{A}} \dots \square^{\boldsymbol{A}}}_{n\text{-times}}\textbf{c}_{i}^{\boldsymbol{A}} = \underbrace{\square^{\boldsymbol{A}} \dots \square^{\boldsymbol{A}}}_{m\text{-times}}\textbf{c}_{j}^{\boldsymbol{A}} = \delta^{\boldsymbol{A}}(\square^{\boldsymbol{A}} a). \end{align*} $$

Then we consider the case where $\varepsilon = \square ^{n}x$ and $\delta = \square ^{m}x$ . From $a \in \boldsymbol {\tau }(\boldsymbol {A})$ it follows

$$ \begin{align*} \underbrace{\square^{\boldsymbol{A}} \dots \square^{\boldsymbol{A}}}_{n\text{-times}}a = \varepsilon^{\boldsymbol{A}}(a) = \delta^{\boldsymbol{A}}(a) = \underbrace{\square^{\boldsymbol{A}} \dots \square^{\boldsymbol{A}}}_{m\text{-times}}a. \end{align*} $$

Consequently,

$$ \begin{align*} \varepsilon^{\boldsymbol{A}}(\square^{\boldsymbol{A}}a) = \square^{\boldsymbol{A}}\underbrace{\square^{\boldsymbol{A}} \dots \square^{\boldsymbol{A}}}_{n\text{-times}}a = \square^{\boldsymbol{A}}\underbrace{\square^{\boldsymbol{A}} \dots \square^{\boldsymbol{A}}}_{m\text{-times}}a = \delta^{\boldsymbol{A}}(\square^{\boldsymbol{A}}a). \end{align*} $$

This establishes (17) and, therefore, $x \vdash \square x$ .

It only remains to prove the implication (iii) $\Rightarrow $ (ii). To this end, set $\boldsymbol {\tau } := \{ x \thickapprox \square x \}$ . By Proposition 3.5, in order to show that $\vdash $ has a $\boldsymbol {\tau }$ -algebraic semantics, it suffices to check that for every $\varGamma \cup \{ \varphi \} \subseteq Fm$ ,

(18) $$ \begin{align} \text{if }\boldsymbol{\tau}(\varphi) \subseteq \theta(\varGamma, \boldsymbol{\tau})\text{, then }\varGamma \vdash \varphi. \end{align} $$

To this end, consider $\varGamma \cup \{ \varphi \} \subseteq Fm$ such that $\boldsymbol {\tau }(\varphi ) \subseteq \theta (\varGamma , \boldsymbol {\tau })$ . Then define

$$ \begin{align*} \phi := \{ \langle \varepsilon, \delta\rangle \in Fm \times Fm : \text{either }\varepsilon, \delta \in \textrm{Cn}_{\vdash}(\varGamma) \text{ or }\varepsilon = \delta \}. \end{align*} $$

We shall see that $\phi $ is a congruence of $\boldsymbol {Fm}$ . As $\phi $ is clearly an equivalence relation on $Fm$ , it suffices to show that $\phi $ preserves the operation $\square $ . To this end, consider $\langle \varepsilon , \delta \rangle \in \phi $ . There are two cases: either $\varepsilon = \delta $ or $\varepsilon \ne \delta $ . If $\varepsilon = \delta $ , then $\square \varepsilon = \square \delta $ and, therefore, $\langle \square \varepsilon , \square \delta \rangle \in \phi $ . Then we consider the case where $\varepsilon \ne \delta $ . As $\langle \varepsilon , \delta \rangle \in \phi $ , we get $\varepsilon , \delta \in \textrm {Cn}_{\vdash }(\varGamma )$ . Now, recall from the assumption that $x \vdash \square x$ and, therefore, $\varepsilon \vdash \square \varepsilon $ and $\delta \vdash \square \delta $ . Together with $\varepsilon , \delta \in \textrm {Cn}_{\vdash }(\varGamma )$ , this implies $\square \varepsilon , \square \delta \in \textrm {Cn}_{\vdash }(\varGamma )$ , whence $\langle \square \varepsilon , \square \delta \rangle \in \phi $ . We conclude that $\phi $ is a congruence of $\boldsymbol {Fm}$ .