Abstract
For one of the most well-known many-valued logics FDE, there are several semantics, including the star semantics by Richard Routley and Valerie Routley, the two-valued relational semantics by Michael Dunn and the four-valued semantics by Nuel Belnap. The last semantics inspired Yaroslav Shramko and Heinrich Wansing to introduce the trilattice SIXTEEN\(_3\). In this article, we offer two alternative semantical presentations for SIXTEEN\(_3\), by applying the Routleys’ semantics and the Dunn semantics. Based on our new semantics, we discuss related systems with less truth values, as well as the relation to FDE-based modal logics.
The work reported in this paper started during DS’s visit to Japan which was supported by JSPS KAKENHI Grant Number JP18K12183 granted to HO. HO was supported by a Sofja Kovalevskaja Award of the Alexander von Humboldt-Foundation, funded by the German Ministry for Education and Research. The work of DS has been carried out as part of the research project “FDE-based modal logics”, supported by the Deutsche Forschungsgemeinschaft, DFG, grant WA 936/13-1. We would like to thank Sergei Odintsov, Yaroslav Shramko, Heinrich Wansing, Zach Weber and the referees for helpful discussions and/or comments on an earlier draft.
Access provided by Autonomous University of Puebla. Download conference paper PDF
Similar content being viewed by others
Keywords
1 Introduction
1.1 Background (I): From Belnap to Shramko-Wansing
Ever since Jan Łukasiewicz and Emil Post started to explore more than two truth values independently in the 1920s, infinitely many kinds of many-valued logics have been introduced. The one that plays the crucial role in this paper is the four-valued logic of Belnap and Dunn, also known as FDE.
The four-valued truth tables for FDE were known since the 1950s, when Timothy Smiley pointed this out to Nuel Belnap, but the four values did not have an intuitive reading. It was Dunn who explicitly connected these four values to the classical truth values, true and false (see [6]). This then inspired Belnap to write the two influential papers [2, 3]. In particular, the four values are now seen as the power set \(\mathcal {P}(\{1,0\})\) of the set of the classical truth-values \(\{1,0\}\), and receive the following intuitive reading:
The above reading also inspired another perspective on the four-values, namely the bilattice of the power set of \(\{1,0\}\) (cf. [1, 8]). In particular, two orders measure the degree of truth and the amount of information.
In [21,22,23] Shramko and Wansing then took this idea of Belnap even a step further. By arguing that the computer metaphor of Belnap can be transformed into considering a computer network communicating with each other about propositions, Shramko and Wansing developed the idea that such computers should be able to handle information that can be, for example, overcomplete and at the same time just true or false. In this way, they introduced SIXTEEN\(_3\) which takes the power set of \(\mathcal {P}(\{1,0\})\) to generate a “useful sixteen-valued logic” which is meant to represent “how a computer network should think”. This is thus a generalization of Belnap’s “useful four-valued logic” which is meant to represent “how a computer should think”. Moreover, SIXTEEN\(_3\) is now a trilattice, rather than a bilattice, where an independent degree of falsity can be defined as an additional order.
Due to the interesting motivation, SIXTEEN\(_3\) has now collected a lot of the attention it deserves. Just to mention some relevant work, Odintsov in [12], added some new algebraic insights and marked an important step on the problem of axiomatization. Heinrich Wansing considers sequent calculi related to SIXTEEN\(_3\) in [25], and an analytic tableaux calculus is devised by Muskens and Wintein in [10]. Finally, the property of interpolation is studied again by Muskens and Wintein in [11].
1.2 Background (II): Routley and Dunn Semantics for FDE
As it is well-known, the four-valued interpretation of FDE is not the only semantics.Footnote 1 For the purpose of this paper, we focus on the following two: Routleys’ star semantics and Dunn’s relational semantics. Let us briefly highlight the key ideas of the two semantics which are both two-valued semantics.Footnote 2
Routleys’ star semantics, devised by Routley and Routley in [20], is a two-valued world semantics, as in the well-known Kripke semantics, but includes the so-called star operation which is an involutive operation on worlds. This star operation is used to interpret the negation. For conjunction and disjunction, it remains to be completely classical.
Dunn’s relational semantics (or Dunn semantics in short) is yet another two-valued semantics which is also free of worlds. The crucial idea is to use a relation rather than a function in interpreting the language. In particular, formulas may be related to both true and false, or neither true nor false. As a consequence, truth and falsity conditions are both necessary, though in the case of FDE, those conditions remain completely classical.
Both approaches have virtues of their own. On the one hand, Routleys’ semantics is rather successful when applied to relevant logics. On the other hand, Dunn gives wonderful insights by giving an intuitive reading of truth values, as we already observed above through Belnap’s semantics. In any case, the important thing here is that there are interesting two-valued semantics for FDE.
1.3 Aim
Based on these backgrounds, the motivation for this paper is rather simple: can we also devise two-valued semantics for logics related to SIXTEEN\(_3\)? To the best of our knowledge, this seems to be not addressed yet in the literature. Therefore, we aim at marking the first step towards filling that gap.
On a broader scope, reducing the number of truth-values of a given system can be traced back to Suszko (cf. [24]), who believed that any multiplication of truth-values is a “mad idea”. We do not wish to conflate our approach of reducing the number of truth-values with Suszko’s critique about many-valued logics in general, but rather during the course of this article we will present an alternative strategy to obtain that goal.Footnote 3
The paper is organized as follows. In Sects. 2 and 3 we will briefly recapitulate the basics of FDE and SIXTEEN\(_3\). These are followed by Sects. 4 and 5 in which we introduce the new two-valued semantics for SIXTEEN\(_3\). Based on the new semantics, we will reflect upon the implications in Sect. 6. Finally, we conclude the paper in Sect. 7 by summarizing our main observations and discuss some possible topics for further research.
2 Two-Valued Semantics for FDE
Our propositional languages consist of a finite set \(\mathsf {C}\) of propositional connectives and a countable set \(\mathsf {Prop}\) of propositional variables which we refer to as \(\mathcal {L}_\mathsf {C}\). Furthermore, we denote by \(\mathsf {Form}_\mathsf {C}\) the set of formulas defined as usual in \(\mathcal {L}_\mathsf {C}\). In this paper, we always assume that \(\{ {{\sim }}, \wedge , \vee \} \subseteq {\mathsf C}\) and just include the propositional connective(s) not from \(\{ {{\sim }}, \wedge , \vee \}\) in the subscript of \(\mathcal {L}_\mathsf {C}\). Moreover, we denote a formula of \(\mathcal {L}_\mathsf {C}\) by A, B, C, etc. and a set of formulas of \(\mathcal {L}_{\mathsf {C}}\) by \(\varGamma \), \(\varDelta \), \(\varSigma \), etc.
First, we review Routleys’ star semantics.
Definition 1
A Routley interpretation for \(\mathcal {L}\) is a structure \(\langle W, *, v \rangle \) where \(W \ne \emptyset \) is a set of worlds, \(*: W\longrightarrow W\) is a function with \(w^{**}=w\), and \(v: W\times \mathsf {Prop}\longrightarrow \{ 0, 1 \}\). The function v is extended to \(I: W\times \mathsf {Form}\longrightarrow \{ 0, 1 \}\) as follows:
Definition 2
For all \(\varGamma \cup \{ A \}\subseteq \mathsf {Form}\), \(\varGamma \,\models _*\,A\) iff for all Routley interpretations \(\langle W, *, v \rangle \) and for all \(w\in W\), if \(I(w, B)=1\) for all \(B\in \varGamma \) then \(I(w, A)=1\).
Second, we review Dunn’s relational semantics.
Definition 3
A Dunn-interpretation for \(\mathcal {L}\) is a relation, r, between propositional variables and the values 1 and 0, namely \(r\subseteq \mathsf {Prop}\times \{ 1, 0 \}\). Given an interpretation, r, this is extended to a relation between all formulas and truth values by the following clauses:
Definition 4
For all \(\varGamma \cup \{ A \}\subseteq \mathsf {Form}\), \(\varGamma \,\models _r\, A\) iff for all Dunn-interpretations r, if Br1 for all \(B\in \varGamma \) then Ar1.
Then, the following result is rather well-known.
Fact 5
For all \(\varGamma \cup \{ A \}\subseteq \mathsf {Form}\), \(\varGamma \,\models _r\, A\) iff \(\varGamma \,\models _*\, A\).
A proof can be found, e.g., in [18, 8.7.17, 8.7.18]. In fact, something stronger can be established by a careful examination of Graham Priest’s proof. To this end, we introduce another semantic consequence relation.
Definition 6
For all \(\varGamma \cup \{ A \}\subseteq \mathsf {Form}\), \(\varGamma \,\models _{*,2}\,A\) iff for all Routley interpretations \(\langle W, *, v \rangle \) such that the number of worlds is 2 and for all \(w\in W\), if \(I(w, B){=}1\) for all \(B\in \varGamma \) then \(I(w, A)=1\).
Then, we obtain the following.
Lemma 1
For all \(\varGamma \cup \{ A \}\subseteq \mathsf {Form}\), \(\varGamma \,\models _r\,A\) iff \(\varGamma \,\models _{*, 2}\,A\).
Proof
For the proof of the left-to-right direction, Priest’s construction works perfectly well with the two-world case. For the other direction, Priest’s construction already establishes the desired result. \(\square \)
As an immediate corollary, we obtain the following result, which can be regarded as logical folkore.
Theorem 1
For all \(\varGamma \cup \{ A \}\subseteq \mathsf {Form}\), \(\varGamma \,\models _*\,A\) iff \(\varGamma \,\models _{*, 2}\,A\). That is, two worlds suffice for the extensional fragment.
Remark 1
In view of the above result, we may conclude that there is a clear understanding of the star in the context of the above language. The star world is simply the other world. Of course, this only works with the simple language, not in the language with the intensional conditional. In the latter case, the star operation is elegantly characterized by Restall (cf. [19]).
3 Basics of SIXTEEN\(_3\)
3.1 Language
There are several languages discussed in relation to the trilattice SIXTEEN\(_3\). Following the convention specified in the previous section, we will mainly deal with \(\mathcal {L}_{{{\sim }}_f}\) and \(\mathcal {L}_{{{\sim }}_f, \wedge _f, \vee _f}\). The latter is referred to as \(\mathcal {L}_\textit{tf}\) in the literature, but for the sake of presentation, we will use the above notation with the hope of being more accessible to wider audience.
Note too that we are omitting the subscript t for connectives. We fully understand that this goes very much against the spirit of the trilattice in general, but for the sake of presentation, and ease of comparison between FDE and SIXTEEN\(_3\), we keep the basic connectives free of subscripts.
3.2 Semantics
Let 16 be the set of generalized truth values which consists of the following 16 values:
Note here that we changed the notation slightly from the original presentation. More specifically, we replaced T and F by 1 and 0. Moreover, the naming strategy for the truth values is very simple. Recall the following representation:
Then, except for the value \(\mathbf{A}\), the inclusion of capital letters N, F, T and B corresponds to the fact that n, f, t and b are members of the generalized truth value. And, for \(\mathbf{A}\), it stands for all values n, f, t and b are members of the set.
Now we can define three different orderings on 16.
Definition 7
For every \(x, y\in \mathbf{16}\):
We can then easily see that meets and joins exist in 16 for all three partial orders. Therefore, we use \(\sqcap \) and \(\sqcup \) with the appropriate subscripts for these operations under the corresponding orders. Then, the algebraic structure of 16 comes out as the trilattice SIXTEEN\(_3\) \(= \langle \mathbf{16}, \sqcap _i, \sqcup _i, \sqcap _t, \sqcup _t, \sqcap _f, \sqcup _f \rangle \).
We can associate with each of the lattice orders of SIXTEEN\(_3\) a unary operation which is an involution of order two with respect to this ordering and preserves the other orders. The unary operations \(-_t\), \(-_f\), and \(-_i\) corresponding to the orders \(\le _t\), \(\le _f\) and \(\le _i\), respectively, are defined as follows.
We are now ready to assign generalized truth values of 16 to our language. More specifically, given a 16-valuation \(v: \mathsf {Prop} \rightarrow \mathbf{16}\), we extend the valuation to \(\mathsf {Form}_{{{\sim }}_f, \wedge _f, \vee _f}\) as follows.
Definition 8
For every \(A, B\in \mathsf {Form}_{{{\sim }}_f, \wedge _f, \vee _f}\):
Based on this, we can finally define the semantic consequence relations.
Definition 9
For every \(A, B\in \mathsf {Form}_{{{\sim }}_f, \wedge _f, \vee _f}\):
-
\(A\,\models _t\,B\) iff for all 16-valuations v: \(v(A)\le _t v(B)\);
-
\(A\,\models _f\,B\) iff for all 16-valuations v: \(v(A)\le _f v(B)\).
Remark 2
We are not using the information order at all to interpret our language, but we introduced them above to emphasize that 16 is a trilattice. We will come back to the unary connective interpreted via \(-_i\) towards the end of this paper, but only briefly, in the conclusion section. For discussions on the language including informational connectives, see e.g. [14].
3.3 Proof Systems
We now turn to the proof system. Note that we will only offer the proof system for the language \(\mathcal {L}_{{{\sim }}_f}\), and just remark on the case of full language, namely the language \(\mathcal {L}_{{{\sim }}_f, \wedge _f, \vee _f}\).
Definition 10
\(\vdash \) is a binary consequence relation on the language \(\mathcal {L}_{{{\sim }}_f}\) satisfying the following axioms and rules.
Remark 3
Note that the binary consequence relation characterized in terms of the axioms from (a\(_t\)1) to (a\(_t\)7), as well as the rules from (r\(_1\)) to (r\(_t\)4) is sound and complete with respect to FDE for the language \(\mathcal {L}\).
Finally, the following result was established by Shramko and Wansing in [22, Theorems 4.10, 4.13].
Theorem 2
(Shramko & Wansing). For all \(A, B\in \mathsf {Form}_{{{\sim }}_f}\), \(A\vdash B\) iff \(A\,\models _t\,B\).
Remark 4
The problem of axiomatizing \(\models _t\) for the language \(\mathcal {L}_{{{\sim }}_f, \wedge _f, \vee _f}\) was left open in [22], but Odintsov in [12] marked the first step by showing that \(\models _t\) is axiomatizable and that the consequence relation can be characterized by the intersection of two related consequence relations. Odintsov also introduced an expansion of \(\mathcal {L}_{{{\sim }}_f, \wedge _f, \vee _f}\) by adding an implication, and presented an axiomatization of \(\models _t\) in the expanded language. A definite solution to the original problem was given in [14] by Odintsov and Wansing by making use of algebraic results related to SIXTEEN\(_3\).
4 Alternative Semantics for SIXTEEN\(_3\) (I)
The first alternative semantics will have two star operations. More specifically, we take the star semantics for FDE, and add one more star to capture the additional connective \({{\sim }}_f\). Our strategy here is to prove the soundness and completeness with respect to the proof system given by Shramko and Wansing to establish the equivalence between the original semantics and the two-star semantics.
4.1 Semantics
Definition 11
A two-star interpretation for \(\mathcal {L}_{{{\sim }}_f}\) is at tuple \(\mathcal {M}=\langle W, g, *_1, *_2, v \rangle \) where \(W\ne \emptyset \) is a set of worlds, \(g\in W\); \(*_i: W\longrightarrow W\) is a function with \(w^{*_i*_i}=w\) and \(w^{*_i*_j}=w^{*_j*_i}\); \(v: W\times \mathsf {Prop}\rightarrow \{ 0, 1 \}\). The function v is extended to \(I: W\times \mathsf {Form}\rightarrow \{ 0, 1 \}\) by the following condition:
Remark 5
It should be clear, from the definition, that the fragment with only the “truth connectives” will coincide with FDE. Note also that the truth condition for \({{\sim }}_f\) does not look like a truth condition for negation. We will reflect upon this connective in Sect. 6.
We then define two kinds of semantic consequence relation.
Definition 12
Let \(\varGamma \cup \{ A \}\) be set of sentences in \(\mathcal {L}_{{{\sim }}_f}\). Then,
-
\(\varGamma \,\models _{*, \forall }\,A\) iff for all two-star interpretations \(\langle W, g, *_1, *_2, v \rangle \) and for all \(w\in W\), \(I(w, A)=1\) if \(I(w, B)=1\) for all \(B \in \varGamma \).
-
\(\varGamma \,\models _{*, g}\,A\) iff for all two-star interpretations \(\langle W, g, *_1, *_2, v \rangle \), \(I(g, A)=1\) if \(I(g, B)=1\) for all \(B\in \varGamma \).
Remark 6
As we will establish below, these two consequence relations are equivalent as in some (not all!) modal logics (recall Kripke’s seminal paper and the more recent text books). However, it will be useful to have both for our purposes.
4.2 Equivalence of Three Semantic Consequence Relations
We will now establish the equivalence of \(\models _{t}, \models _{*, \forall }\) and \(\models _{*, g}\) via the proof system. More specifically, in view of Theorem 2 of Shramko and Wansing, we prove the following three statements: for all \(A, B\in \mathsf {Form}_{{{\sim }}_f}\),
Note here that the second item is obvious. Therefore, we prove the first and the third item. The first item, which is soundness, is quite straightforward.
Proposition 1
For all \(A, B\in \mathsf {Form}_{{{\sim }}_f}\), if \(A\vdash B\) then \(A\,\models _{*, \forall }\,B\).
Proof
We only note that we need \(\models _{*, \forall }\), instead of \(\models _{*, g}\), to establish the soundness, especially for the rules (r\(_t\)4) and (r\(_t\)5). \(\square \)
For the purpose of establishing the third item, we construct a suitable canonical model. To this end, we introduce some standard notions.
Definition 13
Let \(\varGamma \) be a set of sentences. Then, \(\varGamma \) is
-
a theory iff \(\varGamma \) is closed under \(\vdash \) and \(\wedge \), i.e., for all A, B, if \(A\in \varGamma \) and \(A\vdash B\) then \(B\in \varGamma \), and if \(A\in \varGamma \) and \(B\in \varGamma \), then \(A\wedge B\in \varGamma \);
-
prime iff for all A, B, if \(A\vee B\in \varGamma \) then \(A\in \varGamma \) or \(B\in \varGamma \).
The following fact is well known, due to Lindenbaum.
Lemma 2
(Lindenbaum). For all A, B, if \(A\not \vdash B\) then there is a prime theory \(\varGamma \) such that \(A\in \varGamma \) and \(B\not \in \varGamma \).
We will also make use of the following lemma which is already established by Shramko and Wansing in [22, Lemma 4.11].
Lemma 3
(Shramko & Wansing). Let \(\varGamma \) be a theory, and let \(\varGamma ^*\) be defined as follows:
Then \(\varGamma ^*\) is a theory, \({{\sim }}_f A\in \varGamma ^*\) iff \(A \in \varGamma \), and \(\varGamma ^*\) is prime iff \(\varGamma \) is prime.
We can then prove completeness as well.
Theorem 3
For all \(A, B\in \mathsf {Form}_{{{\sim }}_f}\), if \(A\,\models _{*, g}\,B\) then \(A\vdash B\).
Proof
The details can be found in Appendix A. \(\square \)
As a corollary, we obtain the following desired result:
Corollary 1
For all \(A, B\in \mathsf {Form}_{{{\sim }}_f}\), \(A\,\models _t\,B\) iff \(A\,\models _{*, g}\,B\) iff \(A\,\models _{*, \forall }\,B\).
We will now turn to two observations related to this result.
4.3 Two Basic Observations
First, we observe that we only need four worlds for two-star interpretations to characterize the syntactic consequence relation \(\vdash \). To this end, we introduce one more semantic consequence relation.
Definition 14
For all \(A, B\in \mathsf {Form}_{{{\sim }}_f}\), \(A\,\models _{*, g, 4}\,B\) iff for all two-star interpretations \(\langle W, g, *_1, *_2, v \rangle \) such that the number of worlds is 4, \(I(g, B)=1\) if \(I(g, A)=1\).
Then, we obtain in analogy to Theorem 1 the following result:
Proposition 2
For all \(A, B\in \mathsf {Form}_{{{\sim }}_f}\), \(A\,\models _{*, g}\,B\) iff \(A\,\models _{*, g, 4}\,B\).
Proof
The left-to-right direction is obvious. For the other direction, it suffices to prove that \(A\vdash B\) if \(A\,\models _{*, g, 4}\,B\) in view of Proposition 1. But this is already established by the proof for Theorem 3. \(\square \)
Remark 7
We have a relatively clear formal understanding of star operations. However, as in the case for FDE, we do not know what they mean. Only that each star corresponds to a different “mate” relation, cf. [18, p. 151].
The second observation, which relies on the first observation, is that \(\models _t\) is equivalent to yet another semantic consequence relation defined in terms of preservation of designated values. More precisely, we introduce the following consequence relation.
Definition 15
For all \(A, B\in \mathsf {Form}_{{{\sim }}_f}\), \(A\,\models _{16}\,B\) iff for all 16-valuations v: \(v(B)\in \mathcal {D}\) if \(v(A)\in \mathcal {D}\), where \(\mathcal {D}:= \{ x\in \mathbf{16} : \mathbf{T}\in x \}\).
Then, by unpacking the definition of \(\models _{*, g, 4}\), we obtain the following result:
Proposition 3
For all \(A, B\in \mathsf {Form}_{{{\sim }}_f}\), \(A\,\models _t\,B\) iff \(A\,\models _{16}\,B\).
Remark 8
The reason of introducing \(\models _{*, g}\) is to establish this connection to the 16-valued semantic consequence relation defined via designated values.
Note also that the result of the proposition above was already discussed in Lemma 4.3 in [22], for the language \(\mathcal {L}\). In Lemma 4.9 of the same paper an additional restriction for the consequence relation is discussed for the language \(\mathcal {L}_{{{\sim }}_f, \wedge _f, \vee _f}\) In the language \(\mathcal {L}_{{{\sim }}_f}\), however, we do not need such additional restriction.
5 Alternative Semantics for SIXTEEN\(_3\) (II)
The second alternative semantics will have only one star operation, but will be based on four-valued worlds, in analogy to the relational semantics of FDE. Therefore, the new semantics presented in this section can be seen as a hybrid of Routleys’ semantics and Dunn semantics. The equivalence of the semantics will be established through the semantics given in the previous section.
5.1 Semantics
Definition 16
A one-star interpretation for \(\mathcal {L}_{{{\sim }}_f}\) is a tuple \(\mathcal {M}=\langle W, g, *, r \rangle \) where W is a non-empty set of worlds, \(g\in W\); \(*: W\longrightarrow W\) is a function with \(w^{**}=w\); and \(r_w\subseteq \mathsf {Prop}\times \{ 0, 1 \}\) for all \(w\in W\). Given an interpretation, \(r_w\), this is extended to a relation between all formulas and truth values by the following clauses:
Remark 9
As one can see from the above definition, the one-star interpretation is a hybrid of Routleys’ semantics, for the use of the star operation, and Dunn semantics, for the use of the relation instead of the function.
Definition 17
For all \(A, B\in \mathsf {Form}_{{{\sim }}_f}\), \(A\,\models _r\,B\) iff for all one-star interpretations \(\mathcal {M}\), \(Br_g1\) if \(Ar_g1\).
5.2 Equivalence of Two Semantics
Proposition 4
For all \(A, B\in \mathsf {Form}_{{{\sim }}_f}\), if \(A\,\models _{*, g}\,B\) then \(A\,\models _r\,B\).
Proof
The details are spelled out in Appendix B. \(\square \)
Proposition 5
For all \(A, B\in \mathsf {Form}_{{{\sim }}_f}\), if \(A\,\models _r\,B\) then \(A\,\models _{*,g}\,B\).
Proof
The details are spelled out in Appendix C. \(\square \)
Remark 10
As in the case for FDE it is possible that the number of worlds for \(\models _{*,g}\) can be reduce to 2. This can be seen by careful examination of the proofs of Lemma 1 and Proposition 5.
6 Reflections on \({{\sim }}_f\)
The operator \({{\sim }}_f\) can be regarded as the negation with respect to the falsity order of the trilattice SIXTEEN\(_3\). However, in the context of this article, in which we focus solely on truth-order, it can be observed that \({{\sim }}_f\) is more than just a simple negation.
6.1 \({{\sim }}_f\) in Special Cases
The introduction of SIXTEEN\(_3\) inspired Dmitri Zaitsev to consider some variants with less truth values in [26]. In brief, Zaitsev suggests to apply the power set of a three-element set, rather than the four-element set used by Shramko and Wansing. Due to the limitation of space, we cannot discuss the details of how our two-valued semantics will capture one of Zaitsev’s systems.
However, since it is rather natural to consider some variants with less truth values, we briefly consider three special cases of two-star interpretations, and connect the resulting system to those known in the literature.
First, as expected, if we require \(w^{*_2}=w\) for all \(w\in W\), then we simply obtain an expansion of FDE with \({{\sim }}_f A \vdash A\) and \(A \vdash {{\sim }}_f A\). Second, if we require \(w^{*_1}=w^{*_2}\) for all \(w\in W\), then we obtain an expansion of FDE with \({{\sim }}_f\) as conflation.Footnote 4 Since classical negation is definable in terms of de Morgan negation and conflation, and conflation is definable in terms of de Morgan negation and classical negation, the resulting system is equivalent to the expansion of FDE by classical negation, called BD+ in [5]. Finally, if we require \(w^{*_1}=w\) for all \(w\in W\), then \({{\sim }}\) is a classical negation, and \({{\sim }}_f\) is again conflation. Since de Morgan negation is definable in terms of classical negation and conflation, the resulting system is again equivalent to BD+.
6.2 \({{\sim }}_f\) as a Modal Operator
In SIXTEEN\(_3\), the operator \({{\sim }}_f\) serves as a negation over the falsity ordering. In what follows, we will, however, show that truth condition for \({{\sim }}_f\), understood as in Sect. 4, suffice to interpret \({{\sim }}_f\) as a modal operator satisfying the K-axiom, as well as the rule of necessitation. Since our language is rather weak, we add \(\rightarrow \) which satisfies the following truth condition in a two-star interpretation.
In fact, this connective is the implication introduced by Odintsov in [12] as \(\rightarrow _t\).
It is now possible to prove the following proposition.
Proposition 6
For all \(A, B\in \mathsf {Form}_{{{\sim }}_f, \rightarrow }\),
-
1.
\(\models _{*, \forall }\,{{\sim }}_f (A \rightarrow B) \rightarrow ({{\sim }}_f A \rightarrow {{\sim }}_f B)\),
-
2.
\(\dfrac{\models _{*, \forall }\,A}{\models _{*, \forall } {{\sim }}_f A}\) and \(\dfrac{\models _{*, \forall }\,{{\sim }}_f A}{\models _{*, \forall }\,A}\).
Remark 11
The T and S4 axiom are not valid in this semantics. Furthermore, the equivalence \({{\sim }}{{\sim }}_f{{\sim }}A \leftrightarrow {{\sim }}_f A\) shows that \({{\sim }}_f\) is self-dual and hence also contains properties of a possibility operator. The negative modality \({{\sim }}\) behaves in a similar way.Footnote 5
Given that \({{\sim }}_f\) is not defined via an accessibility relation over worlds, but rather a function that maps worlds to worlds, one may doubt that \({{\sim }}_f\) counts as modal operator at all. However, as described by van Benthem in [4], it is possible to model propositional modal logic with a family of functions \(\mathcal {F}\), rather than accessibility relations. A model \(\mathcal {M} = \langle W, \mathcal {F}, V \rangle \) is then a tuple in the usual manner, with the following clause for the necessity operator: \(I(w,\Box A) = 1\) iff \(I(f(w),A) = 1\) for all \(f \in \mathcal {F}\). For example, the modal logic T is complete with respect “for all frames whose function set \(\mathcal {F}\) contains the identity function” [4].
In analogy to van Benthem’s approach, we may regard our two-star interpretation as a model \(\mathcal {M} = \langle W,g, *_1, \mathcal {F}, V \rangle \) where \(\mathcal {F} = \{*_2\}\) (recall Definition 11). We would then have \(I(w,{{\sim }}_f A) = 1\) iff \(I(f(w),A) = 1\) for all \(f \in \mathcal {F}\). Therefore, if van Benthem’s approach is seen as an approach to modality, then \({{\sim }}_f\) will be also counted as a modality at least in that sense. Hence, the language \(\mathcal {L}_{{{\sim }}_f}\) can be interpreted as an FDE-based modal language, where FDE is captured in terms of the star semantics (recall Definition 1), as, for example, in [7, 9].Footnote 6
7 Concluding Remarks
What we hope to have established in this paper is that it is possible to provide two-valued semantics for a logic based on SIXTEEN\(_3\). In particular, we made essential use of Routleys’ star operation for both two-valued semantics. However, our result here is just a first step, and there seem to be a number of problems to be explored in more details. We will mention two of them.
The first problem is related to the language. In this paper, we focused on the most simple language associated to SIXTEEN\(_3\), namely \(\mathcal {L}_{{{\sim }}_f}\). However, this is only one of the many possible choices. In particular, it seems more than natural to deal with \(\wedge _f\) and \(\vee _f\), but these connectives seem to be resistant. For example, if we consider the truth condition for \(\wedge _f\) in a two-star interpretation, then a straightforward application of our method suggests to split truth condition depending on the number of stars applied at the state. We do not know, at the time of writing, if we can capture \(\wedge _f\) in a two-star interpretation by a single truth condition. We should also note that some connectives discussed in the literature can be captured. For example, \(\lnot \) and \({{\sim }}_i\), in a two-star interpretation, will have the following truth conditions respectively:
-
\(I(w, \lnot A)=1\) iff \(I(w, A)\ne 1\)
-
\(I(w, {{\sim }}_i A)=1\) iff \(I(w^{*_1*_2}, A)=1\)
The second problem is to explore the relation between the two-valued semantics and the trilattice. Note that in our two-valued semantics, we are making essential use of the star operation, but this seems to give rise to some difficulties. Here is a reason: In the context of FDE, informational join and meet of the bilattice naturally inspire to introduce binary connectives, and these connectives can be captured easily in terms of Dunn semantics by giving truth and falsity conditions. However, it is far from obvious if we can capture the same connectives based on the star semantics by equally simple conditions. And a similar issue may carry over to the case with SIXTEEN\(_3\). In fact, this might also be related to the first problem related to \(\wedge _f\) and \(\vee _f\).
Notes
- 1.
For a recent overview, see for example [17].
- 2.
The formal details will be given in the next section, so we are justified to be brief.
- 3.
For a mechanical procedure to reduce the number of truth values in FDE and its expansions, see [16].
- 4.
Given a Dunn interpretation, conflation, written as −, is characterized by the following truth and falsity conditions: \(-Ar1\) iff not Ar0, and \(-Ar0\) iff not Ar1.
- 5.
We thank Sergei Odintsov for pointing this out.
- 6.
References
Arieli, O., Avron, A.: Reasoning with logical bilattices. J. Log. Lang. Inf. 5(1), 25–63 (1996)
Belnap, N.: How a computer should think. In: Ryle, G. (ed.) Contemporary Aspects of Philosophy, pp. 30–55. Oriel Press (1976)
Belnap, N.: A useful four-valued logic. In: Dunn, J., Epstein, G. (eds.) Modern Uses of Multiple-Valued Logic, pp. 8–37. D. Reidel Publishing Co. (1977)
van Benthem, J.: Beyond accessibility. In: de Rijke, M. (ed.) Diamonds and Defaults: Studies in Pure and Applied Intensional Logic. SYLI, vol. 229, pp. 1–18. Springer, Dordrecht (1993). https://doi.org/10.1007/978-94-015-8242-1_1
De, M., Omori, H.: Classical negation and expansions of Belnap-Dunn logic. Stud. Log. 103(4), 825–851 (2015)
Dunn, J.M.: Intuitive semantics for first-degree entailment and ‘coupled trees’. Philos. Stud. 29, 149–168 (1976)
Fuhrmann, A.: Models for relevant modal logics. Stud. Log. 49(4), 501–514 (1990)
Ginsberg, M.: Multi-valued logics: a uniform approach to AI. Comput. Intell. 4, 243–247 (1988)
Mares, E.D., Meyer, R.K.: The semantics of R4. J. Philos. Log. 22(1), 95–110 (1993)
Muskens, R., Wintein, S.: Analytic tableaux for all of SIXTEEN\(_3\). J. Philos. Log. 44(5), 473–487 (2015)
Muskens, R., Wintein, S.: Interpolation in 16-valued trilattice logics. Stud. Log. 106(2), 345–370 (2018)
Odintsov, S.P.: On axiomatizing Shramko-Wansing’s logic. Stud. Log. 91(3), 407–428 (2009)
Odintsov, S.P., Wansing, H.: Modal logics with Belnapian truth values. J. Appl. Non-Class. Log. 20, 279–301 (2010)
Odintsov, S.P., Wansing, H.: The logic of generalized truth values and the logic of bilattices. Stud. Log. 103(1), 91–112 (2015)
Odintsov, S.P., Wansing, H.: Disentangling FDE-based paraconsistent modal logics. Stud. Log. 105(6), 1221–1254 (2017)
Omori, H., Sano, K.: Generalizing functional completeness in Belnap-Dunn logic. Stud. Log. 103(5), 883–917 (2015)
Omori, H., Wansing, H.: 40 years of FDE: an introductory overview. Stud. Log. 105(6), 1021–1049 (2017)
Priest, G.: An Introduction to Non-Classical Logic: From If to Is, 2nd edn. Cambridge University Press, Cambridge (2008)
Restall, G.: Negation in relevant logics (how i stopped worrying and learned to love the routley star). In: Gabbay, D.M., Wansing, H. (eds.) What is Negation?, pp. 53–76. Kluwer Academic Publishers (1999)
Routley, R., Routley, V.: Semantics for first degree entailment. Noûs 6, 335–359 (1972)
Shramko, Y., Wansing, H.: Truth and Falsehood - An Inquiry into Generalized Logical Values, 1st edn. Springer, Dordrecht (2012). https://doi.org/10.1007/978-94-007-0907-2
Shramko, Y., Wansing, H.: Some useful 16-valued logics: how a computer network should think. J. Philos. Log. 34(2), 121–153 (2005)
Shramko, Y., Wansing, H.: Hyper-contradictions, generalized truth values and logics of truth and falsehood. J. Log. Lang. Inf. 15(4), 403–424 (2006)
Suszko, R.: Remarks on Łukasiewicz’s three-valued logic. Bull. Sect. Log. 4, 87–90 (1975)
Wansing, H.: The power of Belnap: sequent systems for SIXTEEN\(_3\). J. Philos. Log. 39, 369–393 (2010)
Zaitsev, D.: A few more useful 8-valued logics for reasoning with tetralattice EIGHT\(_4\). Stud. Log. 92(2), 265–280 (2009)
Author information
Authors and Affiliations
Corresponding authors
Editor information
Editors and Affiliations
Appendices
A Details of the Proof of Theorem 3
We prove the contrapositive. Assume \(A\not \vdash B\). Then, by Lindenbaum’s lemma, there is a prime theory \(\varGamma \) such that \(A\in \varGamma \) and \(B\not \in \varGamma \). We then define a two-star interpretation \(\langle W, g, *_1, *_2, v \rangle \) as follows:
If we can show that the above condition holds for all formulas, then the result follows since at \(a\in W\), \(I(a, A)=1\) but \(I(a, B)\ne 1\), i.e. \(A\not \models _*\,B\). We prove this by induction on the complexity of A. We only prove the cases for \({{\sim }}\) and \({{\sim }}_f\), since the cases for \(\wedge \) and \(\vee \) are straightforward.
Case 1. If A is an element of \(\mathsf {Prop}\), the result holds by definition.
Case 2. If \(A={{\sim }}B\), then
Case 3. If \(A={{\sim }}_f B\), then
This completes the proof. \(\square \)
B Details of the Proof of Proposition 4
We prove the contrapositive. Assume \(A\not \models _r\,B\). Then, there is a one-star interpretation \(\langle W, g, *, r \rangle \) such that \(Ar_g1\), but not \(Br_g1\). We then define a two-star interpretation \(\langle W, g *_1, *_2, v \rangle \) as follows:
If we can show that the above condition holds for all formulas, then the result follows since at \(a\in W\), \(v(a, A)=1\) but \(v(a, B)\ne 1\), i.e. \(A\not \models _{*,g}\,B\). We prove this by induction. We only prove the cases for \({{\sim }}\) and \({{\sim }}_f\), since the cases for \(\wedge \) and \(\vee \) are straightforward.
Case 1. If A is an element of \(\mathsf {Prop}\), the result holds by definition.
Case 2. If \(A={{\sim }}B\), then
Case 3. If \(A={{\sim }}_f B\), then
This completes the proof. \(\square \)
C Details of the Proof for Proposition 5
We prove the contrapositive. Assume \(A\not \models _{*,g}\,B\). Then, there is a two-star interpretation \(\langle W, g, *_1, *_2, v \rangle \) such that \(I(g, A)=1\) but \(I(g, B)\ne 1\). We then define a one-star interpretation \(\langle W, g, *, r \rangle \) as follows:
If we can show that the above condition holds for all formulas, then the result follows since at \(a\in W\), \(Ar_a1\) but not \(Br_a1\), i.e. \(A\not \models _r\,B\). We prove this by induction. We only prove the cases for \({{\sim }}\) and \({{\sim }}_f\), since the cases for \(\wedge \) and \(\vee \) are straightforward.
Case 1. If A is an element of \(\mathsf {Prop}\), the result holds by definition.
Case 2. If \(A={{\sim }}B\), then
Case 3. If \(A={{\sim }}_f B\), then
This completes the proof. \(\square \)
Rights and permissions
Copyright information
© 2019 Springer-Verlag GmbH Germany, part of Springer Nature
About this paper
Cite this paper
Omori, H., Skurt, D. (2019). SIXTEEN\(_3\) in Light of Routley Stars. In: Iemhoff, R., Moortgat, M., de Queiroz, R. (eds) Logic, Language, Information, and Computation. WoLLIC 2019. Lecture Notes in Computer Science(), vol 11541. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-59533-6_31
Download citation
DOI: https://doi.org/10.1007/978-3-662-59533-6_31
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-59532-9
Online ISBN: 978-3-662-59533-6
eBook Packages: Computer ScienceComputer Science (R0)