An Interpretation of Łukasiewicz’s 4-Valued Modal Logic

Abstract

A simple, bivalent semantics is defined for Łukasiewicz’s 4-valued modal logic Łm4. It is shown that according to this semantics, the essential presupposition underlying Łm4 is the following: A is a theorem iff A is true conforming to both the reductionist (rt) and possibilist (pt) theses defined as follows: rt: the value (in a bivalent sense) of modal formulas is equivalent to the value of their respective argument (that is, ‘ A is necessary’ is true (false) iff A is true (false), etc.); pt: everything is possible. This presupposition highlights and explains all oddities arising in Łm4.

1 Introduction

Łukasiewicz’s 4-valued modal logic was introduced in [12] (cf. also [11], Chap. VII; cf. the paragraph preceding Definition 2.3 on the label Łm4). The reader can find a good analysis of the history, motivation and different formulations of the system in [5] (cf. also [18]). The aim of this paper is to define a simple, intuitive, bivalent semantics for Łm4 similar to that characterizing classical propositional logic.

Łukasiewicz’s system has not had much influence in the development of modern modal logic. This lack of success is mainly due to the presence in Łm4 of what we can label “Łukasiewicz-type modal paradoxes” , where the term “paradox” has to be understood in the same sense used by Lewis in [10] when referring to “the paradoxes of material conditional” (π α ρ α−δ o ξ α , what comes away from the ‘doxa’ —the common opinion). Among these conspicuous paradoxes are the following (cf. Definition 2.1 about the logical language used in the paper):

$$\begin{array}{@{}rcl@{}} &&\text{p1.} \,\, (A\rightarrow B)\rightarrow (MA\rightarrow MB) \\ &&\text{p2.} \,\, (A\rightarrow B)\rightarrow (LA\rightarrow LB) \\ &&\text{p3.} \,\, (MA\wedge MB)\rightarrow M(A\wedge B) \\ &&\text{p4.} \,\, L(A\vee B)\rightarrow (LA\vee LB) \\ &&\text{p5.}\,\, LA\rightarrow (B\rightarrow LB)\\ &&\text{p6.} \,\, LA\rightarrow (MB\rightarrow B) \end{array} $$

It is clear that p1-p6 are, to say the least, difficult to understand according to the standard notions of ‘necessity’ and ‘possibility’. Actually, Hughes and Cresswell point out that “if by a modal logic we mean a logic of possibility and necessity, this system [Łm4] takes us to the limits of what should be regarded as a modal logic at all” ([7], p. 310 —quoted in [5], p. 176). And on their part, Font and Hajek express an extended opinion when they affirm that “Łukasiewicz’s system is rather a dead end from an intuitive or applied point of view” ([5], p. 160). The semantics we are going to define identifies the essential presupposition —not Łukasiewicz’s own motivation at all!— underlying Łm4 and thus it can explain why these and other oddities and difficulties afflict Łukasiewicz’s system. But let us recall the standard semantics for Łm4.

Łukasiewicz defined his system syntactically by using both inference and rejection rules, and claimed that it was determined by a certain 4-valued matrix (cf. Definition 4.1 below). By reformulating the presentation of Łukasiewicz’s system, Smiley [17] and especially Lemmon [9] (Section 5) proved that Łukasiewicz was right (cf. the axiomatization of Łm4 by Lemmon in Definition 2.3).

Lemmon also provided an algebraic semantics for Łm4 that can be generally reformulated in Kripke semantics as follows (cf. [9], Section 5; [5] and [18]). A Łm4-model is a structure $(K,O,R,\vDash )$ where K is a set of worlds; O is a set of (non-normal) worlds (anything is possible in them); R is the accessibility relation, and finally, $\vDash$ is a (valuation) relation that evaluates $\rightarrow$, ∧, ∨ and $\lnot$ standardly while evaluates L and M as follows:

$$\begin{array}{@{}rcl@{}} a\vDash LA\text{ iff }a\notin O\, \& \forall x(Rax\Rightarrow x\vDash A) \\ a\vDash MA\text{ iff }a\in O\text{ or }\exists x(Rax\, \& x\vDash A) \end{array} $$

It also has to be remarked that R has the following properties: (i) $\forall x,y\in K(Rxy\Rightarrow x=y)$; (ii) $x\notin O\Rightarrow Rxx$.

Now, as it is well known, normal modal logics cannot be characterized by means of finite matrices (cf. [4]; [2], Section 9), which of course entails that Łm4 is not normal, as it happens with the Kripke models w.r.t. which Łm4 is sound and complete, which are non-normal too, as we have seen. The aim of this paper is then to provide a simpler semantics for Łm4 similar to the bivalent semantics characterizing classical propositional logic. The essential presupposition in this semantics —and the source of all difficulties Łm4 presents— can generally be described as follows. Consider the following theses: (1) Reductionist thesis: there are two (truth) values, T and F, representing truth and falsity in the classical sense, and the value of LA and MA is the value assigned to A ; (2) the possibilist (or non necessitarianist) thesis: nothing is necessary or, equivalently, everything is possible. The explicit rejection of both theses is established by Łukasiewicz as a ‘conditio sine qua non’ of any (basic) modal logic (cf. [5], p. 175; [18], Section 2). But, nevertheless, according to the semantics that we are going to define and w.r.t. which Łm4 is sound and complete, the essential presupposition underlying Łukasiewicz’s system is the following: A is a theorem of Łm4 iff A is true according to both the reductionist and the possibilist theses. However, notice that this does not mean that Łm4 endorses both theses (far from it), but rather (in a sense to be made precise below) that it corrects the reductionist thesis with the possibilist one, or the other way round. (Remark that if possibilism is arguable —cf., e.g., [15] and [16]—, reductionism —in the sense defined above— seems to lack any justification whatsoever).

Thus, as Hughes and Cresswell remarked, Łm4 takes us to the limits of what can be considered as a modal logic (to the limits of what can be considered an arguable philosophical thesis?), although, be it as it may, Łm4 is undoubtedly a very interesting system from more than one point of view (cf., for example, [5] on its algebraic nice properties).

In order to expound the general features of our semantics (explained in detail in Section 3), let us introduce some terminology. Formulas of the form LA (MA) are named “necessitives” (“possibilitives”). (The (ugly) terminology is borrowed from Anderson and Belnap —[1], Section 5.2—; the qualifying term for this terminology, “ugly” , is also Anderson and Belnap’s.) A “necessitive interpretation” is a function from the set of wffs $\mathcal {F}$ to the set {T,F} where T and F represent truth and falsity in the classical sense. All necessitive interpretations evaluate $\rightarrow$, ∧, ∨, $\leftrightarrow$ and $\lnot$ according to the classical two-valued tables, but differ in the interpretation of necessitive and possibilitive formulas (cf. Definition 2.1 about the logical language used in the paper). In fact, there are two classes of “necessitive interpretations” : “necessitative interpretations” and “strongly non-necessitative interpretations” (“necessitative” is another ugly term coming from “necessitation” , in its turn taken from the locution “necessitation rule” , i.e., the rule $A\Rightarrow LA$. Cf. propositions 3.12, 3.13 below about this rule). A necessitative interpretation is a necessitive interpretation assigning to each necessitive and possibilitive formula the value assigned to its respective argument (A is the argument of L A and of MA); a strongly non-necessitative interpretation is a necessitive interpretation assigning F to all necessitives and T to all possibilitives. Then, a wff A is a theorem of Łukasiewicz’s 4-valued modal logic iff it is validated (assigned the value T) by all necessitative and all strongly non-necessitative interpretations.

It is now easy to see why the paradoxes p1-p6 are validated. Let us take p5 as an example. It is clear that each necessitative interpretation I validates p5 ($LA\rightarrow (B\rightarrow LB)$) since I validates $A\rightarrow (B\rightarrow B)$; it is also obvious that each strongly non-necessitative interpretation validates p5: no strongly necessitative interpretation validates the antecedent of p5. In the same sense, one can immediately see why the characteristic axioms of Lewis’ S5 ($MA\rightarrow LMA$; $MLA\rightarrow LA$) are not theorems of Łm4: although validated by each necessitative interpretation, they are invalidated by all strongly non-necessitative interpretations. Finally, to take a last example, the strong theses (1) MA and (2) $\lnot LA$ and the collapsing formulas (3) $A\rightarrow LA$ and (4) $MA\rightarrow A$ are invalidated as follows. Theses 1 and 2: by any necessitative interpretation assigning F (in 1) and T (in 2) to A (1 and 2 are validate by any strongly non-necessitative interpretation); formulas 3 and 4: by any strongly non-necessitative interpretation assigning T (in 3) and F (in 4) to A (3 and 4 are validated by any necessitative interpretation).

The structure of the paper is as follows. In Section 2, the logic Łm4 is defined and some facts about theories built upon Łm4 are proved. These facts are used in the completeness proof in Section 3. Section 3 is the main section of the paper. In it, the bivalent semantics that has generally been delineated above is introduced. Then, completeness is shown by an easy Henkin-style proof. Consistent, complete and necessitative (strongly non-necessitative) theories are used as canonical necessitative (strongly non-necessitative) interpretations. Next, it is shown that each non-theorem fails to belong to a consistent and complete necessitative (or strongly non-necessitative) theory. Once soundness and completeness of Łm4 w.r.t. the bivalent semantics is proved, it has been shown that the latter in fact characterizes Łukasiewicz’s 4-valued modal logic. Nevertheless, in Section 4, the bivalent semantics and Łukasiewicz’s 4-valued matrix are put in correspondence by showing that for each necessitive interpretation invalidating a given formula there is a corresponding interpretation in Łukasiewicz’s matrix invalidating the same formula. The section is ended with the proof of soundness and completeness w.r.t. validity in Łukasiewicz’s 4-valued matrix. In Section 5, we end the paper with a couple of concluding remarks.

2 The Logic Łm4

We begin by defining the logical language and the notion of logic considered in this paper.

Definition 2.1 (Language)

The propositional language consists of a denumerable set of propositional variables p ₀,p ₁,...,p _n ,..., and the following connectives: $\rightarrow$ (conditional), $\lnot$ (negation) and L (necessity). Other propositional connectives such as ∧ (conjunction), ∨ (disjunction), $\leftrightarrow$ (biconditional) and M (possibility) are eventually introduced by definition. The set of wffs is defined in the customary way.

A, B (possibly with subscripts 0,...1,...n), etc., are metalinguistic variables. By $\mathcal {P}$ and $\mathcal {F}$, we shall refer to the set of all propositional variables and the set of all formulas, respectively. (We note that the symbols L (for the necessity operator) and M (for the possibility operator) are used by Łukasiewicz — cf. [5], Note 2, p. 158.)

Definition 2.2 (Logics)

A logic S is a structure $(L,\vdash _{\text {S}})$ where L is a propositional language and $\vdash _{\text {S}}$ is a (proof-theoretical) consequence relation defined by a set of axioms and a set of rules of derivation. The notions of ‘proof’ and ‘theorem’ are understood as it is customary in Hilbert-style axiomatic systems. That is, a proof is a sequence of formulas each one of which is an axiom or the result of applying a rule of derivation to one or more previous formulas in the sequence. A theorem is a proven formula. The notion of ‘proof from premises’ is also understood as it is customary. In symbols, ‘A is a theorem of S’ is rendered by $\vdash _{\text {S}}A$; and ‘A is provable from Γ in S’, by ${\Gamma } \vdash _{\text {S}}A$.

Łukasiewicz’s system can be defined as follows (the label Łm4 abbreviates ‘Łukasiewicz modal 4-valued logic’ and it is intended to distinguish Łm4 from the linearly ordered many-valued and infinite valued Łukasiewicz’s logics and, in particular, from the 4-valued logic Ł ₄ —Łukasiewicz used the symbol Ł for Łm4).

Definition 2.3 (The logic Łm4)

The logic Łm4 is formulated as follows:

Axioms

$$\begin{array}{@{}rcl@{}} &&\text{A1. } A\rightarrow (B\rightarrow A) \\ &&\text{A2. } [A\rightarrow (B\rightarrow C)]\rightarrow \lbrack (A\rightarrow B)\rightarrow (A\rightarrow C)] \\ &&\text{A3. } (\lnot A\rightarrow \lnot B)\rightarrow (B\rightarrow A) \\ &&\text{A4. } LA\rightarrow A \\ &&\text{A5. } LA\rightarrow (B\rightarrow LB) \end{array} $$

Rules of derivation

$$\text{Modus Ponens (MP): }A\And A\rightarrow B\Rightarrow B $$

Definitions

$$\begin{array}{@{}rcl@{}} && A\vee B=_{\text{df}}\lnot A\rightarrow B \\ && A\wedge B=_{\text{df}}\lnot (A\rightarrow \lnot B) \\ && A\leftrightarrow B=_{\text{df}}(A\rightarrow B)\And (B\rightarrow A) \\ && MA=_{\text{df}}\lnot L\lnot A \end{array} $$

Remark 2.4 (On the axiomatization of Łm4)

Notice that A1-A3 together with MP is one of the formulations of classical propositional logic (CL) defined in [3]. On the other hand, remark that the classical axiomatization by Lemmon ([9], p. 214) adds the axiom A6, $L(A\rightarrow B)\rightarrow (LA\rightarrow LB)$, but this axiom has been shown to not be independent by Tkaczyk in [18], who also proves that A4 and A5 can be changed by the sole axiom (JP) $(LA\wedge B)\rightarrow (A\wedge LB)$ (‘Jumping necessity axiom’, in Tkaczyk’s words), cf. [18], p. 231.

Remark 2.5 (Some theorems of Łm4)

The following theorems of Łm4 will be useful:

$$\begin{array}{@{}rcl@{}} &&\text{t1. } A\rightarrow A \\ &&\text{t2. } [(A\rightarrow B)\wedge A]\rightarrow B\\ &&\text{t3. } \lnot A\rightarrow (A\rightarrow B) \\ &&\text{t4. } [(A\rightarrow B)\wedge (\lnot A\rightarrow B)]\rightarrow B \\ &&\text{t5. } (A\wedge \lnot LA)\rightarrow \lnot LB \end{array} $$

Notice that t1-t4 are theorems of CL, while t5 is immediate by A5 and CL.

Finally, we note that the Deduction Theorem (DT) is provable in Łm4.

Proposition 2.6 (The Deduction Theorem DT)

For any set of wffs Γ and wff A, B, if ${\Gamma } ,A\vdash _{\text {{\L }m4}}B$ , then ${\Gamma } \vdash _{\text {{\L }m4}}A\rightarrow B$.

Proof

As it is known, DT is provable in any extension of the implicative fragment of propositional intuitionistic logic (axiomatized by A1, A2 and MP) with MP as the sole rule of inference (cf. e.g., [13]). □

Next, we prove some facts about theories built upon Łm4. These facts are used in the completeness proofs of Section 3. Firstly, the notion of a theory is defined.

Definition 2.7 (Łm4-theories)

A Łm4-theory (theory, for short) is a set of formulas containing all theorems of Łm4 and closed under modus ponens (MP). That is, $\mathcal {T}$ is a theory iff (1) if $\vdash _{\text {{\L }m4}}A$ then $A\in \mathcal {T}$; and (2) if $A\rightarrow B\in \mathcal {T}$ and $A\in \mathcal {T}$, then $B\in \mathcal {T}$.

Definition 2.8 (Classes of theories)

Let $\mathcal {T}$ be a theory. We set (1) $\mathcal {T}$ is consistent iff for no wff A, $A\wedge \lnot A\in \mathcal {T}$; (2) $\mathcal {T}$ is complete iff for every wff A, $A\in \mathcal {T}$ or $\lnot A\in \mathcal {T}$; (3) $\mathcal {T}$ is necessitative iff for every wff A, $LA\in \mathcal {T}$ iff $A\in \mathcal {T}$; (4) $\mathcal {T}$ is strongly non necessitative iff for every wff A, $MA\in \mathcal {T}$.

As commented in the introduction to this paper, the “necessitation rule” (NR) is the following: $A\Rightarrow LA$. It will be proved that NR is not admissible in Łm4 (cf. propositions 3.12 and 3.13), but necessitative theories are closed under NR anyway. On the other hand, (consistent) strongly non-necessitative theories do not contain a sole necessitive formula. Both classes of theories are essential to the development of the paper and shall be put in correspondence with necessitative and strongly non-necessitative interpretations, as the reader may guess. A couple of lemmas are recorded to end the section. The first one recalls the main property of conditionals in complete theories; the second one proves a first extension result.

Lemma 2.9 (The conditional in complete theories)

Let $\mathcal {T}$ be a complete theory. Then, for any wffs A, B, $A\rightarrow B\in \mathcal {T}$ iff $A\notin \mathcal {T}$ or $B\in \mathcal {T}$.

Proof

(1) Left to right: by t2; (2) right to left: by A1 and t3. □

Lemma 2.10 (First extension lemma)

Let $\mathcal {T}$ be a theory and A a wff such that $A\notin \mathcal {T}$ . Then, there is a consistent, complete theory Θ such that $\mathcal {T} \subseteq {\Theta }$ and A∉Θ.

Proof

Extend $\mathcal {T}$ to a maximal theory Θ such that A∉Θ. For reductio, suppose that Θ is not complete, that is, B∉Θ, $\lnot B\notin {\Theta }$ for some wff B. Define the sets $[{\Theta } ,B]=\{C\mid B\rightarrow C\in {\Theta } \}$, $[{\Theta } ,\lnot B]=\{C\mid \lnot B\rightarrow C\in {\Theta } \}$. We prove: (1) [Θ,B] and $[{\Theta } ,\lnot B]$ are closed by MP: by A2 and the fact that Θ is a theory; (2) ${\Theta } \subseteq [{\Theta } ,B]$ and ${\Theta } \subseteq [{\Theta } ,\lnot B]$: by A1, as Θ is a theory; (3) [Θ,B] and $[{\Theta } ,\lnot B]$ are theories: these sets are closed by MP (by 1) and contain all theorems of Łm4 (by 2); (4) ${\Theta } \nsupseteq \lbrack {\Theta } ,B]$, ${\Theta } \nsupseteq \lbrack {\Theta } ,\lnot B]$: by t1, B∈[Θ,B] and $\lnot B\in [ {\Theta } ,\lnot B]$, but, by hypothesis, B∉Θ and $\lnot B\notin {\Theta }$. Consequently, (by the maximallity of Θ) we have A∈[Θ,B], $A\in [{\Theta } ,\lnot B]$ whence A∈Θ (by t4), which is impossible. Therefore, Θ is complete. Moreover, Θ is consistent: by t3. □

3 Bivalent Semantics for Łm4

We proceed into the definition of the bivalent semantics. Firstly, the notions of a necessitative interpretation (in symbols, $\boxdot$-interpretation) and a strongly non-necessitative interpretation (in symbols, $\boxminus$-interpretation) are defined.

Definition 3.1 ($\boxdot$ -interpretations)

A $\boxdot$-interpretation, I, is a function from $\mathcal {F}$ to {T,F} such that for all $p_{i}\in \mathcal {P}$ and A, $B\in \mathcal {F}$ the following conditions are fulfilled:

$$\begin{array}{@{}rcl@{}} &&\text{1.} I(p_{i})=T\text{ or }I(p_{i})=F \\ &&\text{2.} I(\lnot A)=T\text{ iff }I(A)=F \\ &&\text{3.} I(A\rightarrow B)=T\text{ iff }I(A)=F\text{ or }I(B)=T \\ &&\text{4.} I(LA)=T\text{ iff }I(A)=T \end{array} $$

Definition 3.2 ($\boxminus$ -interpretations)

An $\boxminus$-interpretation, I, is a function from $\mathcal {F}$ to {T,F} such that for all $p_{i}\in \mathcal {P}$ and A, $B\in \mathcal {F}$ the following conditions are fulfilled:

$$\begin{array}{@{}rcl@{}} &&\text{1.} I(p_{i})=T\text{ or }I(p_{i})=F \\ &&\text{2.} I(\lnot A)=F\text{ iff }I(A)=T \\ &&\text{3.} I(A\rightarrow B)=F\text{ iff }I(A)=T\text{ and }I(B)=F \\ &&\text{4.} I(LA)=F\text{ iff }I(A)=T\text{ or }I(A)=F \end{array} $$

It will be useful to introduce labels to refer to the set of all necessitive interpretations (in symbols, $\blacksquare$-interpretations; cf. Section 1) and to the set of all interpretations belonging to each one of the two classes defined above (necessitative and strongly non-necessitative interpretations).

Definition 3.3 ($\blacksquare$ -interpretations)

Let us refer by $I^{\boxdot }$ ($I^{\boxminus }$) to the set of all $\boxdot$-interpretations ($\boxminus$-interpretations). By $I^{\blacksquare }$, we shall refer to the set $I^{\boxdot }\cup I^{\boxminus }$, that is, to the set of all $\boxdot$-interpretations and $\boxminus$-interpretations.

Now, let $I\in I^{\blacksquare }$, $I^{\prime }\in I^{\boxdot }$ and $I^{\prime \prime }\in I^{\boxminus }$. We remark that for all A, $B\in \mathcal {F}$, the following conditions are fulfilled:

$$\begin{array}{@{}rcl@{}} &&\text{1. } I(A\wedge B)=T\text{ iff }I(A)=I(B)=T \\ &&\text{2. } I(A\vee B)=T\text{ iff }I(A)=T\text{ or }I(B)=T \\ &&\text{3. } I^{\prime }(MA)=T\text{ iff }I(A)=T\text{ } \\ &&\text{4. } I^{\prime \prime }(MA)=T\text{ iff }I(A)=T\text{ or }I(A)=F \end{array} $$

(Cf. definitions of ∧, ∨ and M in Definition 2.3.)

On the other hand, we remark that for any set of wffs Γ and $I\in I^{\blacksquare }$, we have: (1) I(Γ)=T iff ∀A∈Γ(I(A)=T); (2) I(Γ)=F iff ∃A∈Γ(I(A)=F).

Now, validity in the semantics of necessitive interpretations is defined as follows.

Definition 3.4 ($\blacksquare$ -validity)

A wff A is $\blacksquare$-valid (in symbols, $\vDash _{\blacksquare }A$) iff I(A)=T for all $I\in I^{\blacksquare }$. And the rule $A_{0}\& A_{1}\& ...\& A_{n}\Rightarrow B$ preserves $\blacksquare$-validity iff, for all $I\in I^{\blacksquare }$, I(B)=T if I(A _i )=T for each A _i (1≤i≤n).

In what follows, we proceed into the definition of canonical interpretations.

Definition 3.5 ($\mathcal {T}$ -interpretations)

Let $\mathcal {T}$ be a consistent, complete theory. A $\mathcal {T}$ -interpretation, I, is a function from $\mathcal {F}$ to {T,F} defined as follows: for any $A\in \mathcal {F}$, I(A)=T iff $A\in \mathcal {T}$.

As it is to be expected, there are two main classes of consistent and complete theories: necessitative and strongly non-necessitative theories (cf. Definition 2.8).

Definition 3.6 (The set $\mathcal {T}^{\boxdot }$)

$\mathcal {T}^{\boxdot }$ is the set of all consistent, complete and necessitative theories.

Definition 3.7 (The set $\mathcal {T}^{\boxminus }$)

$\mathcal {T}^{\boxminus }$ is the set of all consistent, complete and strongly non-necessitative theories.

Definition 3.8 (The set $\mathcal {T}^{\blacksquare }$)

By $\mathcal {T}^{\mathcal {\blacksquare }}$ we shall refer to the set $\mathcal {T}^{\boxdot }\mathcal {\cup T}^{\boxminus }$.

Notice that $\mathcal {T}^{\boxdot }\mathcal {\cap T}^{\mathcal { \boxminus }}\mathcal {=\emptyset }$.

Lemma 3.9 (Each $\mathcal {T\in T}^{\boxdot }$ induces an $I^{\boxdot }$ -interpretation)

Let $\mathcal {T}$ be a consistent, complete and necessitative theory; and let I be the $\mathcal {T}$ -interpretation built upon $\mathcal {T}$ , as indicated in Definition 3.5. Then, I is an I ^⊡ -interpretation.

Proof

Let $p_{i}\in \mathcal {P}$ and A, $B\in \mathcal {F}$. (1) $p_{i}\in \mathcal {T}$ or $\lnot p_{i}\in \mathcal {T}$: by completeness of $\mathcal {T}$; (2) $\lnot A\in \mathcal {T}$ iff $A\notin \mathcal {T}$: by consistency and completeness of $\mathcal {T}$; (3) $A\rightarrow B\in \mathcal {T}$ iff $A\notin \mathcal {T}$ or $B\in \mathcal {T}$: by Lemma 2.9 (properties of the conditional in complete theories); (4) $LA\in \mathcal {T}$ iff $A\in \mathcal {T}$: by A4 and the fact that $\mathcal {T}$ is necessitative. □

Lemma 3.10 (Each $\mathcal {T\in T}^{\boxminus }$ induces an $I^{\boxminus }$ -interpretation)

Let $\mathcal {T}$ be a consistent, complete and strongly non-necessitative theory; and let I be the $\mathcal {T}$ -interpretation built upon $\mathcal { T}$ , as indicated in Definition 3.5. Then, I is an $I^{\boxminus }$ - interpretation.

Proof

Clauses (1)-(3) are proved similarly as in Lemma 3.9. So, let us prove clause (4). As $\mathcal {T}$ is strongly non-necessitative, $\lnot LA\in \mathcal {T}$ for any wff A; hence $LA\notin \mathcal {T}$ by the consistency of $\mathcal {T}$. Finally, I(L A)=F, for any wff A, as was to be proved. □

Before proving completeness, we prove soundness w.r.t. $\blacksquare$ -validity.

Theorem 3.11 (Soundness w.r.t. $\blacksquare$ -validity)

For any $A\in \mathcal {F}$ , if $\vdash _{\text {{\L }m4}}A$ , then $\vDash _{\blacksquare }A$.

Proof

Let $I\in I^{\blacksquare }$. It is obvious that I validates A1-A5 and MP. □

Next, we turn into the proof of completeness. Firstly, we record two easy but important facts about necessitives in Łm4.

Proposition 3.12 (No theorems of necessitive form)

Let A be any wff. Then, LA is not a theorem of Łm4.

Proof

Let A be any wff and $I\in I^{\boxminus }$. Then, I(L A)=F and so, $\nvdash _{\text {{\L }m4}}A$ by Theorem 3.11. □

An immediate corollary of Proposition 3.12 is the following:

Proposition 3.13 (Nec does not preserve $\blacksquare$ -validity)

The rule necessitation (Nec), that is,

$$A\Rightarrow LA $$

does not preserve $\blacksquare$ -validity (Nec does not hold in Łm4).

Proof

It is immediate: by Proposition 3.12, there are no theorems of necessitive form in Łm4 (notice that Nec is not even admissible in Łm4). □

Nevertheless, we have:

Proposition 3.14 (Negations of theorems are not possible)

Let A be a theorem of Łm4. Then, $M\lnot A$ is not provable in Łm4.

Proof

Let A be a theorem of Łm4, let $I\in I^{\boxdot }$. By the soundness theorem, I(A)=T (Theorem 3.11). Thus, I(L A)=T, and so, $I(\lnot LA)=F$. Then, $\nvdash _{\text {{\L }m4}}M\lnot A$ follows by definition of M and the soundness theorem. □

Now, the main extension lemma can be proved and, then, the completeness theorem.

Lemma 3.15 (Main extension lemma)

Let $\mathcal {T}$ be a theory and A a wff such that $A\notin \mathcal {T}$ . Then, there is a consistent and complete theory Θ such that $\mathcal {T}\subseteq {\Theta }$ and A∉Θ. Moreover, Θ is either necessitative or else strongly non-necessitative.

Proof

Assume the hypothesis of Lemma 3.15. By Lemma 2.10, there is a consistent and complete theory Θ such that $\mathcal {T}\subseteq {\Theta }$ and A∉Θ. Now, let $p_{i}\in \mathcal {P}$. By propositions 3.12 and 3.14, neither $L(p_{i}\rightarrow p_{i})$ nor $\lnot L(p_{i}\rightarrow p_{i})$ are theorems of Łm4, but as Θ is consistent and complete, either (1) $L(p_{i}\rightarrow p_{i})\in {\Theta }$, or (2) $\lnot L(p_{i}\rightarrow p_{i})\in {\Theta }$, but not both. Suppose (1) $L(p_{i}\rightarrow p_{i})\in {\Theta }$ and let A be any wff. By A4 and A5, A∈Θ iff L A∈Θ. So, Θ is necessitative. But, on the other hand, suppose (2) $\lnot L(p_{i}\rightarrow p_{i})\in {\Theta }$. As $p_{i}\rightarrow p_{i}\in \mathcal {T}$, $\lnot L\lnot A\in {\Theta }$ (for any A) follows by t5; hence MA, by definition of M and, consequently, Θ is strongly non-necessitative. □

Theorem 3.16 (Completeness w.r.t. $\blacksquare$ -validity)

For any A, if $\vDash _{\blacksquare }A$ , then $\vdash _{\text {{\L }m4}}A$.

Proof

We prove the contrapositive of the claim. Suppose $\nvdash _{\text {{\L }m4}}A$ and let Łm4 be the set of its theorems. By Lemma 3.15, there is a consistent and complete theory $\mathcal {T}$ such that $A\notin \mathcal {T}$ . Moreover, $\mathcal {T}$ is either necessitative or strongly non-necessitative. Therefore, by Lemma 3.9 and Lemma 3.10, $\mathcal {T}$ induces a $\blacksquare$-interpretation I such that I(A)≠T. Consequently, $\nvDash _{\blacksquare }A$ by Definition 3.4, as was to be proved. □

The logic Łm4 has been axiomatized following Lemmon’s formulation of Łukasiewicz’s 4-valued modal logic (cf. Definition 2.3). And, as we have just seen, Łm4 is sound and complete w.r.t. the bivalent semantics defined in this section. Therefore, these bivalent semantics determine (or characterize) Łukasiewicz 4-valued modal logic. Nevertheless, we shall put in correspondence the bivalent semantics and Łukasiewicz’s matrix by proving that for each necessitive interpretation invalidating a given formula, there is a corresponding interpretation in Łukasiewicz’s matrix falsifying the same formula.

4 The Bivalent Semantics and the Matrix MŁm4

Let us first define (our version of) Łukasiewicz’s matrix MŁm4 (cf. [5] and [18]).

Definition 4.1 (The matrix MŁm4)

The matrix MŁm4 is the structure (V, $D,f_{\rightarrow },f_{\lnot },f_{L})$ where V={0,1,2,3} and it is partially ordered as shown in the following diagram:

D={3}, and $f_{\rightarrow }$, $f_{\lnot }$ and f _L are defined according to the following tables:

V is the set of (truth) values and D is the set of designated values. The notions of an MŁm4-interpretation, MŁm4-validity and preservation of MŁm4-validity by a rule of derivation are defined in the standard way. That is, an MŁm4-interpretation is a function from $\mathcal { F}$ to V, according to the functions $f_{\rightarrow }$, $f_{\lnot }$ and f _L as defined above; A is MŁm4-valid (in symbols, $\vDash _{\text {M {\L }m4}}A$) iff I(A)∈D for all MŁm4-interpretations I; a rule of derivation $A_{0}\& A_{1}\& ,...,A_{n}\Rightarrow B$ preserves MŁm4-validity (in symbols, $\{A_{0},A_{1},...,A_{n}\}\vDash _{\text {M{\L }m4}}B$) iff, for all MŁm4-interpretations I, I(B)∈D if I(A _i )∈D for each A _i (1≤i≤n). Finally, for any set of wffs Γ and MŁm4-interpretation I, $I({\Gamma } )=\inf \{I(A):A\in {\Gamma } \}$.

We note the following remark on the definition just stated.

Remark 4.2 (On the notation of MŁm4)

Łukasiewicz’s tables are usually presented by pairs of zeros and ones: 00,01,10,11, which correspond to 0,1,2 and 3 in Definition 4.1, respectively. Instead, Łukasiewicz used 0,3,2 and 1 for 00,01,10 and 11, respectively. (The notation in Łm4 is chosen because it is easier to use with the tester in [6], in case the reader needs one.) For the reader’s convenience, we record the tables for ∧, ∨ and M (cf. Definition 2.3):

In the following lemma, it is shown how to define an MŁm4-interpretation for each necessitive interpretation.

Lemma 4.3 (Corresponding MŁm4-interpretations to $\blacksquare$ -interpretations)

Let $I\in I^{\blacksquare }$ . Then, there is a MŁm4-interpretation IŁ such that for any $A\in \mathcal {F}$ , (1) IŁ (A)∈{3,2} if I(A)=T ; and (2) IŁ (A)∈{0,2} if I(A)=F.

Proof

Let $I\in I^{\blacksquare }$. We define a MŁm4-interpretation IŁ as follows: for each $p_{i}\in \mathcal {P}$, we set (i) IŁ (p _i )=3 iff I(p _i )=T; (ii) IŁ (p _i )=0 iff I(p _i )=F. Then, we prove (1) and (2) by induction on the length of A. We have to consider the following cases: (a) A is a propositional variable; (b) A is of the form $\lnot B$ ; (c) A is of the form $B\rightarrow C$; (d) A is of the form LB. Now, case (a) follows from the definition of IŁ, and concerning cases (b) and (c), it is easy to prove the following: IŁ (B)∈{3,2} iff I(B)=T and IŁ (B)∈{0,2} iff I(B)=F. Let us prove case (cii) as way of an example (H.I abbreviates hypothesis of induction).

Case (cii): IŁ$(B\rightarrow C)\in \{0,2\}$ iff $I(B\rightarrow C)=F$. We have IŁ$(B\rightarrow C)\in \{0,2\}$ iff (by MŁm4) IŁ (B)∉{0,2} and IŁ (C)∈{0,2} iff (H.I) I(B)=T and I(C)=F iff (definitions 3.1 and 3.2) $I(B\rightarrow C)=F$. But in order to prove case (d), we have to separately consider $\boxdot$-interpretations and $\boxminus$-interpretations.

Case (d): $\boxdot$-interpretations. Suppose that the function $I\in I^{\blacksquare }$ we are considering is a ⊡-interpretation. (di) Let I(L B)=T. By Definition 3.1, I(B)=T, hence IŁ (B)∈{3,2} (by H.I) and finally, IŁ (L B)∈2 (by MŁm4). (dii) Let now I(L B)=F. By Definition 3.1, I(B)=F, hence IŁ (B)∈{0,2} (by H.I) and so, I Ł (L B)∈{0,2} (by MŁm4). $\boxminus$-interpretations. Suppose that the function $I\in I^{\blacksquare }$ we are considering is a $\boxminus$ -interpretation. Then, case (di) (I(L B)=T) cannot arise since I(L A)=F for any wff A. (dii) Let I(L B)=F. We have I(L B)=F iff (by Definition 3.2) I(B)=T or I(B)=F iff (by H.I) IŁ (B)∈{3,2} or IŁ (B)∈{0,2} iff (by MŁm4) IŁ (L B)∈{0,2}. □

By using Lemma 4.3, it is easy to prove that for each necessitive interpretation invalidating a given formula, there is a MŁm4-interpretation invalidating the same formula, whence completeness w.r.t. M Łm4-validity follows.

Theorem 4.4 (Completeness w.r.t. MŁm4-validity)

For any $A\in \mathcal {F}$ , if $\vDash _{\text {M{\L }m4}}A$ , then $\vdash _{ \text {{\L }m4}}A$.

Proof

Suppose $\nvdash _{\text {{\L }m4}}A$. By the completeness theorem w.r.t. $\blacksquare$-validity (Theorem 3.16), there is some $I\in I^{\blacksquare }$ such that I(A)≠T. So, I(A)=F. By the lemma just proved (Lemma 4.3), there is some Łm4-interpretation IŁ such that IŁ (A)∉{3,2} and IŁ (A)∈{0,2}. Consequently, IŁ (A)=0. That is, $\nvDash _{\text {M{\L }m4}}A$. □

The section is ended with a proof of the “strong” soundness and completeness, but before, let us note the following remark.

Remark 4.5 (Soundness w.r.t. MŁm4-validity)

As we have just seen, for any wff A not provable in Łm4, there is a MŁm4-interpretation IŁ invalidating it. On the other hand, it is straight-forward to check that all axioms of Łm4 are MŁm4-valid and that MP preserves MŁm4-validity. Therefore, we have: (soundness w.r.t. MŁm4-validity): if $\vdash _{\text {{\L }m4}}A$, then $\vDash _{\text {M{\L }m4}}A$.

Strong soundness and completeness are immediate. Actually, these properties can be proved for Łm4 similarly as they are proved for classical propositional logic CL (axiomatized by A1-A3 and MP, for example), once the simple theorems have been previously proved.

Definition 4.6 (Consequence relations)

For any set of wffs Γ and wff A, we set (1) ${\Gamma } \vdash _{\text {{\L }m4}}A$ is understood in the standard sense (cf. Definition 2.2); (2) ${\Gamma } \vDash _{\blacksquare }A$ iff I(A)=T if I(Γ)=T for all $I\in I^{\blacksquare }$ (cf. definitions 3.3 and 3.4); (3) ${\Gamma } \vDash _{ \text {M{\L }m4}}A$ iff I(A)=3 if I(Γ)=3 for any MŁm4-interpretation I (cf. Definition 4.1); (4) ${\Gamma } \vDash A$ iff ${\Gamma } \vDash _{\blacksquare }A$ (or, equivalently, ${\Gamma } \vDash _{\text {M {\L }m4}}A$).

Then, we prove:

Theorem 4.7 (Strong soundness and completeness)

For any set of wffs Γ and wff A, we have (1) if ${\Gamma } \vdash _{ \text {{\L }m4}}A$ , then ${\Gamma } \vDash A$ ; (2) if ${\Gamma } \vDash A$ , then ${\Gamma } \vdash _{\text {{\L }m4}}A$.

Proof

(1) It is immediate: by the (simple) soundness theorem (cf. Theorem 3.11 and Remark 4.5) the axioms are [$\blacksquare$ / MŁm4]-valid and MP preserves [$\blacksquare$ / MŁm4]-validity. (2) Suppose ${\Gamma } \vDash A$ and let Γ={B ₁,...,B _n }. It is clear that $\vDash B_{1}\rightarrow (...\rightarrow (B_{n}\rightarrow A)...)$. Then, we have $\vdash _{\text {{\L }m4}}B_{1}\rightarrow (...\rightarrow (B_{n}\rightarrow A)...)$ by the (simple) completeness theorem (cf. Theorem 3.16 and Theorem 4.4); hence, ${\Gamma } \vdash _{\text {{\L }m4}}A$. □

5 Concluding Remarks

We think that the semantics presented in this paper clarify what Łukasiewicz’s system does really mean and where its difficulties really come from. The paper is closed with two remarks. The first one relates our results to a theorem by Lemmon in his outstanding works [8] and [9]; the second one states that the difficulties raised by Łm4 can (and in fact have been) surmounted.

5.1 On the Systems PC and E

Consider the following axioms

$$\begin{array}{@{}rcl@{}} &&\text{a1. } A\rightarrow LA \\ &&\text{a2. } MA \end{array} $$

Under the head “Three degenerate systems, intersection results” , in Section 5 of [9], Lemmon investigates Łukasiewicz’s logic Łm4 along with the system PC and E that can be axiomatized as follows:

PC: Łm4 plus a1.

E: Łm4 plus a2.

Each one of the three systems is endowed with an algebraic semantics. The system PC is “degenerate” in the sense that it collapses into classical propositional logic; and E is “degenerate” in the sense that $LA\leftrightarrow F$ is a theorem (F is a falsity constant syntactically equivalent to the negation of any given theorem). However, it is not explained why Łm4 can be named “degenerate” and although this is not the place to discuss the question, we cannot but remark that neither E nor Łm4 can in our opinion be labelled at all “degenerate” (cf. in this respect the comments by Mortensen in [16] about the relationship between possibilism and truth-functional modal logic). Anyway, the topic is mentioned here for two reasons. The first one is that it may be worth noting that a semantics has been provided above for PC and E. Consider the following axioms

$$\begin{array}{@{}rcl@{}} &&\text{a3. } L(A\rightarrow A) \\ &&\text{a4. } \lnot L(A\rightarrow A) \end{array} $$

Notice that a3 and a4 instead of a1 and a2 suffice for axiomatizing PC and E, respectively. Then, it is obvious that PC is sound and complete w.r.t. $\boxdot$-validity, being this notion defined in the set $I^{\boxdot }$ (the set of all necessitative interpretations) similarly as $\blacksquare$ -validity was defined given the set $I^{\blacksquare }$ (cf. definitions 3.1, 3.3 and 3.4). On the other hand, it is not less clear that E is sound and complete w.r.t. $\boxminus$-validity defined in the set $I^{\boxminus }$ similarly as $\boxdot$-validity has just been defined (cf. Definition 3.2). The second reason why this topic is mentioned is that the facts just reported and the general results in the present paper conform to the following theorem proved by Lemmon: $\vdash _{\text {{\L }m4}}A$ iff both $\vdash _{\text {PC}}A$ and $\vdash _{\text {E}}A$ (cf. [9], Theorem 60, p. 216).

5.2 The Logic ŁB4

The logic ŁB4 defined in [14] is the logic characterized by modifying the matrix MŁm4 as follows: the tables for $\lnot$ and L are changed by the following ones:

ŁB4 is a strong and rich 4-valued modal logic without “Łukasiewicz-type” modal paradoxes.