Thursday, June 18, 2015

Modal logic semantics

This is part of my series on debugging the ontological argument.

At this point in the series, we will shift gears, switching from predicate logic to modal logic.  Modal logic has produces some of the most complicated and interesting ontological arguments, but it is also a fascinating topic all to itself.  In this post, I will simply cover the necessary background on modal logic.

In modal logic takes propositional logic and adds modal operators.  In standard modal logic there are two modal operators denoted $\square$ and $\Diamond$.  A modal operator takes in any proposition P, and produces another related proposition.  The proposition $\square$P means "It is necessary that P", and the proposition $\Diamond$P means "It is possible that P".  The symbols are also related to each other by
$$\square = \lnot\Diamond\lnot\tag{1}\label{ref1}$$ $$\Diamond = \lnot\square\lnot\tag{2}\label{ref2}$$
(Note that \ref{ref1} and \ref{ref2} are equivalent to each other.)

The next question to ask is, what does it mean to be necessary?  What does it mean to be possible?

The key thing to understand is that $\square$ and $\Diamond$ don't have any inherent meaning at all.  They are just symbols which obey certain rules.  To talk about their meaning, we must shift from talking about logic to talking about semantics.

What we can do is create a semantic model, from which all the logical rules follow.  In general, there will be many possible semantic models which generate the same logical rules.  I will discuss one particular semantic model created by philosopher Saul Kripke in the 1950s and 60s.  I should warn that this is an exercise in rehashing the Wikipedia article, but Kripke's work is so important that the exercise is worthwhile.

Kripke Semantics

I can't think of a better way to explain Kripke semantics than with an illustration:
Figure 1.  If you borrow any of my images, please credit me.

Each of the gray ellipses represents a possible world.  A possible world has a true/false assignment to every proposition.1  In other words, if we have any proposition P, it may be true in some possible worlds, and false in others.  We say that world u "satisfies" proposition P (commonly denoted "u $\models$ P") if and only if P is true in world u.  This is called the satisfaction relation.  The satisfaction is a function whose arguments are a possible world and a proposition, and whose output is a boolean.2

One of these possible worlds (in darker gray, labeled t) is the actual world.   That's the one we live in!  We say that a proposition is true if the actual world satisfies that proposition.

I also drew lots of blue arrows going between possible worlds.  This arrow represents the accessibility relation.  If there is an arrow drawn from world w to world u, then we say u is "accessible" from world w (commonly denoted "w R u").  Worlds may also be accessible from themselves, or they may be inaccessible from themselves.

The big green box is the set of all possible worlds.  The set of all possible worlds, along with the accessibility relation, is called the frame.  The frame, along with the satisfaction relation, is called the model.

There are many different frames I could have drawn.  I could have drawn a different number of worlds or I could have connected the arrows in different ways.  I am not saying that there are many "possible" frames, because remember we're still trying to define what "possible" even means.

In Kripke semantics, $\square$ and $\Diamond$ are interpreted as follows:
$$[w \models \square P] \Leftrightarrow [\forall u \epsilon W ~(w R u \Rightarrow u \models P)]\tag{3}\label{ref3}$$ $$[w \models \Diamond P] \Leftrightarrow [\exists u \epsilon W ~(w R u \wedge u \models P)]\tag{4}\label{ref4}$$
Allow me to translate.  We say that a proposition P is necessary with respect to world w if P is true in all possible worlds accessible from w.  A proposition P is possible with respect to world w if P is true in at least one possible world accessible from w.

Figure 2.

If you're not sure you get it, here are some examples of statements which are true in the model shown in Figure 2.
1. $w \models \Diamond P$
2. $w \models \Diamond Q$
3. $u \models \square \lnot Q$
4. $u \models \Diamond P$
5. $v \models \square Q$
6. $\lnot (v \models \Diamond Q)$

S5 modal logic

Kripke semantics raises new question.  What does it mean for one world to be "accessible" from another?  We need another layer of semantics to explain that one.

There are actually multiple meanings we can assign to the idea of "accessibility".  For instance, we might say that a world u is accessible from world w if and only if u is a possible future of w.  If that is the meaning, then all accessibility relationships are one-way only, and no world is accessible from itself.

Another interpretation of "accessibility" is that world u is accessible from world w if and only if both worlds obey the same physical laws.  In this interpretation, all accessibility relationships are two way, and every world is accessible from itself.

The modal ontological argument does not require any particular interpretation of "accessibility".  However, it does require that "accessibility" conforms to a few specific rules.  Specifically, we want the following conditions:
$$w R w\tag{5}\label{ref5}$$ $$w R u \Rightarrow u R w\tag{6}\label{ref6}$$ $$w R u \wedge u R v \Rightarrow w R v\tag{7}\label{ref7}$$
\ref{ref5} is the reflexivity condition, and it says that all worlds are accessible from themselves.  \ref{ref6} is the symmetry condition, and it says that all accessibility goes both ways.  \ref{ref7} is the transitivity condition, and it says that it is always possible to access the worlds which are accessible through another accessible world.

Here is an illustration of a frame that fulfills the above conditions:

Figure 3.

With these rules, the frame can always be partitioned into one or more subframes.  In Figure 3, the subframes are {t,v,x}, {u,w}, and {y}.  Within each subframe, each world is accessible from each other world.  However, there is no access between  distinct subframes.  Since the different subframes are inaccessible from each other, we might as well just consider the one subframe that includes the actual world and ignore the rest.

These conditions on accessibility create S5 modal logic.  S5 contains additional axioms, which I show below for completeness.  It's not necessary to understand these axioms unless you want to follow the modal logic proofs step by step.
$$\text{If P is a theorem, then}~ \square P\tag{N}\label{N}$$ $$\square(P \Rightarrow Q) \Rightarrow (\square P \Rightarrow \square Q)\tag{K}\label{K}$$ $$\square P \Rightarrow P \tag{T}\label{T}$$ $$\square P \Rightarrow \square\square P\tag{s4}\label{s4}$$ $$\Diamond P \Rightarrow \square\Diamond P\tag{s5}\label{s5}$$
Among other things, these axioms imply that there are no meaningful "meta-modalities".  For example, the statement "it is possible that it is possible that P" is just equivalent to "it is possible that P."


Modal logic is interpreted through a "frame", or a set of possible worlds.  S5 modal logic, which is the kind used by the modal ontological arguments, requires that the frame is partitioned into one or more subframes.  One of these subframes contains the actual world.  $\square$ P means that P is true in all possible worlds within our subframe.  $\Diamond$ P means that P is true in at least one possible world within our subframe.

But here's what we don't know.  The frame can consist of any number of worlds, as long as there's at least one world.  The frame can be partitioned into subframes in any number of ways.  If I describe to you a possible world, even if you agreed that it exists you wouldn't necessarily agree that it's accessible.

I have final important point.  The frame isn't real.  The frame is a construction to help us understand what's going on.  We can equally well choose a different frame, and that frame is no more or less true than the first.  When we talk about S5 modal logic, we're not making an assumption about what the frame "really" is, we're just choosing to confine our discussion to a particular kind of frame.


1. Each possible world can also be considered to have its own set of objects.  However, this isn't really relevant, since we won't be discussing predicates in modal logic until later.

2. I'm using basic computer programming terms, and I'm not sure how much I can assume people understand them.  A "boolean" is simply a single bit of information, containing the value "true" or "false".