General frame explained
In logic, general frames (or simply frames) are Kripke frames with an additional structure, which are used to model modal and intermediate logics. The general frame semantics combines the main virtues of Kripke semantics and algebraic semantics: it shares the transparent geometrical insight of the former, and robust completeness of the latter.
Definition
A modal general frame is a triple
, where
is a Kripke frame (i.e.,
is a
binary relation on the set
), and
is a set of subsets of
that is closed under the following:
, defined by
\BoxA=\{x\inF\mid\forally\inF(xRy\toy\inA)\}
.They are thus a special case of fields of sets with additional structure. The purpose of
is to restrict the allowed valuations in the frame: a model
based on the Kripke frame
is
admissible in the general frame
, if
\{x\inF\midx\Vdashp\}\inV
for every
propositional variable
.The closure conditions on
then ensure that
belongs to
for
every formula
(not only a variable).
A formula
is
valid in
, if
for all admissible valuations
, and all points
. A
normal modal logic
is valid in the frame
, if all axioms (or equivalently, all theorems) of
are valid in
. In this case we call
an
-
frame.
A Kripke frame
may be identified with a general frame in which all valuations are admissible: i.e.,
\langleF,R,l{P}(F)\rangle
, where
denotes the
power set of
.
Types of frames
In full generality, general frames are hardly more than a fancy name for Kripke models; in particular, the correspondence of modal axioms to properties on the accessibility relation is lost. This can be remedied by imposing additional conditions on the set of admissible valuations.
A frame
is called
\forallA\inV(x\inA\Leftrightarrowy\inA)
implies
,
\forallA\inV(x\in\BoxA ⇒ y\inA)
implies
,
- compact, if every subset of
with the
finite intersection property has a non-empty intersection,
contains all singletons,
- refined, if it is differentiated and tight,
- descriptive, if it is refined and compact.
Kripke frames are refined and atomic. However, infinite Kripke frames are never compact. Every finite differentiated or atomic frame is a Kripke frame.
Descriptive frames are the most important class of frames because of the duality theory (see below). Refined frames are useful as a common generalization of descriptive and Kripke frames.
Operations and morphisms on frames
Every Kripke model
\langleF,R,{\Vdash}\rangle
the general frame
, where
is defined as
V=\{\{x\inF\midx\VdashA\}\midA\hbox{isaformula}\}.
The fundamental truth-preserving operations of generated subframes, p-morphic images, and disjoint unions of Kripke frames have analogues on general frames. A frame
is a
generated subframe of a frame
, if the Kripke frame
is a generated subframe of the Kripke frame
(i.e.,
is a subset of
closed upwards under
, and
), and
A
p-morphism (or
bounded morphism)
is a function from
to
that is a p-morphism of the Kripke frames
and
, and satisfies the additional constraint
for every
.The
disjoint union of an indexed set of frames
Fi=\langleFi,Ri,Vi\rangle
,
, is the frame
, where
is the
disjoint union of
,
is the union of
, and
V=\{A\subseteqF\mid\foralli\inI(A\capFi\inVi)\}.
The refinement of a frame
is a refined frame
defined as follows. We consider the
equivalence relationx\simy\iff\forallA\inV(x\inA\Leftrightarrowy\inA),
and let
be the set of equivalence classes of
. Then we put
\langlex/{\sim},y/{\sim}\rangle\inS\iff\forallA\inV(x\in\BoxA ⇒ y\inA),
Completeness
Unlike Kripke frames, every normal modal logic
is complete with respect to a class of general frames. This is a consequence of the fact that
is complete with respect to a class of Kripke models
\langleF,R,{\Vdash}\rangle
: as
is closed under substitution, the general frame induced by
\langleF,R,{\Vdash}\rangle
is an
-frame. Moreover, every logic
is complete with respect to a single
descriptive frame. Indeed,
is complete with respect to its canonical model, and the general frame induced by the canonical model (called the
canonical frame of
) is descriptive.
Jónsson–Tarski duality
General frames bear close connection to modal algebras. Let
be a general frame. The set
is closed under Boolean operations, therefore it is a
subalgebra of the power set
Boolean algebra \langlelP(F),\cap,\cup,-\rangle
. It also carries an additional
unary operation,
. The combined structure
\langleV,\cap,\cup,-,\Box\rangle
is a modal algebra, which is called the
dual algebra of
, and denoted by
.
In the opposite direction, it is possible to construct the dual frame
to any modal algebra
A=\langleA,\wedge,\vee,-,\Box\rangle
. The Boolean algebra
\langleA,\wedge,\vee,-\rangle
has a
Stone space, whose underlying set
is the set of all
ultrafilters of
. The set
of admissible valuations in
consists of the
clopen subsets of
, and the accessibility relation
is defined by
xRy\iff\foralla\inA(\Boxa\inx ⇒ a\iny)
for all ultrafilters
and
.
A frame and its dual validate the same formulas; hence the general frame semantics and algebraic semantics are in a sense equivalent. The double dual
of any modal algebra is isomorphic to
itself. This is not true in general for double duals of frames, as the dual of every algebra is descriptive. In fact, a frame
is descriptive
if and only if it is isomorphic to its double dual
.
It is also possible to define duals of p-morphisms on one hand, and modal algebra homomorphisms on the other hand. In this way the operators
and
become a pair of contravariant functors between the
category of general frames, and the category of modal algebras. These functors provide a
duality (called
Jónsson–Tarski duality after
Bjarni Jónsson and
Alfred Tarski) between the categories of descriptive frames, and modal algebras. This is a special case of a more general duality between complex algebras and fields of sets on relational structures.
Intuitionistic frames
The frame semantics for intuitionistic and intermediate logics can be developed in parallel to the semantics for modal logics. An intuitionistic general frame is a triple
, where
is a
partial order on
, and
is a set of
upper subsets (
cones) of
that contains the empty set, and is closed under
- intersection and union,
- the operation
.Validity and other concepts are then introduced similarly to modal frames, with a few changes necessary to accommodate for the weaker closure properties of the set of admissible valuations. In particular, an intuitionistic frame
is called
\forallA\inV(x\inA\Leftrightarrowy\inA)
implies
,
- compact, if every subset of
with the finite intersection property has a non-empty intersection.Tight intuitionistic frames are automatically differentiated, hence refined.
The dual of an intuitionistic frame
is the
Heyting algebra F+=\langleV,\cap,\cup,\to,\emptyset\rangle
. The dual of a Heyting algebra
A=\langleA,\wedge,\vee,\to,0\rangle
is the intuitionistic frame
, where
is the set of all prime filters of
, the ordering
is
inclusion, and
consists of all subsets of
of the form
where
. As in the modal case,
and
are a pair of contravariant functors, which make the category of Heyting algebras dually equivalent to the category of descriptive intuitionistic frames.
It is possible to construct intuitionistic general frames from transitive reflexive modal frames and vice versa, see modal companion.
See also
References
- Alexander Chagrov and Michael Zakharyaschev, Modal Logic, vol. 35 of Oxford Logic Guides, Oxford University Press, 1997.
- Patrick Blackburn, Maarten de Rijke, and Yde Venema, Modal Logic, vol. 53 of Cambridge Tracts in Theoretical Computer Science, Cambridge University Press, 2001.
