1
$\begingroup$

I am just beginning to study basic modal logic as described here (up to page 5 so far). My first impression -- I'm sure it can't be right -- is that it is just different symbols for the same concepts in ordinary predicate logic. Instead of $\forall x: P(x)$, we write $\square P$ (quantifying over a domain of discourse corresponding the set of all "possible worlds.") Instead of $\exists x: P(x)$, we write $\diamond P$. It also seems that the other logical connectors are the same as those in propositional logic. What can we do in this basic modal logic that we cannot do in predicate logic or vice versa?

EDIT: No need to reinvent the wheel. See Standard Translation (from modal to FOL) at https://en.wikipedia.org/wiki/Standard_translation

FOLLOW-UP: Using these Standard Translations, I was able to formally derive a number of "axioms" of modal logic (some said to be controversial at wiki). Theorems 1-5, make no use of any restrictions on the accessibility relation R. The remainder variously make use of reflexive, symmetry and transitive properties on R.

$\endgroup$
  • $\begingroup$ I assume you read the abstract. This cs.tau.ac.il/~annaz/teaching/TAU_winter08/Seminar/modalea.pdf has some Powerpoint slides with motivating examples. $\endgroup$ – John Douma Oct 29 '18 at 19:32
  • $\begingroup$ @MauroALLEGRANZA Note that you're really comparing modal logic with propositional logic, which isn't what this question is about. $\endgroup$ – Noah Schweber Oct 29 '18 at 19:55
  • 2
    $\begingroup$ Reflexivity and transitivity are less objectionable (in my mind) but there are still important situations where we don't want either. And each of these is certainly not true of all Kripke frames in general. (And even worse, there are modal logics of interest which don't play well with Kripke frames in the first place!) Basically, I think you're doing some injustice to modal logic in terms of your axiomatization: you're restricting attention to a very very narrow modal logic (specifically, I think you've built S$5$). $\endgroup$ – Noah Schweber Nov 1 '18 at 14:14
  • 1
    $\begingroup$ For example, in temporal logic we certainly don't want symmetry! And we might not want reflexivity either, if we interpret accessibility as moving strictly forward in time. Finally, the provability logic GL actively objects to reflexivity, by way of the Lob axiom. As for a nontransitive example, anytime the accessibility relation corresponds to something like "is close to," we probably don't want to assume transitivity since "close to close to $x$" doesn't necessarily imply "close to $x$." $\endgroup$ – Noah Schweber Nov 1 '18 at 14:20
  • 1
    $\begingroup$ Well the wikipedia article starts with "This article needs attention from an expert in logic. The specific problem is: inaccurate, partly wrong, presentation. WikiProject Logic may be able to help recruit an expert. (November 2016)", so what do you expect? $\endgroup$ – j4n bur53 Nov 1 '18 at 15:22
11
$\begingroup$

Your impression is right, but missing the point in some sense: modal logic is strictly less powerful than first-order logic, and this is one of the reasons it is so important in various contexts (especially applications of logic in computer science)! The reason is that there is a fundamental "power-versus-tameness" tradeoff implicit in any choice of logic, and we often prefer the latter to the former. Modal logic should be thought of as a particularly well-behaved fragment of first-order logic: we're often interested in decidable (or similarly nice) fragments of first-order logic in applications, and modal logic and its variants provide a wide swath of examples of such logics.

Note that this is reflected in the history of modal logic: it long predated first-order logic, and was an expansion of propositional logic by adding modal operators. After first-order logic burst on the scene, we came to understand modal logic as an intermediate logic, and that's the perspective I'm describing here since I think it matches more the perspective you're adopting.

This paper by Vardi is a useful source in this regard. In particular, the following passage from page $2$ is quite relevant:

  • "There are two main computational problems associated with modal logic. The first problem is checking if a given formula is true in a given state of a given Kripke structure. This problem is known as the model-checking problem. The second problem is checking if a given formula is true in all states of all Kripke structures. This problem is known as the validity problem. Both problems are decidable. The model-checking problem can be solved in linear time, while the validity problem is PSPACE-complete. This is rather surprising when one considers the fact that modal logic, in spite of its apparent propositional syntax, is essentially a first-order logic, since the necessity and possibility modalities quantify over the set of possible worlds, and model checking and validity for first-order logic are computationally hard problems. Furthermore, the undecidability of first-order logic is very robust. Only very restricted fragments of first-order logic are decidable ..."

Vardi goes on to talk about types of tameness, specifically focusing on two ways of generating tame fragments of first-order logic - bounding the quantifiers and limiting the number of variables - and then argues that modal logic really represents a third, and extremely robust, kind of tameness. At this point we move beyond the focus of this specific question; the point I want to make is that modal logic is not a strengthening of first-order logic, but rather quite the opposite, and that for many applications this is actually a good thing.

The last section of Chagrov and Zakharyaschev's book is also relevant, and in general I strongly recommend that book: it's quite dense, but has a huge wealth of material.

It's worth noting that the idea of looking at "tame" fragments of "wild" logics appears all over the place, e.g. the analysis of monadic second-order logic (contra full second-order logic) and the decomposition of $\mathcal{L}_{\omega_1\omega}$ into well-behaved countable sublogics. Coming from a more set- or model-theoretic background, it may seem odd at first to apply the same idea to first-order logic because of how "primal" it is, but it is in fact a very rich line of research.


To add a bit of detail, here's the translation of modal logic into first-order logic (well, for Kripke frames anyways; I'll leave generalizations as exercises):

Given a Kripke frame $\mathcal{K}=(W,\leadsto,\models_\mathcal{K})$ ($W$ = worlds, $\leadsto$ = accessibility relation, $\models_\mathcal{K}$ = valuation) in a propositional language $\Sigma=\{p_i\}_{i\in I}$, our corresponding language $\Sigma_\mathcal{K}$ consists of a unary predicate $P_i$ for each $i\in I$ and a binary relation symbol $R$, and our corresponding structure $M_\mathcal{K}$ has domain $W$, interprets $P_i$ as $\{w\in W: w\models_\mathcal{K} p_i\}$, and interprets $R$ as $\{(u,v)\in W^2: u\leadsto v\}$.

(Note that this is not quite what you've described: you've described the "local" version, where we focus on a single world in $\mathcal{K}$.)

Now, for every modal sentence $s$ in the language $\Sigma$, we get a first-order formula $\varphi_s(x)$ in one free variable saying that $s$ holds at $x$ in the sense of $\mathcal{K}$; meanwhile, the formula $\psi_s\equiv\forall x(\varphi_s(x))$ says of course that $s$ holds throughout $\mathcal{K}$. The key point here is:

There are first-order sentences not coming from modal sentences in this, or any reasonable, way.

For example, consider something like "$\forall x\exists y(R(x,y)\vee R(y,x))$." How precisely can you express this modally, in any sense?


EDIT: That said, there are aspects of modal logic which take it beyond first-order. (I previously said a bit about this in comments, but I think now it's a good idea to put it in the answer body.) In particular, we say that a frame (without a chosen valuation) validates a given modal sentence if every valuation makes that sentence true at every world. Each modal sentence $\varphi$ then defines a class of frames $V(\varphi)$. For example, $$(\Diamond\Diamond p)\iff(\Diamond p)$$ is validated exactly in the transitive frames.

Viewing (sans valuation) frames as directed graphs, we can ask whether every "modal validation" class $V(\varphi)$ is an elementary class. The answer turns out to be no, the easiest example in my opinion being the Lob axiom $$\lambda\equiv\Box(\Box (p)\rightarrow p)\rightarrow \Box(p).$$ (Proof: it's not hard to show that $V(\lambda)$ is the set of transitive, converse well-founded frames, that is, those transitive frames not admitting any infinite sequence of worlds each of which sees the next. Now use the compactness theorem.)

See also j4n bur53's answer, and this paper of Thomason. Note that when people say that a given modal sentence has no first-order equivalent, or isn't first-order expressible, they're talking about validity.

$\endgroup$
3
$\begingroup$

An example of a modal logic, that cannot be modelled via first order logic, is the McKinsey axiom. This axiom reads as follows:

$$M: \quad \Box ~ \Diamond ~ \phi \, \rightarrow \, \Diamond ~ \Box ~\phi$$

This modal logic is not mentioned in Joel McCance script, because the script only deals with couple of first order definable modal logics.

See also:
Is there a more useful formulation of the
frame condition for the McKinsey axiom?

https://math.stackexchange.com/a/1279608/4414

$\endgroup$
  • 1
    $\begingroup$ +1. To explain how this doesn't contradict what I wrote in my answer: what's really being said here is "the class of Kripke frames validating $M$ is not first-order." The axiom $M$ itself is easily translated into first-order logic in the sense described in my answer, but my answer is talking "post-valuation" whereas validity is talking about possible valuations. Incidentally, the Lob axiom $\Box(\Box p\rightarrow p)\rightarrow\Box p$ also gives an example of a sentence whose validating class isn't first-order definable. $\endgroup$ – Noah Schweber Oct 30 '18 at 2:33
  • $\begingroup$ According to van Benthem you cannot translate M to first order. Since it is $Π_1^1$. See for yourself: staff.science.uva.nl/j.vanbenthem/docs/CT.pdf , in premisse position, as an axiom M, you cannot turn a $\forall P(...) \vDash ...$ into a $\forall P( ... \vDash ...)$, it is equivalent to $\exists P (... \vDash ...)$. There is no problem with the translation in consequence position. $\endgroup$ – j4n bur53 Oct 30 '18 at 3:17
  • $\begingroup$ Again, the issue is what you mean when you say "translate $M$ to first-order." The thing that isn't expressible in first-order is the statement "this frame validates $M$." But we can easily write a sentence which holds of (the first-order structure corresponding to) a frame with valuation if and only if every world in the frame satisfies "$\Box\Diamond\varphi\implies \Diamond\Box\varphi$" (where $\varphi$ is a given propositional atom) with respect to that valuation. $\endgroup$ – Noah Schweber Oct 30 '18 at 3:24
  • $\begingroup$ Well from the context of my post M should act as an axiom. I don't know anything about your post. So I guess I cannot answer, I didn't go through your post, since I knew the McKinsey axiom from elsewhere. $\endgroup$ – j4n bur53 Oct 30 '18 at 3:25
  • $\begingroup$ The $\Pi^1_1$-ness comes from the fact that when we talk about validation, we're quantifying over all possible valuations, and this amounts to treating the propositional atom as an arbitrary subset of the set of worlds, and universally quantifying over it. $\endgroup$ – Noah Schweber Oct 30 '18 at 3:25
1
$\begingroup$

You were asking for correspondence. But your DC Proof results only show "valid if" and not "valid iff". So they only show sufficient conditions, but not necessary conditions. This is a little pointless. For example you have proved:

$$reflexiv+transitive \vdash "\Diamond P \Rightarrow \Box \Diamond P\,Axiom"$$

But now there is a problem that reflexiv+transitive cannot act as a replacement and hence correspondence of $"\Diamond P \Rightarrow \Box \Diamond P \,Axiom"$. It might give false positive. For example reflexiv+transitive gives:

$$reflexiv+transitive \vdash q \Rightarrow \Diamond q$$

But we do not have:

$$"\Diamond P => \Box \Diamond P\,Axiom" \nvdash q \Rightarrow \Diamond q$$

Proof: That reflexiv+transitive gives $q \Rightarrow \Diamond q$, is a consequence that the later is equivalent to $[] \neg p \Rightarrow \neg p$, and hence can use the correspondence for reflexivity. But on the other hand that the later doesn't hold we only need to show at least one counter model.

enter image description here

Model drawn and evaluated with:
https://rkirsling.github.io/modallogic/

You find a couple of "valid iff" proofs here:
http://www2.math.uu.se/~hedin/TillLog/LectureNotesAL.pdf

$\endgroup$
  • $\begingroup$ I chose several of the so-called axioms in modal logic given at wiki. Most of them did not require any additional assumptions about the accessibility relation. For the others, I arbitrarily picked one or more of the following to make them work and to illustrate how modal logic works when translated into FOL: reflexivity, symmetry, transitivity. References to these properties seem to show up often in the literature of modal logic. I left the converses of those theorems as an exercise just for you, Jan. You seem to have a lot of time on your hands these days. ;^) $\endgroup$ – Dan Christensen Nov 2 '18 at 3:38
  • $\begingroup$ The axiom ◊P=>◻◊P is not equivalent to reflexiv+transitive. It is pointless to prove reflexiv+transitive |- ◊P=>◻◊P. You can easily find counter models with this tool here: rkirsling.github.io/modallogic And you find a couple of "valid iff" proofs here: www2.math.uu.se/~hedin/TillLog/LectureNotesAL.pdf $\endgroup$ – j4n bur53 Nov 2 '18 at 10:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.