Kripke semantics (also known as relational semantics or frame semantics, and often confused with
possible world semantics
A possible world is a complete and consistent way the world is or could have been. They are widely used as a formal device in logic
Logic is an interdisciplinary field which studies truth and reasoning. Informal logic seeks to characterize ...
) is a formal
semantics
Semantics (from grc, σημαντικός ''sēmantikós'', "significant") is the study of reference
Reference is a relationship between objects in which one object designates, or acts as a means by which to connect to or link to, another ...
for
non-classical logic Non-classical logics (and sometimes alternative logics) are formal system
A formal system is an abstract structure used for inferring theorems from axioms according to a set of rules. These rules, which are used for carrying out the inference of t ...
systems created in the late 1950s and early 1960s by
Saul Kripke
Saul Aaron Kripke (; born November 13, 1940) is an American philosopher
American(s) may refer to:
* American, something of, from, or related to the United States of America, commonly known as the United States
** Americans, citizens and nationa ...

and
André Joyal
André Joyal (; born 1943) is a professor of mathematics
Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are ...
. It was first conceived for
modal logic
Modal logic is a collection of formal system
A formal system is an used for inferring theorems from axioms according to a set of rules. These rules, which are used for carrying out the inference of theorems from axioms, are the logical calculus ...
s, and later adapted to
intuitionistic logic
Intuitionistic logic, sometimes more generally called constructive logic, refers to systems of symbolic logic
Mathematical logic, also called formal logic, is a subfield of mathematics exploring the formal applications of logic to mathematics. I ...
and other non-classical systems. The development of Kripke semantics was a breakthrough in the theory of non-classical logics, because the
model theory
In mathematical logic
Mathematical logic is the study of formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory. Research in mathematical logic commonly addresses the mathematical ...
of such logics was almost non-existent before Kripke (algebraic semantics existed, but were considered 'syntax in disguise').
Semantics of modal logic
The language of propositional modal logic consists of a
countably infinite set of
propositional variable
In mathematical logic
Mathematical logic is the study of formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory. Research in mathematical logic commonly addresses the mathematical p ...
s, a set of truth-functional
connectives
In Mathematical logic, logic, a logical connective (also called a logical operator, sentential connective, or sentential operator) is a logical constant used to connect two or more formulas. For instance in the syntax (logic), syntax of proposi ...
(in this article
and
), and the modal operator
("necessarily"). The modal operator
("possibly") is (classically) the
dual
Dual or Duals may refer to:
Paired/two things
* Dual (mathematics), a notion of paired concepts that mirror one another
** Dual (category theory), a formalization of mathematical duality
** . . . see more cases in :Duality theories
* Dual ...
of
and
may be defined in terms of necessity like so:
("possibly A" is defined as equivalent to "not necessarily not A").
Basic definitions
A Kripke frame or modal frame is a pair
, where ''W'' is a (possibly empty) set, and ''R'' is a
binary relation
Binary may refer to:
Science and technology
Mathematics
* Binary number
In mathematics and digital electronics
Digital electronics is a field of electronics
The field of electronics is a branch of physics and electrical engineeri ...
on ''W''. Elements
of ''W'' are called ''nodes'' or ''worlds'', and ''R'' is known as the
accessibility relation
An accessibility relation is a relation which plays a key role in assigning truth values to sentences in the relational semantics
Kripke semantics (also known as relational semantics or frame semantics, and often confused with possible world s ...
.
A Kripke model is a triple
, where
is a Kripke frame, and
is a relation between nodes of ''W'' and modal formulas, such that for all ''w'' ∈ ''W'' and modal formulas ''A'' and ''B'':
*
if and only if
,
*
if and only if
or
,
*
if and only if
for all
such that
.
We read
as “''w'' satisfies
''A''”, “''A'' is satisfied in ''w''”, or
“''w'' forces ''A''”. The relation
is called the
''satisfaction relation'', ''evaluation'', or ''
forcing relation''.
The satisfaction relation is uniquely determined by its
value on propositional variables.
A formula ''A'' is valid in:
* a model
, if
for all ''w'' ∈ ''W'',
* a frame
, if it is valid in
for all possible choices of
,
* a class ''C'' of frames or models, if it is valid in every member of ''C''.
We define Thm(''C'') to be the set of all formulas that are valid in
''C''. Conversely, if ''X'' is a set of formulas, let Mod(''X'') be the
class of all frames which validate every formula from ''X''.
A modal logic (i.e., a set of formulas) ''L'' is
sound
In physics
Physics is the that studies , its , its and behavior through , and the related entities of and . "Physical science is that department of knowledge which relates to the order of nature, or, in other words, to the regular ...

with
respect to a class of frames ''C'', if ''L'' ⊆ Thm(''C''). ''L'' is
complete
Complete may refer to:
Logic
* Completeness (logic)
* Complete theory, Completeness of a theory, the property of a theory that every formula in the theory's language or its negation is provable
Mathematics
* The completeness of the real numbers, ...
wrt ''C'' if ''L'' ⊇ Thm(''C'').
Correspondence and completeness
Semantics is useful for investigating a logic (i.e. a
derivation system) only if the
semantic consequence
Logical consequence (also entailment) is a fundamental concept
Concepts are defined as abstract ideas
A mental representation (or cognitive representation), in philosophy of mind
Philosophy of mind is a branch of philosophy that studies ...
relation reflects its syntactical counterpart, the ''
syntactic consequence'' relation (''derivability''). It is vital to know which modal logics are sound and complete with respect to a class of Kripke frames, and to determine also which class that is.
For any class ''C'' of Kripke frames, Thm(''C'') is a
normal modal logic In logic, a normal modal logic is a set ''L'' of modal formulas such that ''L'' contains:
* All propositional tautology (logic), tautologies;
* All instances of the Saul_Kripke, Kripke schema: \Box(A\to B)\to(\Box A\to\Box B)
and it is closed under: ...
(in particular, theorems of the minimal normal modal logic, ''K'', are valid in every Kripke model). However, the converse does not hold in general: while most of the modal systems studied are complete of classes of frames described by simple conditions,
Kripke incomplete normal modal logics do exist. A natural example of such a system is
Japaridze's polymodal logicJaparidze's polymodal logic (GLP) is a system of provability logic with infinitely many provability modal logic, modalities. This system has played an important role
in some applications of provability algebras in proof theory, and has been extensiv ...
.
A normal modal logic ''L'' corresponds to a class of frames ''C'', if ''C'' = Mod(''L''). In other words, ''C'' is the largest class of frames such that ''L'' is sound wrt ''C''. It follows that ''L'' is Kripke complete if and only if it is complete of its corresponding class.
Consider the schema T :
.
T is valid in any
reflexive frame
: if
, then
since ''w'' ''R'' ''w''. On the other hand, a frame which
validates T has to be reflexive: fix ''w'' ∈ ''W'', and
define satisfaction of a propositional variable ''p'' as follows:
if and only if ''w'' ''R'' ''u''. Then
, thus
by T, which means ''w'' ''R'' ''w'' using the definition of
. T corresponds to the class of reflexive
Kripke frames.
It is often much easier to characterize the corresponding class of
''L'' than to prove its completeness, thus correspondence serves as a
guide to completeness proofs. Correspondence is also used to show
''incompleteness'' of modal logics: suppose
''L''
1 ⊆ ''L''
2 are normal modal logics that
correspond to the same class of frames, but ''L''
1 does not
prove all theorems of ''L''
2. Then ''L''
1 is
Kripke incomplete. For example, the schema
generates an incomplete logic, as it
corresponds to the same class of frames as GL (viz. transitive and
converse well-founded frames), but does not prove the GL-tautology
.
Common modal axiom schemata
The following table lists common modal axioms together with their corresponding classes. The naming of the axioms often varies.
Common modal systems
Canonical models
For any normal modal logic, ''L'', a Kripke model (called the canonical model) can be constructed that refutes precisely the non-theorems of
''L'', by an adaptation of the standard technique of using
maximal consistent sets as models. Canonical Kripke models play a
role similar to the
Lindenbaum–Tarski algebra
In mathematical logic, the Lindenbaum–Tarski algebra (or Lindenbaum algebra) of a model theory#Definition, logical theory ''T'' consists of the equivalence classes of Sentence (mathematical logic), sentences of the theory (i.e., the quotient, unde ...
construction in algebraic
semantics.
A set of formulas is ''L''-''consistent'' if no contradiction can be derived from it using the theorems of ''L'', and Modus Ponens. A ''maximal L-consistent set'' (an ''L''-''MCS''
for short) is an ''L''-consistent set that has no proper ''L''-consistent superset.
The canonical model of ''L'' is a Kripke model
, where ''W'' is the set of all ''L''-''MCS'',
and the relations ''R'' and
are as follows:
:
if and only if for every formula
, if
then
,
:
if and only if
.
The canonical model is a model of ''L'', as every ''L''-''MCS'' contains
all theorems of ''L''. By
Zorn's lemma
Zorn's lemma, also known as the Kuratowski–Zorn lemma, after mathematicians Max August Zorn, Max Zorn and Kazimierz Kuratowski, is a proposition of set theory. It states that a partially ordered set containing upper bounds for every chain (or ...
, each ''L''-consistent set
is contained in an ''L''-''MCS'', in particular every formula
unprovable in ''L'' has a counterexample in the canonical model.
The main application of canonical models are completeness proofs. Properties of the canonical model of K immediately imply completeness of K with respect to the class of all Kripke frames.
This argument does ''not'' work for arbitrary ''L'', because there is no guarantee that the underlying ''frame'' of the canonical model satisfies the frame conditions of ''L''.
We say that a formula or a set ''X'' of formulas is canonical
with respect to a property ''P'' of Kripke frames, if
* ''X'' is valid in every frame that satisfies ''P'',
* for any normal modal logic ''L'' that contains ''X'', the underlying frame of the canonical model of ''L'' satisfies ''P''.
A union of canonical sets of formulas is itself canonical.
It follows from the preceding discussion that any logic axiomatized by
a canonical set of formulas is Kripke complete, and
compact
Compact as used in politics may refer broadly to a pact
A pact, from Latin ''pactum'' ("something agreed upon"), is a formal agreement. In international relations
International relations (IR), international affairs (IA) or internationa ...
.
The axioms T, 4, D, B, 5, H, G (and thus
any combination of them) are canonical. GL and Grz are not
canonical, because they are not compact. The axiom M by itself is
not canonical (Goldblatt, 1991), but the combined logic S4.1 (in
fact, even K4.1) is canonical.
In general, it is
undecidable whether a given axiom is
canonical. We know a nice sufficient condition:
Henrik Sahlqvist identified a broad class of formulas (now called
Sahlqvist formulas) such that
* a Sahlqvist formula is canonical,
* the class of frames corresponding to a Sahlqvist formula is first-order logic, first-order definable,
* there is an algorithm that computes the corresponding frame condition to a given Sahlqvist formula.
This is a powerful criterion: for example, all axioms
listed above as canonical are (equivalent to) Sahlqvist formulas.
Finite model property
A logic has the finite model property (FMP) if it is complete
with respect to a class of finite frames. An application of this
notion is the decidability (logic), decidability question: it
follows from
Post's theorem that a recursively axiomatized modal logic ''L''
which has FMP is decidable, provided it is decidable whether a given
finite frame is a model of ''L''. In particular, every finitely
axiomatizable logic with FMP is decidable.
There are various methods for establishing FMP for a given logic.
Refinements and extensions of the canonical model construction often
work, using tools such as #Model constructions, filtration or
#Model constructions, unravelling. As another possibility,
completeness proofs based on cut-elimination, cut-free
sequent calculus, sequent calculi usually produce finite models
directly.
Most of the modal systems used in practice (including all listed
above) have FMP.
In some cases, we can use FMP to prove Kripke completeness of a logic:
every normal modal logic is complete with respect to a class of
modal algebras, and a ''finite'' modal algebra can be transformed
into a Kripke frame. As an example, Robert Bull proved using this method
that every normal extension of S4.3 has FMP, and is Kripke
complete.
Multimodal logics
Kripke semantics has a straightforward generalization to logics with
more than one modality. A Kripke frame for a language with
as the set of its necessity operators
consists of a non-empty set ''W'' equipped with binary relations
''R
i'' for each ''i'' ∈ ''I''. The definition of a
satisfaction relation is modified as follows:
:
if and only if
A simplified semantics, discovered by Tim Carlson, is often used for
polymodal provability logics. A Carlson model is a structure
with a single accessibility relation ''R'', and subsets
''D
i'' ⊆ ''W'' for each modality. Satisfaction is
defined as
:
if and only if
Carlson models are easier to visualize and to work with than usual
polymodal Kripke models; there are, however, Kripke complete polymodal
logics which are Carlson incomplete.
Semantics of intuitionistic logic
Kripke semantics for
intuitionistic logic
Intuitionistic logic, sometimes more generally called constructive logic, refers to systems of symbolic logic
Mathematical logic, also called formal logic, is a subfield of mathematics exploring the formal applications of logic to mathematics. I ...
follows the same
principles as the semantics of modal logic, but it uses a different
definition of satisfaction.
An intuitionistic Kripke model is a triple
, where
is a preordered Kripke frame, and
satisfies the following conditions:
* if ''p'' is a propositional variable,
, and
, then
(''persistency'' condition (cf. monotonicity)),
*
if and only if
and
,
*
if and only if
or
,
*
if and only if for all
,
implies
,
* not
.
The negation of ''A'', ¬''A'', could be defined as an abbreviation for ''A'' → ⊥. If for all ''u'' such that ''w'' ≤ ''u'', not ''u''
⊩ ''A'', then ''w''
⊩ ''A'' → ⊥ is vacuous truth, vacuously true, so ''w''
⊩ ¬''A''.
Intuitionistic logic is sound and complete with respect to its Kripke
semantics, and it has the finite model property.
Intuitionistic first-order logic
Let ''L'' be a first-order logic, first-order language. A Kripke
model of ''L'' is a triple
, where
is an intuitionistic Kripke frame, ''M
w'' is a
(classical) ''L''-structure for each node ''w'' ∈ ''W'', and
the following compatibility conditions hold whenever ''u'' ≤ ''v'':
* the domain of ''M
u'' is included in the domain of ''M
v'',
* realizations of function symbols in ''M
u'' and ''M
v'' agree on elements of ''M
u'',
* for each ''n''-ary predicate ''P'' and elements ''a''
1,...,''a
n'' ∈ ''M
u'': if ''P''(''a''
1,...,''a
n'') holds in ''M
u'', then it holds in ''M
v''.
Given an evaluation ''e'' of variables by elements of ''M
w'', we
define the satisfaction relation
:
*
if and only if
holds in ''M
w'',
*
if and only if
and
,
*
if and only if
or
,
*
if and only if for all
,
implies
,
* not
,
*
if and only if there exists an
such that
,
*
if and only if for every
and every
,
.
Here ''e''(''x''→''a'') is the evaluation which gives ''x'' the
value ''a'', and otherwise agrees with ''e''.
See a slightly different formalization in.
Kripke–Joyal semantics
As part of the independent development of sheaf theory, it was realised around 1965 that Kripke semantics was intimately related to the treatment of existential quantification in topos theory. That is, the 'local' aspect of existence for sections of a sheaf was a kind of logic of the 'possible'. Though this development was the work of a number of people, the name Kripke–Joyal semantics is often used in this connection.
Model constructions
As in classical
model theory
In mathematical logic
Mathematical logic is the study of formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory. Research in mathematical logic commonly addresses the mathematical ...
, there are methods for
constructing a new Kripke model from other models.
The natural homomorphisms in Kripke semantics are called
p-morphisms (which is short for ''pseudo-epimorphism'', but the
latter term is rarely used). A p-morphism of Kripke frames
and
is a mapping
such that
* ''f'' preserves the accessibility relation, i.e., ''u R v'' implies ''f''(''u'') ''R’'' ''f''(''v''),
* whenever ''f''(''u'') ''R’'' ''v''’, there is a ''v'' ∈ ''W'' such that ''u R v'' and ''f''(''v'') = ''v''’.
A p-morphism of Kripke models
and
is a p-morphism of their
underlying frames
, which
satisfies
:
if and only if
, for any propositional variable ''p''.
P-morphisms are a special kind of bisimulations. In general, a
bisimulation between frames
and
is a relation
''B ⊆ W × W’'', which satisfies
the following “zig-zag” property:
* if ''u B u’'' and ''u R v'', there exists ''v’'' ∈ ''W’'' such that ''v B v’'' and ''u’ R’ v’'',
* if ''u B u’'' and ''u’ R’ v’'', there exists ''v'' ∈ ''W'' such that ''v B v’'' and ''u R v''.
A bisimulation of models is additionally required to preserve forcing
of atomic formulas:
: if ''w B w’'', then
if and only if
, for any propositional variable ''p''.
The key property which follows from this definition is that
bisimulations (hence also p-morphisms) of models preserve the
satisfaction of ''all'' formulas, not only propositional variables.
We can transform a Kripke model into a tree (graph theory), tree using
unravelling. Given a model
and a fixed
node ''w''
0 ∈ ''W'', we define a model
, where ''W’'' is the
set of all finite sequences
such
that ''w
i R w
i+1'' for all
''i'' < ''n'', and
if and only if
for a propositional variable
''p''. The definition of the accessibility relation ''R’''
varies; in the simplest case we put
:
,
but many applications need the reflexive and/or transitive closure of
this relation, or similar modifications.
Filtration is a useful construction which uses to prove Kripke semantics#Finite model property, FMP for many logics. Let ''X'' be a set of
formulas closed under taking subformulas. An ''X''-filtration of a
model
is a mapping ''f'' from ''W'' to a model
such that
* ''f'' is a surjection,
* ''f'' preserves the accessibility relation, and (in both directions) satisfaction of variables ''p'' ∈ ''X'',
* if ''f''(''u'') ''R’'' ''f''(''v'') and
, where
, then
.
It follows that ''f'' preserves satisfaction of all formulas from
''X''. In typical applications, we take ''f'' as the projection
onto the quotient set, quotient of ''W'' over the relation
: ''u ≡
X v'' if and only if for all ''A'' ∈ ''X'',
if and only if
.
As in the case of unravelling, the definition of the accessibility
relation on the quotient varies.
General frame semantics
The main defect of Kripke semantics is the existence of Kripke incomplete logics, and logics which are complete but not compact. It can be remedied by equipping Kripke frames with extra structure which restricts the set of possible valuations, using ideas from algebraic semantics. This gives rise to the general frame semantics.
Computer science applications
Blackburn et al. (2001) point out that because a relational structure is simply a set together with a collection of relations on that set, it is unsurprising that relational structures are to be found just about everywhere. As an example from theoretical computer science, they give labeled transition systems, which model computer program, program execution. Blackburn et al. thus claim because of this connection that modal languages are ideally suited in providing "internal, local perspective on relational structures." (p. xii)
History and terminology
Similar work that predated Kripke's revolutionary semantic breakthroughs:
[preprint]
(See the last two paragraphs in Section 3 Quasi-historical Interlude: the Road from Vienna to Los Angeles.)
* Rudolf Carnap seems to have been the first to have the idea that one can give a possible world semantics for the modalities of necessity and possibility by means of giving the valuation function a parameter that ranges over Leibnizian possible worlds. Bayart develops this idea further, but neither gave recursive definitions of satisfaction in the style introduced by Tarski;
* J.C.C. McKinsey and Alfred Tarski developed an approach to modeling modal logics that is still influential in modern research, namely the algebraic approach, in which Boolean algebras with operators are used as models. Bjarni Jónsson and Tarski established the representability of Boolean algebras with operators in terms of frames. If the two ideas had been put together, the result would have been precisely frame models, which is to say Kripke models, years before Kripke. But no one (not even Tarski) saw the connection at the time.
*Arthur Prior, building on unpublished work of C. A. Meredith, developed a translation of sentential modal logic into classical predicate logic that, if he had combined it with the usual model theory for the latter, would have produced a model theory equivalent to Kripke models for the former. But his approach was resolutely syntactic and anti-model-theoretic.
* Stig Kanger gave a rather more complex approach to the interpretation of modal logic, but one that contains many of the key ideas of Kripke's approach. He first noted the relationship between conditions on accessibility relations and C.I. Lewis, Lewis-style axioms for modal logic. Kanger failed, however, to give a completeness proof for his system;
* Jaakko Hintikka gave a semantics in his papers introducing epistemic logic that is a simple variation of Kripke's semantics, equivalent to the characterisation of valuations by means of maximal consistent sets. He doesn't give inference rules for epistemic logic, and so cannot give a completeness proof;
* Richard Montague had many of the key ideas contained in Kripke's work, but he did not regard them as significant, because he had no completeness proof, and so did not publish until after Kripke's papers had created a sensation in the logic community;
* Evert Willem Beth presented a semantics of intuitionistic logic based on trees, which closely resembles Kripke semantics, except for using a more cumbersome definition of satisfaction.
See also
* Alexandrov topology
* Normal modal logic
* Two-dimensionalism
* Induction_puzzles#Muddy_Children_Puzzle, Muddy Children Puzzle
Notes
:aAfter Andrzej Grzegorczyk.
References
*
*
*
*
*
*
*
*
*
External links
*
*
* N.B: Constructive = intuitionistic.
*
*
{{DEFAULTSORT:Kripke Semantics
Modal logic
Model theory
Mathematical logic
Philosophical logic
Sheaf theory
Non-classical logic
de:Kripke-Semantik