4. Non-classical logics

Classical (modern) logic consists of propositional and predicate logic. Non-classical logics are either extensions or alternatives to classical logic. The former expand it by enriching its language, and the latter reject some of its basic principles replacing them with others. The family of non-classical logics is large. In this part we will briefly consider two of the most important groups of non-classical logics – modal and three-valued logics.

4.1 Modal logic

Modal operators

Modal logic is an extension of classical propositional and predicate logic, which is obtained from the latter by adding so-called modal operators to their symbolic languages. There are usually two modal operators symbolized with “□” and “◊”. Depending on the semantics of the respective modal logic, they have different meanings – “necessarily” and “possibly”; “obligatory” and “permitted”; “it was” (“it will be”), “it always was” (“it always will be”); and others.

Alethic1 modal logic is the oldest of modal logics and often it is what is meant when talking about modal logic. In it, the operator “□” means “necessarily” and the operator “◊” means “possibly”. For example, the sentence “Everything is necessarily identical with itself” may be symbolized by “□∀x x=x” and the sentence “It is possible that Paris is not the capital of France” by “◊¬Fab”, where “a” corresponds to “Paris”, “b” to “France”, and “F” to “…is the capital of…”.

In deontic modal logic, the operator “□” is interpreted as “it is obligatory that”, “ought”, etc., and “◊” is interpreted as “permissible”, “allowed”, etc. For example, the sentence “The Good Samaritan is obliged to help the wounded on the road” may be represented in its symbolism by “□Fab”, where “a” and “b” correspond to “the Good Samaritan” and “the wounded on the road”, respectively, and “F” to the two-place predicate “…helps…”. The formula “◊¬Fab” will then symbolize the sentence “It is permissible for the Good Samaritan not to help the wounded on the road”. “Prohibited” is represented by either “¬◊” (“impermissible”) or by “□¬” (“ought not”).

In temporal modal logic there are two pairs of modal operators – one for the future and one for the past. If we use as indices “p” and “f” for “past” and “future”, respectively, “◊p” will correspond to “it was”, “□p” to “it always was”, “◊f” to “it will be”, and “□f” to “it always will be”. Then if “a” symbolizes “Socrates”, the formula “□f ◊p∃x x=a” will symbolize the true sentence “Socrates will have always existed”. The sentence is true because “∃x x=a” says that there is something that is identical with Socrates, which is equivalent to “Socrates exists”. Thus, the meaning of “◊p∃x x=a” is “There was a moment in the past when Socrates existed”, or in short “Socrates existed”. Accordingly, the meaning of “□f ◊p∃x x=a” is “It will always be a fact that Socrates existed”, or in short “Socrates will have always existed”. Similarly, we can see that “◊f □p∃x x=a” symbolizes the false sentence “There will be a moment when Socrates have always existed”.

In epistemic modal logic, “□” is interpreted as “believes that ...” or “knows that ...”. Knowledge and belief are related to some (knowing or believing) subject, so in the epistemic logic each modal operator has an index that indicates the subject in question (say, “□n”, “◊n”, etc.). Let us interpret “□n” as “n knows that”. If “a” and “b” symbolize “Socrates” and “God”, respectively, “□a∃x(x=b)” will symbolize the sentence “Socrates knows that God exists”. If again the epistemic modal logic in question deals with knowledge, not with belief, the meaning of the other modal operator (“◊n”) can be conveyed by the words “the knowledge of n does not exclude that …” or “according to n’s knowledge, it is possible that”. So, for example, “◊a∃x(x=b)” will symbolize the sentence “Socrates does not exclude the existence of God”.

We will call “□” and “◊” the strong and the weak modal operator, respectively. Regardless of the modal logic (whether it is alethic, deontic, temporal, or epistemic), there is a logical connection between the strong and the weak modal operator analogous to the relationship between the quantifiers in predicate logic. As with the latter, this connection allows one of the two modal operators to be reduced to the other. Let us look at it.

Suppose first that □ and ◊ are interpreted as “necessarily” and “possibly”. Then ¬□α corresponds to “α is not necessary” (for example, “the universe is not infinite by necessity”). But this is like saying “It is possible that not-α” (◊¬α) (“It is possible for the universe to be not infinite”). Thus, there is an equivalence between the modal operators in alethic modal logic analogous to the equivalence between ¬∀xα and ∃x¬α in predicate logic:

¬□α ⇔ ◊¬α

In deontic modal logic, ¬□α corresponds to “It is not obligatory that α”. The last sentence has the same meaning as “It is permitted that not-α” (◊¬α). If I am not obliged to do something, then I am allowed not to do it; and vice versa: if I am allowed not to do something, I am not obliged to do it. Therefore, the same equivalence applies to deontic modal logic.

This equivalence is also valid in temporal modal logic with respect to both pairs of modal operators – for the past and for the future. ¬□pα corresponds to a sentence of the form “α was not always a fact”, which has the same meaning as “It was once non-α” (◊p¬α). (If the Earth has not always existed, then there was a time when the Earth did not exist, and vice versa.) Similarly, “α will not always be a fact” (¬□f α) has the same meaning as “There will be a time when α will not be a fact” (◊f ¬α). (If the Earth will not always exist, there will come a time when the Earth will not exist, and vice versa).

Since α stands in the place of an arbitrary formula, if we specify it as an arbitrary negation (i.e. if we replace “α” with “¬α”), from the above scheme (¬□α ⇔ ◊¬α) we get ¬□¬α ⇔ ◊¬¬α, from which, removing the double negation, we obtain an equivalence scheme by which the weak modal operator may be defined by the strong one and negation:

¬□¬α ⇔ ◊α

Intuitively, not being true that non-α is necessary is the same as α being possible; not being obliged not to do something is the same as being allowed to do it; not being true that non-α was always a fact is the same as α being a fact in some past moment; not being true that non-α will always be a fact is the same as α becoming a fact in some future moment.

The logical equivalence between ¬□¬α and ◊α implies that their negations ¬¬□¬α and ¬◊α are also equivalent and, since ¬¬□¬α is equivalent to □¬α, we obtain the following equivalence scheme:

□¬α ⇔ ¬◊α

To be necessarily not a fact is to be impossible; to be obliged not to do something is to be forbidden to do it; always being not a fact in the past (in the future) is the same as never being a fact in the past (in the future).

Finally, substituting ¬α for α in the above equivalence scheme and removing the double negation, we obtain a fourth relationship between the modal operators, which allows □ to be expressed by ◊ and negation:

□α ⇔ ¬◊¬α

To say that α is necessary is to deny the possibility for it to be false; to say that someone is obliged to do something is to say that he (she) is not allowed not to do it; to say that something has always been a fact is to say that there has not been a moment in which it was not a fact; and similarly for the future.

The following table summarizes the relationship between the strong and the weak modal operator:

¬□α ⇔ ◊¬α ¬□¬α ⇔ ◊α □¬α ⇔ ¬◊α □α ⇔ ¬◊¬α
Alethic
not necessarily
⇕
possibly not 		not necessarily not
⇕
possibly 		necessarily not
⇕
not possibly 		necessarily
⇕
not possibly not
Deontic
not obliged to
⇕
permitted not to 		not obliged not to
⇕
permitted to 		obliged not to
⇕
not permitted to 		obliged to
⇕
not permitted not to
Temporal
it not always was
⇕
once it was not 		it not always was not
⇕
it was 		it always was not
⇕
it is not true that it was 		it always was
⇕
it is not true that once it was not
it not always will
⇕
sometime it will not 		it not always will not
⇕
it will 		it always will not
⇕
it is not true that it will 		it always will
⇕
it is not true that sometime it will not

From the fact that the relationship between modal operators is completely analogous to the relationship between quantifiers, it follows that modal operators will behave exactly like quantifiers when there is a series of operators on one side of which there is a negation. Then the negation can pass on the other side of the series with each operator switching to the opposite one (the strong becoming weak, and vice versa). For example, no matter how we interpret the operators, the expression “¬□□◊□” will have the same meaning as “◊◊□◊¬”.

Syntax of modal logic

The only difference between the symbolic languages of modal logics and those of classical propositional or predicate logic is that the former have two additional symbols – the modal operators □ and ◊. (In temporal modal logic, the operators are four). From a syntactic point of view, modal operators behave exactly like the logical connective of negation – just like it, they are placed at the beginning of an arbitrary formula α, resulting in a new formula (□α or ◊α). (We have seen that depending on the type of modal logic, □α expresses different things – “necessarily α”, “it is obligatory that α”, etc. – but this is a matter of semantics, not syntax.)

For the strict formulation of the syntax of modal propositional logic as well as the syntax of modal predicate logic, it is sufficient to add the following single syntactic rule to the syntactic rules of propositional logic (see) and the syntactic rules of predicate logic (see):

If α is a well-formed formula, then □α and ◊α are also well-formed formulas.2

By this new rule and the other syntactic rules, we can conclude, for example, that “□∀x(Fxa→◊¬◊Gx)” is a well-formed formula of the modal predicate logic, while “∃x□(Fxa → ◊Gx ∨ Ha)” is not such, or that “□(¬p→◊¬□q)” is a well-formed formula of the modal propositional logic, while “□(p→◊q ∨ ¬r)” is not such.

Semantics of modal logic

There are two factors that determine whether a sentence is true or false. One is its meaning, which depends on the meaning of the words and expressions of which it is composed, and the other is the situation in the world. Take, for example, the sentence “Earth is a planet”. It is true, and its truth is determined, first, by the meaning of the words in it – by the fact that the word “Earth” (as opposed to, for example, the word “Socrates”) denotes the planet Earth and by the fact that the predicate “…is a planet” is true of the planets. If the meaning of the word “Earth” was the same, but the meaning of the word “planet” was such that it was true not of the planets but, for example, of those and only those things that have a rectangular shape, the sentence would be false. The second factor that determines the truth of this sentence is that the state of affairs in the world is such that the Earth is a planet. If the situation were different, it could be false even if the words of which it is composed had the same meaning.

The interpretation of the non-logical symbols in propositional or predicate logic (“p”, “q”,… as statements; “F”, “G”,… as predicates; “a”, “b”,… as singular terms) fixes one of the two factors – the meaning, while the other, the state of affairs in the world, classical logic leaves as it is. When the meaning of the symbols is fixed by their interpretation, the state of affairs in the world automatically determines the truth values of the formulas. So, in classical logic, the interpretation of formulas varies, while the situation in the world is constant. On the contrary, in modal logic the second factor also varies, as different alternative states of affairs are considered. The need for this is rooted in the modal concepts themselves. Let us see why.

A sentence of the form “It is possible that α” may be true when α itself is false. For example, the sentence “It is possible that Berlin is not the capital of Germany” is true (this is at least logically possible) although Berlin is in fact the capital of Germany. Similarly, a sentence of the form “It is necessary that α” may be false when α is true. For example, “It is necessary that Berlin is the capital of Germany” is a false sentence although Berlin is the capital of Germany. The reason for the differences in truth value between α, on the one hand, and □α and ◊α, on the other hand, is that the truth or falsity of the latter depends not only on the situation in the actual world but also on the situation in alternative possible worlds. For “It is possible that α” to be true, it is sufficient to exist at least one possible world in which α is true (even though α may be false in the real world). “It is possible that Berlin is not the capital of Germany” is true because we can imagine a possible world in which another city is the capital of Germany. Similarly, for the sentence “It is necessary that α” to be true it is not enough α to be a true sentence – it must be true in every possible world. “Berlin is the capital of Germany by necessity” is a false sentence because, although Berlin is in fact the capital of Germany, we can easily imagine many possible worlds in which this is not the case.

In the semantics of classical (propositional or predicate) logic, sentences receive truth values only with respect to the actual situation, i.e. only with respect to the actual world, which is why in this semantics there is no talk of possible worlds at all. On the contrary, the semantics of modal logic is often called possible worlds semantics because for sentences such as “Necessarily α” and “Possibly α” to receive a truth value, the sentence α must receive a truth value in every possible world – in fact, in every possible world in a set of possible worlds that we imagine to be the set of all possible worlds. We will denote that set by “W”. W is different in different contexts or modal logics. A sentence of the form “Necessarily α” is true in any possible world of W (the actual world is only one of them) if and only if α is true in every world of W; and a sentence of the form “Possibly α” is true in any possible world of W if and only if α is true in at least one world of W. So, the following semantic rule is basic for modal logics:

(1) □α is true in a possible world of W if and only if α is true in each world of W.
◊α is true in a possible world of W, if and only if α is true in at least one world of W.

Adding this semantic rule to the semantic rules of propositional or predicate logic, we obtain a certain semantics for modal propositional or modal predicate logic. An important difference between semantics of classical logic and semantics of modal logic is that in the latter the sentences receive truth values always with respect to some possible world from W. The actual world is just one of them.

A few words about the concept of a possible world. We can think of it as maximally determined possible states of affairs. As a rule, a possible state of affairs is not maximally determined. Such is, for example, that Berlin is not the capital of Germany (a false one). It is determined in terms of which is the capital of Germany but not determined in terms of everything else. We may increase its determinedness by adding, for example, that the snow is white in it. We may continue making it more definite by saying, for example, that (unlike the actual situation) Bonn is larger than Berlin in it, etc., etc. To become a possible world, a state of affairs must become as definite as possible – it must be such that each sentence in the language is either true or false in it.

Essentially, the possible worlds semantics defines the notion of necessity as truth in every possible world and the notion of possibility as truth in at least one possible world. This shows the reason for the complete analogy between the relationship between quantifiers (the synonymy of “¬∀x” and “∃x¬”, etc.) and the relationship between modal operators (the synonymy of “¬□” and “◊¬”, etc.). Modal operators are like quantifiers that quantify not over the things in the world (the universe of discourse), but over the possible worlds in the set of all possible worlds. Through the universal quantifier we affirm that something is true of every object of the discourse universe, and through the strong modal operator (the operator of necessity in the alethic modal logic) we affirm that something is true in every world of the set of all possible worlds. Similarly, through the existential quantifier, we affirm that something is true of at least one thing in the universe of discourse, and through the weak modal operator (that of possibility in alethic modal logic) we affirm that something is true in at least one world of the set of all possible worlds.

As we know from classical logic, the concepts of logical inference and logical equivalence can be reduced to the concept of logical validity (see): from α logically follows β if and only if α→β is logically valid (tautology in propositional logic), and α is logically equivalent to β if and only if α↔β is logically valid. So, to define the concepts of logical inference and logical equivalence, it is sufficient to define the concept of logical validity. The latter is defined as follows:

A modal logic’s formula is logically valid if and only if regardless of what the set of the possible worlds W is and how we interpret the formula’s non-logical symbols (“F”, “p”, “a”, etc.), it is always true in every possible world of W.

For simplicity (and because its semantics is more unproblematic) we will adhere to the modal propositional logic. Its non-logical symbols are propositional letters (“p”, “q”, ...), whose interpretation in a possible world consists in giving them certain truth values. This corresponds to the fact that they represent certain sentences, which must be either true or false in each possible world. According to the above definition of logical validity, a formula will be logically valid if no matter what the set of possible worlds W is and what truth values are given to the propositional letters in the different possible worlds, in each of them the formula will be true.

Any modal logic’s formula that has the form of a tautology will be logically valid. For example, whatever formula α is, the formula α→α will be logically valid because regardless of the truth value of α in a possible world, α→α will be true in it. This shows that α→α will be true in each world of any set of possible worlds W regardless of what truth values the propositional letters involved in α are given in any world of W. α (and so α→α) may contain modal operators but this does not affect the above argument; it is important that the formula has the form of a tautology as a whole, it does not have to be a formula of propositional logic.

In modal propositional logic, logically valid are also many other formulas that do not have the form of a tautology – their validity is related to the modal operators. We will introduce a general method by which we will check whether a modal formula is valid. The method uses diagrams and works as follows. To check whether a formula is logically valid, we assume that it is not valid, i.e. that there is a set of possible worlds W and truth values given to the propositional letters in the different worlds of W such that the formula becomes false in one of the worlds. We will draw certain conclusions from this assumption. If we come to a contradiction, this will prove that the assumption is not possible, which means that the formula is true in each world of any set of possible worlds W for any interpretation of the propositional letters, i.e. that it is logically valid. If we do not come to a contradiction, we will come to a model of the negation of the formula, i.e. we will find a set of possible worlds W and a possible world where the formula is false for some interpretation of the propositional letters. This will prove that the formula is not logically valid.

Here is an example. The diagram below is a proof that any formula of the form □α→α (“If something is necessary, it is a fact”) is logically valid, i.e. that α is a logical consequence of □α.

The rectangle corresponds to some world of some set of possible worlds W denoted by “w1”. We assume that the formula □α→α is false in this world (for some truth values of the propositional letters in the worlds of W). Then the negation of the formula is true in w1, which is why we have written ¬(□α→α) on the first line. Generally, the sentences we write in the rectangle of a world are such that we know that they are true in it. The second formula is logically equivalent to the first by Imp3, so it must also be true in w1. From the truth of □α∧¬α, by S, we infer that □α and ¬α are also true in w1 (third and fourth line). Since the sentence □α (“Necessarily α”) is true in w1, it follows from the semantic rule (1) introduced above that α is true in every possible world of W and therefore also in w1, which is why we write α on the bottom line. α, however, contradicts ¬α. Since there can be no contradiction in any possible world, the initial assumption (that there are a set of possible worlds and a world in it in which □α→α is false) is impossible. Therefore, any formula of the form □α→α is logically valid.

As another example, we will show that the formulas of the type □α→□□α are logically valid, i.e. that from the fact that something is necessary follows that it is necessarily necessary. The diagram below is a proof of this:

We assume that in some possible world w1 the negation of □α→□□α is true, from which, as in the previous example, it follows that □α and ¬□□α are true in w1. By the relationship between the modal operators, “¬□” in ¬□□α can be replaced by “◊¬”, as a result of which we get that ◊¬□α is true in w1 (the bottom line). Since ◊¬□α is true in w1, it follows from semantic rule (1) that there must be a possible world (let us call it “w2”) in which ¬□α is true. So, we draw a second rectangle for the world w2 and at the top we write ¬□α. From the relationship between the modal operators, ¬□α is equivalent to ◊¬α and the latter must be true in w2. By the semantic rule (1), from the truth of ◊¬α in w2 we infer that there is a possible world (let us call it “w3”) in which ¬α is true. Accordingly, we draw a new rectangle and write ¬α at the top of it. In w1, however, □α is true, from which, by the semantic rule (1), it follows that α is true in every possible world. In particular, α must true in w3, which contradicts the truth of ¬α there. We came to a contradiction, which completes the proof.

There is something very similar between this procedure and the proof procedure of predicate logic (see 3.5 Proof procedure). In the latter, we used existential instantiations to introduce new constants and then we applied universal instantiations to them. Similarly, in the introduced diagram method, the truth of ◊α in a given world allows us to introduce a new world in which α is true, and then the truth of □β in any world allows us to infer the truth of β in the introduced world. This similarity between the two procedures is not accidental. We have already seen that the strong and the weak modal operators behave like quantifiers over the set of all possible worlds.

The semantics we obtain through the semantic rule (1) is not the only semantics of modal logic. This is the simplest semantics, which is usually considered to correspond best to the alethic modalities, i.e. to the concepts of necessity and possibility, but even in the alethic modal logic there are other semantics in respect to which some of the logically valid formulas for the introduced semantics cease to be valid, and others which are not valid for it become valid. Furthermore, this semantics is not suitable for deontic and temporal modal logics.

The semantic rule (1) can be generalized so that it becomes applicable to all modal logic semantics. This is done by introducing the so-called accessibility relation, which we will denote by “R”. This is a relation between two possible worlds, which we do not need to give a certain meaning to yet. The only thing we will assume is that some possible worlds are in this relation to some possible worlds or to themselves, and others are not. When a world is in the accessibility relation to some world, we will say that the latter is accessible from the former. To take into account the accessibility relation, we will modify the semantic rule (1) as follows. □α will be true in a possible world w1 not simply when α is true in every possible world, but when it is true in every possible world accessible from w1; accordingly, ◊α will be true in the world w1 not simply when there is a possible world in which α is true, but when there is a possible world accessible from w1 in which α is true. Here is the generalized semantic rule:

(2) □α is true in a possible world w1 of W if and only if α is true in every world of W that is accessible from w1 (i.e. in every world w such that w1Rw).
◊α is true in a possible world w1 of W if and only if α is true in at least one world of W that is accessible from w1 (i.e. in at least one world w such that w1Rw).

The above semantic rule is a generalization of the semantic rule (1) because (1) is obtained from (2) when the accessibility relation is such that every possible world of W is in it to every world of W (including itself). Then the relation does not restrict the worlds in which to look at the truth value of α in order to determine the truth value of □α or ◊α in a given world – we should take into account all worlds of W. This is way in the first semantic rule there is no talk of the accessibility relation at all.

In “3.5 Proof procedure” we spoke about the formal properties of relations; such as reflexivity, symmetry, transitivity, etc. Here is another formal property: if a relation is such that each element of a given set is in the relation with each element of the set (including itself), the relation is said to be universal in that set. Therefore, the semantic rule (1) is obtained from the semantic rule (2) by assuming that the accessibility relation is universal in the set of possible worlds W.

By imposing different formal properties on the accessibility relation, we obtain different semantics that determine in different ways which sentences are logically valid and which are not. For example, for all formulas of the type □α→α to be valid, the accessibility relation R must be reflexive; for the formulas of the type □α→□□α to be valid, R must be transitive; etc. We have proved above that both types of sentences are logically valid because we have in fact assumed that R is universal (that each world is accessible from each world). When a relation is universal, it is also reflexive and transitive. However, if R is reflexive but not transitive, □α→α will continue to be logically valid, but not □α→□□α. Conversely, if R is transitive but not reflexive, the second type of sentences will be logically valid, but not the first.

It can be proved that when R is universal, the logically valid sentences are exactly the same as when R is simultaneously reflexive, symmetric and transitive. Relations of the latter type are called equivalence relations. So, the universal accessibility relation and the equivalence accessibility relation define the same semantics of modal logic, although the two formal properties are not equivalent: every universal relation is an equivalence relation, but not the other way around – some equivalence relations are not universal.

Defining a given semantics of modal propositional logic by determining the formal properties of the accessibility relation leads to determining an infinite set of logically valid formulas for this semantics. We can think of these sets of formulas as systems of modal logic. For historical reasons, some of them have received their own names.

The set of all logically valid formulas when the accessibility relation is an equivalence relation (or a universal relation), is called S5.

The set of all logically valid formulas when the accessibility relation is reflexive and transitive (but not necessarily symmetric) is called S4. S4 is a proper subset4 of S5. The reason for the latter is that any logically valid formula for a reflexive and transitive accessibility relation is logically valid also when the accessibility relation is an equivalence relation (or universal relation) but not the other way around. For example, a formula of the type ◊α→□◊α is logically valid when the accessibility relation is universal, but it is not logically valid when R is reflexive and transitive (but necessarily symmetric).

The diagram below shows why a formula of the type ◊α→□◊α (“If something is possible, it is possible by necessity”) is logically valid only if the accessibility relation is symmetric.

We assume that ◊α→□◊α is false in w1, from which (by Imp) it follows that ◊α and ¬□◊α are also true there. From the relationship between modal operators, the last formula is equivalent to ◊□¬α (¬□◊α is equivalent to ◊¬◊α, which is equivalent to ◊□¬α). From the truth of ◊α in w1, it follows that there exists a possible world w2 which is accessible from w1 and in which α is true. We will indicate that a world is accessible from a world by an arrow. That w2 is accessible from w1 is indicated by the arrow from the rectangle of w1 to that of w2. The truth of ◊□¬α in w1 implies that there is a possible world w3 which is accessible from w1 and in which □¬α is true. From here, to arrive at a contradiction, we need to use the formal properties of symmetry and transitivity of the accessibility relation R. Since w3 is accessible from w1, from the symmetry of R, it follows that w1 is also accessible from w3. This is indicated by the arrow from w3 to w1. Since w1 is accessible from w3 and w2 is accessible from w1, by the transitivity of R, it follows that w2 is accessible from w3 (indicated by the arrow from w3 to w2). From the latter fact and the truth of □¬α in w3, we can infer that ¬α is true in w2, which contradicts the truth of α there. We have come to a contradiction, which shows that any formula of the form ◊α→□◊α is logically valid if the accessibility relation is symmetric and transitive (and therefore also if it is universal or an equivalence relation).

The set of all logically valid formulas when the accessibility relation is reflexive and symmetric (but not necessarily transitive) is called B. Like S4, B is a proper subset of S5. S4 and B are two intersecting sets, but neither is a subset of the other – □α→α, for example, belongs to both, □α→□□α only to S4, and α→□◊α only to B.

The diagram below shows why sentences of the form α→□◊α (“If something is a fact, it is necessarily possible”) are logically valid only if the accessibility relation is symmetric.

Assuming that α→□◊α is false in a possible world w1, we infer (by Imp) that α and ¬□◊α are true in it. From the relationship between modal operators, the latter formula is logically equivalent to ◊□¬α. Because of the truth of ◊□¬α in w1, there is a possible world w2 which is accessible from w1 and in which □¬α is true. If we do not assume that the accessibility relation R is symmetric, we will stop here without being able to arrive at a contradiction. Since w2 is accessible from w1, the symmetry of R implies that w1 is accessible from w2. Then, since □¬α is true in w2, ¬α will be true in w1, which contradicts the truth of α in w1. We have thus proved that any sentence of the form α→□◊α is logically valid if the accessibility relation is symmetric.

When the accessibility relation is reflexive, every possible world is accessible from itself. Then from the rectangle of each world we should draw a curved arrow leading back to it. Above, the first use of the diagram method was to prove the validity of the scheme □α→α. In this proof, we tacitly assumed the reflexivity of the accessibility relation (actually, its universality, which includes reflexivity) because from the truth of □α in w1 we concluded that α is true in w1. However, such a conclusion is justified only on the condition that w1 is accessible from itself.

The set of all logically valid formulas when we do not impose any conditions on the accessibility relation is called K. K is a proper subset of each of the above systems. None of the above-mentioned logically valid formulas (except the tautologies) belong to K. To K belong, for example, all formulas of the form □(α→β)→(□α→□β) – they are logically valid without imposing any conditions on the accessibility relation.

The mentioned historical reason for the names of the above sets of formulas or systems is that from the early 20th century, when modal logic emerged, to its middle the possible worlds semantics did not exist and modal logic was developed only in the form of various axiomatic systems. The above names are in fact the names of the axiomatic systems in question. In the 1960s, when the semantics of possible worlds with the accessibility relation between them was formulated ((Hintikka, 1961), (Kripke, 1963a, 1963b)), it turned out that if we impose certain formal properties on that relation, logically valid with respect to the semantics thus obtain become exactly those formulas that are deducible in the previously formulated axiomatic systems!

As for deontic, temporal, and epistemic modal logics, their semantics are also obtained by imposing certain combinations of formal properties on the accessibility relation. For example, according to the standard understanding of time, the accessibility relation in the semantics of temporal modal logic should be transitive and asymmetric, while in the semantics of deontic modal logic it should be transitive and symmetric. To obtain any adequate semantics for these two modal logics, more formal properties are certainly needed but we will stop here. We will end the topic of modal logic with two more philosophical questions concerning alethic modality (the notions of necessity and possibility).

Different kinds of necessity and possibility

Alethic modal logic (modal logic in the narrow sense) interprets the strong and the weak modal operator as “necessarily” and “possibly”, respectively. Necessity and possibility, however, can be understood differently. For example, we could distinguish (without claiming completeness) between logical, physical, and contextual necessity and possibility. The sentence “It is possible that there exists a body moving at a speed greater than the speed of light” is true if “possible” is understood as logically possible but it is false if it is understood as physically possible.

For the semantics of alethic modal logic, we could use the semantic rule (1), which does not mention the accessibility relation. It is often assumed that the semantics obtained in this way largely corresponds to the intuitive understanding of “necessary” and “possible”. The difference between the notions of necessity and possibility will then manifest itself as a difference between the sets of possible worlds W.

When necessity and possibility are understood as logical necessity and possibility, W should include all logically possible worlds. Since it is logically possible that the laws of physics are different from the actual physical laws, and in particular it is possible that they allow motion at a higher speed than the speed of light, in W there must be possible worlds in which some bodies move at such speed. In these worlds the sentence “There is a body moving at a greater speed than the speed of light” will be true, which, according to the semantic rule (1), will make the sentence “It is possible that there exists a body moving at a greater speed than the speed of light” true in every possible world of W and therefore in our possible world.

If we understand “necessary” and “possible” as expressing physical necessity and possibility, W should be the set of all physically possible worlds, i.e. those worlds that have the same physical laws as our world. Many of these worlds will be very different from ours – for example, in some of them the Earth and humans will not exist, etc. The set of all physically possible worlds is a proper subset of the set of all logically possible worlds because a physically possible world is also logically possible but in many of the logically possible worlds the laws of physics (or part of them) will not be the same. In no physically possible world, for example, there is a body that moves at a greater speed than the speed of light. Therefore, among the possible worlds in W there will be no world in which the sentence “There is a body moving at a greater speed than the speed of light” is true, which, according to the semantic rule (1), will make the sentence “It is possible that there is a body moving at a greater speed than the speed of light” false in each world of W, including our possible world. Thus, this sentence becomes false if “possible” is understood as physically possible. From the fact that the physically possible worlds are a proper subset of the logically possible worlds, it follows that everything physically possible is also logically possible but not the other way around – there are states of affairs that are logically possible but physically impossible. For the same reason, everything that is logically necessary is physically necessary but not the other way around – there are states of affairs that are physically but not logically necessary.

Just as physical necessity is weaker than logical necessity, contextual necessity is weaker than physical necessity. By “contextual necessity and possibility” we mean the various ways in which “necessary” and “possible” are used in everyday language. For example, if in some context I say to someone at noon “It will not be possible for me to go to the meeting tonight”, I have in mind various possible developments of the situation from noon to evening that depend on my decisions and actions but not only on them. I make the statement because I believe that in none of these developments of the situation I will go to the meeting tonight. Each of the possible developments corresponds to a multitude of physically possible worlds – unless one believes in miracles, one assumes that every possible development of the situation takes place in accordance with the laws of physics. At the time of making the statement, I do not know what possible world will turn out to be the actual one in the end, but since (in my opinion) the sentence “I will go to the meeting tonight” will be false in all of them, the sentence “It will not be possible for me to go to the meeting tonight” will be true in all of them and so the sentence will be true in the actual world. So, we can assume that in such usages the set of possible worlds W consists of certain physically possible worlds each of which contains one of the possible developments of the situation referred to by the speaker. (One possible development of the situation is contained by many possible worlds as they can differ in various irrelevant details such as the air temperature tonight, etc.) Just as the set of all physically possible worlds is a proper subset of the set of all logically possible worlds, so the various sets of contextually possible worlds are proper subsets of the set of all physically possible worlds. That I do not have in mind all physically possible worlds is clear from the fact that in some of them the Earth, I and the meeting do not exist at all.

Counterfactual conditionals and disposition terms

The so-called counterfactual conditionals can be logically analyzed through contextual necessity and possibility. An example of such a sentence is “If Newton had not discovered the law of universal attraction, someone else would have discovered it”.

Consider the following (semi)symbolic representation of that sentence:

(3) □ (Newton did not discover the law of universal attraction → Someone else discovered the law of universal attraction)

In terms of the possible worlds semantics, (3) tells us that in every possible world of W (think of W as containing every possible human history) it is true that if Newton did not discover the law of universal attraction, someone else discovered it. In other words, in each possible history either Newton or someone else discovers the law. This seems to correspond to the meaning of the initial sentence, so we could assume that any sentence of the type “If A had happened, B would have happened” can be symbolized by “□(α→β)”, where α and β are the corresponding symbolizations of the sentences A and B, and the set of possible worlds W contains all the relevant alternative developments of the situation according to the speaker. Like the example with the sentence “It will not be possible for me to go to the meeting tonight”, W contains only physically possible worlds, but it does not contain all such worlds. For example, we can safely exclude the physically possible worlds in which the Earth or humankind does not exist. So, the involved concept seems to be that of contextual necessity.

Note that counterfactual conditionals cannot be treated as biconditionals, i.e. as non-modal sentences. A biconditional “A→B” is true when its antecedent A is false, and the falsehood of A in “If A had happened, B would have happened” is always assumed – we know that Newton discovered the law of universal attraction but we are talking about the non-factual (but possible) situation in which he did not. If we formalize it as “A→B” (instead of “□(A→B)”), each counterfactual conditional, however obviously false, would turn out to be trivially true.

Modal operators are also required in the logical analysis of the so-called disposition terms – predicates such as “water-soluble”, “fragile”, “cowardly”, etc. There is a direct connection between them and the counterfactual conditionals. That something is soluble in water does not mean that it is dissolved in water or that it will be dissolved in water. It could be water-soluble even if water did not exist. The solubility of something in water means that if it were immersed in water, it would dissolve. Expressed in terms of the possible worlds semantics, it means that in every physically possible world in which the thing in question is immersed in water, it is dissolved in it. Therefore, the sentence “a is soluble in water” can be represented (semi)symbolically as follows:

□ (a has been immersed in water → a has dissolved)

The predicate (disposition term) “…is water-soluble” is therefore the following compound predicate, which contains ordinary predicates and a modal operator:

□ (…has been immersed in water → …has dissolved)

So, if we symbolize the predicate “…has been immersed in water” with “F” and “…has dissolved” with “G”, the fully symbolic representation of the sentence “a is water-soluble” would be “□(Fa→Ga)”. The modal operator expresses physical necessity.

Exercises

(Download the exercises as a PDF file.)
(1) Symbolize the following sentences in the language of modal propositional logic.
1) John will not necessarily come to the meeting.
2) Necessarily, everything is finite or infinite.
3) If you are obliged to vote, then you are allowed to vote.
4) Smoking is forbidden in the room but is allowed in the hallway.
5) This is not only possible; it is possible by necessity.
6) This is necessary, but it is not necessary by necessity.
7) If this happened once, it will happen in the future.
8) It is possible that everything is necessarily finite.
9) This is not necessarily necessary, but it is possible by necessity.
10) If it is permissible for this to be mandatory, it is mandatory for it to be permissible.
11) If this ever happens, it has always been a fact that it will.
12) If this happened, it will always be a fact that it did.
13) If this is necessary, it is a fact, and if it is a fact, it is possible.
14) If it has always been a fact that this will happen, then there will come a time when it has already happened.
15) This already happened, but there was a time when it has not happened yet.
(2) Are the following pairs of expressions logically equivalent? If not, change one of the modal operators in the first expression so that they become equivalent.
1) ¬□α ◊¬α
2) ¬◊¬α ¬¬□α
3) □¬□□¬α ¬◊□¬□α
4) □¬¬◊¬α ¬◊□α
5) □¬□□¬α □◊◊α
6) ¬◊□□α □◊□¬α
7) ◊◊¬□□¬α ◊◊◊◊α
8) ◊◊¬□□¬α ¬□□□¬□α
9) ◊◊¬□□¬α ◊◊◊¬◊¬α
10) ◊◊□□¬α ¬□□□◊α
(3) Prove with diagrams that the following schemes are logically valid with respect to semantic rule (1).
1) □α → ◊α
2) ◊□α → ◊α
3) [□(α→β) ∧ □¬β] → ¬α
4) (◊α ∧ ◊β) → ◊(α ∨ β)
5) [□(α ∨ β) ∧ □¬α] → □β
6) ◊(α ∨ β) → (◊α ∨ ◊β)
7) □α → □□□□α
8) ◊(α ∨ β) → (◊◊α ∨ ◊β)
9) [□(α ∨ β) ∧ □(α→γ) ∧ □(β→γ)] → □γ
10) ¬◊(α ∨ β) → □(¬α→ ¬β)
(4) Prove with diagrams that the following schemes are logically valid (with respect to semantic rule (2)) without imposing any conditions on the accessibility relation.
1) □(α→β) → (□α→□β)
2) (□α ∧ □β) → □(α ∧ β)
3) □α → □(α ∨ β)
4) (□α ∧ ◊β) → ◊(α ∧ β)
5) □(β→α) → ¬◊(¬α ∧ β)
6) □(α→β) → (◊α→◊β)
7) □□α → □(◊α ∨ □β)
(5) Prove with diagrams that the following schemes are logically valid when the accessibility relation is reflexive.
1) α → ◊α
2) □α → ◊◊α
3) □(□α→α)
4) □(α→◊α)
5) □□□α → α
6) □(α→β) → (α→◊β)
7) [□(¬α→β) ∧ (α→□β)] → ◊β
(6) Prove with diagrams that the following schemes are logically valid when the accessibility relation is transitive.
1) ◊◊α → ◊α
2) ◊◊◊α → ◊α
3) □α → □¬◊◊¬α
4) [◊◊◊(α→β) ∧ □α] → ◊β
5) □(α→β) → □(□α→□β)
6) □◊α → □◊□◊α
(7) Prove with diagrams that the following schemes are logically valid when the accessibility relation is symmetric.
1) ◊□α → α
2) ◊□α → □◊α
(8) Prove with diagrams that the following schemes are logically valid when the accessibility relation is symmetric and transitive.
1) ◊□α → □α
2) □(□α ∨ β) → (□α ∨ □β)
3) ◊□α → □□α
(9) Prove with diagrams that the following schemes are logically valid when the accessibility relation is reflexive and transitive.
1) ◊◊□α → ◊α
2) (□α ∨ □□□β) → (□□□α ∨ □β)5
1. “Aletheia” means “truth” in ancient Greek. ↩ 2. In temporal modal logic, instead of □α, we have □pα and □fα and instead of ◊α, we have ◊pα and ◊fα. So, we need to add four rules. ↩ 3. All inference schemes and equivalence schemes that we use are from 1.8 Natural deduction. ↩ 4. A set is a proper subset of another when all the elements of the first are elements of the second, but the second has elements that are not elements of the first. ↩ 5. You should consider different cases in the proof. ↩