Page 363 - Encyclopedia of Philosophy of Language

is sound with respect to the class of models in which R is transitive and there is no infinite sequence of worlds W!, w2, w3 ,... such that R(w,, w2), and R(w2,w3)and —
It is important to note that if a system is sound with respect to a class of models, it by no means follows that these are the only models in which the theorems of the system are all valid. In the case of T, for exam- ple, there are certainly models which are not reflexive, yet in which all the theorems of T are valid.
3.2 Completeness and Canonical Models
The system K is complete with respect to the class of all modal models. This is to say that every WFF that is valid—that is, valid in every model—is a theorem of the system K.
The fundamental idea behind a proof of com- pleteness is familiar from nonmodal propositional and predicate logic. The aim is to show that every WFF that is not a theorem is not valid. Then, one notes that A is not a theorem if and only if ~ A is consistent (that is, no contradiction can be proved from ~A), and that A is not valid if and only if ~ A is satisfiable. So, to demonstrate completeness, it is sufficient to show that if a WFF is consistent, then it is satisfiable— which, in the case of modal systems, means that it is true at some world in some model. Usually, the aim is to prove a stronger result; namely, that if a set of WFFS Z is consistent, then there is a world in some model such that all the WFFSin £ are true at that world. Such a world is said to satisfy I. In this statement of 'strong completeness,' the set 2 may be infinite.
In the case of normal modal systems, it is possible to establish an even stronger completeness result. In the case of the system K, for example, it can be shown that there is a single modal model—the 'canonical model' for K—with the property that each set of WFFS Z that is consistent in K is satisfied by some world in that model. (The method of canonical models was introduced by Lemmon and Scott (1977); for a later exposition, see Hughes and Cresswell (1984).)
Clearly, the existence of this canonical model for K shows that K is complete with respect to the class of all modal models. The method of canonical models can also be applied to T, to yield a model in which each set of WFFS that is consistent in T is satisfied by some world. Furthermore, this canonical model for T is a reflexive model; and that suffices to show that T is complete with respect to the class of reflexive models. In a similar way, the method of canonical models can be used to show that the systems K4, S4, B, and S5 are complete with respect to the classes of models in which the R-relation is transitive (K4), reflexive and transitive (S4), reflexive and symmetric (B), and an equivalence relation (S5) respectively.
The application of the method of canonical models to the system G is more indirect (Boolos 1979). But for each of the other systems, this establishes a class
of modal models with respect to which the system is both sound and complete.
3.3 Characterization and Frames
For each of the six modal systems K, K4, T, S4, B, and S5, there is a class of models that exactly characterizes the system, in the sense that the theorems of the system are exactly the WFFS that are valid in all models in that class. Furthermore, in each case, the class of models is defined in terms of a condition upon the R-relation (or no condition in the case of K).
However, quite generally, there will be many differ- ent classes of models that characterize the same system. The system K, for example, is characterized by the class of all modal models. But it is also char- acterized by the class of all models in which the R- relation is irreflexive; that is, in which, for each world w, w is not R-related to itself.
The system T is characterized by the class of reflex- ive models, but—as already noted—there are models for T in which the R-relation is not reflexive. So, the class of models in which all the theorems of T are valid is more inclusive than the class of reflexive models. The canonical model for T is, of course, a model for T, and so belongs to this more inclusive class; so, for each WFF that is not a theorem of T, there is a model in the class in which that WFF is not valid. Consequently, the class of all models for T charac- terizes the system T. Similarly, it can be seen that the class of models comprising just the canonical model for T characterizes the system T. In fact, for any normal modal system, the class of all models for the system, and the class comprising just the canonical model for the system, will each characterize the system.
The class of reflexive models is far from being the unique class of models that characterizes the system T. In particular, it has been seen that a class including nonreflexive models characterizes T. The discussion now introduces the notion of a frame: a pair <W,R>, where W is a set (the set of possible worlds) and R is a binary relation on W (the accessibility relation). A WFFof propositional modal logic is 'valid on a frame' <W, R> if it is valid in every model <W, R, V> based upon that frame. A frame <W,R> is said to be a 'frame for a modal system' if every theorem of that system is valid on <W, R>.
It is possible to show that if <W, R, V> is a non- reflexive model for T, then there is another model <W, R, V > on the same frame <W, R> in which some theorem of T is not valid. Thus, if <W, R> is a frame for T, then R is reflexive (in which case the frame is also said to be reflexive). As a consequence, one can say not only that the class of reflexive frames charac- terizes T, but also that the class of reflexive frames is the most inclusive class of frames that characterizes T.
Similarly, it is also possible to show that any frame 341
Modal Logic