# Modal System S4

Updated on August 7, 2014

## Modal Logics

While there is one classical propositional logic, there is an open number of modal logics that extend it. Taking standard propositional logic to be represented in an idiom L, we have in the lexicon, propositional variables {p, q, ...} - denumerable stock with subscripts allowed; the logic is determined by defining Boolean connectives over a set of two truth-values {T, F} - true and false - and the connectives can be only {~, &} but we can expand to {~, &, V, ->} where the symbols denote respectively the truth-functions negation, conjunction, inclusive disjunction and material implication. We allow for parentheses, as needed for disambiguation, and we set the grammar of L in the usual way (in infix, not prefix notation: so, "p & q" is well-formed whereas "& p q" or "p q &" aren't.)

To extend L to some modal system, e.g. MLi, we construct a model, which is a mathematical abstract object with three members: <W, R, //>, where W is a non-empty set that is presumed to contain as members possible worlds, R is the relationship between members of W, and // is a function that assigns to every proposition a truth-value in each world. This is the so-called Leibniz-Kripke semantics and it provides an intuitive semantics for modeling modal systems that used to be uninterpreted (and could not be checked for soundness or completeness relative to some reasonable semantical representation).

Why do we get many modal logics while we only have one propositional logic that is available to be extended? The answer lies in that the relation R is available and can be tweaked in as many different ways as one wishes. But we can define R also in terms of its properties. Relations have properties - like reflexivity, transitivity, symmetry, and many others. If we put no restrictions on R, so that every member of W accesses every member of W, we get the so-called Leibnizian system that corresponds to what CI Lewis had constructed syntactically as S5: we think that this modal system captures the features of the modality we consider to be logical necessity. It is controversial what logical necessity is exactly: is it the characteristic of logical truths of a formal system? is it the same as analyticity? is it a matter of how inferential rules are set in a logical system? ...

Is it intuitive that we would be able to extend propositional logic to an open-ended variety of modal logics? The idea is this: there are many - we may not know how many - species or kinds of modality. We saw logical necessity as a modality above. We also have physical necessity - we can readily appreciate that a proposition can be logically possible but physically impossible, which gives us a clue about a distinction. The modal qualifier in a statement like "it is morally forbidden that p" where p is some proposition is called deontic (having to do with what is morally necessary, which means obligatory, and what is not, which means morally permissible not to do.) It is greatly important that temporal qualifiers on statements (like in "it has always been the case that p") also behave modally. The set W in a temporal model can be represented as the set of moments in the ongoing time-flow. It is possible then to think about what properties the time-flow relation has (for instance, transitivity): accordingly we restrain R, the relation among members of W in the modal model, and we can examine what logical truths accrue for such a system.

The propositional logic that is extended by means of modal systems is itself a special case - we can say, it is a degenerate case - of modal logic: if we set the relation R to empty (an empty set has no members), then, of course it does not matter how many members W has and we have exactly propositional logic. This alerts us to something which perceptive students of logic are aware of: the propositions of propositional logic are "flattened", so to speak; they cannot be affected by variable context (hence what is known as the Russellian "eternal proposition" of propositional logic.) This is what this means. As an example take the proposition expressed by the sentence "Socrates fell into a trance." Intuitively, we would think that the truth-value of this proposition varies depending on the time-reference of the propositional content. The proposition should be true when this happened and false at all other times even including the time when Socrates does not exist (since we are playing with only true and false as values.) But propositional logic cannot handle this. The way it is constructed, propositional logic must have all meanings (the propositions expressed by declarative sentences) refer to some settled truth-value (true or false.) Hence, the above proposition about Socrates is taken as being "Socrates falls into a trance at time-x and in place-y, ..." and with all other context-sensitive elements also fixed like this: now, of course, we have a proposition about which we can have that is has a fixed truth-value (true or false.) All this is another way of saying that the propositional logic cannot track meaning dynamically along variable contexts. But modal logic can! The dynamic element is introduced, in our semantics, via the relationship R that allows possible worlds, members of W, to access certain other worlds (possibly including themselves.)

In this way we have both a motivation for seeking a multiplicity of modal systems - not just one as with the standard propositional logic - as well as some basic understanding of the semantical mechanisms that permit constructing models for such modal logics.

It is fascinating that depending on what restrictions we place on R, we get corresponding logical truths that are valid in any system that has this restriction. The restrictions themselves can be expressed fully in the standard logic known as Predicate Logic. This indicates a deep relationship between modal logics and the standard system known as Predicate or First-Order Logic. Nevertheless, close attention shows that, actually, the expressive force required for expressing those restrictions is in higher-order logic and this explains why modal logic can do the trick of tracking dynamically beyond what first-order logic does. (First-order or Predicate Logic has symbols for quantifying over individuals, as in "someone came to dinner." Second-order logic also adds symbols for quantifying over predicates themselves like in "some colors are brighter than others". From a logician's point of view, certain things go wrong when this higher-level is attained. There are also philosophical objections since it seems that, to make sense semantically, second-order logic has to speak about "Platonic" abstract things or Forms like "colors.") It is not to be assumed that we can find a characteristic logical truth in modal logic for any restriction we may impose on R. For instance, we cannot do this with irreflexivity (the property according to which every member of W is not related to itself.) This can be remedied by adding more to our modal systems - specifically, by means of a trick that makes special propositions that are uniquely true each at a given world.)

## The S-series of Modal Logics

A model for a modal system is a triple <W, R, //>. W cannot be empty and is understood as a set of possible worlds (each one of which is included in its full description, which means that for any conceivable proposition p, p is either true or false in each world.) R stands for the accessibility relation. // assigns to each proposition in the model a truth-value in each member of W.

Example:

• M = <W, R, //>
• W = {w0, w1, w2}
• R = {<w0, w0>, <w0, w1>, <w0, w2>}
• /p/ = {w1, w2}
• /q/ = {}

Let us read this. Our W set has three members - three possible worlds of which the one referred to by "w0" can be thought of as the actual world. The members of R are indicated: wo is R-related to itself and to w1 and to w2 and no other relations of access are available. The proposition denoted by "p" is true in w1 and in w2 (so, it is false in w0) and "q" is true nowhere (which means, again, that it is false everywhere.)

We can define now modals like "necessarily" and "possibly." The definitions are intuitively appealing. A proposition p is necessary at world wj if and only if it is true in every world accessed by wj. A proposition p is possible in wj if and only if there is at least one world accessed by wj where p is true. For symbols, we have "N" for "necessarily true that p" and "P" for "possibly true that p." The following relationships between the two modals (the strong and the weak modal) can be easily ascertained. ("<->" stands for "if and only if" in a metalanguage in which we speak about our model. We retain in the metalanguage the symbols for the Boolean connectives of propositional logic, {~, &, V, ->}.)

• Np <-> ~ P ~ p
• Pp <-> ~ N ~ p
• ~ Np <-> P ~ p
• ~ Pp <-> N ~ p

In every so-called normal modal logic, the following (principle K) holds:

• N(p -> q) -> (Np -> Nq)

We can think of this as sanctioning a modal modus ponens (with propositional modus ponens depending on the logical truth of: ((p -> q) & p) -> p.) We can rewrite K, transforming by using inferential principles from the basic propositional logic L:

• (N(p -> q) & Np) -> Nq

We can return to our model M above and compute truth-values at the base world w0.

• M = <W, R, //>
• W = {w0, w1, w2}
• R = {<w0, w0>, <w0, w1>, <w0, w2>}
• /p/ = {w1, w2}
• /q/ = {}
• At w0: ~ p, Np, ~ P~p,~ Pq, N~q.
• Even though p is false at w0, p is true in every possible world accessed by w0: so, p is necessarily true at w0. This sounds odd but let's see how we can motivate a narrative that seems rightly modeled by our model. Suppose that "p" refers to the proposition expressed by "people care for each other." This is not true, as a general case, in our actual world but suppose that w1 and w2 represent worlds that are logically possible and are morally ideal in certain respects. p then should true in those worlds. And then p is deontically necessary in our actual world: "it is morally obligatory (deontically necessary) in our actual world that people do care for each other." The proposition referred to by "q", let's say, is: "alien species treat humans as fertilizer," which is happens to be false in the actual world but, importantly, is false also in the morally ideal worlds: so, in the actual world, it is the case that "it is morally obligatory that it is not true that aliens use humans as fertilizer."
• Notice how the worlds not accessed do not matter for the modals! In our model M, the actual world w0 is not accessed by w0. This makes perfectly good sense: the actual world is not morally ideal. Moreover, we cannot model deontic modalities if we let worlds access themselves - in other words, we don't want R to be reflexive: this is all fitting because: if we make R reflexive (enforcing that every possible world accesses itself), then we have as logical truth in this system "Np -> p" which, translated into deontic modalities, means: "if it is morally obligatory that p, then it is actually true that p." Obviously, we don't want this!

## Modeling Modal Systems

It is possible to construct modal logic systems like the ones in the S-series C.I.Lewis originated by means of the axiomatic method. We indicate below how the normal logics in the S-series are axiomatized.

Common to all normal logics is the axiom K and a rule of derivation called N (for necessitation). Additionally, based on (K) we have a derivation rule known as Modal Modus Ponens (MMP). Because modal systems extend propositional logic, it is understood that all theses and derivation of rules of the basic propositional logic are available to the modal systems.

1. (K) N(p -> q) -> (Np -> Nq)
2. (N) if µ is a syntactically correct formula that is a thesis of Propositional Logic, then Nµ is a thesis (considered as derivable in) for Modal Propositional Logic.
3. (MMP) If N(p -> q) and Np are derivable in our modal system, then we can take Nq as being derivable in the system,

The normal systems in the S-series we designated as K, D, T, B, S4, S5. The derivation rules are as above. K is always included. What distinguishes the systems are the corresponding axioms. The basic normal system K only has (K) has its axioms. For the rest, we have:

• T has the axiom (T): Np -> p
• D has the axiom (D): Np -> Pp
• B has the axiom (B): p -> NPp
• S4 has the axiom (4): Np -> NNp
• S5 has the axiom (5): Pp -> NPp

When we deploy axiomatizations to characterize modal systems we do not specify what kinds of thing we are talking about; we shouldn't because an axiomatic system is like a collection of recipies for how to manipulate symbols in order to form syntactically correct formulas and how to effect transformation that take us from axioms and already proven theses to more proofs of theses in the system. When, however, we model we have abstract items to talk about. The modeling approach is as indicated previously. We use the Leibniz-Kripke model which is a triple M = <W, R, //>. What is remarkable is that we know exactly what conditions or restrictions on the relation R give us what corresponding members of the S-series!

N is defined: (Np, w) if and only if (iff) for all w', such that Rww', (p, w').

P is defined: (Pp, w) if and only if (iff) for all w', such that Rww', (p, w').

It seems that we are forcing a translation from propositional into modal logic. Check it out. "p" stands for propositional atomic or singular letter and "µj" stands for well-formed formula of propositional logic. The Boolean truth-functions are symbolized by {~, &, V, ->}. We need symbols from predicate logic to translate. Think of "p, w" as a predicate-term compound and take the quantifiers to be "all" ("A") and "at least one ("E").

• Tr(p) = p, w
• Tr(~ µ) = ~ Tr(µ)
• Tr(µ1 & µ2) = Tr(µ1) & Tr(µ2)
• Tr(µ1 V µ2) = Tr(µ1) V Tr(µ2)
• Tr(µ1 -> µ2) = Tr(µ1) -> Tr(µ2)
• Tr(Np, w) = Aw'(Rww' -> p, w')
• Tr (Pp, w) = Ew'(Rww' & p, w')

Example (straightforward translation, and then applying simplifications that produce equivalent formulas in predicate logic):

Tr(Np -> NNp, w0) = Tr(Np, w0) -> Tr(NNp, w0) = Aw'(Rww' -> p, w') -> Aw'(Rww' -> Np, w') = Aw'(Rww' -> p, w') -> Aw'(Rww' -> Aw''(Rw'w'' -> p, w'')) = Aw'(Rww' -> p, w') -> Aw'Aw''(Rww' -> (Rw'w'' -> p, w'')) = Aw'(Rww' -> p, w') -> Aw'Aw''((Rww' & Rw'w'') -> p, w'')

We present the correspondences between axiomatic systems in the S-series and models in the ∫k-series:

• For the system K, the minimal normal modal system, no conditions are imposed on R. We designate the model-based system matching K, ∫k.
• For the system D, called deontic, the condition on R is called seriality. It can be expressed in first-order language as follows: for every member w1 of W, there is at least one member w2 of W such that Rw1w2 (w1 and w2 are R-related, or <w1, w2> belongs to R, or, intuitively, w1 "looks into" or accesses w2. ∫kser
• For the system T, called alethic, the condition on R is reflexivity: for every member w of W, Rww or w accesses itself. ∫kr
• For the system B, called Brouwerian, the condition is symmetry: for every pair of worlds w1 and w2 of W, if Rw1w2 then Rw2w1 - or, for any world that accesses another world, the second also accesses the first. Notice that if not-Rw1w2 then the conditional (if Rw1w2, then Rw2w1) is also true - vacuously (because the antecedent is false.) This is unintuitive but the connective in our modal logics for "if-then" is the same as that of standard propositional logic and the "if-then" function of propositional is so defined that it allows for vacuous and trivial implication. Vacuous implication is from a false antecedent and trivial implication is to a true conditional. Here is the definition of implication: T->T=T, T->F=F, F->T=T, F->F=F. ∫ks
• For the system S4, which we will take as epistemic here, the conditions on R are reflexivity (see definition above) and also transitivity which means: for any three worlds w1, w2, and w3, if Rw1w2 and Rw2w3, then Rw1w3: if any three worlds are so related that the first accesses the second and the second accesses the third, then the first has to access the third. The remarks about vacuity and triviality of implication made above apply here too of course. ∫krt
• Finally, the system S5, called Leibnizian or the system of logical necessity, requires in addition to reflexivity also symmetry and transitivity. ∫krst

The systems are related in certain ways. A system extends another system properly if and only if it has all the theses of the other system plus at least one thesis not in the system that is extended. It is clear that the conditions on R are inter-related in ways that determine how the systems themselves are related. For instance, a reflexive system has to be serial (since every world is guaranteed a world to access, even if this world is the world itself.) A serial system, however, may not be reflexive. A system ∫i is stronger than a system ∫j iff ∫i proves more than ∫j: for this to happen we need more conditions on R; when we place more conditions on R, we make it harder to produce counterexamples for any given formula. We can think of implicative formulas as giving us argument forms in which the antecedent is the premise and the consequent is the conclusion. A counterexample to an argument form is an instance of the form in which all the premises are true and the conclusion is false. For instance, take the characteristic thesis of S4, which is the 4-axiom: Np -> NNp. This is an implicative formula. As an argument form, the 4-axiom has "Np" as premise and "NNp" as conclusion. It can be written as: Np \- NNp. In modeling the S-systems above, which are weaker than S4, we can generate counterexamples to Np \- NNp, i.e. we can show instances in which Np is made true and NNp is made false. But in modeling S4, by means of ∫krt, it becomes impossible to find a counterexample to Np \- NNp. Here is the proof of that:

1. Given premise: Np, w0. (Np is true at the actual world of evaluation, w0.)
2. Assumed Premise: ~ Np (We assume the negation of what we want to prove (that is, we assume that ~ Np); if we reach a contradiction, we have proven Np.)
3. From 1: in all worlds w, such that Rw0w: p, w. (This we have from the definition of N.)
4. From 2: P~p. (We get this thanks to the relationship between strong and weak modal operators: Np and ~ P~p are logically equivalent.)
5. From 4: there has to be at least one possible world, w1, such that: ~ p, w1. (We get this from the definition of P.)
6. From 3: p, w1. (w1 is just one of the worlds accessed by R. So, it must be that p is true at w1 since it is necessarily true at w0.)
7. From 5 and 6: ! (We have contradiction: p, w1 and ~ p, w1)
8. 2-7: Np. (We have successfully applied reductio: our assumed premise has brought us to a contradiction.)

## S4 - interpreted

The model by means of which we interpret S4 has reflexivity and transitivity as conditions on R. Each possible world looks into itself and into every possible world seen by any world it looks into.

More accurately, it is the frame on which the model is built that matters. The frame F = <W, R> which is the model minus the valuations on atomic propositional variables. This frame validates:

F /- Np -> NNp and /- PPp -> Pp

The famous logician Kurt Godel used this modal system for translating intensionally the connectives of propositional logic for the purpose of modeling Intuitionistic Logic. This is a sub-Logic of Propositional (it proves less but everything it proves is also provable in standard propositional logic.) The philosophical motivation for Intuitionistic Logic arises from the view that, in Mathematics at least, "truth" means probability in principle by means of a constructible proof-procedure. And "not" means that there is in principle an available and constructible proof procedure for demonstrating that not-p.

Another application if the model for S4 is epistemic (having to do with knowledge.) Caution is needed, though. Let us interpret the strong modal operator N as "to know that" - symbolizing by K. Given the theses of our S4-model, we will obtain unacceptable logical truths for certain definitions of "know." Notice that "Kp -> KKp" is a thesis. This reads: if one knows, then she knows that she knows. This is unacceptable for many readings of "know."

The notion of "know" for which the model seems fit is "omniscient knowledge." This can be local omniscience - for instance a computer program may be taken as being omniscient with respect to its entire database. The weak operator, interpreting P, is B: reasonable belief. We know that in every modal system, then strong and weak modal operators are mutually inter-definable: Lp = ~ P ~ p. The is rendered as Kp = ~ B ~ p: to know that p is the same as not to reasonably believe that not-p. Similarly, we have: K ~ p = ~ B p; ~ K p = B ~ p. All this makes sense for omniscient knowledge but not for ither notions of knowledge.

The system S4 has only seven distinct modalities. This means that no matter how many iterated modal operators we have in S4 formulas, they are reducible - they are logically equivalent - to the following seven. (We count a formula or letter p as a zero-degree modality.): {p, Np, Pp, NPNp, PNPp, NPp, PNp}. For instance, NNp is reducible to Np - one of the seven modalities.

For the epistemic interpretation, the seven distinct modalities are as follows. (We lose track of intuitive readings of iterated modals when we have three or more iterated or nestled modals, as fir instance in something like KBBKBBKp.)

Epistemic modalities - no more needed, the rest can be reduced to one of the following seven: {p, Kp, Bp, KBKp, BKBp, KBp, BKp}.

160

0

16

6

2

15

3