2.1 Syntax

The syntax of a (propositional) logic is defined, as usual, by means of a signature, an indexed family $\Sigma =\{\Sigma ^{(n)}\}_{n\in {\mathbb N}_0}$ of countable sets where each $\Sigma ^{(n)}$ contains all allowed n-place connectives, and a denumerable set P of variables (which we consider fixed once and for all). As standard, $L_{\Sigma }(P)$ denotes the set of all formulas Footnote ¹ constructed from the variables in P using the connectives in $\Sigma $ . We will use $p,q,r,\dots $ to denote variables, $A,B,C,\dots $ to denote formulas, and $\Gamma ,\Delta ,\Theta ,\dots $ to denote sets of formulas, in all cases, possibly, with annotations.

We use $\operatorname *{\mathrm {\textsf {var}}}(A)$ , $\operatorname *{\mathrm {\textsf {sub}}}(A)$ , $\operatorname *{\mathrm {\textsf {hd}}}(A)$ to denote, respectively, the set of variables occurring in A, the set of subformulas of A, and the head constructor of A, given a formula $A\in L_{\Sigma }(P)$ . These notations have simple recursive definitions: $\operatorname *{\mathrm {\textsf {var}}}(p)=\operatorname *{\mathrm {\textsf {sub}}}(p)=\{p\}$ , and $\operatorname *{\mathrm {\textsf {hd}}}(p)=p$ for $p\in P$ ; and if $c\in \Sigma ^{(n)}$ and $A_1,\dots ,A_n\in L_{\Sigma }(P)$ , $\operatorname *{\mathrm {\textsf {var}}}(c(A_1,\dots ,A_n))=\bigcup _{i=1}^n\operatorname *{\mathrm {\textsf {var}}}(A_i)$ , $\operatorname *{\mathrm {\textsf {sub}}}(c(A_1,\dots ,A_n))=\{c(A_1,\dots ,A_n)\}\cup \bigcup _{i=1}^n\operatorname *{\mathrm {\textsf {sub}}}(A_i)$ , and $\operatorname *{\mathrm {\textsf {hd}}}(c(A_1,\dots ,A_n))=c$ . We also consider the extensions of the $\operatorname *{\mathrm {\textsf {var}}}$ and $\operatorname *{\mathrm {\textsf {sub}}}$ notations to sets of formulas given, for $\Gamma \subseteq L_{\Sigma }(P)$ , by $\operatorname *{\mathrm {\textsf {var}}}(\Gamma )=\bigcup _{A\in \Gamma }\operatorname *{\mathrm {\textsf {var}}}(A)$ , and mutatis mutandis for $\operatorname *{\mathrm {\textsf {sub}}}$ .

As we will consider combined logics, with mixed syntax, we need to consider different signatures, as well as relations and operations between signatures. Signatures being families of sets, the usual set-theoretic notions can be smoothly extended to signatures. We will sometimes abuse notation, and confuse a signature $\Sigma $ with the set $(\biguplus _{n\in {\mathbb N}_0}\Sigma ^{(n)})$ of all its connectives, and write $c\in \Sigma $ when c is some n-place connective $c\in \Sigma ^{(n)}$ . For this reason, the empty signature, with no connectives at all, will be simply denoted by $\emptyset $ .

Let $\Sigma ,\Sigma _0$ be two signatures. We say that $\Sigma _0$ is a subsignature of $\Sigma $ , and write $\Sigma _0\subseteq \Sigma $ , whenever $\Sigma _0^{(n)}\subseteq {\Sigma }^{(n)}$ for every $n\in {\mathbb N}_0$ . Expectedly, given signatures $\Sigma _1,\Sigma _2$ , we can also define their shared subsignature $\Sigma _1\cap \Sigma _2=\{\Sigma _1^{(n)}\cap {\Sigma _2}^{(n)}\}_{n\in {\mathbb N}_0}$ , their combined signature $\Sigma _1\cup \Sigma _2=\{\Sigma _1^{(n)}\cup {\Sigma _2}^{(n)}\}_{n\in {\mathbb N}_0}$ , and their difference signature $\Sigma _1\setminus \Sigma _2=\{{\Sigma _1}^{(n)}\setminus \Sigma _2^{(n)}\}_{n\in {\mathbb N}_0}$ . Clearly, $\Sigma _1\cap \Sigma _2$ is the largest subsignature of both $\Sigma _1$ and $\Sigma _2$ , and contains the connectives shared by both. When there are no shared connectives we have that $\Sigma _1\cap \Sigma _2=\emptyset $ . Analogously, $\Sigma _1\cup \Sigma _2$ is the smallest signature that has both $\Sigma _1$ and $\Sigma _2$ as subsignatures, and features all the connectives from both $\Sigma _1$ and $\Sigma _2$ in a combined signature. Furthermore, $\Sigma _1\setminus \Sigma _2$ is the largest subsignature of $\Sigma _1$ which does not share any connectives with $\Sigma _2$ .

A substitution is a function $\sigma :P\to L_{\Sigma }(P)$ , that of course extends freely to a function $\sigma :L_{\Sigma _0}(P)\to L_{\Sigma }(P)$ for every $\Sigma _0\subseteq \Sigma $ . As usual, we use $A^{\sigma }$ to the denote the formula that results from $A\in L_{\Sigma _0}(P)$ by uniformly replacing each variable $p\in \operatorname *{\mathrm {\textsf {var}}}(A)$ by $\sigma (p)$ , and $\Gamma ^{\sigma }=\{A^{\sigma }:A\in \Gamma \}$ for each $\Gamma \subseteq L_{\Sigma }(P)$ .

Note that if $\Sigma _0\subseteq \Sigma $ then $L_{\Sigma _0}(P)\subseteq L_{\Sigma }(P)$ . Still, $L_{\Sigma _0}(P)$ and $L_{\Sigma }(P)$ are both denumerable. In fact, the pair can be endowed with a very useful bijection capturing the view of an arbitrary $L_{\Sigma }(P)$ formula from the point of view of $\Sigma _0$ , the skeleton function $\operatorname *{\mathrm {\textsf {skel}}}_{\Sigma _0}:L_{\Sigma }(P)\to L_{\Sigma _0}(P)$ (or simply $\operatorname *{\mathrm {\textsf {skel}}}_0$ , or even $\operatorname *{\mathrm {\textsf {skel}}}$ ), whose underlying idea we borrow from [Reference Marcelino and Caleiro55]. Note that, given $A\in L_{\Sigma }(P)$ , $\operatorname *{\mathrm {\textsf {hd}}}(A)$ may be in $\Sigma \setminus \Sigma _0$ , in which case we dub A a $\Sigma _0$ -monolith or simply a monolith. The idea is simply to replace monoliths by dedicated variables, just renaming the original variables. Let $\operatorname *{\mathrm {\textsf {Mon}}}(\Sigma _0,\Sigma )$ be the set of all monoliths. It is easy to see that $\operatorname *{\mathrm {\textsf {Mon}}}(\Sigma _0,\Sigma )$ is always countable, though it can be finite when $\Sigma \setminus \Sigma _0$ contains nothing but a finite set of $0$ -place connectives. In any case, $\operatorname *{\mathrm {\textsf {Mon}}}(\Sigma _0,\Sigma )\cup P$ is always denumerable, because P is, and thus we can fix a bijection $\eta :\operatorname *{\mathrm {\textsf {Mon}}}(\Sigma _0,\Sigma )\cup P\to P$ . The $\operatorname *{\mathrm {\textsf {skel}}}$ bijection is now definable from $\eta $ , recursively, by letting $\operatorname *{\mathrm {\textsf {skel}}}(p)=\eta (p)$ for $p\in P$ , and for $c\in \Sigma ^{(n)}$ and $A_1,\dots ,A_n\in L_{\Sigma }(P)$ , $\operatorname *{\mathrm {\textsf {skel}}}(c(A_1,\dots ,A_n))=c(\operatorname *{\mathrm {\textsf {skel}}}(A_1),\dots ,\operatorname *{\mathrm {\textsf {skel}}}(A_n))$ if $c\in \Sigma _0$ , and $\operatorname *{\mathrm {\textsf {skel}}}(c(A_1,\dots ,A_n))=\eta (c(A_1,\dots ,A_n))$ if $c\in \Sigma \setminus \Sigma _0$ .

The $\operatorname *{\mathrm {\textsf {skel}}}$ bijection thus defined can be inverted by means of the substitution $\operatorname *{\mathrm {\textsf {unskel}}}_{\Sigma _0}:P\to L_{\Sigma }(P)$ (or simply $\operatorname *{\mathrm {\textsf {unskel}}}_0$ , or even $\operatorname *{\mathrm {\textsf {unskel}}}$ ) defined by $\operatorname *{\mathrm {\textsf {unskel}}}(p)=\eta ^{-1}(p)$ . Note that $\operatorname *{\mathrm {\textsf {skel}}}(A)^{\operatorname *{\mathrm {\textsf {unskel}}}}=A$ for every $A\in L_{\Sigma }(P)$ .

Note also that the restriction of $\operatorname *{\mathrm {\textsf {skel}}}$ to P, $\operatorname *{\mathrm {\textsf {skel}}}:P \to L_{\Sigma _0}(P)$ (with a slight abuse of notation, we will use the same name) is a substitution, and $\operatorname *{\mathrm {\textsf {skel}}}(A)=A^{\operatorname *{\mathrm {\textsf {skel}}}}$ for every $A\in L_{\Sigma _0}(P)$ .

Henceforth, we will often apply $\operatorname *{\mathrm {\textsf {skel}}}$ and $\operatorname *{\mathrm {\textsf {unskel}}}$ not just to formulas, but also directly to sets of formulas, or even binary relations involving formulas and sets of formulas. For that purpose, we let $\operatorname *{\mathrm {\textsf {skel}}}(X)=\{\operatorname *{\mathrm {\textsf {skel}}}(x):x\in X\}$ if X is a set, and $\operatorname *{\mathrm {\textsf {skel}}}(Y,Z)=(\operatorname *{\mathrm {\textsf {skel}}}(Y),\operatorname *{\mathrm {\textsf {skel}}}(Z))$ if $(Y,Z)$ is a pair, and mutatis mutandis for $\operatorname *{\mathrm {\textsf {unskel}}}$ .

2.2 Consequence relations

With respect to the very notion of logic, we will not only consider the traditional Tarski-style set-formula notion of consequence (single-conclusion), but also the more general Scott-style set-set notion of consequence (multiple-conclusion), which plays an essential role in our results.

A multiple-conclusion logic is a pair ${\langle \Sigma ,\vartriangleright \rangle }$ where $\Sigma $ is a signature, and $\vartriangleright $ is a multiple-conclusion consequence relation over $L_{\Sigma }(P)$ , that is, $\vartriangleright \ \subseteq \wp ({L_{\Sigma }(P)})\times \wp ({L_{\Sigma }(P)})$ is a relation satisfying the properties below, for every $\Gamma ,\Delta ,\Gamma ',\Delta ',\Omega \subseteq L_{\Sigma }(P)$ and $\sigma :P\to L_{\Sigma }(P)$ :

1. (O) if $\Gamma \cap \Delta \neq \emptyset $ then $\Gamma \vartriangleright \Delta $ ,

2. (D) if $\Gamma \vartriangleright \Delta $ then $\Gamma \cup \Gamma '\vartriangleright \Delta \cup \Delta '$ ,

3. (C) if $\Gamma \cup \underline {\Omega }\vartriangleright \overline {\Omega }\cup \Delta $ for each partitionFootnote ² ${\langle \underline {\Omega },\overline {\Omega }\rangle }$ of $\Omega $ , then $\Gamma \vartriangleright \Delta $ ,

4. (S) if $\Gamma \vartriangleright \Delta $ then $\Gamma ^{\sigma }\vartriangleright \Delta ^{\sigma }$ .

Often, the relation also satisfies the following property, for every $\Gamma ,\Delta \subseteq L_{\Sigma }(P)$ :

1. (F) if $\Gamma \vartriangleright \Delta $ then there exist finite sets $\Gamma _{\textrm {fin}}\subseteq \Gamma $ and $\Delta _{\textrm {fin}}\subseteq \Delta $ such that $\Gamma _{\textrm {fin}}\vartriangleright \Delta _{\textrm {fin}}$ .

Property (C) is best known as cut for sets. The other properties are usually known as overlap (O), dilution (D), substitution invariance (S), and compactness (F) (see [Reference Scott67, Reference Shoesmith and Smiley72, Reference Wójcicki75]). As is well known, a multiple-conclusion logic ${\langle \Sigma ,\vartriangleright \rangle }$ has a compact version ${\langle \Sigma ,\vartriangleright _{\textrm {fin}}\rangle }$ defined to be the largest compact multiple-conclusion logic such that $\vartriangleright _{\textrm {fin}}{\subseteq }\vartriangleright $ .

A pair of sets of formulas ${\langle \Gamma ,\Delta \rangle }$ is said to be a theory-pair of ${\langle \Sigma ,\vartriangleright \rangle }$ (see [Reference Blasio, Caleiro and Marcos18]) when, for every $A\in L_{\Sigma }(P)$ , if ${\Gamma }\vartriangleright {\{A\}\cup \Delta }$ then $A\in \Gamma $ , and also, if ${\Gamma \cup \{A\}}\vartriangleright {\Delta }$ then $A\in \Delta $ . It is clear that, given sets $\Gamma ,\Delta $ , the pair of sets ${\langle \Gamma ,\Delta \rangle }^{\vartriangleright }={\langle \{A:{\Gamma }\vartriangleright {\{A\}\cup \Delta }\},\{A:{\Gamma }\cup {\{A\}\vartriangleright \Delta }\}\rangle }$ is the least theory-pair containing ${\langle \Gamma ,\Delta \rangle }$ .

A theory-pair ${\langle \Gamma ,\Delta \rangle }$ is consistent if ${\Gamma }\not \vartriangleright \Delta $ (otherwise, by dilution, we necessarily have $\Gamma =\Delta =L_{\Sigma }(P)$ ). A consistent theory-pair is maximal if there is no consistent theory-pair that properly contains it, that is, if ${\langle \Gamma ',\Delta '\rangle }$ is a consistent theory with $\Gamma \subseteq \Gamma '$ and $\Delta \subseteq \Delta '$ then $\Gamma =\Gamma '$ and $\Delta =\Delta '$ . Equivalently, using cut for the set of all formulas, a consistent theory-pair ${\langle \Gamma ,\Delta \rangle }$ is maximal precisely if ${\langle \Gamma ,\Delta \rangle }$ is a partition of $L_{\Sigma }(P)$ . This implies, obviously, that a consistent theory-pair can always be extend to a maximal one.

We say that a pair ${\langle \Sigma ,\vdash \rangle }$ is a single-conclusion logic if $\Sigma $ is a signature and $\vdash $ is a single-conclusion consequence relation over $L_{\Sigma }(P)$ , that is, $\vdash \ \subseteq \wp ({L_{\Sigma }(P)})\times {L_{\Sigma }(P)}$ is a relation, and $\operatorname *{\mathrm {\textsf {min}}}({\langle \Sigma ,\vdash \rangle })$ is a multiple-conclusion logic, where $\operatorname *{\mathrm {\textsf {min}}}({\langle \Sigma ,\vdash \rangle })={\langle \Sigma ,\vartriangleright _{\vdash }\rangle }$ is defined, for $\Gamma ,\Delta \subseteq L_{\Sigma }(P)$ , by $\Gamma \vartriangleright _{\vdash }\Delta $ if and only if there exists $A\in \Delta $ such that $\Gamma \vdash A$ . It is well known (see [Reference Shoesmith and Smiley72]) that this constitutes an alternative definition of the usual notion of Tarski-style consequence relation, inheriting the usual properties of reflexivity, monotonicity, transitivity, and structurality from properties (ODCS), as well as compactness from (F), when it holds. Again, a single-conclusion logic ${\langle \Sigma ,\vdash \rangle }$ has a compact version ${\langle \Sigma ,\vdash _{\textrm {fin}}\rangle }$ defined to be the largest compact single-conclusion logic such that $\vdash _{\textrm {fin}}{\subseteq }\vdash $ .

More standardly, now, a set of formulas ${\Gamma }$ is said to be a theory of ${\langle \Sigma ,\vdash \rangle }$ when, for every $A\in L_{\Sigma }(P)$ , if ${\Gamma }\vdash {A}$ then $A\in \Gamma $ . Given a set $\Gamma $ , we know that $\Gamma ^{\vdash }=\{A:{\Gamma }\vdash A\}$ is the least theory that contains $\Gamma $ .

As usual, a theory ${\Gamma }$ is consistent if $\Gamma \neq L_{\Sigma }(P)$ . A consistent theory $\Gamma $ is maximal relatively to $A\notin \Gamma $ if every theory that properly contains $\Gamma $ must also contain A, that is, if $\Gamma \cup \{B\}\vdash A$ for every $B\notin \Gamma $ . A consistent theory $\Gamma $ is relatively maximal if it is maximal relatively to some formula $A\notin \Gamma $ . According to the usual Lindenbaum Lemma (see, for instance, [Reference Wójcicki75]), if a single-conclusion logic is compact then a consistent theory always has a relatively maximal extension.

Every multiple-conclusion logic ${\langle \Sigma ,\vartriangleright \rangle }$ has of course a single-conclusion companion defined simply by $\operatorname *{\mathrm {\textsf {sing}}}({\langle \Sigma ,\vartriangleright \rangle })={\langle \Sigma ,\vartriangleright _{\operatorname *{\mathrm {\textsf {sing}}}}\rangle }$ where, for $\Gamma \cup \{A\}\subseteq L_{\Sigma }(P)$ , $\Gamma \vartriangleright _{\operatorname *{\mathrm {\textsf {sing}}}} A$ if and only if $\Gamma \vartriangleright \{A\}$ .

When ${\langle \Sigma ,\vdash \rangle }$ is a single-conclusion logic, it is clear that the single-conclusion companion of $\operatorname *{\mathrm {\textsf {min}}}({\langle \Sigma ,\vdash \rangle })$ is precisely ${\langle \Sigma ,\vdash \rangle }$ . There may however be many multiple-conclusion logics whose single-conclusion companion coincides with ${\langle \Sigma ,\vdash \rangle }$ , which we dub as multiple-conclusion counterparts of ${\langle \Sigma ,\vdash \rangle }$ . Indeed, among the many possible multiple-conclusion counterparts of ${\langle \Sigma ,\vdash \rangle }$ , we have that $\operatorname *{\mathrm {\textsf {min}}}({\langle \Sigma ,\vdash \rangle })$ is precisely the minimal [Reference Shoesmith and Smiley72]. Note that whenever $\operatorname *{\mathrm {\textsf {sing}}}({\langle \Sigma ,\vartriangleright \rangle })={\langle \Sigma ,\vdash \rangle }$ , it is easy to see that $\Gamma $ is a theory of ${\langle \Sigma ,\vdash \rangle }$ if and only if there exists $\Delta $ such that the pair ${\langle \Gamma ,\Delta \rangle }$ is a theory-pair of ${\langle \Sigma ,\vartriangleright \rangle }$ .

For both types of logics (we will use $\propto $ as a placeholder for either a multiple-conclusion $\vartriangleright $ or a single-conclusion $\vdash $ ), it is well-known that the logics with a common signature form a complete lattice (under the inclusion ordering on the consequence relations), as in both cases it is relatively straightforward to check that intersections of consequence relations are consequence relations (see [Reference Shoesmith and Smiley72, Reference Wójcicki75]). These facts make it relatively easy to enrich the signature of a logic. If $\Sigma _0\subseteq \Sigma $ and ${\langle \Sigma _0,\propto _0\rangle }$ is a logic then the extension of ${\langle \Sigma _0,\propto _0\rangle }$ to $\Sigma $ , denoted by ${\langle \Sigma ,\propto _0^{\Sigma }\rangle }$ , is the least logic (of the same type) with signature $\Sigma $ such that ${\propto _0}\subseteq {\propto _0^{\Sigma }}$ . It is relatively simple to see that $\propto _0^{\Sigma }=\bigcup _{\sigma :P\to L_{\Sigma }(P)}\sigma (\propto _0)=\operatorname *{\mathrm {\textsf {unskel}}}(\propto _0)$ . Just note that for each substitution $\sigma :P\to L_{\Sigma }(P)$ we have that $({\operatorname *{\mathrm {\textsf {skel}}}}\circ {\sigma }):P\to L_{\Sigma _0}(P)$ is also a substitution, and also $\operatorname *{\mathrm {\textsf {unskel}}}\circ ({\operatorname *{\mathrm {\textsf {skel}}}}\circ {\sigma })=\sigma $ . The fact that $\operatorname *{\mathrm {\textsf {skel}}},\operatorname *{\mathrm {\textsf {unskel}}}$ are bijections make it straightforward to show that $\propto _0^{\Sigma }$ is indeed a consequence relation of the correct type.

Let $\Gamma ,\Delta ,\{A\}\subseteq L_{\Sigma }(P)$ . Concretely, in the multiple-conclusion case, we have that ${\Gamma }\vartriangleright _0^{\Sigma }{\Delta }$ if and only if ${\operatorname *{\mathrm {\textsf {skel}}}(\Gamma )}\vartriangleright _0{\operatorname *{\mathrm {\textsf {skel}}}(\Delta )}$ if and only if there exist $\Gamma _0,\Delta _0\subseteq L_{\Sigma _0}(P)$ and $\sigma :P\to L_{\Sigma }(P)$ such that $\Gamma _0^{\sigma }\subseteq \Gamma $ , $\Delta _0^{\sigma }\subseteq \Delta $ , and $\Gamma _0\vartriangleright _0\Delta _0$ .

Analogously, in the single-conclusion case, we have that ${\Gamma }\vdash _0^{\Sigma }{A}$ if and only if ${\operatorname *{\mathrm {\textsf {skel}}}(\Gamma )}\vdash _0{\operatorname *{\mathrm {\textsf {skel}}}(A)}$ if and only if there exist $\Gamma _0,\{A_0\}\subseteq L_{\Sigma _0}(P)$ and $\sigma :P\to L_{\Sigma }(P)$ such that $\Gamma _0^{\sigma }\subseteq \Gamma $ , $A_0^{\sigma }=A$ , and $\Gamma _0\vdash _0\ A_0$ .

It is also quite natural to formulate the combination of logics (also known as fibring) as follows.

Note that it follows easily that the combination of compact logics is necessarily compact. Indeed, if ${\langle \Sigma _1,\propto _1\rangle }$ , ${\langle \Sigma _2,\propto _2\rangle }$ are compact then the least logic ${\langle \Sigma _1\cup \Sigma _2,\propto _{12}\rangle }$ such that $\propto _1,\propto _2{\subseteq }\propto _{12}$ is also the least logic such that $\propto _{1,\textrm {fin}},\propto _{2,\textrm {fin}}{\subseteq }\propto _{12}$ . Since it is clear that $\propto _{1,\textrm {fin}},\propto _{2,\textrm {fin}}{\subseteq }\propto _{12,\textrm {fin}}$ , it follows that $\propto _{12}{=}\propto _{12,\textrm {fin}}$ .

2.3 Calculi

Logics are often defined by syntactic means, using symbolic calculi. Again, we will consider multiple as well as single-conclusion calculi.

A multiple-conclusion calculus is pair ${\langle \Sigma ,R\rangle }$ where $\Sigma $ is a signature, and $R\subseteq \wp (L_{\Sigma }(P))\times \wp (L_{\Sigma }(P))$ is a set of (schematic) (multiple-conclusion) inference rules, each rule ${\langle \Gamma ,\Delta \rangle }\in R$ being usually represented as $\frac {\;\Gamma \;}{\Delta }$ where $\Gamma $ is the set of premises and $\Delta $ the set of conclusions of the rule, also represented as $\frac {\;A_1\;\dots \;A_n\;}{\;B_1\;\dots \;B_m\;}$ when $\Gamma =\{A_1,\dots ,A_n\}$ and $\Delta =\{B_1,\dots ,B_m\}$ . We can associate a multiple-conclusion logic ${\langle \Sigma ,\vartriangleright _R\rangle }$ to a given calculus ${\langle \Sigma ,R\rangle }$ by means of a suitable tree-shaped notion of derivation (see [Reference Caleiro, Marcelino, Iemhoff, Moortgat and de Queiroz20, Reference Marcelino and Caleiro57, Reference Shoesmith and Smiley72]). For the purpose of this paper, however, it is sufficient to characterize ${\langle \Sigma ,\vartriangleright _R\rangle }$ as the least multiple-conclusion logic such that ${R}\subseteq {\vartriangleright _R}$ , being compact when the rules in R all have finite sets of premises and conclusions.

A single-conclusion calculus is pair ${\langle \Sigma ,R\rangle }$ where $\Sigma $ is a signature, and $R\subseteq \wp (L_{\Sigma }(P))\times L_{\Sigma }(P)$ is a set of (schematic) (single-conclusion) inference rules, each rule ${\langle \Gamma ,A\rangle }\in R$ being usually represented as $\frac {\;\Gamma \;}{A}$ where $\Gamma $ is the set of premises and A the conclusion of the rule. It is clear that single-conclusion calculi can be rephrased as particular cases of multiple-conclusion calculi, in particular, those whose rules all have singleton sets of conclusions, and that the corresponding notion of derivation will now be linear-shaped, and coincide with the usual notion of proof in Hilbert-style calculi, giving rise to an associated single conclusion logic ${\langle \Sigma ,\vdash _R\rangle }$ . Again, in any case, ${\langle \Sigma ,\vdash _R\rangle }$ is the least single-conclusion logic such that ${R} \subseteq {\vdash _R}$ , and again it is finitary if all the rules in R have finitely many premises. In that case, if we use R for both a single conclusion-calculus and its singleton-conclusion multiple-conclusion rephrasal, it is straightforward to see that ${\langle \Sigma ,\vartriangleright _R\rangle }=\operatorname *{\mathrm {\textsf {min}}}({\langle \Sigma ,\vdash _R\rangle })$ .

When $\Sigma _0\subseteq \Sigma $ and ${\langle \Sigma _0,R_0\rangle }$ is a calculus, it is immediate that ${\propto _{{\langle \Sigma _0,R_0\rangle }}^{\Sigma }}={\propto _{{\langle \Sigma ,R_0\rangle }}}$ , that is, the extension of ${\langle \Sigma _0,\propto _{R_0}\rangle }$ to $\Sigma $ is precisely ${\langle \Sigma ,\propto _{R_0}\rangle }$ .

Combining calculi at this level is quite simple, as has been known for a long time in the single-conclusion case [Reference Caleiro19]. The logic associated with joining the rules of two calculi is precisely the combination of the logics defined by each calculi, as we show next.

For simplicity, whenever $\propto {=}\propto _R$ (in either the single or the multiple-conclusion scenarios), we will say that R constitutes an axiomatization of the logic ${\langle \Sigma ,\propto \rangle }$ .

2.4 Semantics

Another common way of charactering logics is by semantic means. For their universality we shall consider logical matrices, but will consider an extension of the usual notion which also incorporates two less common ingredients: non-determinism and partiality, following [Reference Avron and Lev3, Reference Baaz, Lahav and Zamansky10]. These two ingredients play essential roles in our forthcoming results.

A partial non-deterministic matrix (PNmatrix) is a pair ${\langle \Sigma ,\mathbb {M}\rangle }$ where $\Sigma $ is a signature, and $\mathbb {M}={\langle V,D,\cdot _{\mathbb {M}}\rangle }$ is such that V is a set (of truth-values), $D\subseteq V$ is the set of designated values, and for each $n\in {\mathbb N}_0$ and $c\in \Sigma ^{(n)}$ , $\cdot _{\mathbb {M}}$ provides the truth-table $c_{\mathbb {M}}:V^n\to \wp (V)$ of c in $\mathbb {M}$ . When appropriate we shall refer to $\mathbb {M}$ as a $\Sigma $ -PNmatrix. When $c_{\mathbb {M}}(x_1,\dots ,x_n)\neq \emptyset $ for all $x_1,\dots ,x_n\in V$ we say that the truth-table of c in $\mathbb {M}$ is total. When $c_{\mathbb {M}}(x_1,\dots ,x_n)$ has at most one element for all $x_1,\dots ,x_n\in V$ we say that the truth-table of c in $\mathbb {M}$ is deterministic. When all the truth-tables are total, we say that ${\langle \Sigma ,\mathbb {M}\rangle }$ is also total, or equivalently that it is a non-deterministic matrix (Nmatrix). Analogously, when all the truth-tables are deterministic, we say that ${\langle \Sigma ,\mathbb {M}\rangle }$ is also deterministic, or equivalently that it is a partial matrix (Pmatrix). Finally, if ${\langle \Sigma ,\mathbb {M}\rangle }$ is total and deterministic we say that it is simply a matrix (the usual notion of a logical matrix, up to an isomorphism).

Given $X\subseteq V$ , $\mathbb {M}_X={\langle X,\cdot _{\mathbb {M}_X},D\cap X\rangle }$ is the substructure of $\mathbb {M}={\langle V,D,\cdot _{\mathbb {M}}\rangle }$ obtained by restricting it to values in X, that is, for and $x_1,\ldots ,x_k\in X$ . We say that $X\neq \emptyset $ is a total component of $\mathbb {M}$ whenever $\mathbb {M}_X$ is an Nmatrix. We denote by $\textsf {Tot}_{\mathbb {M}}$ the set of total components of $\mathbb {M}$ . A truth-value $x\in V$ is said to be spurious in $\mathbb {M}$ if there is no total component $X\in \textsf {Tot}_{\mathbb {M}}$ such that $x\in X$ .

A $\mathbb {M}$ -valuation is a function $v:L_{\Sigma }(P)\to V$ such that $v(c(A_1,\dots ,A_n))\in c_{\mathbb {M}}(v(A_1),\dots ,v(A_n))$ for every $n\in {\mathbb N}_0$ , every n-place connective $c\in \Sigma $ , and every $A_1,\dots ,A_n\in L_{\Sigma }(P)$ . We denote the set of all $\mathbb {M}$ -valuations by $\textrm {Val}(\mathbb {M})$ . Note that if x is spurious in $\mathbb {M}$ and $v\in \textrm {Val}(\mathbb {M})$ then $x\notin v(L_{\Sigma }(P))\in \textsf {Tot}_{\mathbb {M}}$ . Consequently, we have that $\textrm {Val}(\mathbb {M})=\bigcup _{X\in \textsf {Tot}_{\mathbb {M}}}\textrm {Val}(\mathbb {M}_X)$ .

As is well known, if ${\langle \Sigma ,\mathbb {M}\rangle }$ is a matrix then every function $f:Q\to V$ with $Q\subseteq P$ can be extended to a $\mathbb {M}$ -valuation (in an essentially unique way for all formulas A with $\operatorname *{\mathrm {\textsf {var}}}(A)\subseteq Q$ ). When $\mathbb {M}$ is a Nmatrix, a function f as above can possibly be extended in many different ways. Still, we know from [Reference Avron and Lev3] that a function $f:\Gamma \to V$ with $\Gamma \subseteq L_{\Sigma }(P)$ can be extended to a $\mathbb {M}$ -valuation provided that $\operatorname *{\mathrm {\textsf {sub}}}(\Gamma )\subseteq \Gamma $ and that $f(c(A_1,\dots ,A_n))\in c_{\mathbb {M}}(f(A_1),\dots ,f(A_n))$ whenever $c(A_1,\dots ,A_n)\in \Gamma $ . We dub such a function a prevaluation of the PNmatrix $\mathbb {M}$ . In case $\mathbb {M}$ is not total, in general, one does not even have such a guarantee [Reference Baaz, Lahav and Zamansky10], unless $f(\Gamma )\subseteq X$ for some $X\in \textsf {Tot}_{\mathbb {M}}$ .

Given a signature $\Sigma $ , a bivaluation is a function $b:L_{\Sigma }(P)\to \{0,1\}$ . The set of all such bivaluations is denoted by $\textrm {BVal}(\Sigma )$ . A set of bivaluations ${\mathcal B}\subseteq \textrm {BVal}(\Sigma )$ is known to characterize a multiple-conclusion relation ${\vartriangleright _{{\mathcal B}}}\subseteq {\wp (L_{\Sigma }(P))\times \wp (L_{\Sigma }(P))}$ defined by $\Gamma \vartriangleright _{{\mathcal B}}\Delta $ when, for every $b\in {\mathcal B}$ , either $0\in b(\Gamma )$ or $1\in b(\Delta )$ . Of course, ${\mathcal B}$ also characterizes the more usual single conclusion relation ${\vdash _{{\mathcal B}}}\subseteq {\wp (L_{\Sigma }(P))\times L_{\Sigma }(P)}$ such that $\Gamma \vdash _{{\mathcal B}} A$ when $\Gamma \vartriangleright _{{\mathcal B}} \{A\}$ , i.e., ${\langle \Sigma ,\vdash _{\mathcal B}\rangle }=\operatorname *{\mathrm {\textsf {sing}}}({\langle \Sigma ,\vartriangleright _{\mathcal B}\rangle })$ . In both cases, ${\langle \Sigma ,\propto _{{\mathcal B}}\rangle }$ is a logic whenever ${\mathcal B}$ is closed under substitutions, that is, if $b\in {\mathcal B}$ and $\sigma : P\to L_{\Sigma }(P)$ then $(b\circ \sigma )\in {\mathcal B}$ . By definition, if ${{\mathcal B}'}\subseteq {{\mathcal B}}$ then ${\propto _{{\mathcal B}}}\subseteq {\propto _{{\mathcal B}'}}$ .

A PNmatrix ${\langle \Sigma ,\mathbb {M}\rangle }$ with $\mathbb {M}={\langle V,D,\cdot _{\mathbb {M}}\rangle }$ defines a set of induced bivaluations, closed under substitutions, $\textrm {BVal}(\mathbb {M})=\{t\circ v: v\in \textrm {Val}(\mathbb {M})\}$ , where $t:V\to \{0,1\}$ such that $t(x)=1$ if $x\in D$ , and $t(x)=0$ if $x\notin D$ , simply captures the distinction between designated and undesignated values. We will write $\propto _{\mathbb {M}}$ instead of $\propto _{\textrm {BVal}(\mathbb {M})}$ , and say that ${\langle \Sigma ,\propto _{\mathbb {M}}\rangle }$ is the $\textrm {type}$ -conclusion logic characterized by $\mathbb {M}$ , for $\textrm {type}\in \{\textrm {single},\textrm {multiple}\}$ , which is always compact (finitary) when V is finite. Clearly, $\operatorname *{\mathrm {\textsf {sing}}}({\langle \Sigma ,\vartriangleright _{\mathbb {M}}\rangle })={\langle \Sigma ,\vdash _{\mathbb {M}}\rangle }$ .

Note that if ${\langle \Gamma ,\Delta \rangle }$ is a maximal consistent theory-pair of ${\langle \Sigma ,\vartriangleright _{\mathbb {M}}\rangle }$ then there must exist $b\in \textrm {BVal}(\mathbb {M})$ such that $b^{-1}(1)=\Gamma $ , and consequently also $b^{-1}(0)=\Delta $ . In the single-conclusion case, it is well-known that if $\Gamma $ is a relatively maximal theory of ${\langle \Sigma ,\vdash _{\mathbb {M}}\rangle }$ then there must also exist $b\in \textrm {BVal}(\mathbb {M})$ such that $b^{-1}(1)=\Gamma $ (see [Reference Shoesmith and Smiley72]).

When $\Sigma _0\subseteq \Sigma $ and ${\mathcal B}_0\subseteq \textrm {BVal}(\Sigma _0)$ , it is straightforward to check that ${\mathcal B}_0^{\Sigma }=\{b\circ \operatorname *{\mathrm {\textsf {skel}}}:b\in {\mathcal B}_0\}\subseteq \textrm {BVal}(\Sigma )$ characterizes the extension to $\Sigma $ of the logic characterized by ${\mathcal B}_0$ . It is worth noting that ${\mathcal B}_0^{\Sigma }$ is still closed under substitutions because $\operatorname *{\mathrm {\textsf {skel}}}{\circ }\sigma {\circ }\operatorname *{\mathrm {\textsf {unskel}}}:P\to L_{\Sigma _0}(P)$ is a substitution, and $\operatorname *{\mathrm {\textsf {skel}}}(A^{\sigma })=\operatorname *{\mathrm {\textsf {skel}}}(A)^{\operatorname *{\mathrm {\textsf {skel}}}\circ \sigma \circ \operatorname *{\mathrm {\textsf {unskel}}}}$ ; consequently, we have that $b\circ \operatorname *{\mathrm {\textsf {skel}}}\circ \sigma =(b\circ \operatorname *{\mathrm {\textsf {skel}}}\circ \sigma \circ \operatorname *{\mathrm {\textsf {unskel}}})\circ \operatorname *{\mathrm {\textsf {skel}}}$ and $b\circ \operatorname *{\mathrm {\textsf {skel}}}\circ \sigma \circ \operatorname *{\mathrm {\textsf {unskel}}}$ is in ${\mathcal B}_0$ if b is. When ${\langle \Sigma _0,\mathbb {M}_0\rangle }$ is a PNmatrix it is very easy, making essential use of non-determinism, to define a PNmatrix ${\langle \Sigma ,\mathbb {M}_0^{\Sigma }\rangle }$ that characterizes the extension to $\Sigma $ of the logic characterized by $\mathbb {M}_0$ . If $\mathbb {M}_0={\langle V_0,D_0,\cdot _{\mathbb {M}_0}\rangle }$ , one defines $\mathbb {M}_0^{\Sigma }={\langle V_0,D_0,\cdot _{\mathbb {M}_0}^{\Sigma }\rangle }$ such that $c_{\mathbb {M}_0}^{\Sigma }=c_{\mathbb {M}_0}$ if $c\in \Sigma _0$ , and $c_{\mathbb {M}_0}^{\Sigma }(x_1,\dots ,x_n)=V_0$ for every $x_1,\dots ,x_n\in V_0$ if $c\in \Sigma \setminus \Sigma _0$ is a n-place connective. It is straightforward to check that $\textrm {Val}({\mathbb {M}_0^{\Sigma }})=\{v\circ \operatorname *{\mathrm {\textsf {skel}}}:v\in \textrm {Val}({\mathbb {M}_0})\}$ .

Our work in the next section of the paper is to prove results that enable us to describe the semantics of the combination of logics characterized by (P)(N)matrices, analogous to Proposition 2. Before tackling these problems, it is certainly useful to ground all the relevant notions to concrete illustrative examples.

2.5 Illustrations

In this subsection we present a few examples illustrating the relevant notions, as introduced earlier, including the new semantic phenomena brought by partiality and non-determinism, the divide between the single- and multiple-conclusion settings, and also the idiosyncrasies of combined logics.

Example 3 (Classical logic, fragments, and combinations)

Let $\Sigma _{\textsf {cls}}$ be the usual connectives $\top ,\neg ,\wedge ,\vee ,\to $ , that is, $\Sigma _{\textsf {cls}}^{(0)}=\{\top \}$ , $\Sigma _{\textsf {cls}}^{(1)}=\{\neg \}$ , $\Sigma _{\textsf {cls}}^{(2)}=\{\wedge ,\vee ,\to \}$ , and $\Sigma _{\textsf {cls}}^{(n)}=\emptyset $ for $n>2$ .

For simplicity, given some connectives $\Theta $ of the signature, we will write $\Sigma _{\textsf {cls}}^{\Theta }$ to denote the subsignature of $\Sigma _{\textsf {cls}}$ containing only the connectives in $\Theta $ .

Take, for instance, $\Sigma _0=\Sigma _{\textsf {cls}}^{\neg ,\to }\subseteq \Sigma _{\textsf {cls}}$ and $\Sigma ^{\prime }_0=\Sigma _{\textsf {cls}}^{\to }\subseteq \Sigma _{\textsf {cls}}$ . The formula $A=\neg ((\neg p)\to (p\wedge (q\to q)))\in L_{\Sigma _{\textsf {cls}}}(P)$ is such that its skeleton from the point of view of $\Sigma _0$ is $\operatorname *{\mathrm {\textsf {skel}}}_{\Sigma _0}(A)= \neg ((\neg p')\to r)$ , if $\operatorname *{\mathrm {\textsf {skel}}}_{\Sigma _0}(p)=p'$ and for the monolith we have $\operatorname *{\mathrm {\textsf {skel}}}_{\Sigma _0}(p\wedge (q\to q))=r$ . However, from the point of view of $\Sigma ^{\prime }_0$ we have that $\operatorname *{\mathrm {\textsf {skel}}}_{\Sigma ^{\prime }_0}(A)$ is itself a variable, as A is a monolith.

Consider now the Boolean $\Sigma _{\textsf {cls}}$ -matrix defined by the following tables.

It is well-known that this matrix characterizes classical propositional logic, and we will write $\vdash _{\textsf {cls}}$ to denote . However, we can also consider a multiple-conclusion version of classical logic, and write $\vartriangleright _{\textsf {cls}}$ to denote . Of course, we have that , but in this case . Note that $\emptyset \not \vdash _{\textsf {cls}}p$ and $\emptyset \not \vdash _{\textsf {cls}}\neg p$ , but one has $\emptyset \vartriangleright _{\textsf {cls}}p,\neg p$ .

The multiple-conclusion version of classical logic $\vartriangleright _{\textsf {cls}}$ is known from [Reference Shoesmith and Smiley72] to be alternatively characterized by the following multiple-conclusion calculus.

$$ \begin{align*}\qquad\qquad\qquad\frac{\quad}{ \;\top\;}\qquad\qquad\qquad\frac{p \,,\, \neg p}{ }\qquad\qquad\qquad\frac{ }{\;p \,,\, \neg p\;} \qquad\end{align*} $$

$$ \begin{align*}\qquad\qquad\frac{\; p\wedge q\;}{p}\qquad\qquad\qquad \frac{\; p\wedge q\;}{q}\qquad\qquad \qquad\frac{\;p\,,\, q\;}{p\wedge q} \end{align*} $$

$$ \begin{align*}\qquad\qquad\frac{p}{\; p\vee q\;}\qquad\qquad\qquad \frac{q}{\;p \vee q\;}\qquad\qquad\qquad \frac{p\vee q}{\;p\,,\, q\;} \end{align*} $$

$$ \begin{align*}\qquad\qquad\frac{}{\;p\,,\,p\to q\;}\qquad\qquad\quad \frac{\;p\,,\,p\to q\;}{q}\qquad\qquad\quad \frac{q}{\;p\to q\;} \end{align*} $$

It is crucial to observe that the axiomatization above is completely modular with respect to syntax, as each rule involves a single connective. Said another way, the axiomatization is obtained by joining axiomatizations of each of its single-connective fragments, or equivalently we have that

$$ \begin{align*}{\langle \Sigma_{\textsf{cls}},\vartriangleright_{\textsf{cls}}\rangle}={\langle \Sigma_{\textsf{cls}}^{\top},\vartriangleright^{\top}_{\textsf{cls}}\rangle}\bullet{\langle \Sigma^{\neg}_{\textsf{cls}},\vartriangleright^{\neg}_{\textsf{cls}}\rangle}\bullet{\langle \Sigma^{\wedge}_{\textsf{cls}},\vartriangleright^{\wedge}_{\textsf{cls}}\rangle}\bullet{\langle \Sigma^{\vee}_{\textsf{cls}},\vartriangleright^{\vee}_{\textsf{cls}}\rangle}\bullet{\langle \Sigma^{\to}_{\textsf{cls}},\vartriangleright^{\to}_{\textsf{cls}}\rangle}, \end{align*} $$

where $\vartriangleright ^c_{\textsf {cls}}{=}\vartriangleright _{\textsf {cls}}{\cap }(\wp (L_{\Sigma _{\textsf {cls}}^c}(P))\times \wp (L_{\Sigma _{\textsf {cls}}^c}(P)))$ for each $c\in \Sigma _{\textsf {cls}}$ is the corresponding single-connective fragment of the logic. This fact marks a sharp contrast with respect to the single-conclusion setting, which goes well beyond classical logic, and that will play a key role in our developments. For instance, the single-conclusion version of classical logic is known to be characterized by the following single-conclusion calculus.

$$ \begin{align*}\frac{}{\;\top\;}\quad \frac{}{\;p\to (q \to p)\;}\quad \frac{}{\;(p\to (q \to r))\to ((p\to q)\to(p \to r))\;}\quad \frac{\;p \qquad p \to q\;}{q}\end{align*} $$

$$ \begin{align*}\frac{}{\;(p\wedge q) \to p\;}\qquad \frac{}{\;(p\wedge q) \to q\;}\qquad \frac{}{\;(r\to p) \to ((r\to q) \to (r\to(p\wedge q)))\;} \end{align*} $$

$$ \begin{align*}\frac{}{\;p \to (p\vee q)\;}\qquad \frac{}{\;q \to (p\vee q)\;}\qquad \frac{}{\;(p \to r) \to ((q \to r) \to ((p\vee q)\to r)))\;} \end{align*} $$

$$ \begin{align*}\frac{}{\;\neg(p\to p) \to q\;}\qquad \frac{}{\;(p\to \neg q)\to (q\to \neg p)\;}\qquad \frac{}{\;\neg \neg p\to p\;}\end{align*} $$

The fact that the single-conclusion axiomatization is not at all modular with respect to syntax, and that most rules refer to more than one connective, is definitely not a coincidence, as shown in [Reference Caleiro, Marcelino and Marcos26]. Indeed, each of the single-connective fragments $\vdash _{\textsf {cls}}^c{=}\vdash _{\textsf {cls}}{\cap }(\wp (L_{\Sigma _{\textsf {cls}}^c}(P))\times L_{\Sigma _{\textsf {cls}}^c}(P))$ of $\vdash _{\textsf {cls}}$ for each connective $c\in \Sigma _{\textsf {cls}}$ can be axiomatized as follows (see [Reference Rautenberg65]).

It is clear that joining all these rules will yield a logic much weaker than classical logic (see [Reference Caleiro, Marcelino and Marcos26]), that is,

$$ \begin{align*} {\langle \Sigma_{\textsf{cls}},\vdash_{\textsf{cls}}\rangle}\supsetneq{\langle \Sigma_{\textsf{cls}}^{\top},\vdash^{\top}_{\textsf{cls}}\rangle}\bullet{\langle \Sigma^{\neg}_{\textsf{cls}},\vdash^{\neg}_{\textsf{cls}}\rangle}\bullet{\langle \Sigma^{\wedge}_{\textsf{cls}},\vdash^{\wedge}_{\textsf{cls}}\rangle}\bullet{\langle \Sigma^{\vee}_{\textsf{cls}},\vdash^{\vee}_{\textsf{cls}}\rangle}\bullet{\langle \Sigma^{\to}_{\textsf{cls}},\vdash^{\to}_{\textsf{cls}}\rangle}. \end{align*} $$

A suitable semantics for the resulting combined logic is not obvious.

The previous example, though very familiar, was useful for illustrating some of the notions and notations used in this paper, and in particular, the differences between the single- and multiple-conclusion settings, in particular, when combining logics. However, even in a two-valued scenario, non-determinism allows for characterizing some interesting non-classical connectives and logics.

Example 4 (Some new two-valued connectives)

Consider the signature $\Sigma $ such that $\Sigma ^{(0)}=\{\bot \mkern -14mu\top \}$ , $\Sigma ^{(1)}=\{\square \}$ , $\Sigma ^{(2)}=\{\rightsquigarrow ,{\wedge \!\!\!\!\vee }\}$ , and $\Sigma ^{(n)}=\emptyset $ for $n>2$ , and the Boolean-like $\Sigma $ -Nmatrix defined by the following tables.

The $0$ -place connective $\bot \mkern -14mu\top $ is known as botop in [Reference Marcos58]. Since the interpretation of $\bot \mkern -14mu\top $ is fully non-deterministic the connective is unrestricted, in the sense that its logic is characterized by the empty calculus, without any rules.

Then, $\square $ is a $1$ -place modal-like box operator whose logic is characterized by the usual (global) necessitation rule:

$$ \begin{align*} \frac{p}{\square p}. \end{align*} $$

The $2$ -place implication-like connective $\rightsquigarrow $ is characterized solely by the rule of modus ponens:

$$ \begin{align*}\frac{p\,,\, p \rightsquigarrow q}{q}.\end{align*} $$

All rules above serve both the single- and multiple-conclusion settings.

Lastly, the $2$ -place connective ${\wedge \!\!\!\!\vee }$ , was named platypus in [Reference Marcelino53], and features some properties of classical conjunction mingled with classical disjunction. Its multiple-conclusion logic is characterized by the following two (familiar) rules.

$$ \begin{align*}\frac{p\,,\,q}{p{\wedge\!\!\!\!\vee} q}\qquad\qquad\frac{p{\wedge\!\!\!\!\vee} q}{p\,,\,q}\end{align*} $$

As shown in [Reference Marcelino53], the single-conclusion logic of platypus cannot be finitely axiomatized.

Of course, the added richness provided by non-determinism goes well beyond the two-valued cases seen above.

Example 5 (Information sources)

In [Reference Avron, Ben-Naim and Konikowska6], the authors introduce a logic for modelling the reasoning of a processor which collects information from different classical sources. Each source may provide information that a certain formula of classical logic is true, or false, or no information at all. This situation gives rise to four possible situation as, for each formula, $(t)$ the processor may have information that it is true and no information that it is false, or $(f)$ information that it is false and no information that it is true, or $(\top )$ have information that it is true and also information that it is false, or $(\bot )$ have no information at all about the formula. This situation is easily understandable if one reads the situations as collecting the available classical truth-values (0,1) for each formula as

$$ \begin{align*}t=\{1\},\quad f=\{0\},\quad \top=\{0,1\},\quad \bot=\emptyset.\end{align*} $$

As originally presented, the logic is defined over the signature $\Sigma _S=\Sigma _{\textsf {cls}}^{\wedge ,\vee ,\neg }$ and characterized by the Nmatrix $\mathbb {S} = {\langle \{f,\bot ,\top ,t\},\{\top ,t\},\cdot _{\mathbb {S}}\rangle }$ defined by the tables below.

Clearly, both conjunction and disjunction have non-deterministic interpretations. For instance, note that $t\wedge _{\mathbb {S}}t=\{t,\top \}$ . Thus, a valuation $v\in \textrm {Val}(\mathbb {S})$ may be such that there exist formulas $A,B$ with $v(A)=v(B)=v(A\wedge B)=t$ and $v(B\wedge A)=\top $ .

From [Reference Caleiro, Marcelino, Iemhoff, Moortgat and de Queiroz20, Reference Marcelino and Caleiro57] we know that both $\vartriangleright _{\mathbb {S}}$ and $\vdash _{\mathbb {S}}$ are axiomatized by the following rules.

$$ \begin{align*}\frac{p\,,\, q}{\;p\wedge q\;}\quad \frac{\;p\wedge q\;}{p}\quad \frac{\;p\wedge q\;}{q} \quad \frac{\neg p}{\;\neg(p\wedge q)\;} \quad \frac{\neg q}{\;\neg(p\wedge q)\;}\end{align*} $$

$$ \begin{align*}\frac{p}{\;p\vee q\;}\quad \frac{q}{\;p\vee q\;}\quad \frac{\;\neg(p\vee q)\;}{\neg p} \quad \frac{\;\neg(p\vee q)\;}{\neg q} \quad \frac{\neg p\,,\,\neg q}{\;\neg(p\vee q)\;} \end{align*} $$

$$ \begin{align*} \quad\frac{p}{\;\neg \neg p\;}\quad \frac{\;\neg \neg p\;}{p} \end{align*} $$

The fact that this single-conclusion calculus characterizes the multiple-conclusion consequence $\vartriangleright _{\mathbb {S}}$ is remarkable, implying that $\operatorname *{\mathrm {\textsf {min}}}({\langle \Sigma _S,\vdash _{\mathbb {S}}\rangle }){=}{\langle \Sigma _S,\vartriangleright _{\mathbb {S}}\rangle }$ . Particularly, given any set of formulas $\Gamma $ , note that $\Gamma \not \vartriangleright _{\mathbb {S}}\emptyset $ , as the function such that $v(A)=\top $ for all formulas $A\in L_{\Sigma _S}(P)$ , is such that $v\in \textrm {Val}(\mathbb {S})$ .

Note that these logics could not possibly be characterized by finite matrices. Let $p\in P$ be a variable, and define $A_0=p$ and $A_{k+1}=p\lor A_k$ for $k\in {\mathbb N}_0$ . Note that $\Gamma =\{A_k:k\in {\mathbb N}_0\}$ satisfies $\operatorname *{\mathrm {\textsf {sub}}}(\Gamma )\subseteq \Gamma $ , and consider for each $i\in {\mathbb N}_0$ the prevaluation $f_i:\Gamma \to \{f,\bot ,\top ,t\}$ of $\mathbb {S}$ defined by

$$ \begin{align*} f_i(A_k)= \begin{cases} f, & \mbox{ if }k<i, \\ \top, & \mbox{ otherwise. } \end{cases} \end{align*} $$

Each $f_i$ thus extends to a valuation $v_i\in \textrm {Val}(\mathbb {S})$ showing that $A_i\not \vdash _{\mathbb {S}} A_k$ for $k<i$ . Hence, $\vdash _{\mathbb {S}}$ fails to be locally finite and therefore cannot be characterized by a finite set of finite matrices [Reference Caleiro, Marcelino and Rivieccio25]. The same applies to $\vartriangleright _{\mathbb {S}}$ , simply because $\operatorname *{\mathrm {\textsf {sing}}}({\langle \Sigma _S,\vartriangleright _{\mathbb {S}}\rangle }){=}{\langle \Sigma _S,\vdash _{\mathbb {S}}\rangle }$ .

Besides allowing for a great amount of compression of the number of necessary truth-values, non-determinism has another outstanding property regarding modularity with respect to syntax.

Example 6 (Language extensions)

Above, given a logic ${\langle \Sigma _0,\propto _0\rangle }$ and $\Sigma _0\subseteq \Sigma $ , we have defined its extension to the larger signature as ${\langle \Sigma ,\propto _0^{\Sigma }\rangle }$ . If ${\langle \Sigma _0,\propto _0\rangle }$ has an associated calculus ${\langle \Sigma _0,R\rangle }$ , then it is clear that the extension ${\langle \Sigma ,\propto _0^{\Sigma }\rangle }$ is associated with the exact same rules via the calculus ${\langle \Sigma ,R\rangle }$ .

Take, for instance, single-conclusion classical propositional logic ${\langle \Sigma _{\textsf {cls}},\vdash _{\textsf {cls}}\rangle }$ as defined in Example 3. Suppose that we wish to consider its extension to a larger signature $\Sigma \supseteq \Sigma _{\textsf {cls}}$ containing a new connective $c\in \Sigma ^{(2)}$ . We know that the exact same calculus presented above is associated with the extended logic ${\langle \Sigma ,\vdash ^{\Sigma }_{\textsf {cls}}\rangle }$ . What is more, we also have that the extended logic is characterized by the $\Sigma $ -Nmatrix which extends the $\Sigma _{\textsf {cls}}$ -matrix by letting

where the unrestricted connective is interpreted in a fully non-deterministic manner. This extension could not be characterized by a finite matrix [Reference Avron and Lev3].

At last, we should illustrate the advantages and intricacies that result from introducing partiality.

Example 7 (Kleene’s strong three-valued logic)

We consider the (single-conclusion) implication-free fragment of Kleene’s strong three-valued logic as defined in [Reference Font38]. This logic is defined over the signature $\Sigma =\Sigma _{\textsf {cls}}^{\wedge ,\vee ,\neg }$ and is usually characterized by means of two three-valued $\Sigma $ -matrices. Equivalently, the logic is given just by the four-valued Pmatrix $\mathbb {KS}={\langle \{0,a,b,1\},\{b,1\},\cdot _{\mathbb {KS}}\rangle }$ defined by the following truth-tables.

Note that several entries of the tables are empty, namely $a\wedge _{\mathbb {KS}}b=b\wedge _{\mathbb {KS}}a=a\vee _{\mathbb {KS}}b=b\vee _{\mathbb {KS}}a=\emptyset $ . As such, a valuation in $\textrm {Val}(\mathbb {KS})$ cannot both use the values a and b. Further, a valuation must either use both $0,1$ , or none, because $\neg _{\mathbb {KS}}(0)=1$ and $\neg _{\mathbb {KS}}(1)=0$ . As a consequence, we have $\textsf {Tot}_{\mathbb {KS}}=\{\{a\},\{b\},\{0,1\},\{0,a,1\},\{0,b,1\}\}.$ The two three-valued matrices mentioned above correspond to the restrictions $\mathbb {KS}_X$ to the maximal total components $X=\{0,a,1\}$ and $X=\{0,b,1\}$ .

The single-conclusion logic ${\langle \Sigma ,\vdash _{\mathbb {KS}}\rangle }$ is known to be associated with the calculus.

$$ \begin{align*} \frac{\;p\wedge q\;}{\;\; p\;\;} \quad \frac{\;p\wedge q\;}{\;\; q\;\;}\quad \frac{\;\;p\quad q\;\;}{p\wedge q} \end{align*} $$

$$ \begin{align*} \frac{p}{\;p\vee q\;}\quad \frac{\;p\vee p\;}{p}\quad \frac{\;p\vee q\;}{q\vee p}\quad \frac{\;p\vee (q \vee r)\;}{(p \vee q)\vee r} \end{align*} $$

$$ \begin{align*} \frac{p\lor (q\land r)}{(p\lor q)\land (p\lor r)}\qquad \frac{(p\lor q)\land (p\lor r)}{p\lor (q\land r)} \end{align*} $$

$$ \begin{align*} \frac{p \lor r}{\neg \neg p \lor r}\qquad \frac{\neg \neg p \lor r}{p \lor r} \qquad \frac{\neg (p \lor q) \lor r}{ (\neg p \land \neg q) \lor r} \end{align*} $$

$$ \begin{align*} \frac{(\neg p \land \neg q) \lor r}{\neg (p \lor q) \lor r}\qquad\frac{\neg (p \land q) \lor r}{(\neg p \lor \neg q) \lor r}\qquad\frac{(\neg p \lor \neg q) \lor r}{\neg (p \land q) \lor r} \qquad \frac{(p\land \neg p)\lor r}{(q\lor \neg q) \lor r} \end{align*} $$

The Pmatrix ${\mathbb {KS}}$ also characterizes the multiple-conclusion logic ${\langle \Sigma ,\vartriangleright _{\mathbb {KS}}\rangle }$ , which is known from [Reference Caleiro, Marcelino, Iemhoff, Moortgat and de Queiroz20] to be associated with the calculus.

$$ \begin{align*} \frac{p\,,\, q}{\;p\wedge q\;}\quad \frac{\;p\wedge q\;}{p}\quad \frac{\;p\wedge q\;}{q} \quad \frac{\neg p}{\;\neg(p\wedge q)\;} \quad \frac{\neg q}{\;\neg(p\wedge q)\;} \quad \frac{\;\neg(p\wedge q)\;}{\;\neg p\,,\, \neg q\;} \end{align*} $$

$$ \begin{align*} \frac{p}{\;p\vee q\;}\quad \frac{q}{\;p\vee q\;}\quad \frac{\;\neg(p\vee q)\;}{\neg p} \quad \frac{\;\neg(p\vee q)\;}{\neg q} \quad \frac{\neg p\,,\,\neg q}{\;\neg(p\vee q)\;} \quad \frac{\;p\vee q\;}{\;p\,,\, q\;} \end{align*} $$

$$ \begin{align*} \quad\frac{p}{\;\neg \neg p\;}\quad \frac{\;\neg \neg p\;}{p}\quad \frac{\;p\,,\, \neg p\;}{q\,,\,\neg q} \end{align*} $$

This latter multiple-conclusion calculus is clearly more natural. As it contains genuinely multiple-conclusion rules, in this case, $\operatorname *{\mathrm {\textsf {min}}}({\langle \Sigma ,\vdash _{\mathbb {KS}}\rangle }){\subsetneq }{\langle \Sigma ,\vartriangleright _{\mathbb {KS}}\rangle }$ . Note, for instance, that $p\vee q\vartriangleright _{\mathbb {KS}} p,q$ , but that $p\vee q\not \vdash _{\mathbb {KS}} p$ and $p\vee q\not \vdash _{\mathbb {KS}} q$ .

Partiality can indeed be used in almost all cases to provide a single PNmatrix for a logic characterized by a set of Nmatrices, as we will see later.

3.1 The multiple-conclusion case

In the multiple-conclusion case, the characterization we need is really very simple, if one considers bivaluations. The result stems directly from the known fact (see [Reference Shoesmith and Smiley72]) that for every multiple-conclusion logic ${\langle \Sigma ,\vartriangleright \rangle }$ the set ${\mathcal B}=\{b\in \textrm {BVal}(\Sigma ):b^{-1}(1)\not \vartriangleright b^{-1}(0)\}$ is the only one set of bivaluations such that ${\vartriangleright }={\vartriangleright _{{\mathcal B}}}$ . Note that this also implies that ${\vartriangleright _{{\mathcal B}}}\subseteq {\vartriangleright _{{\mathcal B}'}}$ if and only if ${{\mathcal B}'}\subseteq {{\mathcal B}}$ .

We fix signatures $\Sigma _1,\Sigma _2$ , and sets of bivaluations ${\mathcal B}_1\subseteq \textrm {BVal}(\Sigma _1)$ and ${\mathcal B}_2\subseteq \textrm {BVal}(\Sigma _2)$ , both closed under substitutions.

This result allows us to obtain a clean abstract characterization of the combination of multiple-conclusion logics. One just needs to note that, given a signature $\Sigma $ , a partition ${\langle \underline {\Omega },\overline {\Omega }\rangle }$ of $L_{\Sigma }(P)$ is essentially the same thing as a bivaluation $b\in \textrm {BVal}(\Sigma )$ with $b^{-1}(1)=\underline {\Omega }$ and $b^{-1}(0)=\overline {\Omega }$ .

Corollary 9. Let ${\langle \Sigma _1,\vartriangleright _1\rangle }$ , ${\langle \Sigma _2,\vartriangleright _2\rangle }$ be multiple-conclusion logics, and consider their combination ${\langle \Sigma _1\cup \Sigma _2,\vartriangleright _{12}\rangle }={\langle \Sigma _1,\vartriangleright _1\rangle }\bullet {\langle \Sigma _2,\vartriangleright _2\rangle }$ . For every $\Gamma ,\Delta \subseteq L_{\Sigma _1\cup \Sigma _2}(P)$ , we have

$$ \begin{align*} \Gamma\vartriangleright_{12}\Delta \end{align*} $$

$$ \begin{align*} \textrm{if and only if} \end{align*} $$

$$ \begin{align*} \textrm{for each partition }{\langle \underline{\Omega},\overline{\Omega}\rangle}\textrm{ of }L_{\Sigma_1\cup\Sigma_2}(P)\textrm{, there is }k\in\{1,2\}\textrm{ such that } \end{align*} $$

$$ \begin{align*} \Gamma\cup\underline{\Omega}\vartriangleright_k^{\Sigma_1\cup\Sigma_2}\overline{\Omega}\cup\Delta. \end{align*} $$

The question is now whether we can mimic this simplicity at the level of PNmatrices. It turns out that one can define a very simple but powerful operation (already studied in [Reference Marcelino, Caleiro, Kennedy and de Queiroz56] with respect to Nmatrices, but only in the disjoint case) in order to combine PNmatrices.

We fix PNmatrices ${\langle \Sigma _1,\mathbb {M}_1\rangle }$ and ${\langle \Sigma _2,\mathbb {M}_2\rangle }$ , with $\mathbb {M}_1={\langle V_1,D_1,\cdot _{\mathbb {M}_1}\rangle }$ and $\mathbb {M}_2={\langle V_2,D_2,\cdot _{\mathbb {M}_2}\rangle }$ .

Note that $V_{\ast }$ contains all pairs of truth-values which are compatible, that is, either both designated, or both undesignated. The pairs where both values are designated constitute $D_{\ast }$ . The truth-table of a shared connective $c\in \Sigma _1\cap \Sigma _2$ comprises all the pairs of values in the truth-tables of $\mathbb {M}_1,\mathbb {M}_2$ which are compatible. The truth-table of a non-shared connective, say $c\in \Sigma _1\setminus \Sigma _2$ , has each possible value in the truth-table of $\mathbb {M}_1$ paired with all compatible values in $V_2$ . Clearly, the resulting PNmatrix is fundamentally non-deterministic for non-shared connectives whenever the given PNmatrices have several designated values, and several undesignated values. For shared connectives, non-determinism may appear if inherited from some of the given PNmatrices. Partiality, on its turn, is crucial to the interpretation of shared connectives, showing up whenever the values given by the truth-tables of $\mathbb {M}_1,\mathbb {M}_2$ cannot be paired compatibly. For non-shared connectives, partiality may still appear if inherited from the given PNmatrices, or in pathological cases where the given PNmatrices do not have designated values, or do not have undesignated values.

Before characterizing the exact scope of this construction, we should note that valuations in $\mathbb {M}_1\ast \mathbb {M}_2$ are always suitable combinations of valuations in $\mathbb {M}_1$ and $\mathbb {M}_2$ . For $k\in \{1,2\}$ , we will use $\pi _k:V_{\ast }\to V_k$ to denote the obvious projection functions, i.e., $\pi _1(x,y)=x$ and $\pi _2(x,y)=y$ . Easily, if $v\in \textrm {Val}({\mathbb {M}_1\ast \mathbb {M}_2})$ then $(\pi _k\circ v)\in \textrm {Val}({\mathbb {M}_k}^{\Sigma _1\cup \Sigma _2})$ . Also, it is clear that $v(A)$ , $(\pi _1\circ v)(A)$ , $(\pi _2\circ v)(A)$ are all compatible for every formula A in the combined language. Further, if $v_1\in \textrm {Val}(\mathbb {M}_1^{\Sigma _1\cup \Sigma _2})$ , $v_2\in \textrm {Val}(\mathbb {M}_2^{\Sigma _1\cup \Sigma _2})$ , and $v_1(A)$ is compatible with $v_2(A)$ for every $A\in L_{\Sigma _1\cup \Sigma _2}(P)$ , then $(v_1\ast v_2)\in \textrm {Val}(\mathbb {M}_1\ast \mathbb {M}_2)$ with $(v_1\ast v_2)(A)=(v_1(A),v_2(A))$ for each A. These properties apply also to prevaluations over any set of formulas closed under taking subformulas.

Now, we can show that the multiple-conclusion logic characterized by a strict product is the corresponding combined logic.

This result, besides being based on a simple operation on PNmatrices, has a very useful feature: it provides a finite-valued semantics for the combined logic whenever we are given finite-valued semantics for both given multiple-conclusion logics.

Let us look at some examples, starting with the two-valued case.

Example 13 (Multiple-conclusion two-valued combinations)

Take two signatures $\Sigma _1,\Sigma _2$ and consider two-valued PNmatrices ${\langle \Sigma _1,\mathbb {M}_1\rangle }, {\langle \Sigma _2,\mathbb {M}_2\rangle }$ with $\mathbb {M}_1={\langle \{0,1\},\{1\},\cdot _{\mathbb {M}_1}\rangle }$ and $\mathbb {M}_2={\langle \{0,1\},\{1\},\cdot _{\mathbb {M}_2}\rangle }$ , such as those in Examples 3 or 4.

Note that according to Definition 10, $\mathbb {M}_1\ast \mathbb {M}_2$ is also two-valued, having values $(0,0)$ and $(1,1)$ , with the latter designated. In the following discussion, for simplicity, we shall rename the two values to just 0 and 1, respectively, and assume that the strict product is $\mathbb {M}_1\ast \mathbb {M}_2={\langle \{0,1\},\{1\},\cdot _{\ast }\rangle }$ .

If $c\in \Sigma _1\cap \Sigma _2$ is a shared connective, and assuming for the sake of exposition that c is a $2$ -place connective, we have that $c_{\ast }$ behaves as depicted below.

This behaviour is absolutely similar for connectives with any number of places, that is, $c_{\ast }(x_1,\ldots ,x_k)=c_{\mathbb {M}_1}(x_1,\ldots ,x_k)\cap c_{\mathbb {M}_2}(x_1,\ldots ,x_k)$ for any $k\in {\mathbb N}_0$ and $c\in (\Sigma _1\cap \Sigma _2)^{(k)}$ . Consequently, $c_{\ast }(x_1,\ldots ,x_k)=c_{\mathbb {M}_1}(x_1,\ldots ,x_k)= c_{\mathbb {M}_2}(x_1,\ldots ,x_k)$ whenever $c_{\mathbb {M}_1}(x_1,\ldots ,x_k)= c_{\mathbb {M}_2}(x_1,\ldots ,x_k)$ .

If $c\in \Sigma _1\cup \Sigma _2$ is not a shared connective, and assuming without loss of generality that $c\in \Sigma _1$ , $c\notin \Sigma _2$ , then in the strict product we have $c_{\ast }=c_{\mathbb {M}_1}$ . This implies that one could simply consider the extended PNmatrices $\mathbb {M}_1^{\Sigma _1\cup \Sigma _2},\mathbb {M}_2^{\Sigma _1\cup \Sigma _2}$ and just use the equation above, as $c_{\mathbb {M}_1}(x_1,\ldots ,x_k)\cap \{0,1\}=c_{\mathbb {M}_1}(x_1,\ldots ,x_k)$ .

It is clear that the resulting PNmatrix may be genuinely partial in case some of the sets are disjoint, and in general will be a Pmatrix whenever starting with two matrices.

Recalling Example 3, we see that given any two sets of classical connectives $\Theta _1,\Theta _2$ , if $\mathbb {M}_1$ and $\mathbb {M}_2$ are the corresponding fragments of the classical matrix , it follows that $\mathbb {M}_1\ast \mathbb {M}_2$ is the fragment of corresponding to $\Theta _1\cup \Theta _2$ . According to Theorem 12, this implies that ${\langle \Sigma _{\textsf {cls}}^{\Theta _1\cup \Theta _2},\vartriangleright _{\textsf {cls}}^{\Theta _1\cup \Theta _2}\rangle }={\langle \Sigma _{\textsf {cls}}^{\Theta _1},\vartriangleright ^{\Theta _1}_{\textsf {cls}}\rangle }\bullet {\langle \Sigma ^{\Theta _2}_{\textsf {cls}},\vartriangleright ^{\Theta _2}_{\textsf {cls}}\rangle }$ and thus we have

$$ \begin{align*} {\langle \Sigma_{\textsf{cls}},\vartriangleright_{\textsf{cls}}\rangle}={\langle \Sigma_{\textsf{cls}}^{\top},\vartriangleright^{\top}_{\textsf{cls}}\rangle}\bullet{\langle \Sigma^{\neg}_{\textsf{cls}},\vartriangleright^{\neg}_{\textsf{cls}}\rangle}\bullet{\langle \Sigma^{\wedge}_{\textsf{cls}},\vartriangleright^{\wedge}_{\textsf{cls}}\rangle}\bullet{\langle \Sigma^{\vee}_{\textsf{cls}},\vartriangleright^{\vee}_{\textsf{cls}}\rangle}\bullet{\langle \Sigma^{\to}_{\textsf{cls}},\vartriangleright^{\to}_{\textsf{cls}}\rangle}. \end{align*} $$

We will see later that in the single-conclusion case the situation can be dramatically different.

Let us now consider a richer example.

Example 14 (Combining the three-valued implications of Kleene and Łukasiewicz)

Consider the signature $\Sigma $ with $\Sigma ^{(2)}=\{\to \}$ and $\Sigma ^{{n}}=\emptyset $ for $n\neq 2$ . The three-valued implications of Kleene and Łukasiewicz are defined by the well-known matrices $\mathbb {K}={\langle \{0,\frac {1}{2},1\},\{1\},\cdot _{\mathbb {K}}\rangle }$ and $\mathbb {L}={\langle \{0,\frac {1}{2},1\},\{1\},\cdot _{\mathbb {L}}\rangle }$ defined below.

According to Theorem 12, we know that ${\langle \Sigma ,\vartriangleright _{\mathbb {K}}\rangle }\bullet {\langle \Sigma ,\vartriangleright _{\mathbb {L}}\rangle }$ is characterized by the five-valued $\Sigma $ -Pmatrix $\mathbb {K}\ast \mathbb {L}={\langle \{00,0\frac {1}{2},\frac {1}{2}0,\frac {1}{2}\frac {1}{2},11\},\{11\},\cdot _{\ast }\rangle }$ given by the truth-table below, where for simplicity we have renamed each truth-value $(x,y)$ to $xy$ .

Analyzing $\mathbb {K}\ast \mathbb {L}$ it is clear that the values $\frac {1}{2}0$ and $\frac {1}{2}\frac {1}{2}$ are spurious, in the sense that they cannot be used by any valuation. This happens because the two corresponding diagonal entries of the table are empty, that is, $(\frac {1}{2}0\to _{\ast }\frac {1}{2}0)=(\frac {1}{2}\frac {1}{2}\to _{\ast }\frac {1}{2}\frac {1}{2})=\emptyset $ .

Removing these spurious elements we obtain the following table.

Further, we also have that $(0\frac {1}{2}\to _{\ast }00)=\emptyset $ . Hence, taking into account the fact that $x \to _{\ast } x=11$ we conclude that the total components of the Pmatrix are $\textsf {Tot}_{\mathbb {K}\ast \mathbb {L}}=\{\{11\},\{00,11\},\{0\frac {1}{2},11\}\}$ . This fact implies that $\textrm {BVal}(\mathbb {K}\ast \mathbb {L})$ is precisely the set of all classical interpretations of classical implication, simply because the restrictions of the Pmatrix to its maximal total components $X=\{00,11\}$ and $X=\{0\frac {1}{2},11\}$ are both isomorphic copies of the two-valued truth-table of classical implication. We can conclude, thus, that ${\langle \Sigma ,\vartriangleright _{\mathbb {K}}\rangle }\bullet {\langle \Sigma ,\vartriangleright _{\mathbb {L}}\rangle }={\langle \Sigma ,\vartriangleright _{\mathbb {K}\ast \mathbb {L}}\rangle }= {\langle \Sigma _{\textsf {cls}}^{\to },\vartriangleright _{\textsf {cls}}^{\to }\rangle }$ coincides with the multiple-conclusion implication-only fragment of classical logic, as defined in Example 3.

Confirmation of this interesting fact can be obtained by putting together calculi for the logics, according to Proposition 2. These multiple-conclusion versions of the logics are not very well known, but a calculus for $\vartriangleright _{\mathbb {K}}$ can be readily obtained using the technique of [Reference Caleiro, Marcelino, Iemhoff, Moortgat and de Queiroz20, Reference Marcelino and Caleiro57], whereas a calculus for $\vartriangleright _{\mathbb {L}}$ can be found in [Reference Avron2]. Of course, all the rules in these calculi are classically valid, because $\vartriangleright _{\mathbb {K}},\vartriangleright _{\mathbb {L}}{\subseteq } \vartriangleright _{\textsf {cls}}^{\to }$ (all classical valuations are permitted in both matrices). Further, as we know the rules of classical implication from Example 3, it suffices to note that: (1) ${q}\vartriangleright _{\mathbb {K}}{p\to q}$ , and also ${q}\vartriangleright _{\mathbb {L}}{p\to q}$ ; (2) ${p,p\to q}\vartriangleright _{\mathbb {K}}q$ , and also ${p,p\to q}\vartriangleright _{\mathbb {L}}q$ ; and (3) $\emptyset \vartriangleright _{\mathbb {L}}p\to p$ and ${p\to p}\vartriangleright _{\mathbb {K}}p,p\to q$ which implies that $\emptyset \vartriangleright _{\mathbb {K}\ast \mathbb {L}}p,p\to q$ .

We will return to this example in the more familiar single-conclusion setting.

We shall now illustrate how different it is to combine logics with or without shared connectives.

Example 15 (The three-valued implications of Kleene and Łukasiewicz, disjointly)

We shall revisited Example 14, combining the (multiple-conclusion) logics of Kleene’s and Łukasiewicz’s three-valued implications, but now assuming that the connectives are syntactically different, i.e., that Kleene’s implication comes from a signature $\Sigma _K$ with $\Sigma _K^{(2)}=\{\to ^K\}$ and $\Sigma _K^{{n}}=\emptyset $ for $n\neq 2$ , whereas Łukasiewicz’s implication comes from a disjoint signature $\Sigma _L$ with $\Sigma _L^{(2)}=\{\to ^L\}$ and $\Sigma _L^{{n}}=\emptyset $ for $n\neq 2$ . The corresponding matrices are now ${\langle \Sigma _K,\mathbb {K'}\rangle }$ with $\mathbb {K'}={\langle \{0,\frac {1}{2},1\},\{1\},\cdot _{\mathbb {K'}}\rangle }$ and ${\langle \Sigma _L,\mathbb {L'}\rangle }$ with $\mathbb {L'}={\langle \{0,\frac {1}{2},1\},\{1\},\cdot _{\mathbb {L'}}\rangle }$ defined below.

According to Theorem 12, we know that ${\langle \Sigma _K,\vartriangleright _{\mathbb {K'}}\rangle }\bullet {\langle \Sigma _L,\vartriangleright _{\mathbb {L'}}\rangle }$ is characterized by the five-valued $(\Sigma _K\cup \Sigma _L)$ -Nmatrix $\mathbb {K'}\ast \mathbb {L'}={\langle \{00,0\frac {1}{2},\frac {1}{2}0,\frac {1}{2}\frac {1}{2},11\},\{11\},\cdot _{\ast }\rangle }$ given by the truth-tables below.

Of course, this is quite different from simply considering the given three-valued interpretations of each connective. Note that since all designated entries of $\to ^K_{\mathbb {K'}}$ are also designated in $\to ^L_{\mathbb {L'}}$ one could perhaps wrongly expect to have that $p\to ^Kq\vartriangleright _{\mathbb {K'}\ast \mathbb {L'}}p\to ^Lq$ . This assertion can be shown to fail by considering, for instance, any valuation $v\in \textrm {Val}(\mathbb {K'}\ast \mathbb {L'})$ with $v(p)=0\frac {1}{2}$ and $v(q)=00$ , simply because $(0\frac {1}{2}\to ^K_{\ast }00)=\{11\}$ is necessarily designated but $(0\frac {1}{2}\to ^L_{\ast }00)=\{0\frac {1}{2},\frac {1}{2}\frac {1}{2}\}$ contains no designated value.

3.2 The single-conclusion case

The results above really illustrate the simplifying power of using multiple conclusions. Of course, things are not so simple in the single-conclusion scenario. Still, we know enough to be able to take nice conclusions from the same line of reasoning. Let us start with bivaluations.

If we analyze the proof of Proposition 8, it is simple to understand why it cannot be simply replicated in the single-conclusion case. The same line of reasoning would allows us to conclude that ${\vdash _{{\mathcal B}_1},\vdash _{{\mathcal B}_2}}\subseteq {\vdash _{{\mathcal B}_{12}^{\operatorname *{\mathrm {\textsf {mult}}}}}}$ with ${\mathcal B}^{\operatorname *{\mathrm {\textsf {mult}}}}_{12}={{\mathcal B}_1^{\Sigma _1\cup \Sigma _2}\cap {\mathcal B}_2^{\Sigma _1\cup \Sigma _2}}$ . However, in general, ${\langle \Sigma _1\cup \Sigma _2,\vdash _{{\mathcal B}_{12}^{\operatorname *{\mathrm {\textsf {mult}}}}}\rangle }$ may very well not be the least such single-conclusion logic. Given ${\langle \Sigma _1\cup \Sigma _2,\vdash _{{\mathcal B}}\rangle }$ with ${\vdash _{{\mathcal B}_1},\vdash _{{\mathcal B}_2}}\subseteq {\vdash _{{\mathcal B}}}$ , we cannot guarantee that ${\mathcal B}\subseteq {{\mathcal B}_1^{\Sigma _1\cup \Sigma _2}}$ and ${\mathcal B}\subseteq {{\mathcal B}_2^{\Sigma _1\cup \Sigma _2}}$ . Concretely, assuming that $\Gamma \not \vdash _{{\mathcal B}} A$ we still know that $\Gamma \not \vdash _{{\mathcal B}_1}^{\Sigma _1\cup \Sigma _2} A$ and $\Gamma \not \vdash _{{\mathcal B}_2}^{\Sigma _1\cup \Sigma _2} A$ . Thus, we still have bivaluations $b_k\in {\mathcal B}_k^{\Sigma _1\cup \Sigma _2}$ such that $b_k(\Gamma )\subseteq \{1\}$ and $b_k(A)=0$ , for $k\in \{1,2\}$ . However, now, despite the fact that $b_1$ and $b_2$ coincide for all formulas in $\Gamma \cup \{A\}$ , we have no way of making sure that $b_1=b_2$ .

This problem lies in a crucial difference from the multiple-conclusion case, as the same single-conclusion logic can be characterized by distinct sets of bivaluations. Given ${\mathcal B}\subseteq \textrm {BVal}(\Sigma )$ , let its meet-closure be the set ${\mathcal B}^{\cap }=\{b_X:X\subseteq {\mathcal B}\}\subseteq \textrm {BVal}(\Sigma )$ with each meet defined by $b_X(A)=1$ precisely if $b(A)=1$ for every $b\in X$ , for each $A\in L_{\Sigma }(P)$ . It is well known that ${\vdash _{{\mathcal B}}}\subseteq {\vdash _{{\mathcal B}'}}$ if and only if ${{\mathcal B}'}\subseteq {{\mathcal B}}^{\cap }$ , and thus that two sets of bivaluations characterize the same single-conclusion logic precisely when their meet-closures coincide. Indeed, every single-conclusion logic ${\langle \Sigma ,\vdash \rangle }$ is such that ${\vdash }={\vdash _{{\mathcal B}}}$ provided that ${{{\mathcal B}^{\cap }}}=\{b\in \textrm {BVal}(\Sigma ):b^{-1}(1)\textrm { is a theory of }{\langle \Sigma ,\vdash \rangle }\}$ , which is the largest set of bivaluations that characterizes ${\langle \Sigma ,\vdash \rangle }$ .

The trick is then to work with meet-closed sets of bivaluations, that is, ${\mathcal B}={\mathcal B}^{\cap }$ . In that case, it is worth noting that ${\langle \Sigma ,\vartriangleright _{{\mathcal B}}\rangle }=\operatorname *{\mathrm {\textsf {min}}}({\langle \Sigma ,\vdash _{{\mathcal B}}\rangle })$ .

Note that ${\mathcal B}^{\operatorname *{\mathrm {\textsf {sing}}}}_{12}$ is necessarily meet-closed, as it is the intersection of meet-closed sets. Hence, not only $\operatorname *{\mathrm {\textsf {min}}}({\langle \Sigma _1,\vdash _{{\mathcal B}_1}\rangle })={\langle \Sigma _1,\vartriangleright _{{\mathcal B}_1^{\cap }}\rangle }$ and $\operatorname *{\mathrm {\textsf {min}}}({\langle \Sigma _2,\vdash _{{\mathcal B}_2}\rangle })={\langle \Sigma _2,\vartriangleright _{{\mathcal B}_2^{\cap }}\rangle }$ , but also $\operatorname *{\mathrm {\textsf {min}}}({\langle \Sigma _1,\vdash _{{\mathcal B}_1}\rangle }\bullet {\langle \Sigma _2,\vdash _{{\mathcal B}_2}\rangle })={\langle \Sigma _1,\vartriangleright _{{\mathcal B}_1^{\cap }}\rangle }\bullet {\langle \Sigma _2,\vartriangleright _{{\mathcal B}_2^{\cap }}\rangle }$ .

The next abstract characterization of combined single-conclusion logics follows. Just note that given $b\in {\mathcal B}\subseteq \textrm {BVal}(\Sigma )$ closed under substitutions, it is always the case that $b^{-1}(1)$ is a theory of ${\langle \Sigma ,\vdash _{\cal B}\rangle }$ . The converse is in general not true, unless ${\mathcal B}$ is meet-closed. Concretely, if $\Gamma \subseteq L_{\Sigma }(P)$ is a theory of ${\langle \Sigma ,\vdash _{\cal B}\rangle }$ then there always exists $b\in {\mathcal B}^{\cap }$ such that $b^{-1}(1)=\Gamma $ .

Corollary 17. Let ${\langle \Sigma _1,\vdash _1\rangle }$ , ${\langle \Sigma _2,\vdash _2\rangle }$ be single-conclusion logics, and consider their combination ${\langle \Sigma _1\cup \Sigma _2,\vdash _{12}\rangle }={\langle \Sigma _1,\vdash _1\rangle }\bullet {\langle \Sigma _2,\vdash _2\rangle }$ . For every $\Gamma \cup \{A\}\subseteq L_{\Sigma _1\cup \Sigma _2}(P)$ , we have

$$ \begin{align*} \Gamma\vdash_{12}A \end{align*} $$

$$ \begin{align*} \textrm{if and only if} \end{align*} $$

$$ \begin{align*} \textrm{ for each }\Gamma\subseteq\Omega\subseteq L_{\Sigma_1\cup\Sigma_2}(P), \end{align*} $$

$$ \begin{align*} \textrm{if } {\Omega}\textrm{ is a theory of both }{\langle \Sigma_1\cup\Sigma_2,\vdash_1^{\Sigma_1\cup\Sigma_2}\rangle}\textrm{ and } {\langle \Sigma_1\cup\Sigma_2,\vdash_2^{\Sigma_1\cup\Sigma_2}\rangle}\textrm{ then }A\in\Omega. \end{align*} $$

This result captures neatly the intuition one already had from Proposition 2, amounting to the fact that $\Gamma \vdash _{12}A$ precisely when A is obtained by closing $\Gamma $ with respect to both $\vdash _1$ and $\vdash _2$ .

Turning to PNmatrices, expectedly, Theorem 12 does not immediately apply to single-conclusion logics, as shown by the next counterexample.

As before, the problem lies with the fact that, in general, the set of bivaluations induced by a PNmatrix does not have to be meet-closed. In order to cope with this possibility, we consider the following property.

If ${\langle \Sigma _0,\mathbb {M}_0\rangle }$ with $\mathbb {M}_0={\langle V_0,D_0,\cdot _{\mathbb {M}_0}\rangle }$ is a saturated PNmatrix and $\Sigma _0\subseteq \Sigma $ then it is worth noting that ${\langle \Sigma ,\mathbb {M}_0^{\Sigma }\rangle }$ is also saturated. Indeed, it suffices to observe, first, that $\Gamma $ is a consistent theory of ${\langle \Sigma ,\vartriangleright _{\mathbb {M}_0^{\Sigma }}\rangle }$ if and only if $\operatorname *{\mathrm {\textsf {skel}}}(\Gamma )$ is a consistent theory of ${\langle \Sigma _0,\vartriangleright _{\mathbb {M}_0}\rangle }$ , and second, that if $v^{-1}(D_0)=\operatorname *{\mathrm {\textsf {skel}}}(\Gamma )$ for some valuation $v\in \textrm {Val}(\mathbb {M}_0)$ then $(v\circ \operatorname *{\mathrm {\textsf {skel}}})\in \textrm {Val}(\mathbb {M}_0^{\Sigma })$ with $(v\circ \operatorname *{\mathrm {\textsf {skel}}})^{-1}(D_0)=\operatorname *{\mathrm {\textsf {skel}}}^{-1}(v^{-1}(D_0))=\operatorname *{\mathrm {\textsf {skel}}}^{-1}(\operatorname *{\mathrm {\textsf {skel}}}(\Gamma ))=\Gamma $ .

Of course, a PNmatrix that has a meet-closed set of bivaluations is necessarily saturated. It turns out, however, that saturation does not necessarily imply a meet-closed set of bivaluations, but it gets sufficiently close. Let $\mathtt { 1}:L_{\Sigma }(P)\to \{0,1\}$ be the trivial bivaluation such that $\mathtt {1}(A)=1$ for every $A\in L_{\Sigma }(P)$ . It is well known that ${\vdash _{{\mathcal B}}}={\vdash _{{\mathcal B}'}}$ for ${\mathcal B}'=\{\mathtt {1}\}\cup {\mathcal B}$ .

Under the assumption that the PNmatrices are saturated, Theorem 12 can now be adapted to the single-conclusion case too.

As a corollary of this proof it also results that ${\langle \Sigma _1\cup \Sigma _2,{\mathbb {M}_1\ast \mathbb {M}_2}\rangle }$ is a saturated PNmatrix, and thus that saturation is preserved by the strict product operation.

Example 22 (Strict product and saturation)

Recall the discussion in Example 18 about the single-conclusion combination of the $\neg $ -only and $\wedge $ -only fragments of classical logic, ${\langle \Sigma ^{\neg }_{\textsf {cls}},\vdash ^{\neg }_{\textsf {cls}}\rangle }$ and ${\langle \Sigma ^{\wedge }_{\textsf {cls}},\vdash ^{\wedge }_{\textsf {cls}}\rangle }$ .

Since the set of all classical bivaluations for the $\wedge $ -only language is meet-closed, the classical $\Sigma ^{\wedge }_{\textsf {cls}}$ -matrix $\mathbb {M}_1={\langle \{0,1\},\{1\},\cdot _{\mathbb {M}_1}\rangle }$ with , whose truth-table is shown below, is saturated.

On the other hand, as seen before, the set of all classical bivaluations for the $\neg $ -only language is not meet-closed, and the corresponding two-valued matrix is not saturated. Instead, let us consider the three-valued $\Sigma ^{\neg }_{\textsf {cls}}$ -matrix $\mathbb {M}_2={\langle \{0,\frac {1}{2},1\},\{1\},\cdot _{\mathbb {M}_2}\rangle }$ as defined below.

It turns out that $\vdash _{\mathbb {M}_2}{=}\vdash ^{\neg }_{\textsf {cls}}$ . Further, $\mathbb {M}_2$ is saturated. To see this, given a consistent theory $\Gamma $ of ${\langle \Sigma ^{\neg }_{\textsf {cls}},\vdash ^{\neg }_{\textsf {cls}}\rangle }$ , it suffices to consider the valuation $v\in \textrm {Val}(\mathbb {M}_2)$ such that

$$ \begin{align*}v(A)= \begin{cases} 1, & \mbox{ if }\;A\in\Gamma, \\ 0, & \mbox{ if }\;\neg A\in\Gamma,\\ \frac{1}{2}, & \mbox{ if }\;A,\neg A\notin\Gamma. \end{cases} \end{align*} $$

By the consistency of $\Gamma $ we know that v is well defined, because A and $\neg A$ cannot both be in $\Gamma $ due to rule $\frac {\;\;p\quad \neg p\;\;}{q}$ . Additionally, rules $\frac {p}{\;\;\neg \neg p\;\;}$ and $\frac {\;\;\neg \neg p\;\;}{p}$ guarantee that v is indeed a valuation of $\mathbb {M}_2$ .

Given the saturation of the two matrices, according to Theorem 21, the resulting combined logic ${\langle \Sigma ^{\neg }_{\textsf {cls}},\vdash ^{\neg }_{\textsf {cls}}\rangle }\bullet {\langle \Sigma ^{\wedge }_{\textsf {cls}},\vdash ^{\wedge }_{\textsf {cls}}\rangle }{=}{\langle \Sigma ^{\neg ,\wedge }_{\textsf {cls}},\vdash \rangle }$ is characterized by the strict product $\mathbb {M}_1\ast \mathbb {M}_2$ . By Definition 10 the resulting truth-values are $00,0\frac {1}{2},11$ (where, again, we are simplifying each pair $(x,y)$ to simply $xy$ ). Renaming these values to simply $0,\frac {1}{2},1$ , respectively, we have that $\mathbb {M}_1\ast \mathbb {M}_2={\langle \{0,\frac {1}{2},1\},\{1\},\cdot _{\ast }\rangle }$ is defined by the truth-tables below.

A valuation $v\in \textrm {Val}(\mathbb {M}_1\ast \mathbb {M}_2)$ such that $v(p)=0$ , $v(\neg p)=1$ and $v(p\wedge p)=v(\neg (p\wedge p))=\frac {1}{2}$ shows that $\neg p\not \vdash \neg (p\wedge p)$ .

Of course, this implies that putting together calculi for each of the connectives is not enough to fully characterize the way they interact in classical logic, as can be visually confirmed from the rules in Example 3.

As this point, we should question the scope of applicability of Theorem 21, and how often we can expect to find naturally saturated PNmatrices as in the example above. What should we do when given PNmatrices that are not saturated? Fortunately, there is a simple way of transforming a PNmatrix into a saturated PNmatrix both characterizing the same single-conclusion logic.Footnote ³

For each $k\in {\mathbb N}$ we use $\pi _k:V^{\omega }\to V$ to denote the obvious projection function, i.e., $\pi _k({\langle x_i\rangle }_{i\in {\mathbb N}})=x_k$ . Clearly, we have that $v\in \textrm {Val}(\mathbb {M}^{\omega })$ if and only if $(\pi _k\circ v)\in \textrm {Val}(\mathbb {M})$ for every $k\in {\mathbb N}$ .

Proof We first show that ${\vdash _{\mathbb {M}}}={\vdash _{\mathbb {M}^{\omega }}}$ .

Suppose that $\Gamma \vdash _{\mathbb {M}} A$ , and let $v\in \textrm {Val}(\mathbb {M}^{\omega })$ be such that $v(\Gamma )\subseteq D^{\omega }$ . For every $k\in {\mathbb N}$ , this means that $(\pi _k\circ v)(\Gamma )\subseteq D$ and thus that $(\pi _k\circ v)(A)\in D$ . We conclude that $v(A)\in D^{\omega }$ and so $\Gamma \vdash _{\mathbb {M}^{\omega }} A$ .

Suppose now that $\Gamma \vdash _{\mathbb {M}^{\omega }} A$ , and let $v\in \textrm {Val}(\mathbb {M})$ be such that $v(\Gamma )\subseteq D$ . Easily, $v^{\omega }$ defined by $\pi _k(v^{\omega }(A))=v(A)$ for every $k\in {\mathbb N}$ is such that $v^{\omega }\in \textrm {Val}(\mathbb {M}^{\omega })$ , and $v^{\omega }(\Gamma )\subseteq D^{\omega }$ . Therefore, we have that $v^{\omega }(A)\in D^{\omega }$ and therefore, for any $k\in {\mathbb N}$ , $\pi _k(v^{\omega }(A))=v(A)\in D$ . We conclude that $\Gamma \vdash _{\mathbb {M}} A$ .

To show that ${\langle \Sigma ,\mathbb {M}^{\omega }\rangle }$ is saturated, let $\Gamma $ be a consistent theory of ${\langle \Sigma ,\vdash _{\mathbb {M}}\rangle }$ , and fix $A\notin \Gamma $ . For each formula $B\notin \Gamma $ we know that there exists a valuation $v_B\in \textrm {Val}(\mathbb {M})$ such that $v_B(\Gamma )\subseteq D$ and $v_B(B)\notin D$ . Fix an enumeration $\eta :{\mathbb N}\to L_{\Sigma }(P)$ and define, for each $k\in {\mathbb N}$ , the valuation $v_k\in \textrm {Val}(\mathbb {M})$ such that

$$ \begin{align*}v_k=\left\{\begin{array}{ll} v_{\eta(k),} & \textrm{if }\eta(k)\notin\Gamma,\\ v_A, & \textrm{if }\eta(k)\in\Gamma. \end{array} \right.\end{align*} $$

Let $v\in \textrm {Val}(\mathbb {M}^{\omega })$ be such that $(\pi _k\circ v)=v_k$ for every $k\in {\mathbb N}$ . We have that $v(\Gamma )\subseteq D^{\omega }$ because $v_k(\Gamma )\subseteq D$ for every $k\in {\mathbb N}$ , and for every $B\notin \Gamma $ , we have that $v(B)\notin D^{\omega }$ because with $k=\eta ^{-1}(B)$ we have $v_k(B)=v_B(B)\notin D$ . We conclude that ${\langle \Sigma ,\mathbb {M}^{\omega }\rangle }$ is saturated.Footnote ⁴

The following result follows from Theorem 21 and Lemma 24.

Though still usable, this result does not provide us with a finite-valued semantics for the combined logic, even if departing from finite-valued PNmatrices. Indeed, in the relevant cases, a $\omega $ -power PNmatrix is always non-countable, the exceptions being $\omega $ -powers of PNmatrices with at most one truth-value, which are actually saturated to begin with. Note also that the situation is not unexpected, as we know that some combinations cannot be endowed with finite-valued semantics [Reference Marcelino and Caleiro55], and it is playing the role of meet-closure in the case of bivaluations. Still, there are cases when saturation is not necessary (we will see a relevant example of this phenomenon in Section 5.1), or when saturation can be achieved by a finite power of the given PNmatrix. We present some examples below, and further discuss this question in the conclusion of the paper.

Example 26 (Three-valued implications of Kleene and Łukasiewicz)

Recall Example 14, where we discussed the combination of the three-valued implications of Kleene and Łukasiewicz in the multiple-conclusion setting, with shared implication, and we concluded that the resulting logic coincided with the multiple-conclusion version of the implication-fragment of classical logic.

Now, we shall see that, incidentally, the corresponding single-conclusion combination also coincides with classical implication, albeit for distinct reasons. For easier readability, we recall here the signature $\Sigma $ with $\Sigma ^{(2)}=\{\to \}$ and $\Sigma ^{{n}}=\emptyset $ for $n\neq 2$ , and the three-valued implication matrices of Kleene and Łukasiewicz, respectively, $\mathbb {K}={\langle \{0,\frac {1}{2},1\},\{1\},\cdot _{\mathbb {K}}\rangle }$ and $\mathbb {L}={\langle \{0,\frac {1}{2},1\},\{1\},\cdot _{\mathbb {L}}\rangle }$ , defined below.

Concerning the combined logic ${\langle \Sigma ,\vdash \rangle }={\langle \Sigma ,\vdash _{\mathbb {K}}\rangle }\bullet {\langle \Sigma ,\vdash _{\mathbb {L}}\rangle }$ , Theorem 21 cannot be applied directly as the matrices are not saturated, which renders the strict product obtained in Example 14 useless as our envisaged semantics for the combined logic.

Concerning $\mathbb {K}$ , let $\Gamma =\{p\to p\}^{\vdash _{\mathbb {K}}}$ . The theory is consistent, as in particular, we have $p\to p \not \vdash _{\mathbb {K}} p$ (as can be confirmed by any valuation $v\in \textrm {Val}(\mathbb {K})$ with $v(p)=0$ ) and also $p\to p \not \vdash _{\mathbb {K}} p\to q$ (as witnessed by any valuation $v\in \textrm {Val}(\mathbb {K})$ with $v(p)=1$ and $v(q)=0$ ). Therefore, $p,p\to q\notin \Gamma $ . However, there is no valuation $v\in \textrm {Val}(\mathbb {K})$ such that $\Gamma =v^{-1}(\{1\})$ , simply because if $v(p\to p)=1$ and $v(p)\neq 1$ then by just inspecting the truth-table we conclude that $v(p)=0$ and $v(p\to q)=1$ .

Concerning $\mathbb {L}$ , consider $\Gamma =\emptyset ^{\vdash _{\mathbb {L}}}$ . The theory is consistent, as in particular, we have $\emptyset \not \vdash _{\mathbb {L}} p$ (as can be confirmed by any valuation $v\in \textrm {Val}(\mathbb {L})$ with $v(p)=0$ ), $\emptyset \not \vdash _{\mathbb {L}} p\to q$ (as witnessed by any valuation $v\in \textrm {Val}(\mathbb {L})$ with $v(p)=1$ and $v(q)=0$ ), and also $\emptyset \not \vdash _{\mathbb {L}} q\to r$ (as witnessed by any valuation $v\in \textrm {Val}(\mathbb {L})$ with $v(q)=1$ and $v(r)=0$ ). Therefore, $p,p\to q,q\to r \notin \Gamma $ . However, there is no valuation $v\in \textrm {Val}(\mathbb {L})$ such that $\Gamma =v^{-1}(\{1\})$ , simply because if $v(p),v(p\to q)\neq 1$ then by just inspecting the truth-table we conclude that $v(p)=\frac {1}{2}$ , $v(q)=0$ and $v(q\to r)=1$ .

We must therefore consider the $\omega $ -power of each of the matrices. Note that in both cases, the resulting truth-values are denumerable tuples ${\langle x_i\rangle }_{i\in {\mathbb N}}$ with each $x_i\in \{0,\frac {1}{2},1\}$ . For simplicity, we will rename each ${\langle x_i\rangle }_{i\in {\mathbb N}}$ as the pair of sets ${\langle X_0,X_1\rangle }$ with $X_0=\{i\in {\mathbb N}:x_i=0\}$ and $X_1=\{i\in {\mathbb N}:x_i=1\}$ . Of course, then, $X_{\frac {1}{2}}=\{i\in {\mathbb N}:x_i=\frac {1}{2}\}={\mathbb N}\setminus (X_0\cup X_1)$ . The resulting set of truth-values corresponds to $V^{\omega }=\{{\langle X_0,X_1\rangle }:X_0,X_1\subseteq {\mathbb N}, X_0\cap X_1=\emptyset \}$ . As both matrices have $1$ as their only designated value, we also get in both cases that $D^{\omega }=\{{\langle \emptyset ,{\mathbb N}\rangle }\}$ . The resulting matrices are thus $\mathbb {K}^{\omega }={\langle V^{\omega },D^{\omega },\cdot _{\mathbb {K}^{\omega }}\rangle }$ and $\mathbb {L}^{\omega }={\langle V^{\omega },D^{\omega },\cdot _{\mathbb {L}^{\omega }}\rangle }$ , defined according to the tables below.

According to Theorem 25, we know that ${\langle \Sigma ,\vdash _{\mathbb {K}}\rangle }\bullet {\langle \Sigma ,\vdash _{\mathbb {L}}\rangle }$ is characterized by the infinite $\Sigma $ -Pmatrix $\mathbb {K}^{\omega }\ast \mathbb {L}^{\omega }$ . Representing pairs of pairs as four-tuples we get the set of truth-values $V_{\ast }=\{{\langle X_0,X_1,Y_0,Y_1\rangle }:X_0,X_1,Y_0,Y_1\subseteq {\mathbb N}, X_0\cap X_1=Y_0\cap Y_1=\emptyset \textrm {, and }X_1={\mathbb N}\textrm { iff }Y_1={\mathbb N}\}$ , and designated values $D_{\ast }=\{{\langle \emptyset ,{\mathbb N},\emptyset ,{\mathbb N}\rangle }\}$ . The resulting strict product is then $\mathbb {K}^{\omega }\ast \mathbb {L}^{\omega }={\langle V_{\ast },D_{\ast },\cdot _{\ast }\rangle }$ as defined by the table below.

This semantics has a non-trivial look, but it turns out that one can still draw valuable conclusions from it. Due to the partiality of $\mathbb {K}^{\omega }\ast \mathbb {L}^{\omega }$ it is worth noting that the Pmatrix has a lot of spurious values. For a truth-value ${\langle X_0,X_1,Y_0,Y_1\rangle }$ , if ${\langle X_0,X_1,Y_0,Y_1\rangle }\to _{\ast }{\langle X_0,X_1,Y_0,Y_1\rangle }$ is non-empty then it must contain a single element ${\langle X_1\cap X_0,X_0\cup X_1,Y_1\cap Y_0,Y_0\cup Y_1\cup Y_{\frac {1}{2}}\rangle }={\langle \emptyset ,X_0\cup X_1,\emptyset ,{\mathbb N}\rangle }={\langle \emptyset ,{\mathbb N},\emptyset ,{\mathbb N}\rangle }$ . Of course, this happens only when $X_{\frac {1}{2}}=\emptyset $ , or otherwise ${\langle X_0,X_1,Y_0,Y_1\rangle }$ is spurious.

This observation implies that if $v\in \textrm {Val}(\mathbb {K}^{\omega }\ast \mathbb {L}^{\omega })$ then $\pi _1\circ v\in \textrm {Val}(\mathbb {K}^{\omega })$ never uses the $\frac {1}{2}$ value of matrix $\mathbb {K}$ . As $\mathbb {K}$ behaves classically for the $0,1$ values, we conclude that all bivaluations in $\textrm {BVal}(\mathbb {K}^{\omega }\ast \mathbb {L}^{\omega })$ are classical. On the other hand, we know from Lemmas 11, 20, and 24 that $\textrm {BVal}(\mathbb {K}^{\omega }\ast \mathbb {L}^{\omega })=\textrm {BVal}(\mathbb {K}^{\omega })\cap \textrm {BVal}(\mathbb {L}^{\omega })= \textrm {BVal}(\mathbb {K})^{\cap }\cap \textrm {BVal}(\mathbb {L})^{\cap }$ , because obviously $\mathtt { 1}\in \textrm {BVal}(\mathbb {K}),\textrm {BVal}(\mathbb {L})$ . Since not just $\mathbb {K}$ but also $\mathbb {L}$ behaves classically for the $0,1$ values, we conclude that all classical bivaluations are in $\textrm {BVal}(\mathbb {K}^{\omega }\ast \mathbb {L}^{\omega })$ . Thus, we have that ${\langle \Sigma ,\vdash _{\mathbb {K}}\rangle }\bullet {\langle \Sigma ,\vdash _{\mathbb {L}}\rangle }={\langle \Sigma ,\vdash _{\mathbb {K}^{\omega }\ast \mathbb {L}^{\omega }}\rangle }={\langle \Sigma ^{\to }_{\textsf {cls}},\vdash ^{\to }_{\textsf {cls}}\rangle }$ is precisely the implication fragment of classical logic.

Again, we can confirm this fact by putting together calculi for the logics, according to Proposition 2. Even without listing the rules, and since it is well known that $\vdash _{\mathbb {K}},\vdash _{\mathbb {L}}{\subseteq } \vdash ^{\to }_{\textsf {cls}}$ , it suffices to check that all rules of the calculus for $\vdash ^{\to }_{\textsf {cls}}$ (see Example 3) obtain when we join them. The rule of modus ponens is unproblematic, as we have both $p,p\to q\vartriangleright _{\mathbb {K}}q$ and $p,p\to q\vartriangleright _{\mathbb {L}}q$ . Concerning the classical axioms $p\to (q\to p),(p\to (q\to r))\to ((p\to q)\to (p\to r)),(((p\to q)\to p)\to p)$ , or actually any other classical tautology A, note that $\{p\to p:p\in \operatorname *{\mathrm {\textsf {var}}}(A)\}\vdash _{\mathbb {K}}A$ , simply because a valuation $v\in \textrm {Val}(\mathbb {K})$ such that $v(p\to p)=1$ must be classical, as $v(p)\neq \frac {1}{2}$ . On the side of Łukasiewicz, it is clear that $\emptyset \vdash _{\mathbb {K}}B\to B$ for any formula B. Hence, in the combined logic, we know that $\emptyset \vdash p\to p$ for each $p\in \operatorname *{\mathrm {\textsf {var}}}(A)$ , and also that $\{p\to p:p\in \operatorname *{\mathrm {\textsf {var}}}(A)\}\vdash A$ which implies that $\emptyset \vdash A$ for any classical tautology A.

One must, of course, look again at the combination of fragments of classical logic, now in the single-conclusion setting.

Example 27 (Combining fragments of classical logic)

Recall Example 3, as well as the multiple-conclusion scenario that we have explored in Example 13. We will now see how much challenging and interesting it is to combine fragments of classical logic in the single-conclusion setting, by means of four distinct cases.

(1) Let us first consider the combination of the fragments of classical logic corresponding to $\Sigma ^{\wedge }_{\textsf {cls}}$ and $\Sigma ^{\top }_{\textsf {cls}}$ . It is easy to see that the corresponding two-valued classical matrices are both saturated. Hence, the combined logic ${\langle \Sigma ^{\wedge }_{\textsf {cls}},\vdash ^{\wedge }_{\textsf {cls}}\rangle }\bullet {\langle \Sigma ^{\top }_{\textsf {cls}},\vdash ^{\top }_{\textsf {cls}}\rangle }$ is directly characterized by the corresponding strict product, which coincides with the two-valued classical matrix for the fragment $\Sigma ^{\wedge ,\top }_{\textsf {cls}}$ . We conclude thus, that ${\langle \Sigma ^{\wedge }_{\textsf {cls}},\vdash ^{\wedge }_{\textsf {cls}}\rangle }\bullet {\langle \Sigma ^{\top }_{\textsf {cls}},\vdash ^{\top }_{\textsf {cls}}\rangle }={\langle \Sigma ^{\wedge ,\top }_{\textsf {cls}},\vdash ^{\wedge ,\top }_{\textsf {cls}}\rangle }$ , which is compatible with our knowledge that joining single-conclusion calculi for $\vdash ^{\wedge }_{\textsf {cls}}$ and $\vdash ^{\top }_{\textsf {cls}}$ yields a calculus for $\vdash ^{\wedge ,\top }_{\textsf {cls}}$ .

(2) Now, let us reanalyze the combination of ${\langle \Sigma ^{\neg }_{\textsf {cls}},\vdash ^{\neg }_{\textsf {cls}}\rangle }$ and ${\langle \Sigma ^{\wedge }_{\textsf {cls}},\vdash ^{\wedge }_{\textsf {cls}}\rangle }$ . We already know from Examples 18 and 22 that the combination ${\langle \Sigma ^{\neg }_{\textsf {cls}},\vdash ^{\neg }_{\textsf {cls}}\rangle }\bullet {\langle \Sigma ^{\wedge }_{\textsf {cls}},\vdash ^{\wedge }_{\textsf {cls}}\rangle }$ is weaker than $\vdash ^{\neg ,\wedge }_{\textsf {cls}}$ . However, since the two-valued classical matrix for negation is not saturated, we have instead considered an adequate three-valued saturated matrix. Of course, we did not need to know that such a matrix existed, and instead we could have blindly obtained the $\omega $ -power of the two-valued classical matrix for negation, and then obtained its strict product with the saturated two-valued classical matrix for negation. The semantics thus obtained would be less amiable, but still characterizes the combination. Alternatively, we could have noted that the four-valued $2$ -power of the matrix of negation would already be saturated (the three-valued matrix used before is a simplification of it).

(3) As a last interesting example of disjoint combination let us consider the fragments ${\langle \Sigma ^{\wedge }_{\textsf {cls}},\vdash ^{\wedge }_{\textsf {cls}}\rangle }$ and ${\langle \Sigma ^{\vee }_{\textsf {cls}},\vdash ^{\vee }_{\textsf {cls}}\rangle }$ . We already know from [Reference Caleiro, Marcelino and Marcos26] that the combination ${\langle \Sigma ^{\wedge ,\vee }_{\textsf {cls}},\vdash \rangle }={\langle \Sigma ^{\wedge }_{\textsf {cls}},\vdash ^{\wedge }_{\textsf {cls}}\rangle }\bullet {\langle \Sigma ^{\vee }_{\textsf {cls}},\vdash ^{\vee }_{\textsf {cls}}\rangle }$ is weaker than $\vdash ^{\wedge ,\vee }_{\textsf {cls}}$ . Indeed, we have that $p\vee (p\wedge p)\not \vdash p$ , as can be confirmed by any valuation with $\emptyset \subsetneq v(p)\subsetneq {\mathbb N}$ and $v(p\wedge p)={\mathbb N}\setminus v(p)\neq {\mathbb N}$ , which then implies that $v(p\vee (p\wedge p))={\mathbb N}$ , on the Nmatrix resulting from the strict product of the two-valued classical matrix for conjunction and the $\omega $ -power of the two-valued classical matrix for disjunction, corresponding (after renaming) to $\mathbb {M}_{\ast }={\langle \wp ({\mathbb N}),\{{\mathbb N}\},\cdot _{\ast }\rangle }$ as defined by the tables below.

Of course a simpler semantics would be desirable, but we know that the two-valued classical matrix for disjunction is not saturated. For instance, note that $\{p\vee q\}\not \vdash ^{\vee }_{\textsf {cls}}p$ and $\{p\vee q\}\not \vdash ^{\vee }_{\textsf {cls}}q$ but any valuation v of the two-valued matrix that sets $v(p\vee q)=1$ necessarily must have $v(p)=1$ or $v(q)=1$ .

(4) Finally, we shall look at a non-disjoint example, the combination of the fragments corresponding to $\Sigma ^{\neg ,\to }_{\textsf {cls}}$ and $\Sigma ^{\vee ,\to }_{\textsf {cls}}$ . It seems clear, from the calculus for $\vdash _{\textsf {cls}}$ shown in Example 3, that all rules involving negation or disjunction only additionally use the shared connective of implication. We may therefore conjecture that ${\langle \Sigma ^{\neg ,\to }_{\textsf {cls}},\vdash ^{\neg ,\to }_{\textsf {cls}}\rangle }\bullet {\langle \Sigma ^{\vee ,\to }_{\textsf {cls}},\vdash ^{\vee ,\to }_{\textsf {cls}}\rangle }={\langle \Sigma ^{\neg ,\vee ,\to }_{\textsf {cls}},\vdash ^{\neg ,\vee ,\to }_{\textsf {cls}}\rangle }$ . To confirm this, we first note that none of the two-valued classical matrices for the fragments is saturated. This is simply because both include implication, $\emptyset \not \vdash _{\textsf {cls}} p$ and $\emptyset \not \vdash _{\textsf {cls}} p\to q$ but any classical valuation will have $v(p)=1$ or $v(p\to q)=1$ . Thus, we need to consider the strict product of the $\omega $ -power of each of the matrices, which results (after renaming) in the PNmatrix $\mathbb {M}_{\ast }={\langle \wp ({\mathbb N})\times \wp ({\mathbb N}),\{({\mathbb N},{\mathbb N})\},\cdot _{\ast }\rangle }$ as defined by the tables below, where we use $\overline {X}={\mathbb N}\setminus X$ .

All classical bivaluations can be simply obtained in $\mathbb {M}_*$ by taking only the two values ${\langle \emptyset ,\emptyset \rangle }$ and ${\langle {\mathbb N},{\mathbb N}\rangle }$ . Seeing that all valuations of $\mathbb {M}_{\ast }$ are classical (i.e., they respect the operations in ) is slightly harder. Let $v\in \textrm {Val}(\mathbb {M}_{\ast })$ .

We have $v(p\to p)={\langle {\mathbb N},{\mathbb N}\rangle }$ and hence $v(\neg (p\to p))={\langle \emptyset ,U_0\rangle }$ for some $U_0\subsetneq {\mathbb N}$ . Consequently, for any formula A, if $v(A)={\langle Z,W\rangle }$ then $v(\neg (p\to p)\to A)\in ({\langle \emptyset ,U_0\rangle }\to _{\ast }{\langle Z,W\rangle })$ and thus $v(\neg (p\to p)\to A)={\langle \overline {\emptyset }\cup Z,\overline {U_0}\cup W\rangle }={\langle {\mathbb N}\cup Z,\overline {U_0}\cup W\rangle }={\langle {\mathbb N},{\mathbb N}\rangle }$ , which implies $\overline {U_0}\cup W={\mathbb N}$ , or equivalently $U_0\subseteq W$ . Further, $v(\neg A)={\langle \overline {Z},T\rangle }$ for some T such that $U_0\subseteq T\subseteq {\mathbb N}$ . We can see that $v(A\to (\neg A\to \neg (p\to p)))= {\langle \overline {Z}\cup Z\cup \emptyset ,\overline {W}\cup \overline {T}\cup U_0\rangle }={\langle {\mathbb N},{\mathbb N}\rangle }$ , which means that $\overline {W}\cup \overline {T}\cup U_0={\mathbb N}$ and thus that $W\cap T=U_0$ . Also, we can see that $v((\neg A\to A)\to A)= {\langle \overline {Z}\cup Z,(T\cap \overline {W})\cup W\rangle }={\langle {\mathbb N},{\mathbb N}\rangle }$ , which means that $(T\cap \overline {W})\cup W={\mathbb N}$ and thus that $\overline {W}\subseteq T$ . From these observations, we conclude that $T=\overline {W}\cup U_0$ .

Let $f:{\mathbb N}\to \overline {U_0}$ be any surjective function. We claim that the function defined by $v'(B)=f^{-1}(\pi _2(v(B))\setminus U_0)$ is a valuation over (on the relevant connectives), which is compatible with v, as whenever $U_0\subseteq X$ we have $f^{-1}(X\setminus U_0)={\mathbb N}$ if and only if $X={\mathbb N}$ . It is straightforward to check that $v'(B\vee C)=v'(B)\cup v'(C)$ and $v'(B\to C)=\overline {v'(B)}\cup v'(C)$ , and also easy to see that $v'(\neg B)=\overline {v'(B)}$ using the observations in the previous paragraph.

4.1 PNmatrices and rexpansions

In order to explore the relationships among PNmatrices, let us consider a suitable notion of homomorphism. If $\Sigma _0\subseteq \Sigma $ , ${\langle \Sigma _0,\mathbb {M}_0\rangle }$ and ${\langle \Sigma ,\mathbb {M}\rangle }$ are PNmatrices, with $\mathbb {M}_0={\langle V_0,D_0,\cdot _{\mathbb {M}_0}\rangle }$ and $\mathbb {M}={\langle V,D,\cdot _{\mathbb {M}}\rangle }$ , a strict homomorphism $h:{\langle \Sigma ,\mathbb {M}\rangle }\to {\langle \Sigma _0,\mathbb {M}_0\rangle }$ is a function $h:V\to V_0$ such that $h^{-1}(D_0)=D$ , and for every $n\in {\mathbb N}_0$ , $c\in \Sigma _0^{(n)}$ , and $x_1,\dots x_n\in V$ , $h(c_{\mathbb {M}}(x_1,\dots ,x_n))\subseteq c_{\mathbb {M}_0}(h(x_1),\dots ,h(x_n))$ . If $v\in \textrm {Val}(\mathbb {M})$ then $(h\circ v)\in \textrm {Val}({\mathbb {M}_0^{\Sigma }})$ . Further, the strictness condition $h^{-1}(D_0)=D$ implies that $v(A)$ and $(h\circ v)(A)$ are compatible for every formula $A\in L_{\Sigma }(P)$ . Consequently, we have that $\textrm {BVal}(\mathbb {M})\subseteq \textrm {BVal}(\mathbb {M}_0^{\Sigma })$ , and therefore ${\propto _{\mathbb {M}_0}}\subseteq {\propto _{\mathbb {M}}}$ both in the single and the multiple-conclusion cases. PNmatrices with strict homomorphisms constitute a category $\mathbf {PNMatr}$ .

Expectedly, the strict product of PNmatrices as introduced in Definition 10 enjoys a universal characterization, whose proof is straightforward.

It goes without saying that the relationships between valuations in the PNmatrices ${\langle \Sigma _1,\mathbb {M}_1\rangle },{\langle \Sigma _2,\mathbb {M}_2\rangle }$ and valuations in ${\langle \Sigma _1\cup \Sigma _2,\mathbb {M}_1\ast \mathbb {M}_2\rangle }$ mediated by the projection homomorphisms that were presented in Section 3.1 are simple consequences of the universal property enjoyed by products in a category.

A dual construction is also possible. The key idea is that one can take crucial advantage of partiality to blend together PNmatrices. Let $\mathcal {M}=\{{\langle \Sigma ,\mathbb {M}_i\rangle }:i\in I\}$ be a set of PNmatrices, each $\mathbb {M}_i={\langle V_i,D_i,\cdot _{\mathbb {M}_i}\rangle }$ . The sum of $\mathcal {M}$ is the PNmatrix $(\Sigma ,\oplus \mathcal {M})$ where $\oplus \mathcal {M}={\langle V,D,\cdot _{\oplus }\rangle }$ is defined by $V=\bigcup _{i\in I} (\{i\}\times V_i)$ , $D=\bigcup _{i\in I} (\{i\}\times D_i)$ , and for $n\in {\mathbb N}_0$ and $c\in \Sigma ^{(n)}$ , $c_{\oplus }((i_1,x_1),\dots ,(i_n,x_n))=\bigcup _{\stackrel {i\in I : i=i_1=\dots =i_n}{}}(\{i\}\times c_{\mathbb {M}_i}(x_1,\dots ,x_n))$ .

It is clear that $(\Sigma ,\oplus \mathcal {M})$ is a coproduct of $\mathcal {M}$ in $\mathbf {PNMatr}$ , with inclusion homomorphisms $\iota _i:{\langle \Sigma ,\mathbb {M}_i\rangle }\to {\langle \Sigma ,\oplus \mathcal {M}\rangle }$ defined, for each $i\in I$ and each $x\in V_i$ , by $\iota _i(x)=(i,x)$ . Therefore, we have $\bigcup _{i\in I}\textrm {BVal}(\mathbb {M}_i)\subseteq \textrm {BVal}(\oplus \mathcal {M})$ . Perhaps surprisingly, however, it may happen that $\textrm {BVal}(\oplus \mathcal {M})\neq \bigcup _{i\in I}\textrm {BVal}(\mathbb {M}_i)$ .