modal logic

Introduction

Modal logic is the logic of “necessity” and “possibility”. It is an extension of the classical logic, with two additional unary logical connectives $\mathrm{\square }$ and $\mathrm{◇}$. The well-formed formulas of modal logic is then the smallest set satisfying the following:

1. the propositional variables are well-formed formulas,

2. if $A,B$ are (well-formed) formulas, then so are $A\vee B$, $A\wedge B$, $\mathrm{\neg }A$, $A\to B$,

3. if $A$ is a formula, so are $\mathrm{\square }A$ and $\mathrm{◇}A$,

4. and if the logic is first-order, then for any formula $A$, so are $\exists xA$ and $\forall xA$.

Let $L$ be the set of all well-formed formulas described above, and $L_0$ the set of all formulas formed with condition 3 removed. Then $L_0\subseteq L$ is just the set of all formulas of the classical logic (the underlying classical logic), and is part of the reason why we call modal logic an extension of the classical logic. The other reasons have to do with semantics and deductions, to be discussed below.

$\mathrm{\square }A$ is usually interpreted as “it is necessarily true that $A$”, and $\mathrm{◇}A$ as “it is possibly true that $A$”.

In order to study the logical truth and valid deductions in modal logic, we need to know how to interpret $\mathrm{\square }$ and $\mathrm{◇}$. So just what are precisely the meanings of “necessity” and “possibility”? Because of the lack of exact mathematical interpretations of these vague terms, and $\mathrm{\square }$ and $\mathrm{◇}$ more generally, there are a great many kinds of modal logics, than the other well-known logical systems, such as classical logic and intuitionistic logic.

In fact, one can take $\mathrm{\square }$ and $\mathrm{◇}$ to be qualifiers attachable to any propositions (or sentences). So $\mathrm{\square }$ could mean “in South Africa” and $\mathrm{◇}$ “in the U.S.”. Then, if $A$ is the sentence “July is a summer month”, then $\mathrm{\square }A$ and $\mathrm{◇}A$ are read “July is a summer month in South Africa” and “July is a summer month in the U.S.” respectively. Some of the common interpretations of $\mathrm{\square }A$ are:

• (alethic logic) $A$ is necessarily true

• (provability logic) $A$ is provable in PA

• (deontic logic) it ought to be that $A$

• (epistemic logic) it is known that $A$

• (doxastic logic) it is believed that $A$

• (temporal logic) $A$ will always be true

Additionally, for most of the modal logics, $\mathrm{◇}$ is ‘defined” in terms of $\mathrm{\square }$:

$$\mathrm{◇}A:=\mathrm{\neg }\mathrm{\square }\mathrm{\neg }A.$$ (1)

In the next two subsections, we restrict our attention to only propositional modal logic.

Semantics

As mentioned previously, a modal logic is an extension of the classical logic. As such, tautologies and tautological consequences of valid formulas should be valid in any semantical model of modal logic. More precisely, call a formula in a modal logic $L$ prime or quasi-atomic if it is

• either a propositional variable, or

• of the form $\mathrm{\square }A$, where $A$ is in $L$.

It is easy to see that any formula in $L$ can be built up from quasi-atoms using just $\to$ (or other connectives, depending on the choice of axiom system for classical propositional logic). In this sense, $L$ can be thought of as a classical logic where the propositional variables range over quasi-atoms. Now, let $M$ be any semantic model of the $L$, we write

$$M\vDash A$$

to mean $A$ is true in the model $M$. Then,

• if $A$ is an instance of a tautology (viewing $L$ as the classical propositional logic here), then $M\vDash A$,

• if $A_1,\mathrm{\dots },A_n$ tautologically implies $A$, and if $M\vDash A_i$ for each $i$, then $M\vDash A$.

We call a formula in a modal logic $L$ a tautology if it is an instance of a tautology of $L$ viewed as the classical propositional logic over its quasi-atoms. Therefore, $\mathrm{\square }A\to \mathrm{\square }A$ is a tautology, since it is an instance of the tautology $X\to X$. Also, if $\mathrm{\square }A$ and $\mathrm{\square }A\to \mathrm{\square }B$ are both valid, so is $\mathrm{\square }B$, since $\mathrm{\square }B$ may be deduced by modus ponens.

For the majority of the modal logics (known as normal modal logics), the principal semantic model is the Kripke semantics, or possible-world semantics. It is a generalization of the truth-value semantics for the classical propositional logic. A Kripke model $M$ consists of a triple $(W,R,T)$ where $W$ is a non-empty set of elements called possible worlds, $R$ is a binary relation on $W$ (called accessibility relation), and $T$ is a function from the set of atomic propositions (propositional variables) to $P(W)$, the powerset of $W$. Semantic truth condition of a proposition $A$ is written

$$M{\vDash }_{\alpha }A$$

to mean “$A$ is true in possible world $\alpha$ in model $M$”, or ${\vDash }_{\alpha }A$ if $M$ is clear from the context.

The relation $\vDash$ is defined recursively as follows:

1. if $A$ is atomic, then ${\vDash }_{\alpha }A$ iff $\alpha \in T(A)$

2. ${\vDash }_{\alpha }⟂$ for no $\alpha \in W$

3. ${\vDash }_{\alpha }A\to B$ iff if ${\vDash }_{\alpha }A$ then ${\vDash }_{\alpha }B$

4. ${\vDash }_{\alpha }\mathrm{\square }A$ iff for all $\beta$ where $\alpha R\beta$, ${\vDash }_{\beta }A$

The truth conditions of $\mathrm{\neg }A,A\wedge B,A\vee B$, and $\diamond A$ can be derived. For example, ${\vDash }_{\alpha }\mathrm{◇}A$ iff there is some $\beta$ where $\alpha R\beta$, such that ${\vDash }_{\beta }A$.

If $A$ is true in every possible world in $M$, we say that $A$ is true in $M$, and write $M\vDash A$. When $A$ is true in every model, then we say that $A$ is valid, and write $\vDash A$. The formula schema K, for example, is a set of valid formulas. Also, if $A$ is valid, it is easy to see that so is $\mathrm{\square }A$ valid.

In addition to Kripke semantics, there are also a number of semantic tools, some are lattices with operators, some are systems of open neighborhoods in topological spaces, while others are just variations or generalizations of the Kripke models, such as including more than one binary relation on the possible worlds, or having a subset of the possible worlds called “impossible worlds”.

Axiom Systems

As explained in the previous subsection, tautologies and tautological consequences of valid formulas are valid, in any semantic interpretation of a modal logic. Similarly, in any axiom system for a modal logic:

• tautologies are to be considered axioms (or deducible from axioms), and

• modus ponens as an inference rule.

By including additional schemas of formulas as axioms, and imposing additional inference rules, one arrives at axiom systems for the different kinds of modal logics. Some of the common axioms schemas are listed above: K, 4, 5, D, T, B, and W. Some common inference rules (and their abbreviations) are

• RK: ${\displaystyle \frac{(A_1\wedge \mathrm{\cdots }\wedge A_n)\to A}{(\mathrm{\square }{A}_1\wedge \mathrm{\cdots }\wedge \mathrm{\square }{A}_n)\to \mathrm{\square }A}}$, $n\ge 0$

• RR: ${\displaystyle \frac{(A\wedge B)\to C}{(\mathrm{\square }A\wedge \mathrm{\square }B)\to \mathrm{\square }C}}$

• RM: ${\displaystyle \frac{A\to B}{\mathrm{\square }A\to \mathrm{\square }B}}$

• RN (necessitation rule): ${\displaystyle \frac{A}{\mathrm{\square }A}}$

For example, a widely studied class of modal logics is the class of normal modal logics. A modal logic is normal if its axiom system consists of the axiom schema K and the rule RN.

Remarks.

• Like other logical systems, issues of soundness and completeness of a model with respect to an axiom system, as well as various decidability questions are also studied in modal logic. In addition, questions regarding on the equivalence of axiom systems are also very interesting.

• Extending modal logic, one has the notion of multi-modal logic, where the language of the logical system contains several, sometimes infinitely many, modal connectives. From the discussion above, a modal logic where connectives $\mathrm{\square }$ and $\mathrm{◇}$ are not inter-definable (and therefore must be non-normal) is really an example of a bimodal logic.

Title	modal logic
Canonical name	ModalLogic
Date of creation	2013-03-22 19:13:54
Last modified on	2013-03-22 19:13:54
Owner	CWoo (3771)
Last modified by	CWoo (3771)
Numerical id	34
Author	CWoo (3771)
Entry type	Topic
Classification	msc 03B45
Related topic	KripkeSemanticsForModalPropositionalLogic
Defines	quasi-atomic
Defines	quasi-atom