3Accessibility

3.1Variable modality

I have given two kinds of interpretation for the box and the diamond. First I said that we use \(\Box A\) to express that \(A\) is certain, or historically necessary, or obligatory, etc. Then I said that \(\Box A\) means that \(A\) is true at all possible worlds. These were not meant to be competing interpretations. Rather, I have assumed that the ordinary concepts of certainty, historical necessity, obligation, and so on, can be analysed – at least to some approximation – as universal quantifiers over possible worlds.

Take historical necessity. Informally, \(A\) is historically necessary if there is nothing we can do that might render \(A\) false. Let’s say that a world is open if there is something we can do that might bring about that world (in the sense that if we were to perform the relevant action, then we might live in that world). Now, if you think about it, \(A\) is historically necessary iff \(A\) is true at all open worlds. So we can use \(\Box A\) to mean both that \(A\) is historically necessary and that \(A\) is true at all possible worlds, where ‘possible’ means ‘open’.

Other flavours of modality are associated with other domains of worlds. Suppose the box formalizes ‘it is obligatory that’. To a first approximation, \(A\) is obligatory (relative to some norms) iff it is true at all worlds at which the norms are respected. (Think about it!) These worlds are also called ideal. So we can use \(\Box A\) to mean both that \(A\) is obligatory and that \(A\) is true at all possible worlds, where ‘possible’ now means ‘ideal’.

Unfortunately, there are good reasons to think that this approach won’t always work. Remember that the possible-worlds semantics from the previous chapter determines a particular logic: S5. And this logic is not appropriate for every application of modal logic. In deontic logic, for example, we don’t want the schema

(T)

\(\Box A \to A\)

to be valid. We can easily conceive of scenarios in which \(\Box p\) is true (on some interpretation of \(p\)) even though \(p\) is false.

The semantics from the previous chapter renders the (T)-schema valid. Whenever a sentence \(\Box A\) is true at a world \(w\) in a model then \(A\) is true at \(w\) as well, because the box quantifies over all worlds, including \(w\). To make room for deontic logic, we need a semantics in which not all worlds in \(W\) are among the “possible” worlds over which the modal operators quantify. Not all worlds are ideal.

We might also want to allow that the worlds over which the modal operators quantify depend on the world at which the relevant sentence is evaluated. Perhaps you are obligated to do the dishes in worlds where you have promised to do the dishes, but not in worlds where you haven’t made the promise. Worlds in which you don’t do the dishes are then ideal relative to the second kind of world, but not relative to the first.

This type of variability is also needed for other flavours of modality. Suppose the box quantifies over all worlds that are compatible with our knowledge. Which worlds are compatible with our knowledge depends on what we know. But we don’t always know what we know. Sometimes we believe that we know something, but don’t actually know it because it is false. We don’t know it, without knowing that we don’t know it. Among the worlds compatible with our knowledge are then worlds in which we know more than we actually do. What’s compatible with our knowledge in these worlds is different from what’s compatible with our knowledge in the actual world.

Let’s assume, then, that for any world in any scenario there is a set of worlds that are possible relative to \(w\). We assume that \(\Box p\) as true at \(w\) iff \(p\) is true at all worlds that are possible relative to \(w\). If a world \(v\) is possible relative to \(w\) we also say that \(v\) is accessible from \(w\), or (informally) that \(w\) can see \(v\).

Accessibility means different things in different applications. In epistemic logic, a world \(v\) is accessible from \(w\) iff \(v\) is compatible with what is known at \(w\). In the logic of historical necessity, \(v\) is accessible from \(w\) iff \(v\) can be brought about at \(w\). And so on.

Since facts about accessibility matter to the truth-value of modal sentences, they must be represented by our models. From now on, a model for \(\mathfrak {L}_M\) will therefore specify which worlds in \(W\) are accessible from which others (and from themselves). This marks the difference between a “basic model” and a “Kripke model” – named after Saul Kripke, who popularised models of this kind.

\(R\) is the accessibility relation. It is called a relation “on \(W\)” because it holds between members of \(W\). We write ‘\(wRv\)’ to express that \(R\) holds between \(w\) and \(v\).

We also need to update definition 2.2, which settles under what conditions an \(\mathfrak {L}_M\)-sentence is true at a world in a model. The old definition had the following clauses for the box and the diamond:

In the new semantics, the box and the diamond only quantify over accessible worlds:

Here is the full definition, for completeness.

When I speak of truth at a world in a Kripke model, this should always be understood in accordance with definition 3.2. Definition 2.2 defines truth at a world in a basic model.

To see definition 3.2 in action, consider a simple model with two worlds, \(w\) and \(v\). World \(v\) is accessible from world \(w\), but \(w\) is not accessible from \(v\). Neither world can access itself. The interpretation function assigns \(\{ v \}\) to \(p\) and the empty set \(\emptyset \) to all other sentence letters. The model can be pictured as follows, with an arrow representing accessibility:

Using definition 3.2, we can figure out which \(\mathfrak {L}_M\)-sentences are true at which worlds in the model. For example:

• By clause (a) of definition 3.2, \(p\) is true at \(v\) and false at \(w\).

• By clause (h), \(\Diamond p\) is true at \(w\) because \(p\) is true at \(v\) and \(v\) is accessible from \(w\). \(\Diamond p\) is false at \(v\) because there is no world accessible from \(v\) at which \(p\) is true.

• By clause (g), \(\Box \Diamond p\) is false at \(w\) because \(\Diamond p\) is false at \(v\) and \(v\) is accessible from \(w\). \(\Box \Diamond p\) is true at \(v\) because there is no world accessible from \(v\) at which \(\Diamond p\) is false.

Note that \(\Diamond p\) and \(\Box \Diamond p\) have different truth-values at \(w\) (and at \(v\)). In the new semantics, we can no longer ignore all but the last in a string of modal operators. Note also that \(\Box p\) is true at \(w\) even though \(p\) is false; \(\Box p \to p\) is no longer valid.

The next three exercises refer to the following model:

3.2The systems K and S5

As in the previous chapter, we call a sentence valid if it is true at all worlds in all models. But we now use a different conception of models, and a different definition of truth at a world in a model. To avoid confusion, it is best to use different expressions for different kinds of validity. Let’s call the new kind of validity K-validity. (‘K’ for Kripke.) The old kind will henceforth be called S5-validity, because the sentences that are valid by the definition from the previous chapter are precisely the sentences in C.I. Lewis’s system S5.

The same distinction applies to the concept of entailment. Entailment in the old sense (definition 2.4) will henceforth be called S5-entailment. Our new definition of models and truth lead to the concept of K-entailment.

The set of K-valid sentences is a system of modal logic. This system did not figure in C.I. Lewis’s list of systems. It is known as system K.

K is weaker than S5, by which we mean that not all S5-valid sentences are K-valid. \(\Box p \to p\), for example, is S5-valid but not K-valid. Conversely, however, every K-valid sentence is S5-valid. Let’s prove this.

You may remember from section 1.5 that S5 can be axiomatized by five axiom schemas and two rules:

(Dual)

\(\neg \Diamond A \leftrightarrow \Box \neg A\)

(K)

\(\Box (A\to B) \to (\Box A \to \Box B)\)

(T)

\(\Box A \to A\)

(4)

\(\Box A \to \Box \Box A\)

(5)

\(\Diamond A \to \Box \Diamond A\)

(Nec)

\(\text {If $A$ is in the system, then so is }\Box A.\)

(CPL)

\(\text {If }\Gamma \models _{0} A\text { and all members of }\Gamma \text { are in the system, then so is }A.\)

All instances of (Dual), (K), (T), (4), and (5) are S5-valid, and all and only the S5-valid sentences can be derived from instances of these axioms by (Nec) and (CPL).

The system K can be axiomatized by dropping three of the axiom schemas: (T), (4), and (5), leaving only (Dual) and (K). All and only the K-valid sentences can be derived from instances of (Dual) and (K) by (Nec) and (CPL).

(Many authors define \(\Box \) as \(\neg \Diamond \neg \) or \(\Diamond \) as \(\neg \Box \neg \), in which case (Dual) is true by definition. The only remaining axiom schema is then (K). Don’t confuse the schema (K) with the system K!)

3.3Some other normal systems

For many applications of modal logic, we need a concept of validity that lies in between K-validity and S5-validity. Suppose, for example, we read the box as physical necessity and the diamond as physical possibility, understood as compatibility with the laws of nature. On a popular conception of what it means to be a law of nature, nothing that happens is ever incompatible with the laws of nature. Equivalently, anything that is physically necessary is actually the case. We therefore want \(\Box A\) to entail \(A\). On the other hand, it is not clear if \(\Box A\) should entail \(\Box \Box A\): if \(A\) is physically necessary, can we infer that it is physically necessary that \(A\) is physically necessary? Below I will argue that we can’t. If that is right, then the logic of physical necessity is neither K nor S5. We want a logic with (T) (\(\Box A \to A\)) but without (4) (\(\Box A \to \Box \Box A\)). S5 gives us both, K gives us neither.

Our current semantics makes it easy to define systems in between K and S5 by putting restrictions on the accessibility relation in Kripke models.

Let’s say that an \(\mathfrak {L}_M\)-sentence is valid in a class of Kripke models iff the sentence is true at every world in every model that belongs to the class. K-validity is validity in the class of all Kripke models. S5-validity is validity in the class of Kripke models in which every world has access to every world (as mentioned earlier, in the proof of observation 3.1).

If you inspect countermodels to the K-validity of \(\Box p \to p\), you may notice that all of them involve worlds that don’t have access to themselves. If we require that every world can see itself then all instances of the (T)-schema become valid.

A relation \(R\) on a set \(W\) is called reflexive if each member of \(W\) is \(R\)-related to itself. If the accessibility relation in a Kripke model is reflexive, we also call the model itself reflexive. Observation 3.2 therefore states that all instances of (T) are valid in the class of reflexive Kripke models.

The set of all sentences that are valid in the class of reflexive Kripke models is known as system T. Accordingly, any sentence that is valid in this class of Kripke models (every member of system T) is called T-valid.

System T is stronger than K, but weaker than S5. The system can be axiomatized by adding the axiom schema (T) to the axioms and rules of K. We don’t have (4) or (5). \(\Box p \to \Box \Box p\) is S5-valid but not T-valid.

Systems of modal logic sometimes share their name with a schema. For disambiguation, I always put schema names in parentheses. (T) is a schema, T is a system. (K) is a schema, K is a system. All instances of (T) are in T, but many sentences in T – for example, all instances of (K) – are not instances of (T).

In chapter 7, we will study a temporal application of modal logic in which the box is read as ‘it is always going to be the case that’. The “worlds” in a Kripke model here represent times. \(\Box p\) is understood to be true at a time \(t\) iff \(p\) is true at all times after \(t\). The accessibility relation is the earlier-later relation: \(t_1Rt_2\) iff \(t_1\) is earlier than \(t_2\). In this application, we don’t want to assume that \(R\) is reflexive, which would mean that every point in time is earlier than itself. But we’ll want something else. Suppose \(t_1\) is earlier than \(t_2\), and \(t_2\) is earlier than \(t_3\). Then surely \(t_1\) is earlier than \(t_3\).

A relation \(R\) is called transitive if whenever \(xRy\) and \(yRz\) then \(xRz\). As before, we call a Kripke model transitive if its accessibility relation is transitive. When we do temporal logic, we will restrict the relevant models to transitive models.

The set of sentences that are valid in the class of transitive Kripke models is known as system K4. The name alludes to the fact that this system can be axiomatized by adding schema (4) to the axioms and rules of K.

We can combine the systems T and K4 by requiring both reflexivity and transitivity. The set of sentences valid in the class of reflexive and transitive Kripke models is C.I. Lewis’s system S4. It is stronger than K, T, and K4, but weaker than S5.

There are many other conditions we could impose on the accessibility relation, and many combinations of these conditions. Each of them defines a system of modal logic. The following table lists some well-known model classes with the conventional names for the corresponding systems, repeating (for future reference) the ones we already know. We will have a closer look at some of these systems in later chapters, when we turn to applications of modal logic.

S5 occurs twice in the list. We already know S5 as the system for universal models, in which the box and the diamond quantify unrestrictedly over the whole space \(W\). But we also get S5 if we merely require the accessibility relation to be reflexive, transitive, and symmetric.

Relations that are reflexive, transitive, and symmetric are called equivalence relations. An equivalence relation on a set divides the members of the set into classes within which everything stands in the relation to everything. (These classes are called equivalence classes.)

For example, let \(S\) be the relation that holds between two people iff they have the same birthday. This is an equivalence relation. It is reflexive: everyone has the same birthday as themselves. It is transitive: if \(aSb\) and \(bSc\) then \(aSc\). And it is symmetric: if \(aSb\) then \(bSa\). For any person \(a\), consider the class \([a]_S\) of everyone who has the same birthday as \(a\). (A “class” is essentially the same thing as a set.) Everyone in \([a]_S\) has the same birthday as everyone else in \([a]_S\). So within \([a]_S\), the same-birthday relation \(S\) is universal.

Now let me explain why the above two characterisations of S5 are equivalent.

3.4Frames

There is a close connection between conditions on the accessibility relation in Kripke models and modal schemas – between reflexivity and the (T)-schema, between transitivity and the (4)-schema, and so on. What exactly is the connection?

You might think the connection between (T) and reflexivity is this:

• (?) All instances of (T) are valid in a model iff the model is reflexive.

But that’s false. We know (observation 3.2) that all (T) instances are valid in the class of reflexive models. It follows that all (T) instances are valid in every reflexive model. But the other direction fails. There are non-reflexive models in which all (T) instances are valid. The following model is an example.

There are two worlds, both of which can see each other; neither can see itself. \(p\) is true at both worlds, all other sentence letters are false at both worlds. This model is not reflexive, but no instance of the (T)-schema \(\Box A \to A\) is false at any world in the model. (Try to find a false instance!) The fact that the (T)-schema is valid in a class of models therefore does not entail that all models in the class are reflexive. The class might contain models like the one just described.

To understand the connection between modal schemas and conditions on the accessibility relation, we need to talk about frames. A frame is what you get if take a model and remove the interpretation function.

Roughly speaking, if we think of a model as representing a scenario and an interpretation, then a frame is the part of the model that represents the scenario.

Frames can be pictured just like Kripke models, but without any sentence letters in the nodes. The frame of the model displayed above looks like this:

Now remember that validity is truth in virtue of the meaning of the logical expressions. Whether a sentence is valid should not depend on the meaning of the non-logical expressions. So if we define a particular kind of validity by reference to a class of Kripke models, the constraints we impose on the models in the class should be constraints on the frame of the models, not on the interpretation function.

To see the point, suppose I suggested that a sentence is “\(X\)-valid” iff it is true at all worlds in all Kripke model whose interpretation function assigns the empty set to the sentence letter \(p\). So \(\Box \neg p\) is \(X\)-valid, while \(\Box \neg q\) is \(X\)-invalid. But \(\Box \neg p\) and \(\Box \neg q\) have the same logical form. If \(\Box \neg p\) is true in virtue of its logical form, then \(\Box \neg q\) should also be true in virtue of its logical form. \(X\)-validity is not a sensible concept of logical validity. The systems from the previous section were all defined sensibly, by putting constraints on the frame of a Kripke model, not on the interpretation function.

Let’s say that a sentence is valid on a frame if it is true at all worlds in all models with that frame. A sentence is valid in a class of frames if it valid on all frames in the class.

If a sentence is valid in the class of all models whose accessibility relation satisfies a certain condition, then it is also valid in the class of all frames whose accessibility relation satisfies that condition, and vice versa. We could have defined the systems from the previous section in terms of frame classes rather than model classes: K is the set of sentences valid in the class of all frames, T is the set of sentences valid in the class of reflexive frames, and so on. (A reflexive/transitive/etc. frame is a frame with a reflexive/transitive/etc. accessibility relation.)

Now here is the connection between (T) and reflexivity: All (T) instances are valid in a class of frames iff every frame in the class is reflexive. More simply:

If all instances of a schema are valid on all and only the frames whose accessibility relation satisfies a certain property, the schema is said to correspond to that property (and to define the relevant class of frames). Observation 3.5 says that the (T) schema corresponds to reflexivity.

Instead of proving more facts about the correspondence between modal schemas and frame conditions, I will simply give you a list of some important results.

Correspondence facts are often useful when trying to figure out which schemas should be valid on a given interpretation of the modal operators. Return to the case of physical possibility and necessity from the start of section 3.3. I claimed that on this interpretation of the box and the diamond, we should not regard all instances of the (4)-schema \(\Box A \to \Box \Box A\) as valid. My claim is not based on a direct intuition that something could be physically necessary without it being physically necessary that it is physically necessary. My claim is rather based on a judgement about the non-transitivity of physical accessibility. My reasoning goes like this. I assume that a world \(v\) is physically possible relative to a world \(w\) if nothing that happens at \(v\) contradicts the laws of nature at \(w\). This does not imply that \(v\) has the same laws as \(w\). For example, suppose the only law at \(w\) is that ravens are black; at \(v\), there is no such law but there happen to be no non-black ravens. Then what happens at \(v\) does not contradict the laws at \(w\), even though \(v\) has different laws. Relative to the laws of \(v\), worlds with white ravens are physically possible. So a world accessible from a world that is accessible from \(w\) need not itself be accessible from \(w\). Since (4) corresponds to transitivity, I can infer that the logic of physical necessity does not render all instances of that schema valid.

3.5More trees

In section 2.5, I described the tree method for checking whether a sentence is valid, and for constructing countermodels. These were the rules for the box and the diamond:

The rule for \(\Box A\) allows us to infer, from the hypothesis that \(\Box A\) is true at some world, that \(A\) is true at any world that occurs on a tree branch. This made sense given the semantics of the previous chapter, where the box quantified unrestrictedly over all worlds. With the new semantics of the present chapter, we need to change the tree rules.

If \(\Box A\) is true at a world \(w\), and there’s some other world \(v\) on the branch, we can only infer that \(A\) is true at \(v\) if \(v\) is accessible from \(w\). So we need to keep track of which worlds are accessible from any world on a tree. We do this by adding meta-linguistic statements about accessibility to the tree.

For example, suppose we want to expand the following node.

The node represents the hypothesis that \(\Diamond p\) is true at \(w\). It follows that \(p\) is true at some world \(v\). Moreover, that world \(v\) must be accessible from \(w\). So we add two new nodes:

Node \(m+1\) is what we would have added by the old rules. Node \(m\) is a meta-linguistic statement reminding us that \(v\) is accessible from \(w\). ‘\(wRv\)’ is not a sentence of \(\mathfrak {L}_M\); it isn’t true or false relative to a world, which is why node \(m\) has no world label.

What if we want to expand a box node?

By itself, this doesn’t tell us anything about the truth-value of \(p\) at any world. We can’t infer that \(p\) is true at \(w\), because \(w\) might not be accessible from itself. Indeed, if no world is accessible from \(w\), then \(\Box p\) can be true even if \(p\) is false at every world. So we can’t even infer that there is some world or other at which \(p\) is true.

However, suppose a branch that contains node \(n\) also contains the following node.

Now we can infer that \(p\) is true at \(v\). So to expand a box node on a branch, there must be another node on the branch telling us that the world \(w\) at which the box sentence is true has access to some world \(v\).

Here are diagrams of the new rules for the box and the diamond.

If two nodes occur above the dotted line in a rule, as in the rule for \(\Box A\), this means that the rule can only be applied if both nodes already occur on the relevant branch (in any order, and not necessarily adjacent to each other).

As before, the checkmark next to the rules for \(\Diamond A\) and \(\neg \Box A\) indicates that these nodes can only be expanded once on each branch.

The rules for negated boxes and diamonds are what you would expect from the duality of the box and the diamond. Note that only nodes of type \(\Diamond A\) and \(\neg \Box A\) allow us to introduce hypotheses about accessibility into a tree.

The rule for the classical connectives all stay the same. Together, all these rules are known as the K-rules; the tree rules from section 2.5 are the S5-rules.

Here is a schematic tree proof to show that \(\models _K \Box (A \land B) \to (\Box A \land \Box B)\).

The annotation ‘(2,6)’ for node 8 indicates that this node is based on two assumptions from earlier in the branch: the assumption on node 2 that \(\Box (A \land B)\) is true at \(w\), and the assumption on node 6 that \(wRv\). Only these two assumptions together allow us to infer that \(A \land B\) is true at \(v\).

What happens if we try to prove \(\Box p \to p\)?

At this point, no more rules can be applied. We can read off a countermodel from the open branch:

This is the smallest possible Kripke model. It consists of a single world that can’t see itself. ‘\(R = \emptyset \)’ is a way of saying that no world can see any world. If you want to say that \(R\) holds between \(w\) and \(v\) and between \(v\) and \(u\), you might write ‘\(R = \{ (w,v), (v,u) \}\)’ or simply ‘\(wRv, vRu\)’.

For systems in between K and S5 that are characterised by certain constraints on the accessibility relation, we add new rules for manipulating accessibility nodes. For example, if we want to check whether a sentence is T-valid, we use a reflexivity rule in addition to the K-rules. The reflexivity rule says that if a world variable \(\omega \) occurs on a branch, then we may always add \(\omega R\omega \) to the branch.

Here is a proof of \(\Box p \to p\), using the reflexivity rule.

To test for validity in the class of transitive frames (or models), we need a transitivity rule, which allows us to infer \(\omega R\upsilon \) from \(\omega R\nu \) and \(\nu R\upsilon \). Here is a proof of \(\Box p \to \Box \Box p\) that uses this rule.

The following diagrams summarize the tree rules for the frame conditions we have so far considered.

By selectively adding some of these rules to the K-rules, we get tree rules for a variety of modal logics. (Compare the table here.)