Editing Modal logic (section)

==== 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.