Editing Modal logic (section)

==Semantics==

===Relational semantics===

{{See also|Kripke semantics}}

==== Basic notions<!--'Necessary proposition' and 'Necessary propositions' redirect here--> ====

The standard semantics for modal logic is called the ''relational semantics''. In this approach, the truth of a formula is determined relative to a point which is often called a ''[[possible world]]''. For a formula that contains a modal operator, its truth value can depend on what is true at other [[accessibility relation|accessible]] worlds. Thus, the relational semantics interprets formulas of modal logic using [[model (logic)|models]] defined as follows.<ref>Fitting and Mendelsohn. ''[https://books.google.com/books?id=5IxqCQAAQBAJ First-Order Modal Logic]''. Kluwer Academic Publishers, 1998. Section 1.6</ref>

* A ''relational model'' is a tuple <math> \mathfrak{M} = \langle W, R, V \rangle </math> where:
# <math> W </math> is a set of possible worlds
# <math> R </math> is a binary relation on <math> W</math>
# <math>V </math> is a valuation function which assigns a truth value to each pair of an atomic formula and a world, (i.e. <math> V: W \times F \to \{ 0,1 \}</math> where <math>F</math> is the set of atomic formulae)

The set <math> W </math> is often called the ''universe''. The binary relation <math>R</math> is called an [[accessibility relation]], and it controls which worlds can "see" each other for the sake of determining what is true. For example, <math>w R u</math> means that the world <math>u</math> is accessible from world <math>w</math>. That is to say, the [[State of affairs (philosophy)|state of affairs]] known as <math>u</math> is a live possibility for <math>w</math>. Finally, the function <math>V</math> is known as a [[valuation function]]. It determines which [[atomic formula]]s are true at which worlds.

Then we recursively define the truth of a formula at a world <math>w</math> in a model <math>\mathfrak{M}</math>:

* <math>\mathfrak{M}, w \models P</math> iff <math>V(w, P)=1</math>
* <math>\mathfrak{M}, w \models \neg P</math> iff <math>w \not \models P</math>
* <math>\mathfrak{M}, w \models (P \wedge Q) </math> iff <math>w \models P</math> and <math>w \models Q</math>
* <math>\mathfrak{M}, w \models \Box P</math> iff for every element <math>u</math> of <math>W</math>, if <math> w R u</math> then <math>u \models P</math>
* <math>\mathfrak{M}, w \models \Diamond P</math> iff for some element <math>u</math> of <math>W</math>, it holds that <math>w R u</math> and <math>u \models P</math>

According to this semantics, a formula is ''necessary'' with respect to a world <math>w</math> if it holds at every world that is accessible from <math>w</math>. It is ''possible'' if it holds at some world that is accessible from <math>w</math>. Possibility thereby depends upon the accessibility relation <math>R</math>, which allows us to express the relative nature of possibility. For example, we might say that given our laws of physics it is not possible for humans to travel faster than the speed of light, but that given other circumstances it could have been possible to do so. Using the accessibility relation we can [[Logic translation|translate]] this scenario as follows: At all of the worlds accessible to our own world, it is not the case that humans can travel faster than the speed of light, but at one of these accessible worlds there is ''another'' world accessible from ''those'' worlds but not accessible from our own at which humans can travel faster than the speed of light.

==== Frames and completeness====

The choice of accessibility relation alone can sometimes be sufficient to guarantee the truth or falsity of a formula. For instance, consider a model <math>\mathfrak{M}</math> whose accessibility relation is [[reflexive relation|reflexive]]. Because the relation is reflexive, we will have that <math>\mathfrak{M},w \models P \rightarrow \Diamond P </math> for any <math> w \in G </math> regardless of which valuation function is used. For this reason, modal logicians sometimes talk about ''frames'', which are the portion of a relational model excluding the valuation function.

* A ''relational frame'' is a pair <math> \mathfrak{M} = \langle G, R \rangle </math> where <math> G </math> is a set of possible worlds, <math> R </math> is a binary relation on <math> G</math>.

The different systems of modal logic are defined using ''frame conditions''. A frame is called:

* '''[[reflexive relation|reflexive]]''' if ''w R w'', for every ''w'' in ''G''
* '''[[symmetric relation|symmetric]]''' if ''w R u'' implies ''u R w'', for all ''w'' and ''u'' in ''G''
* '''[[transitive relation|transitive]]''' if ''w R u'' and ''u R q'' together imply ''w R q'', for all ''w'', ''u'', ''q'' in ''G''.
* '''[[serial relation|serial]]''' if, for every ''w'' in ''G'' there is some ''u'' in ''G'' such that ''w R u''.
* '''[[euclidean relation|Euclidean]]''' if, for every ''u'', ''t'', and ''w'', ''w R u'' and ''w R t'' implies ''u R t'' (by symmetry, it also implies ''t R u'', as well as ''t R t'' and ''u R u'')

The logics that stem from these frame conditions are:
*''K'' := no conditions
*''D'' := serial
*''T'' := reflexive
*''B'' := reflexive and symmetric
*''S4'' := [[preorder|reflexive and transitive]]
*''[[S5 (modal logic)|S5]]'' := reflexive and [[euclidean relation|Euclidean]]

The Euclidean property along with reflexivity yields symmetry and transitivity. (The Euclidean property can be obtained, as well, from symmetry and transitivity.) Hence if the accessibility relation ''R'' is reflexive and Euclidean, ''R'' is provably [[symmetric relation|symmetric]] and [[transitive relation|transitive]] as well. Hence for models of S5, ''R'' is an [[equivalence relation]], because ''R'' is reflexive, symmetric and transitive.

We can prove that these frames produce the same set of valid sentences as do the frames where all worlds can see all other worlds of ''W'' (''i.e.'', where ''R'' is a "total" relation). This gives the corresponding ''modal graph'' which is total complete (''i.e.'', no more edges (relations) can be added). For example, in any modal logic based on frame conditions:
: <math>w \models \Diamond P</math> if and only if for some element ''u'' of ''G'', it holds that <math>u \models P</math> and ''w R u''.

If we consider frames based on the total relation we can just say that
: <math>w \models \Diamond P</math> if and only if for some element ''u'' of ''G'', it holds that <math>u \models P</math>.
We can drop the accessibility clause from the latter stipulation because in such total frames it is trivially true of all ''w'' and ''u'' that ''w R u''. But this does not have to be the case in all S5 frames, which can still consist of multiple parts that are fully connected among themselves but still disconnected from each other.

All of these logical systems can also be defined axiomatically, as is shown in the next section. For example, in S5, the axioms <math>P \implies \Box\Diamond P</math>, <math>\Box P \implies \Box\Box P</math> and <math>\Box P \implies P</math> (corresponding to ''symmetry'', ''transitivity'' and ''reflexivity'', respectively) hold, whereas at least one of these axioms does not hold in each of the other, weaker logics.

=== Topological semantics ===

Modal logic has also been interpreted using topological structures. For instance, the ''Interior Semantics'' interprets formulas of modal logic as follows.

A ''topological model'' is a tuple <math> \Chi = \langle X, \tau, V \rangle </math> where <math> \langle X, \tau \rangle</math> is a [[topological space]] and <math>V</math> is a valuation function which maps each atomic formula to some subset of <math>X</math>. The basic interior semantics interprets formulas of modal logic as follows:

* <math> \Chi, x \models P </math> iff <math> x \in V(P) </math>
* <math> \Chi, x \models \neg \phi </math> iff <math> \Chi, x \not\models \phi </math>
* <math> \Chi, x \models \phi \land \chi </math> iff <math> \Chi, x \models \phi</math> and <math>\Chi, x \models \chi </math>
* <math> \Chi, x \models \Box \phi </math> iff for some <math> U \in \tau </math> we have both that <math> x \in U </math> and also that <math> \Chi, y \models \phi </math> for all <math> y \in U </math>

Topological approaches subsume relational ones, allowing [[non-normal modal logic]]s. The extra structure they provide also allows a transparent way of modeling certain concepts such as the evidence or justification one has for one's beliefs. Topological semantics is widely used in recent work in formal epistemology and has antecedents in earlier work such as [[David Lewis (philosopher)|David Lewis]] and [[Angelika Kratzer]]'s logics for [[counterfactuals]].