1 Introduction
This paper introduces and investigates a family of metrics applicable to finite and countably infinite strings and, by extension, formal structures described by a countable language. The family of metrics is a weighted generalization of the Hamming distance [Reference Hamming29]. On formal structures, each such metric corresponds to assigning positive weights to a chosen subset of some language describing the structure. The distance between two structures, then, is the sum of the weights of formulas on which the two structures differ in valuation.
While the approach is generally applicable, our main target is metrics on sets of pointed Kripke models, the most widely used semantic structures for modal logic. Apart from mathematical interest, there are several motivations for having a metric between pointed Kripke models. Among these are applications in iterated multi-agent belief revision [Reference Aucher2, Reference Caridroit, Konieczny, de Lima, Marquis, Kaminka, Fox, Bouquet, Hüllermeier, Dignum, Dignum and van Harmelen14–Reference Delgrande, Delgrande and Schaub16, Reference Lehmann, Magidor and Schlechta35], logical meta-theory [Reference Goranko, van Eijck, van Oostrom and Visser24], and the application of dynamical systems theory to information dynamics modeled using dynamic epistemic logic [Reference van Benthem6–Reference van Benthem, Ghosh and Szymanik9, Reference Klein, Rendsvig and Kraus32, Reference Klein and Rendsvig33, Reference Rendsvig, van der Hoek, Holliday and Wang38–Reference Sadzik40]. The latter is our main interest. In a nutshell, this paper contains a theoretical foundation for considering the logical dynamics of dynamic epistemic logic as discrete time dynamical systems: Compact metric spaces (of pointed Kripke models) together with continuous transition functions acting on them.
We have used this foundation in [Reference Klein and Rendsvig33] to study the recurrent behavior of clean maps defined through action models and product update. Among the recurrence results, we show clean maps induced by finite action models may have uncountably many recurrent points, even when initiated on a finite input model. In [Reference Klein, Rendsvig and Kraus32], we use a result by Edelstein [Reference Edelstein20], that every contractive map on a compact metric space has a unique fixed point, to contribute to the discussion concerning the attainability of common knowledge under unreliable communication [Reference Akkoyunlu, Ekanadham, Huber, Browne and Rodriguez-Rosell1, Reference Fagin, Halpern, Moses and Vardi21, Reference Fagin, Halpern, Moses and Vardi22, Reference Gray, Bayer, Graham and Seegmüller26, Reference Halpern and Moses28, Reference Yemini and Cohen44]. We show that the communicating generals may converge to a state of common knowledge iff their language of communication does not include a common knowledge operator.
The paper proceeds as follows: Section 2 presents the weighted generalization of the Hamming distance which in Section 3 is shown applicable to arbitrary sets of structures, given that the structures are abstractly described by a countable set of formulas within a possibly multi-valued semantics. Pointed Kripke models are in focus from Section 4 on, where we show these a concrete instantiation of the metrics defined. Section 5 is on topological properties of the resulting metric spaces. We show that two metrics are topologically equivalent when they agree on which formulas to assign strictly positive weight. The resulting topologies are generalizations of the Stone topology, referred to as Stone-like topologies. We investigate their properties including a clopen set characterization. Section 6 relates the metrics to other metrics from the literature, arguing that the present approach generalize them. Section 7 concerns convergence and limit points. A main result here is that Stone-like topologies are characterized by a logical convergence criterion, providing an argument for their naturalness. This results strengthens a result of [Reference Klein, Rendsvig, Baltag, Seligman and Yamada31]. Further, standard modal logics are used to exemplify discrete, imperfect, and perfect spaces, including relations to the Cantor set. Section 8 concerns mappings induced by product updates with multi-pointed action models—a particular graph product, widely used and studied in dynamic epistemic logic [Reference Baltag and Moss3–Reference Baltag, Renne and Zalta5, Reference van Benthem8, Reference van Benthem, van Eijck and Kooi11, Reference van Ditmarsch, van der Hoek and Kooi19]. As a final result, we show these induced maps continuous with respect to Stone-like topologies, thus establishing the desired connection between dynamic epistemic logic and discrete time dynamical systems.
2 Generalizing the Hamming distance
The method we propose for defining distances between pointed Kripke models is a special case: The general approach concerns distances between finite or infinite strings of letters from some given set, V. In a logical context, the set V may contain truth values for some logic, e.g., with
$V=\{0,1\}$
for normal modal logics. Pointed Kripke models are then represented by countably infinite strings of values from V: Given some enumeration of the corresponding modal language, a string will have a
$1$
on place k just in case the model satisfies the kth formula,
$0$
else (cf. Section 4).
A distance on sets of finite strings of a fixed length has been known since 1950, when it was introduce by Hamming [Reference Hamming29]. Informally, the Hamming distance between two such strings is the number of places on which the two strings differ. This distance is, in general, not well-defined on sets of infinite strings. To accommodate infinite strings, we generalize the Hamming distance:
Definition. Let S be a set of strings over a set V such that
$S\subseteq V^{n}$
for some
$n\in \mathbb {N}\cup \{\omega \}$
. For each
$k\leq n$
, define a disagreement map
$d_{k}:S\times S\longrightarrow \{0,1\}$
by
$$\begin{align*}d_{k}(s,s')={\textstyle \begin{cases} 0, & \text{ if }s_{k}=s^{\prime}_{k},\\ 1, & \text{ else}. \end{cases}} \end{align*}$$
Call
$w:\mathbb {N}\longrightarrow \mathbb {R}_{>0}$
a weight function if it assigns a strictly positive weight to each natural number such that
$(w(k))_{k\in \mathbb {N}}$
forms a convergent series, i.e.,
$\sum _{k=1}^{\infty }w(k)<\infty $
.
For weight function w, the distance function
$d_{w}:S\times S\longrightarrow \mathbb {R}$
is then defined by, for each
$s,s'\in S$
$$\begin{align*}d_{w}(s,s')=\sum_{k=1}^{\infty}w(k)d_{k}(s,s'). \end{align*}$$
Proposition 1. Let S and
$d_{w}$
be as above. Then
$d_{w}$
is a metric on S.
Proof The proof is straightforward.
The Hamming distance is indeed a special case of this Definition: For
$S\subseteq \mathbb {R}^{n}$
, the Hamming distance
$d_{H}$
is defined (cf. [Reference Deza and Deza17]) by
$d_{H}(s,s')=|\{i:1\leq i\leq n,s_{i}\not =s^{\prime }_{i}\}|$
. Then
$d_{H}$
is the metric
$d_{h}$
with weight function
$h(k)=1$
for
$1\leq k\leq n$
,
$h(k)=2^{-k}$
for
$k>n$
.
3 Metrics for formal structures
The above metrics may be indirectly applied to any set of structures that serves as semantics for a countable language. In essence, what is required is simply an assignment of suitable weights to formulas of the language. To illustrate the generality of the approach, we initially take the following inclusive view on semantic valuation:
Definition. Let a valuation be any map
$\nu :X\times D\longrightarrow V$
where X and V are arbitrary sets, and D is countable. Refer to elements of X as structures, to D as the descriptor, and to elements of V as values.
A valuation
$\nu $
assigns a value from V to every pair
$(x,\varphi )\in X\times D$
. Jointly,
$\nu $
and X thus constitute a V-valued semantics for the descriptor D.
Definition. Given a valuation
$\nu :X\times D\longrightarrow V$
and a subset
$D'$
of D, denote by
$\boldsymbol {X}_{D'}$
the quotient of X under
$D'$
equivalence, i.e.,
$\boldsymbol {X}_{D'}=\{\boldsymbol {x}{}_{D'}\colon x\in X\}$
with
$\boldsymbol {x}{}_{D'}=\{y\in X\colon \nu (y,\varphi )=\nu (x,\varphi )\text { for all }\varphi \in D'\}$
.
When the descriptor D is clear from context, we write
$\boldsymbol {x}$
for elements of
$\boldsymbol {X}_{D}$
. We also write
$\nu (\boldsymbol {x},\varphi )$
for
$\nu (x,\varphi )$
when
$\varphi \in D$
. Finally, we obtain a family of metrics on a quotient
$\boldsymbol {X}_{D}$
in the following manner:
Definition. Let
$\nu :X\times D\longrightarrow V$
be a valuation and
$\varphi _{1},\varphi _{2},\ldots $
an enumeration of D. For each
$\varphi _{k}\in D$
, define a disagreement map
$d_{k}:\boldsymbol {X}\times \boldsymbol {X}\longrightarrow \{0,1\}$
by
$$\begin{align*}d_{k}(\boldsymbol{x},\boldsymbol{y})={\textstyle \begin{cases} 0, & \text{ if }\nu(\boldsymbol{x},\varphi_{k})=\nu(\boldsymbol{y},\varphi_{k}),\\ 1, & \text{ else.} \end{cases}} \end{align*}$$
Call
$w:D\longrightarrow \mathbb {R}_{>0}$
a weight function if it assigns a strictly positive weight to each
$\varphi \in D$
such that
$\sum _{\varphi \in D}w(\varphi )<\infty $
.
For weight function w, the distance function
$d_{w}:\boldsymbol {X}_{D}\times \boldsymbol {X}_{D}\longrightarrow \mathbb {R}$
is then defined by, for each
$\boldsymbol {x},\boldsymbol {y}\in \boldsymbol {X}_{D}$
$$\begin{align*}d_{w}(\boldsymbol{x},\boldsymbol{y})=\sum_{k=1}^{|D|}w(\varphi_{k})d_{k}(\boldsymbol{x},\boldsymbol{y}). \end{align*}$$
The set of such maps
$d_{w}$
is denoted
$\mathcal {D}_{(X,\nu ,D)}$
.
Proposition 2. Every
$d_{w}\in \mathcal {D}_{(X,\nu ,D)}$
is a metric on
$\boldsymbol {X}_{D}$
.
Proof Follows from Proposition 1 when identifying each
$\boldsymbol {x}$
with
$(\nu (\boldsymbol {x}, \varphi _{i}))_{i\in \mathbb {N}}$
.
4 The application to pointed Kripke models
We follow the approach just described to apply the metrics to pointed Kripke model. Let X be a set of pointed Kripke models and D a set of modal logical formulas. Interpreting the latter over the former using standard modal logical semantics gives rise to a binary set of values, V, and a valuation function
$\nu :X\times D\rightarrow V$
equal to the classic interpretation of modal formulas on pointed Kripke models. In the following, we consequently omit references to
$\nu $
, writing
$\mathcal {D}_{(X,D)}$
for the family of metrics
$\mathcal {D}_{(X,\nu ,D)}$
.
4.1 Pointed Kripke models, their language and logics
Let be given a signature consisting of a countable, non-empty set of propositional atoms
$\Phi $
and a countable, non-empty set of operator indices,
$\mathcal {I}$
. Call the signature finite when both
$\Phi $
and
$\mathcal {I}$
are finite. The modal language
$\mathcal {L}$
for
$\Phi $
and
$\mathcal {I}$
is given by
$$\begin{align*}\varphi:=\top\;|\;p\;|\;\neg\varphi\;|\;\varphi\wedge\varphi\;|\;\square_{i}\varphi \end{align*}$$
with
$p\in \Phi $
and
$i\in \mathcal {I}$
. The language
$\mathcal {L}$
is countable.
A Kripke model for
$\Phi $
and
$\mathcal {I}$
is a tuple
where:
–
is a non-empty set of states;–
assigns to each
$i\in \mathcal {I}$
an accessibility relation
$R(i)$
;–
is a valuation, assigning to each atom a set of states.
A pair
$(M,s)$
with
is a pointed Kripke model. For the pointed Kripke model
$(M,s)$
, the shorter notation
$Ms$
is used. For
$R(i)$
, we write
$R_{i}$
.
The modal language is evaluated over pointed Kripke models with standard semantics:
Throughout, when referring to a modal language
$\mathcal {L}$
alongside a sets of pointed Kripke models X, we tacitly assume that all models in X share the signature of
$\mathcal {L}$
.
Logics may be formulated in
$\mathcal {L}$
. Here, we take a (modal) logic to be a subset of formulas
$\Lambda \subseteq \mathcal {L}$
which contains all instances of propositional tautologies, include for each
$i\in \mathcal {I}$
the K-axiom
$\square _{i}(p\rightarrow q)\rightarrow \square _{i}p\rightarrow \square _{i}q$
, is closed under Modus ponens (if
$\varphi $
and
$\varphi \rightarrow \psi $
are in
$\Lambda $
, then so is
$\psi $
), Uniform substitution (if
$\varphi $
is in
$\Lambda $
, then so is
$\varphi '$
, where
$\varphi '$
is obtained from
$\varphi $
by uniformly replacing proposition letters in
$\varphi $
by arbitrary formulas), and Generalization (if
$\varphi $
is in
$\Lambda $
, then so is
$\square _{i}\varphi $
).
Every logic here is thus an extension of the minimal normal modal logic K over the language
$\mathcal {L}$
. Normality is a minimal requirement for soundness and completeness with respect to classes of pointed Kripke models (see, e.g., [Reference Blackburn, de Rijke and Venema12]).
4.2 Descriptors for pointed Kripke models
We use sets of
$\mathcal {L}$
-formulas as descriptors for Kripke models. When two models disagree on the truth value of some formula
$\varphi $
, this contributes
$w(\varphi )$
to their distance. The choice of descriptor hence reflects the aspects of interests. To avoid double counting, one may pick descriptors that do not contain logically equivalent formulas. Hence, even if interested in all
$\mathcal {L}$
-expressible aspects, one may still pick a strict subset of
$\mathcal {L}$
as descriptor:
Definition. Let
$\mathcal {L}$
be a language for the set of pointed Kripke models X. A descriptor is any set
$D\subseteq \mathcal {L}$
. Say D is
$\mathcal {L}$
-representative over X if, for every
$\varphi \in \mathcal {L}$
, there is a set
$\{\psi _{i}\}_{i\in I}\subseteq D$
such that any valuation of
$\{\psi _{i}\}_{i\in I}$
semantically entails either
$\varphi $
or
$\neg \varphi $
over X. If the set
$\{\psi _{i}\}_{i\in I}$
can always be chosen finite, call D finitely
$\mathcal {L}$
-representative over X. For a logic
$\Lambda $
, say D is
$\Lambda $
-representative if it is
$\mathcal {L}$
-representative over some space X of pointed
$\Lambda $
-models in which every
$\Lambda $
-consistent set is satisfied in some
$x\in X$
. Let
$$\begin{align*}\overline{D}:=D\cup\{\neg\varphi:\varphi\in D\}. \end{align*}$$
The main implication of a descriptor being
$\mathcal {L}$
-representative is that
$\boldsymbol {X}_{D}$
is identical to
$\boldsymbol {X}_{\mathcal {L}}$
(cf. Lemma 3). We do not generally assume descriptors representative.
4.3 Modal spaces
We construct metrics on sets of structures modulo some modal equivalence. In parlance, we follow [Reference Klein, Rendsvig, Baltag, Seligman and Yamada31] in referring to modal spaces:
Definition. With X a set of pointed Kripke models and D a descriptor, the modal space
$\boldsymbol {X}_{D}$
is the set
$\{\boldsymbol {x}_{D}\colon x\in X\}$
with
$\boldsymbol {x}_{D}=\{y\in X:\forall \varphi \in D,y\vDash \varphi \text { iff }x\vDash \varphi \}$
. The truth set of
$\varphi \in \mathcal {L}$
in
$\boldsymbol {X}_{D}$
is
$[\varphi ]_{D}=\{\boldsymbol {x}\in \boldsymbol {X}_{D}:\forall x\in \boldsymbol {x},x\vDash \varphi \}$
.
The subscripts of
$\boldsymbol {x}_{D}$
and
$[\varphi ]_{D}$
are omitted when the descriptor is clear from context. Write
$\boldsymbol {x}_{D}\vDash \varphi $
for
$\boldsymbol {x}_{D}\in [\varphi ]_{D}$
.Footnote
1
The coarseness of the modal space
$\boldsymbol {X}_{D}$
is determined by the descriptor, with two extremes: At its finest,
$D=\mathcal {L}$
yields as
$\boldsymbol {X}_{D}$
the quotient of X under
$\mathcal {L}$
-equivalence,
$\boldsymbol {X}_{\mathcal {L}}$
; at its coarsest,
$D=\{\top \}$
produces as
$\boldsymbol {X}_{D}$
simply
$\{\{X\}\}$
. To obtain the finest modal space
$\boldsymbol {X}_{\mathcal {L}}$
,
$\mathcal {L}$
is not the only admissible descriptor:
Lemma 3. If
$D\subseteq \mathcal {L}$
is
$\mathcal {L}$
-representative for X, then
$\boldsymbol {X}_{D}$
is identical to
$\boldsymbol {X}_{\mathcal {L}}$
, i.e., for all
$x\in X$
,
$\boldsymbol {x}_{D}=\boldsymbol {x}_{\mathcal {L}}$
.
Proof
$\boldsymbol {x}_{\mathcal {L}}\subseteq \boldsymbol {x}_{D}$
: Trivial.
$\boldsymbol {x}_{D}\subseteq \boldsymbol {x}_{\mathcal {L}}$
: Let
$y\in \boldsymbol {x}{}_{D}$
and let
$\varphi \in \mathcal {L}$
. We show the left-to-right of
$x\vDash \varphi \Leftrightarrow y\vDash \varphi $
, the other direction being similar: Assume
$x\vDash \varphi $
. Let
$S=\{\psi \in D\colon x\vDash \psi \}.$
By representativity, there is no
$x'\in X$
satisfying
$S\cup \{\neg \psi \colon \psi \in D\setminus S\}\cup \{\neg \varphi \}$
. Since
$y\in \boldsymbol {x}_{D}$
it satisfies
$S\cup \{\neg \psi \colon \psi \in D\setminus S\}$
and hence also
$\varphi $
, i.e.,
$y\vDash \varphi $
.
4.4 Metrics on modal spaces
With the introduced, we obtain a family
$\mathcal {D}_{(X,D)}$
of metrics on the D-modal space of a set of pointed Kripke models X:
Proposition 4. Let
$D\subseteq \mathcal {L}$
, let X be a set of pointed Kripke models, let
$\nu :\boldsymbol {X}_{D}\times D\rightarrow \{0,1\}$
be a valuation given by
$\nu (\boldsymbol {x},\varphi )=1$
iff
$\boldsymbol {x}\in [\varphi ]_{D}$
, and let
$w:D\rightarrow \mathbb {R}_{>0}$
be a weight function. Then
$d_{w}$
is a metric on
$\boldsymbol {X}_{D}$
.
Proof Immediate from Proposition 2 as
$\nu $
is well-defined.
5 Topological properties
In fixing a descriptor D for X, one also fixes the family of metrics
$\mathcal {D}_{(X,D)}$
. The members of
$\mathcal {D}_{(X,D)}$
vary in their metrical properties (see Section 6), but topologically, all members of
$\mathcal {D}_{(X,D)}$
are equivalent. To show this, we work with the following generalization of the Stone topology:
Definition. Let
$\boldsymbol {X}_{D}$
be a modal space. The Stone-like topology on
$\boldsymbol {X}_{D}$
is the topology
$\mathcal {T}_{D}$
given by the subbasis
$\mathcal {S}_{D}$
of all sets
$\{\boldsymbol {x}\in \boldsymbol {X}_{D}\colon x\vDash \varphi \}$
and
$\{\boldsymbol {x}\in \boldsymbol {X}_{D}\colon x\vDash \neg \varphi \}$
for
$\varphi \in D$
.
As D need not be closed under conjunction, this subbasis is, in general, not a basis. When
$D\subseteq \mathcal {L}$
is
$\mathcal {L}$
-representative over X,
$\boldsymbol {X}_{D}$
is identical to
$\boldsymbol {X}_{\mathcal {L}}$
, and the Stone-like topology
$\mathcal {T}_{D}$
on
$\boldsymbol {X}_{D}$
is a coarsening of the Stone topology on
$\boldsymbol {X}_{\mathcal {L}}$
which is generated by the basis
${\{\{\boldsymbol {x}\in \boldsymbol {X}_{\mathcal {L}}\colon x\vDash \varphi \}:\varphi \in \mathcal {L}}\}$
. If D is finitely
$\mathcal {L}$
-representative over X,
$\mathcal {T}_{D}$
is identical to the Stone topology on
$\boldsymbol {X}_{\mathcal {L}}$
.
We can now state the promised topological equivalence:
Proposition 5. The metric topology
$\mathcal {T}_{w}$
of any metric
$d_{w}\in \mathcal {D}_{(X,D)}$
on
$\boldsymbol {X}_{D}$
is the Stone-like topology
$\mathcal {T}_{D}$
.
Proof
$\mathcal {T}_{w}\supseteq \mathcal {T}_{D}$
: It suffices to show the claim for all elements of the subbasis
$\mathcal {S}_{D}$
of
$\mathcal {T}_{D}$
. Let
$\boldsymbol {x}{\kern-1.2pt}\in{\kern-1.2pt} \boldsymbol {X}_{D}{\kern-1.2pt}\cap{\kern-1.2pt} B_{D}$
for some
$B_{D}{\kern-1.2pt}\in{\kern-1.2pt} \mathcal {S}_{D}$
. Then
$B_{D}$
is of the form
$\{\boldsymbol {y}{\kern-1.2pt}\in{\kern-1.2pt} \boldsymbol {X}_{D}{\kern-1pt}:{\kern-1pt}y\vDash \varphi \}$
or
$\{\boldsymbol {y}\in \boldsymbol {X}_{D}:y\vDash { {\neg }}\varphi \}$
for some
$\varphi \in D$
. The cases are symmetric, so assume the former. As
$\boldsymbol {x}\in B_{D}$
,
$\boldsymbol {x}\vDash \varphi $
. As
$\varphi \in D$
, its weight
$w(\varphi )$
in the metric
$d_{w}$
is strictly positive. The open ball
$B(\boldsymbol {x},w(\varphi ))$
of radius
$w(\varphi )$
around
$\boldsymbol {x}$
is a basis element of
$\mathcal {T}_{w}$
and contains
$\boldsymbol {x}$
. Moreover,
$B(\boldsymbol {x},w(\varphi ))\subseteq B_{D}$
, since
$y\not \vDash \varphi $
implies
$d_{w}(\boldsymbol {x},\boldsymbol {y})\geq w(\varphi )$
. Hence
$\mathcal {T}_{w}$
is finer than
$\mathcal {T}_{D}$
.
$\mathcal {T}_{w}\subseteq \mathcal {T}_{D}$
: Let
$\boldsymbol {x}\in \boldsymbol {X}_{D}\cap B$
for B an element of
$\mathcal {T}_{w}$
’s metrical basis. That is, B is of the form
$B(\boldsymbol {y},\delta )$
for some
$\delta>0$
. Let
$\epsilon =\delta -d_{w}(\boldsymbol {x},\boldsymbol {y})$
. Note that
$\epsilon>0$
. Let
$\varphi _{1},\varphi _{2},\ldots $
be an enumeration of D. Since
$\sum _{i=1}^{|D|}w(\varphi _{i})<\infty $
, there is some n such that
$\sum _{i=n}^{|D|}w(\varphi _{i})<\epsilon $
. For
$j<n$
, let
$\chi _{j}:=\varphi _{i}$
if
$\boldsymbol {x}\vDash \varphi _{j}$
and
$\chi _{j}:=\neg \varphi _{i}$
otherwise. Let
$\chi =\bigwedge _{j<n}\chi _{j}$
. By construction, all
$\boldsymbol {z}$
with
$\boldsymbol {z}\vDash \chi $
agree with
$\boldsymbol {x}$
on the truth values of
$\varphi _{1},\ldots ,\varphi _{n-1}$
and thus
$d_{w}(\boldsymbol {x},\boldsymbol {z})<\epsilon $
. By the triangular inequality, this implies
$d_{w}(\boldsymbol {y,z})<\delta $
and hence
$\{\boldsymbol {z}\in \boldsymbol {X}_{D}\colon \boldsymbol {z}\vDash \chi \}\subseteq B$
. Furthermore, since
$\mathcal {T}_{D}$
is generated by a subbasis containing
$\{\boldsymbol {x}\in \boldsymbol {X}_{D}\colon \boldsymbol {x}\vDash \varphi \}$
and
$\{\boldsymbol {x}\in \boldsymbol {X}_{D}\colon \boldsymbol {x}\vDash \neg \varphi \}$
for
$\varphi \in D$
, we have
$\{\boldsymbol {z}\in \boldsymbol {X}_{D}\colon \boldsymbol {z}\vDash \chi \}\in \mathcal {T}_{D}$
as desired.
As for any set of models X and any descriptor D the set
$\mathcal {D}_{(X,D)}$
is non-empty, we get:
Corollary 6. Any Stone-like topology
$\mathcal {T}_{D}$
on a space
$\boldsymbol {X}_{D}$
is metrizable.
5.1 Stone spaces
The Stone topology is well-known, but typically defined on the set of ultrafilters of a Boolean algebra, which it turns into a Stone space: A totally disconnected, compact, Hausdorff topological space. When equipping modal spaces with Stone-like topologies, Stone spaces often result.
Proposition 7. For any descriptor D, the space
$(\boldsymbol {X}_{D},\mathcal {T}_{D})$
is totally disconnected and Hausdorff.
Proof As
$\boldsymbol {x}\neq \boldsymbol {y}$
, there is a
$\varphi \in D$
such that
$\boldsymbol {x}\vDash \varphi $
while
$\boldsymbol {y}\not \vDash \varphi $
(or vice versa). The sets
$A=\{\boldsymbol {z}\in \boldsymbol {X}_{D}\colon z\vDash \varphi \}$
and
$\overline {A}=\{\boldsymbol {z}'\in \boldsymbol {X}_{D}\colon z\vDash \neg \varphi \}$
are both open in the Stone-like topology,
$A\cap \overline {A}=\emptyset $
, and
$A\cup \overline {A}=\boldsymbol {X}_{D}$
. As
$\boldsymbol {x}\in A$
and
$\boldsymbol {y}\in \overline {A}$
(or vice versa), the space
$(\boldsymbol {X}_{D},\mathcal {T}_{D})$
is totally disconnected. It is Hausdorff as it is metrizable.
The space
$(\boldsymbol {X}_{D},\mathcal {T}_{D})$
,
$D\subseteq \mathcal {L}$
, is moreover compact when two requirements are satisfied: First, there exists a logic
$\Lambda $
sound with respect to X which is (logically) compact: An arbitrary set
$A\subseteq \mathcal {L}$
of formulas is
$\Lambda $
-consistent iff every finite subset of A is.Footnote
2
As second requirement, we must assume the set X sufficiently rich in model diversity. In short, we require that every
$\Lambda $
-consistent subset of D has a model in X:
Definition. Let
$D\subseteq \mathcal {L}$
and let
$\Lambda $
be sound with respect to X. Then X is
$\Lambda $
-saturated with respect to D if for all subsets
$A,A'\subseteq D$
such that
$B=A\cup \{\neg \varphi \colon \varphi \in A'\}$
is
$\Lambda $
-consistent, there exists x in X such that
$x\vDash \psi $
for all
$\psi \in B$
. If D is also
$\mathcal {L}$
-representative over X, then X is
$\Lambda $
-complete.
For logical compactness,
$\Lambda $
-saturation is a sufficient richness conditions (cf. the proposition below). Remark 5.1 discusses
$\Lambda $
-saturation and
$\Lambda $
-completeness.
Proposition 8. If
$\Lambda $
is compact and X is
$\Lambda $
-saturated with respect to
$D\subseteq \mathcal {L}$
, then the space
$(\boldsymbol {X}_{D},\mathcal {T}_{D})$
is compact.
Proof A basis of
$\mathcal {T}_{D}$
is given by the family of all sets
$\{\boldsymbol {x}\in \boldsymbol {X}_{D}\colon \boldsymbol {x}\vDash \chi \}$
with
$\chi $
of the form
$\chi =\psi _{1}\wedge \cdots \wedge \psi _{n}$
where
$\psi _{i}\in \overline {D}$
for all
$i\leq n$
. Show
$(\boldsymbol {X}_{D},\mathcal {T}_{D})$
compact by showing that every open, basic cover has a finite subcover. Suppose
$\{\{\boldsymbol {x}\in \boldsymbol {X}_{D}\colon \boldsymbol {x}\vDash \chi _{i}\}\colon i\in I\}$
covers
$\boldsymbol {X}_{D}$
, but contains no finite subcover. Then every finite subset of
$\{\neg \chi _{i}\colon i\in I\}$
is satisfied in some
$\boldsymbol {x}\in \boldsymbol {X}_{D}$
and is hence
$\Lambda $
-consistent. By compactness of
$\Lambda $
, the set
$\{\neg \chi _{i}\colon i\in I\}$
is thus also
$\Lambda $
-consistent. Hence, by saturation, there is an
$\boldsymbol {x}\in \boldsymbol {X}_{D}$
such that
$\boldsymbol {x}\vDash \neg \chi _{i}$
for all
$i\in I$
. But then
$\boldsymbol {x}$
cannot be in
$\{\boldsymbol {x}\in \boldsymbol {X}_{D}\colon x\vDash \chi _{i}\}$
for any
$i\in I$
, contradicting that
$\{\{\boldsymbol {x}\in \boldsymbol {X}_{D} \colon \boldsymbol {x}\vDash \chi _{i}\}\colon i\in I\}$
covers
$\boldsymbol {X}$
.
Propositions 7 and 8 jointly yield the following:
Corollary 9. Let
$\Lambda \subseteq \mathcal {L}$
be a compact modal logic sound and complete with respect to the class of pointed Kripke models
$\mathcal {C}$
. Then
$(\mathcal {C}_{\mathcal {L}},\mathcal {T}_{\mathcal {L}})$
is a Stone space.
Proof The statement follows immediately from the propositions of this section when
$\mathcal {C}_{\mathcal {L}}$
is ensured to be a set using Scott’s trick [Reference Scott41].
Remark. When D is
$\mathcal {L}$
-representative for X and
$\boldsymbol {X}_{D}$
is
$\Lambda $
-saturated, one obtains a very natural space, containing a unique point satisfying each maximal
$\Lambda $
-consistent set of formulas. It is thus homeomorphic to the space of all complete
$\Lambda $
-theories under the Stone topology of
$\mathcal {L}$
. Such spaces have been widely studied (see, e.g., [Reference Goranko, van Eijck, van Oostrom and Visser24, Reference Johnstone30, Reference Stone43]). Calling such spaces
$\Lambda $
-complete reflects that the joint requirement ensures that the logic
$\Lambda $
is complete with respect to the set X, but that the obligation of sufficiency lies on the set X to be inclusive enough for
$\Lambda $
, not on
$\Lambda $
to be restrictive enough for X.
5.2 Clopen sets in Stone-like topologies
With the Stone-like topology
$\mathcal {T}_{D}$
generated by the subbasis
$\mathcal {S}_{D}=\{[\varphi ]_{D},[\neg \varphi ]_{D}\colon \varphi \in D\}$
, all subbasis elements are clearly clopen: If U is of the form
$[\varphi ]_{D}$
for some
$\varphi \in D$
, then the complement of U is the set
$[\neg \varphi ]_{D}$
, which again is a subbasis element. Hence both
$[\varphi ]_{D}$
and
$[\neg \varphi ]_{D}$
are clopen. More generally, we obtain the following:
Proposition 10. Let
$\Lambda $
be a logic sound with respect to the set of pointed Kripke models X. If
$\Lambda $
is compact and D is
$\Lambda $
-representative, then
$[\varphi ]_{D}$
is clopen in
$\mathcal {T}_{D}$
for every
$\varphi \in \mathcal {L}$
. If
$(\boldsymbol {X}_{D},\mathcal {T}_{D})$
is also topologically compact, then every
$\mathcal {T}_{D}$
clopen set is of the form
$[\varphi ]_{D}$
for some
$\varphi \in \mathcal {L}$
.
Proof To show that under the assumptions,
$[\varphi ]_{D}$
is clopen in
$\mathcal {T}_{D}$
, for every
$\varphi \in \mathcal {L}$
, we first show the claim for the special case where X is such that every
$\Lambda $
-consistent set
$\Sigma $
is satisfied in some
$x\in X$
. By Proposition 5, it suffices to show that
$\{\boldsymbol {x}\in \boldsymbol {X}_{D}\colon x\vDash \varphi \}$
is open for
$\varphi \in \mathcal {L}\backslash D$
. Fix such
$\varphi $
. As D is
$\Lambda $
-representative,
$\boldsymbol {X}_{D}$
is identical to
$\boldsymbol {X}_{\mathcal {L}}$
(cf. Lemma 3). Hence
$[\varphi ]:=\{\boldsymbol {x}\in X_{D}\colon x\vDash \varphi \}$
is well-defined. To see that
$[\varphi ]$
is open, pick
$\boldsymbol {x}\in [\varphi ]$
arbitrarily. We find an open set U with
$\boldsymbol {x}\in U\subseteq [\varphi ]$
: Let
$D_{x}=\{\psi \in \overline {D}\colon x\vDash \psi \}$
. As witnessed by x, the set
$D_{x}\cup \{\varphi \}$
is
$\Lambda $
-consistent. As D is
$\Lambda $
-representative,
$D_{x}$
thus semantically entails
$\varphi $
over X. Hence, no model
$y\in X$
satisfies
$D_{x}\cup \{\neg \varphi \}$
. By the choice of X,
$\boldsymbol {X}_{D}$
is
$\Lambda $
-saturated with respect to D. This implies that the set
$D_{x}\cup \{\neg \varphi \}$
is
$\Lambda $
-inconsistent. By the compactness of
$\Lambda $
, a finite subset F of
$D_{x}\cup \{\neg \varphi \}$
is inconsistent. Without loss of generality, we can assume that
$\neg \varphi \in F$
. Inconsistency of F implies that
$\psi _{1}\wedge \cdots \wedge \psi _{n}\rightarrow \varphi $
is a theorem of
$\Lambda $
. On the semantic level, this translates to
$\bigcap _{i\leq n}[\psi _{i}]\subseteq [\varphi ]$
. As each
$[\psi _{i}]$
is open,
$\bigcap _{i\leq n}[\psi _{i}]$
is an open neighborhood of
$\boldsymbol {x}$
contained in
$[\varphi ]$
.
Next, we prove the general case. Let X be any set of
$\Lambda $
-models and let Y be such that every
$\Lambda $
-consistent set
$\Sigma $
is satisfied in some
$y\in Y$
. Then the function
$f:\boldsymbol {X}_{D}\rightarrow \boldsymbol {Y}_{D}$
that sends
$\boldsymbol {x}\in \boldsymbol {X}_{D}$
to the unique
$\boldsymbol {y}\in \boldsymbol {Y}_{D}$
with
$x\vDash \varphi \Leftrightarrow y\vDash \varphi $
for all
$\varphi \in \mathcal {L}$
is a continuous map from
$(\boldsymbol {X}_{D},\mathcal {T}_{D})$
to
$(\boldsymbol {Y}_{D},\mathcal {T}_{D})$
with
$f^{-1}\left (\{\boldsymbol {y}\in \boldsymbol {Y}_{D}:\boldsymbol {y}\vDash \varphi \}\right ) =\{\boldsymbol {x}\in \boldsymbol {X}_{D}:\boldsymbol {x}\vDash \varphi \}$
. By the first part,
$\{\boldsymbol {y}\in \boldsymbol {Y}_{D}:\boldsymbol {y}\vDash \varphi \}$
is clopen in
$\boldsymbol {Y}_{D}$
. As the continuous pre-image of clopen sets is clopen, this shows that
$\{\boldsymbol {x}\in \boldsymbol {X}_{D}:\boldsymbol {x}\vDash \varphi \}$
is clopen.
To establish that every
$\mathcal {T}_{D}$
clopen set is of the form
$[\varphi ]_{D}$
for some
$\varphi \in \mathcal {L}$
if
$(\boldsymbol {X}_{D},\mathcal {T}_{D})$
is also topologically compact, it suffices to show that if
$O\subseteq \boldsymbol {X}_{D}$
is clopen, then O is of the form
$[\varphi ]_{D}$
for some
$\varphi \in \mathcal {L}$
. So assume O is clopen. As O and its complement
$\overline {O}$
are open, there are formulas
$\psi _{i},\chi _{i}\in D$
for
$i\in \mathbb {N}$
such that
$O=\bigcup _{i\in \mathbb {N}}[\psi _{i}]_{D}$
and
$\overline {O}=\bigcup _{i\in \mathbb {N}}[\chi _{i}]_{D}$
. Hence
$\{[\varphi _{i}]_{D}\ :\ i\in \mathbb {N}\}\cup \{[\psi _{i}]_{D}\ :\ i\in \mathbb {N}\}$
is an open cover of
$\boldsymbol {X}_{D}$
. By topological compactness, it contains a finite subcover. That is, there are
$I_{1},I_{2}\subset \mathbb {N}$
finite such that
$\boldsymbol {X}_{D}=\bigcup _{i\in I_{1}}[\psi _{i}]_{D}\cup \bigcup _{i\in I_{2}}[\psi _{i}]_{D}$
. In particular,
$O=\bigcup _{i\in I_{1}}[\psi _{i}]_{D}=[\bigvee _{i\in I_{1}}\psi _{i}]_{D}$
which is what we had to show.
By Proposition 8, two immediate consequences are:
Corollary 11. Let
$\Lambda $
be sound with respect to the set of pointed Kripke models X. If
$\Lambda $
is compact, D is
$\Lambda $
-representative, and X is
$\Lambda $
-saturated with respect to D, then the
$\mathcal {T}_{D}$
clopen sets are exactly the sets of the form
$[\varphi ]_{D}$
,
$\varphi \in \mathcal {L}$
.
Corollary 12. Let
$\Lambda \subseteq \mathcal {L}$
be a compact modal logic sound and complete with respect to some class of pointed Kripke models
$\mathcal {C}$
. Then the
$\mathcal {T}_{D}$
clopen sets are exactly the sets of the form
$[\varphi ]_{D}$
,
$\varphi \in \mathcal {L}$
.
Compactness is essential to Proposition 10’s characterization of clopen sets:
Proposition 13. Let
$\boldsymbol {X}_{D}$
be
$\Lambda $
-saturated with respect to D and D be
$\Lambda $
-representative, but
$\Lambda $
not compact. Then there exists a set U clopen in
$\mathcal {T}_{D}$
that is not of the form
$[\varphi ]_{D}$
for any
$\varphi \in \mathcal {L}$
.
Proof As
$\Lambda $
is not compact, there exists a
$\Lambda $
-inconsistent set of formulas
$S=\{\chi _{i}\colon i\in \mathbb {N}\}$
for which every finite subset is
$\Lambda $
-consistent. For simplicity of notation, define
$\varphi _{i}:=\neg \chi _{i}$
. As
$\boldsymbol {X}_{D}$
is
$\Lambda $
-saturated with respect to D,
$\{[\varphi _{i}]\}_{i\in \mathbb {N}}$
is an open cover of
$\boldsymbol {X}_{D}$
that does not contain a finite subcover. For
$i\in \mathbb {N}$
let
$\rho _{i}$
be the formula
$\varphi _{i}\wedge \bigwedge _{k<i}\neg \varphi _{k}$
. In particular, we have that
$(i)\ [\rho _{i}]\cap [\rho _{j}]=\emptyset $
for all
$i\neq j$
and
$(ii) \ \bigcup _{i\in \mathbb {N}} [\rho _{i}]=\bigcup _{i\in \mathbb {N}}[\varphi _{i}]=\boldsymbol {X}_{D}$
, i.e.,
$\{[\rho _{i}]\}_{i\in \mathbb {N}}$
is a disjoint cover of
$\boldsymbol {X}_{D}$
. We further have that
$[\rho _{i}]\subseteq [\varphi _{i}]$
; hence
$\{[\rho _{i}]\}_{i\in \mathbb {N}}$
cannot contain a finite subcover
$\{[\rho _{i}]\}_{i\in I}$
of
$\boldsymbol {X}_{D}$
, as the corresponding
$\{[\varphi _{i}]\}_{i\in I}$
would form a finite cover. In particular, infinitely many
$[\rho _{i}]$
are non-empty. Without loss of generality, assume that all
$[\rho _{i}]$
are non-empty. For all
$S\subseteq \mathbb {N}$
, the set
$U_{S}=\bigcup _{i\in S}[\rho _{i}]$
is open. As all
$[\rho _{i}]$
are mutually disjoint, the complement of
$U_{S}$
is
$\bigcup _{i\not \in S}[\rho _{i}]$
which is also open; hence
$U_{S}$
is clopen. Using again that all
$[\rho _{i}]$
are mutually disjoint and non-empty, we have that
$U_{S}\neq U_{S'}$
whenever
$S\neq S'$
. Hence,
$\{U_{S}\colon S\subseteq {\mathbb {N}}\}$
is an uncountable family of clopen sets. As
$\mathcal {L}$
is countable, there must be some element of
$\{U_{S}\colon S\subseteq {\mathbb {N}}\}$
which is not of the form
$[\varphi ]$
for any
$\varphi \in \mathcal {L}$
.
6 A comparison to alternative metrics
Metrics for Kripke models have been considered elsewhere. For the purpose of belief revision, Caridroit et al. [Reference Caridroit, Konieczny, de Lima, Marquis, Kaminka, Fox, Bouquet, Hüllermeier, Dignum, Dignum and van Harmelen14] present six metrics on finite sets of pointed KD45 Kripke models. These may be shown special cases of the present syntactic approach. A modal space
$\boldsymbol {X}_{\mathcal {L}}$
may be finite when X is finite—as is explicitly assumed by Caridroit et al. in [Reference Caridroit, Konieczny, de Lima, Marquis, Kaminka, Fox, Bouquet, Hüllermeier, Dignum, Dignum and van Harmelen14]—or in special cases, e.g., single-operator S5 models for finite atoms. In these settings, for any metric d on
$\boldsymbol {X}_{\mathcal {L}}$
there is a metric
$d_{w}\in \mathcal {D}_{(X,D)}$
equivalent with d up to translation:
Proposition 14. Let
$(\boldsymbol {X}_{\mathcal {L}},d)$
be a finite metric modal space. Then there exist a descriptor
$D\subseteq \mathcal {L}$
finitely
$\mathcal {L}$
-representative over X, a metric
$d_{w}\in \mathcal {D}_{(X,D)}$
, and some
$c\in \mathbb {R}$
such that
$d_{w}(\boldsymbol {x}_{D}, \boldsymbol {y}_{D})=d(\boldsymbol {x}_{\mathcal {L}},\boldsymbol {y}_{\mathcal {L}})+c$
for all
$\boldsymbol {x}\neq \boldsymbol {y}\in \boldsymbol {X}_{\mathcal {L}}$
.
Proof Since
$\boldsymbol {X}_{\mathcal {L}}$
is finite, there is some
$\varphi _{\boldsymbol {x}}\in \mathcal {L}$
for each
$\boldsymbol {x}\in \boldsymbol {X}_{\mathcal {L}}$
such that for all
$y\in X$
, if
$y\vDash \varphi _{\boldsymbol {x}}$
, then
$y\in \boldsymbol {x}$
. Moreover, let
$\varphi _{\{\boldsymbol {x},\boldsymbol {y}\}}$
denote the formula
$\varphi _{\boldsymbol {x}}\vee \varphi _{\boldsymbol {y}}$
which holds true in
$\boldsymbol {z}\in \boldsymbol {X}_{\mathcal {L}}$
iff
$\boldsymbol {z}=\boldsymbol {x}$
or
$\boldsymbol {z}=\boldsymbol {y}$
. Let
$D=\{\varphi _{\boldsymbol {x}}\colon \boldsymbol {x}\in \boldsymbol {X}_{\mathcal {L}}\}\cup \{\varphi _{\{\boldsymbol {x},\boldsymbol {y}\}}\colon \boldsymbol {x}\neq \boldsymbol {y}\in \boldsymbol {X}_{\mathcal {L}}\}$
. It follows that
$\boldsymbol {X}_{D}=\boldsymbol {X}_{\mathcal {L}}$
; hence D is finitely representative over X.
Next, partition the finite set
$\boldsymbol {X}_{\mathcal {L}}\times \boldsymbol {X}_{\mathcal {L}}$
according to the metric d: Let
$S_{1},\ldots ,S_{k}$
be the unique partition of
$\boldsymbol {X}_{\mathcal {L}}\times \boldsymbol {X}_{\mathcal {L}}$
that satisfies, for all
$i,j\leq k$
:
1. If
$(\boldsymbol {x},\boldsymbol {x'})\in S_{i}$
and
$(\boldsymbol {y},\boldsymbol {y'})\in S_{i}$
, then
$d(\boldsymbol {x},\boldsymbol {x'})=d(\boldsymbol {y},\boldsymbol {y'})$
.2. If
$(\boldsymbol {x},\boldsymbol {x'})\in S_{i}$
and
$(\boldsymbol {y},\boldsymbol {y'})\in S_{j}$
for
$i<j$
, then
$d(\boldsymbol {x},\boldsymbol {x'})<d(\boldsymbol {y},\boldsymbol {y'})$
.
For
$i\leq k$
, let
$b_{i}$
denote
$d(\boldsymbol {x},\boldsymbol {y})$
for any
$(\boldsymbol {x},\boldsymbol {y})\in S_{i}$
. Define a weight function
$w:D\rightarrow \mathbb {R}_{>0}$
by
$$ \begin{align*} w(\varphi_{\boldsymbol{x}}) & ={\textstyle \sum_{i=1}^{k}\sum_{\substack{(\boldsymbol{y},\boldsymbol{z})\in S_{i}\\ \boldsymbol{x}\not\neq\boldsymbol{y},\boldsymbol{z} } }\frac{1+b_{k}-b_{i}}{4}},\\ w(\varphi_{\{\boldsymbol{x},\boldsymbol{y}\}}) & ={\textstyle 2\cdot\frac{1+b_{k}-b_{i}}{4}}\text{ for the }i\text{ with }(\boldsymbol{x},\boldsymbol{y})\in S_{i}. \end{align*} $$
By symmetry,
$(\boldsymbol {x},\boldsymbol {y})\in S_{i}$
implies
$(\boldsymbol {y},\boldsymbol {x})\in S_{i}$
; thus
$w(\varphi _{\{\boldsymbol {x},\boldsymbol {y}\}})$
is well-defined. We get for each
$\boldsymbol {x}$
that
$$ \begin{align*} {\textstyle w(\varphi_{\boldsymbol{x}})+\sum_{\boldsymbol{y}\neq\boldsymbol{x}}w(\varphi_{\{\boldsymbol{x},\boldsymbol{y}\}})} & ={\textstyle \sum_{i=1}^{k}\sum_{\substack{(\boldsymbol{y},\boldsymbol{z})\in S_{i}\\ \boldsymbol{x}\not\in\{\boldsymbol{y},\boldsymbol{z}\} } }\frac{1+b_{k}-b_{i}}{4}+\sum_{i=1}^{k}\sum_{\substack{(\boldsymbol{y},\boldsymbol{z})\in S_{i}\\ \boldsymbol{x}\in\{\boldsymbol{y},\boldsymbol{z}\} } }\frac{1+b_{k}-b_{i}}{4}}\\ & ={\textstyle \sum_{i=1}^{k}\sum_{(\boldsymbol{y},\boldsymbol{z})\in S_{i}}\frac{1+b_{k}-b_{i}}{4}}. \end{align*} $$
For simplicity, let a denote
$\sum _{i=1}^{k}\sum _{(\boldsymbol {y},\boldsymbol {z})\in S_{i}}\frac {1+b_{k}-b_{i}}{4}$
, the rightmost term of the previous equation. Next, note that two models
$\boldsymbol {x}$
and
$\boldsymbol {y}$
differ on exactly the formulas
$\varphi _{\boldsymbol {x}},\varphi _{\boldsymbol {y}}$
and all
$\varphi _{\{\boldsymbol {x},\boldsymbol {z}\}}$
and
$\varphi _{\{\boldsymbol {y},\boldsymbol {z}\}}$
for
$\boldsymbol {z}\not =\boldsymbol {x},\boldsymbol {y}$
. In particular,
$$ \begin{align*} d_{w}(\boldsymbol{x},\boldsymbol{y}) & ={\textstyle w(\varphi_{\boldsymbol{x}})+w(\varphi_{\boldsymbol{y}})+ \sum_{\boldsymbol{z}\neq\boldsymbol{x},\boldsymbol{y}}w(\varphi_{\{\boldsymbol{x},\boldsymbol{z}\}})+\sum_{\boldsymbol{z}\neq\boldsymbol{x},\boldsymbol{y}}w(\varphi_{\{\boldsymbol{y},\boldsymbol{z}\}})}\\ & ={\textstyle w(\varphi_{\boldsymbol{x}})+w(\varphi_{\boldsymbol{y}})+ \sum_{\boldsymbol{z}\neq\boldsymbol{x}}w(\varphi_{\{\boldsymbol{x},\boldsymbol{z}\}})+\sum_{\boldsymbol{z}\neq\boldsymbol{y}}w(\varphi_{\{\boldsymbol{y},\boldsymbol{z}\}})-2w(\varphi_{\{\boldsymbol{x},\boldsymbol{y}\}})}\\ & ={\textstyle 2a-4\cdot\frac{1+b_{k}-b_{i}}{4}}\ \ \ =\ \ \ {\textstyle 2a+b_{i}-1-b_{k}}, \end{align*} $$
where i is such that
$\{\boldsymbol {x},\boldsymbol {y}\}\in S_{i}$
. Denoting
$2a-1-b_{k}$
by c, we get that
$d_{w}(\boldsymbol {x},\boldsymbol {y})=d(\boldsymbol {x},\boldsymbol {y})+c$
whenever
$\boldsymbol {x}\neq \boldsymbol {y}$
.
Caridroit et al. also consider a semantic similarity measure of Aucher [Reference Aucher2] from which they define a distance between finite pointed Kripke models. The construction of the distance is somewhat involved and we do not attempt a quantitative comparison. As to a qualitative analysis, then neither Caridroit et al. nor Aucher offers any form of topological analysis, making comparison non-straightforward. As the fundamental measuring component in Aucher’s distance is based on degree of n-bisimilarity, we conjecture that the topology on the spaces of Kripke models generated by this distance is the n-bisimulation topology, the metric topology of the n-bisimulation metric (defined below), inspired by Goranko’s quantifier depth based distance for first-order logical theories [Reference Goranko, van Eijck, van Oostrom and Visser24]. Finally, Sokolsky et al. [Reference Sokolsky, Kannan, Lee, Hermanns and Palsberg42] introduce a quantitative bisimulation distance for finite, labeled transition systems and consider its computation. Again, we conjecture the induced topology is the n-bisimulation topology.
6.1 Degrees of bisimilarity
Contrary to our syntactic approach to metric construction, a natural semantic approach rests on bisimulations. The notion of n-bisimilarity may be used to define a semantically based metric on quotient spaces of pointed Kripke models where degrees of bisimilarity translate to closeness in space—the more bisimilar, the closer:
Let X be a set of pointed Kripke models for which modal equivalence and bisimilarity coincideFootnote
3
and let
relate
$x,y\in X$
iff x and y are n-bisimilar. Then
is a metric on
$\boldsymbol {X}_{\mathcal {L}}$
. Refer to
$d_{B}$
as the n-bisimulation metric.
For X and
$\mathcal {L}$
based on a finite signature, the n-bisimulation metric is a special case of the presented approach:
Proposition 15. Let
$\mathcal {L}$
have finite signature and let
$(\boldsymbol {X}_{\mathcal {L}},d_{B})$
be a metric modal space under the n-bisimulation metric. Then there exists a
$D\subseteq \mathcal {L}$
such that
$d_{B}\in \mathcal {D}_{(X,D)}$
.
Proof With
$\mathcal {L}$
of finite signature, every model in X has a characteristic formula up to n-bisimulation: For each
$x\in X$
, there exists a
$\varphi _{x,n}\in \mathcal {L}$
such that for all
$y\in X$
,
$y\vDash \varphi _{x,n}$
iff
(cf. [Reference Goranko, Otto, Blackburn, van Benthem and Wolter25, Reference Moss37]). Given that both
$\Phi $
and
$\mathcal {I}$
are finite, so is, for each n, the set
$D_{n}=\{\varphi _{x,n}:x\in X\}\subseteq \mathcal {L}$
. Pick the descriptor to be
$D=\bigcup _{n\in \mathbb {N}}D_{n}$
. Then D is
$\mathcal {L}$
-representative for X, so
$\boldsymbol {X}_{D}$
is identical to
$\boldsymbol {X}_{\mathcal {L}}$
(cf. Lemma 3).
Let a weight function b be given by
$$\begin{align*}{\textstyle b(\varphi)=\frac{1}{2}\left(\frac{1}{n+1}-\frac{1}{n+2}\right)\text{ for }\varphi\in D_{n}.} \end{align*}$$
Then
$d_{b}$
, defined by
$d_{b}(\boldsymbol {x},\boldsymbol {y}) = \sum _{k=1}^{\infty }b(\varphi _{k})d_{k}(\boldsymbol {x},\boldsymbol {y}),$
is a metric on
$\boldsymbol {X}_{\mathcal {L}}$
(cf. Proposition 4).
As models x and y will, for all n, either agree on all members of
$D_{n}$
or disagree on exactly 2 (namely
$\varphi _{n,x}$
and
$\varphi _{n,y}$
) and as, for all
$k\leq n$
,
$y\vDash \varphi _{n,x}$
implies
$y\vDash \varphi _{k,x}$
, and for all
$k\geq n$
,
$y\not \vDash \varphi _{n,x}$
implies
$y\not \vDash \varphi _{k,x}$
, we obtain that
which is exactly
$d_{B}$
.
Remark 16. The construction can be made independent of the set X to the effect that the constructed metric
$d_{b}$
is exactly
$d_{B}$
on any
$\mathcal {L}$
-modal space
$\boldsymbol {X}_{\mathcal {L}}$
.
The n-bisimulation metric only is a special case when the set of atoms and number of modalities are both finite: If either is infinite, there is no metric in
$\mathcal {D}_{(X,D)}$
for a descriptor
$D\subseteq \mathcal {L}$
that is equivalent to the n-bisimulation metric. This follows from an analysis of its metric topology, the n-bisimulation topology,
$\mathcal {T}_{B}$
. A basis for this topology is given by all subsets of
$\boldsymbol {X}_{\mathcal {L}}$
of the form
for
$\boldsymbol {x}\in \boldsymbol {X}_{\mathcal {L}}$
and
$n\in \mathbb {N}$
.
By Propositions 5 and 15—and the fact that the set D constructed in the proof of the latter is finitely
$\mathcal {L}$
-representative over X—we obtain the following:
Corollary 17. If
$\mathcal {L}$
has finite signature, then the n-bisimulation topology
$\mathcal {T}_{B}$
is the Stone(-like) topology
$\mathcal {T}_{\mathcal {L}}$
.
This is not the general case:
Proposition 18. If
$\mathcal {L}$
is based on an infinite set of either atoms or operators, then the n-bisimulation topology
$\mathcal {T}_{B}$
is strictly finer than the Stone(-like) topology
$\mathcal {T}_{\mathcal {L}}$
on
$\boldsymbol {X}_{\mathcal {L}}$
.
Proof
$\mathcal {T}_{B}\not \subseteq \mathcal {T}_{\mathcal {L}}$
: In the infinite atoms case,
$\mathcal {T}_{B}$
has as basis element
$B_{\boldsymbol {x}0}$
, consisting exactly of those
$\boldsymbol {y}$
such that y and x share the same atomic valuation, i.e., are
$0$
-bisimilar. Clearly,
$\boldsymbol {x}\in B_{\boldsymbol {x}0}$
. There is no formula
$\varphi $
for which the
$\mathcal {T}_{\mathcal {L}}$
basis element
$B=\{\boldsymbol {z}\in \boldsymbol {X}\colon z\vDash \varphi \}$
contains
$\boldsymbol {x}$
and is contained in
$B_{\boldsymbol {x}0}$
: This would require that
$\varphi $
implied every atom or its negation, requiring the strength of an infinitary conjunction. For the infinite operators case, the same argument applies, but using
$B_{\boldsymbol {x}1},$
containing exactly those
$\boldsymbol {y}$
for which x and y are
$1$
-bisimilar.
$\mathcal {T}_{\mathcal {L}}\subseteq \mathcal {T}_{B}$
: Consider any
$\varphi \in \mathcal {L}$
and the corresponding
$\mathcal {T}_{\mathcal {L}}$
basis element
$B=\{\boldsymbol {y}\in \boldsymbol {X}\colon y\vDash \varphi \}$
. Assume
$\boldsymbol {x}\in B$
. Let the modal depth of
$\varphi $
be n. Then for every
$\boldsymbol {z}\in B_{\boldsymbol {x}n}$
,
$z\vDash \varphi $
. Hence
$\boldsymbol {x}\in B_{\boldsymbol {x}n}\subseteq B$
.
The discrepancy in induced topologies results as the n-bisimulation metric, in the infinite case, introduces distinctions not finitely expressible in the language: If there are infinitely many atoms or operators, there does not exist a characteristic formula
$\varphi _{x,n}$
satisfied only by models n-bisimilar to x.
The additional open sets are not without consequence—a modal space compact in the Stone(-like) topology need not be so in the n-bisimulation topology: Let
$\boldsymbol {X}_{\mathcal {L}}$
be an infinite modal space with
$\mathcal {L}$
based on an infinite atom set and assume it compact in the Stone(-like) topology. It will not be compact in the n-bisimulation topology:
$\{B_{\boldsymbol {x}0}\colon x\in X\}$
is an open cover of
$\boldsymbol {X}_{\mathcal {L}}$
which contains no finite subcover.
7 Convergence and limit points
We next turn to dynamic aspects of Stone-like topologies. In particular, we focus on the nature of convergent sequences in Stone-like topologies and such topologies’ isolated points.
7.1 Convergence
Being Hausdorff, topological convergence in Stone-like topologies captures the geometrical intuition of a sequence
$(\boldsymbol {x}_{n})$
converging to at most one point, its limit. We write
$(\boldsymbol {x}_{n})\rightarrow \boldsymbol {x}$
when
$\boldsymbol {x}$
is the limit of
$(\boldsymbol {x}_{n})$
. In general Stone-like topologies, such a limit need not exist.
Convergence in Stone-like topologies also satisfies a natural logical intuition, namely that a sequence and its limit should eventually agree on every formula of the language used to describe them. This intuition is captured by the notion of logical convergence, introduced in [Reference Klein, Rendsvig, Baltag, Seligman and Yamada31]:
Definition. Let
$\boldsymbol {X}_{D}$
be a modal space. A sequence of points
$(\boldsymbol {x}_{n})$
logically converges to
$\boldsymbol {x}$
in
$\boldsymbol {X}_{D}$
iff for every
$\psi \in \{\varphi ,\neg \varphi \colon \varphi \in D\}$
for which
$\boldsymbol {x}\vDash \psi $
, there exists some
$N\in \mathbb {N}$
such that
$\boldsymbol {x}_{n}\vDash \psi $
, for all
$n\geq N$
.
The following proposition identifies a tight relationship between Stone-like topologies, topological and logical convergence, strengthening a result in [Reference Klein, Rendsvig, Baltag, Seligman and Yamada31]:
Proposition 19. Let
$\boldsymbol {X}_{D}$
be a modal space and
$\mathcal {T}$
a topology on
$\boldsymbol {X}_{D}$
. Then the following are equivalent:
1. A sequence
$\boldsymbol {x}_{1},\boldsymbol {x}_{2},\ldots $
of points from
$\boldsymbol {X}_{D}$
converges to
$\boldsymbol {x}$
in
$(\boldsymbol {X}_{D},\mathcal {T})$
if, and only if,
$\boldsymbol {x}_{1},\boldsymbol {x}_{2},\ldots $
logically converges to
$\boldsymbol {x}$
in
$\boldsymbol {X}_{D}$
.2.
$\mathcal {T}$
is the Stone-like topology
$\mathcal {T}_{D}$
on
$\boldsymbol {X}_{D}$
.
Proof
$2\Rightarrow 1:$
This is shown, mutatis mutandis, in [Reference Klein, Rendsvig, Baltag, Seligman and Yamada31, Proposition 2].
$1\Rightarrow 2: \ \mathcal {T}_{D}\subseteq \mathcal {T}:$
We show that
$\mathcal {T}$
contains a subbasis of
$\mathcal {T}_{D}$
: for all
$\varphi \in D$
,
$[\varphi ],[\neg \varphi ]\in \mathcal {T}$
. We show that
$[\varphi ]$
is open in
$\mathcal {T}$
by proving that
$[\neg \varphi ]$
is closed in
$\mathcal {T}$
, qua containing all its limit points: Assume the sequence
$(\boldsymbol {x}_{i})\subseteq [\neg \varphi ]$
converges to
$\boldsymbol {x}$
in
$(\boldsymbol {X}_{D},\mathcal {T})$
. For each
$i\in \mathbb {N}$
, we have
$\boldsymbol {x}_{i}\vDash \neg \varphi $
. As convergence is assumed to imply logical convergence, then also
$\boldsymbol {x}\vDash \neg \varphi $
. Hence
$\boldsymbol {x}\in [\neg \varphi ]$
, so
$[\neg \varphi ]$
is closed in
$\mathcal {T}$
. That
$[\neg \varphi ]$
is open in
$\mathcal {T}$
follows by a symmetric argument. Hence
$\mathcal {T}_{D}\subseteq \mathcal {T}$
.
$\mathcal {T}\subseteq \mathcal {T}_{D}:$
The reverse inclusion follows as for every element
$\boldsymbol {x}$
of any open set U of
$\mathcal {T}$
, there is a basis element B of
$\mathcal {T}_{D}$
such that
$\boldsymbol {x}\in B\subseteq U$
. Let
$U\in \mathcal {T}$
and let
$\boldsymbol {x}\in U$
. Enumerate the set
$\{\psi \in \overline {D}\colon x\vDash \psi \}$
as
$\psi _{1},\psi _{2},\dots $
, and consider all conjunctions of finite prefixes
$\psi _{1}$
,
$\psi _{1}\wedge \psi _{2}$
,
$\psi _{1}\wedge \psi _{2}\wedge \psi _{3},\dots $
of this enumeration. If for some k,
$[\psi _{1}\wedge \cdots \wedge \psi _{k}]\subseteq U$
, then
$B=[\psi _{1}\wedge \cdots \wedge \psi _{k}]$
is the desired
$\mathcal {T}_{D}$
basis element as
$\boldsymbol {x}\in [\psi _{1}\wedge \cdots \wedge \psi _{k}]\subseteq U$
. If there exists no
$k\in \mathbb {N}$
such that
$[\psi _{1}\wedge \cdots \wedge \psi _{k}]\subseteq U$
, then for each
$m\in \mathbb {N}$
, we can pick an
$\boldsymbol {x}_{m}$
such that
$\boldsymbol {x}_{m}\in [\psi _{1}\wedge \cdots \wedge \psi _{m}]\setminus U$
. The sequence
$(\boldsymbol {x}_{m})_{m\in \mathbb {N}}$
then logically converges to
$\boldsymbol {x}$
. Hence, by assumption, it also converges topologically to
$\boldsymbol {x}$
in
$\mathcal {T}$
. Now, for each
$m\in \mathbb {N}$
,
$\boldsymbol {x}_{m}$
is in
$U^{c}$
, the compliment of U. However,
$\boldsymbol {x}\notin U^{c}$
. Hence,
$U^{c}$
is not closed in
$\mathcal {T}$
, so U is not open in
$\mathcal {T}$
. This is a contradiction, rendering impossible that there is no
$k\in \mathbb {N}$
such that
$[\psi _{1}\wedge \cdots \wedge \psi _{k}]\subseteq U$
. Hence
$\mathcal {T}_{D}\subseteq \mathcal {T}$
.
In [Reference Klein, Rendsvig, Baltag, Seligman and Yamada31], the satisfaction of point 1 was used as motivation for working with Stone-like topologies. Proposition 19 shows that this choice of topology was necessary, if one wants the logical intuition satisfied. Moreover, it provides a third way of inducing Stone-like topologies, different from inducing them from a metric or a basis, namely through sequential convergence.Footnote 4
7.2 Isolated points
The existence of isolated points may be of interest, e.g., in information dynamics. A sequence
$(\boldsymbol {x}_{n})$
in
$A\subseteq \boldsymbol {X}_{D}$
converges to an isolated point
$\boldsymbol {x}$
in
$A\subseteq \boldsymbol {X}_{D}$
iff for some N, for all
$k>N$
,
$\boldsymbol {x}_{k}=\boldsymbol {x}$
. Hence, if the goal of a given protocol is satisfied only at isolated points, the protocol will either be successful in finite time or not at all.
The existence of isolated points in Stone-like topologies is tightly connected with the expressive power of the underlying descriptor. Say that a point
$\boldsymbol {x}\in \boldsymbol {X}_{D}$
is characterizable by D in
$\boldsymbol {X}_{D}$
if there exists a finite set of formulas
$A\subseteq \overline {D}$
such that for all
$\boldsymbol {y}\in \boldsymbol {X}_{D}$
, if
$\boldsymbol {y}\vDash \varphi $
for all
$\varphi \in A$
, then
$\boldsymbol {y}=\boldsymbol {x}$
. We obtain the following:
Proposition 20. Let
$(\boldsymbol {X}_{D},\mathcal {T}_{D})$
be a modal space with its Stone-like topology. Then
$\boldsymbol {x}\in \boldsymbol {X}_{D}$
is an isolated point of
$\boldsymbol {X}_{D}$
iff
$\boldsymbol {x}$
is characterizable by D in
$\boldsymbol {X}_{D}$
.
Proof
Left-to-right: If
$\{\boldsymbol {x}\}$
is open in
$\mathcal {T}_{D}$
, it must be in the basis of
$\mathcal {T}_{D}$
and thus a finite intersection of subbasis elements, i.e.,
$\{\boldsymbol {x}\}=\bigcap _{\varphi \in A}[\varphi ]$
for some finite
$A\subseteq \overline {D}$
. Then A characterizes
$\boldsymbol {x}$
. Right-to-left: Let A characterize
$\boldsymbol {x}$
in
$\boldsymbol {X}_{D}$
. Each
$[\varphi ],\varphi \in A,$
is open in
$\mathcal {T}_{D}$
by definition. With A finite, also
$\bigcap _{\varphi \in A}[\varphi ]$
is open. Hence
$\{\boldsymbol {x}\}\in \mathcal {T}_{D}$
.
Applying Proposition 20 shows that convergence is of little interest when
$\mathcal {L}$
is the mono-modal language over a finite atom set
$\Phi $
and X is
$S5$
-complete: Then
$(\boldsymbol {X}_{\mathcal {L}},\mathcal {T}_{\mathcal {L}})$
is a discrete space, i.e., contains only isolated points.
7.2.1 Perfect spaces
A topological space
$(X,\mathcal {T})$
with no isolated points is perfect. In perfect spaces, every point is the limit of some sequence, and may hence be approximated arbitrarily well. The property is enjoyed by several natural classes of modal spaces under their Stone-like topologies (cf. Corollary 22). Each such space that is additionally compact is homeomorphic to the Cantor set, as every totally disconnected compact metric space is (see, e.g., [Reference Moise36, Chapter 12]). Proposition 20 implies that a modal space under its Stone-like topology is perfect iff it contains no points characterizable by its descriptor.
Proposition 21. Let
$D\subseteq \mathcal {L}$
, let
$\Lambda $
be a logic, and let X be a set of
$\Lambda $
-models
$\Lambda $
-saturated with respect to D. Then
$(\boldsymbol {X}_{D},\mathcal {T}_{D})$
is perfect iff for every finite
$\Lambda $
-consistent set
$A\subseteq \overline {D}$
there is some
$\psi \in D$
such that both
$\psi \wedge \bigwedge _{\chi \in A}\chi $
and
$\neg \psi \wedge \bigwedge _{\chi \in A}\chi $
are
$\Lambda $
-consistent.
Proof
$\Rightarrow :$
Assume
$(\boldsymbol {X}_{D},\mathcal {T}_{D})$
perfect. Let
$A\subseteq \{\varphi ,\neg \varphi \colon \varphi \in D\}$
be finite and
$\Lambda $
-consistent. We must find
$\psi \in D$
for which both
$\psi \wedge \bigwedge _{\chi \in A}\chi $
and
$\neg \psi \wedge \bigwedge _{\chi \in A}\chi $
are
$\Lambda $
-consistent. As
$\boldsymbol {X}_{D}$
is
$\Lambda $
-saturated with respect to D, there is some
$\boldsymbol {x}\in \boldsymbol {X}_{D}$
with
$x\vDash \bigwedge _{\chi \in A}\chi $
. With
$(\boldsymbol {X}_{D},\mathcal {T}_{D})$
perfect,
$\bigcap _{\varphi \in A}[\varphi ]_{D}\supsetneq \{\boldsymbol {x}\}$
—i.e., there is some
$\boldsymbol {y}\neq \boldsymbol {x}\in \bigcap _{\varphi \in A}[\varphi ]_{D}$
. This implies that there is some
$\psi \in D$
such that
$\boldsymbol {x}\vDash \psi $
and
$\boldsymbol {y}\not \vDash \psi $
or vice versa. Either way,
$\boldsymbol {x}$
and
$\boldsymbol {y}$
witness that
$\psi \wedge \bigwedge _{\chi \in A}\chi $
and
$\neg \psi \wedge \bigwedge _{\chi \in A}\chi $
are both
$\Lambda $
-consistent.
$\Leftarrow :$
No
$\boldsymbol {x}\in \boldsymbol {X}_{D}$
is isolated: By Proposition 20, it suffices to show that
$\boldsymbol {x}$
is not characterizable by D in
$\boldsymbol {X}_{D}$
. For a contradiction, assume some finite
$A\subseteq \overline {D}$
characterizes
$\boldsymbol {x}$
. By assumption, there is some
$\psi \in D$
such that both
$\psi \wedge \bigwedge _{\chi \in A}\chi $
and
$\neg \psi \wedge \bigwedge _{\chi \in A}\chi $
are
$\Lambda $
-consistent. As
$\boldsymbol {X}_{D}$
is
$\Lambda $
-saturated, there are
$y,z\in X$
with
$y\vDash \psi \wedge \bigwedge _{\chi \in A}\chi $
and
$z\vDash \neg \psi \wedge \bigwedge _{\chi \in A}\chi $
. As
$\psi \in D$
,
$\boldsymbol {y}\neq \boldsymbol {z}$
. In particular
$\boldsymbol {x}\neq \boldsymbol {y}$
or
$\boldsymbol {x}\neq \boldsymbol {z}$
, contradicting the assumption that A characterizes
$\boldsymbol {x}$
.
If D is closed under negations and disjunctions, the assumption of Proposition 21 may be relaxed to stating that for any
$\Lambda $
-consistent
$\varphi \in D$
there is some
$\psi \in D$
such that
$\varphi \wedge \psi $
and
$\varphi \wedge \neg \psi $
are both
$\Lambda $
-consistent. This property is enjoyed by many classic modal logics:
Corollary 22. For the following modal logics,
$(\boldsymbol {X}_{\mathcal {L}},\mathcal {T}_{\mathcal {L}})$
is perfect if X is saturated with respect to
$\mathcal {L}$
:
$\mathrm{(i)}$
the normal modal logic K with an infinite set of atoms, as well as
$\mathrm{(ii)} \ KD$
,
$\mathrm{(iii)} \ KD45^{n}$
for
$n\geq 2$
, and
$\mathrm{(iv)} \ S5^{n}$
for
$n\geq 2$
.
7.2.2 Imperfect spaces
It is not difficult to find
$\Lambda $
-complete spaces
$(\boldsymbol {X}_{\mathcal {L}},\mathcal {T}_{\mathcal {L}})$
that contain isolated points. We provide two examples. The first shows that, when working in a language with finite signature, then, e.g., for the minimal normal modal logic K, the K-complete space will have an abundance of isolated points.
Proposition 23. Let
$\mathcal {L}$
have finite signature
$(\Phi ,\mathcal {I})$
and let
$\Lambda $
be such that
$\bigvee _{i\in \mathcal {{I}}}\lozenge _{i}\top $
is not a theorem. If
$(\boldsymbol {X}_{\mathcal {L}},\mathcal {T}_{\mathcal {L}})$
is
$\Lambda $
-complete, then it contains an isolated point. If
$\Lambda $
is exactly K, then it contains infinitely many isolated points.
Proof With
$\bigvee _{i\in \mathcal {{I}}}\lozenge _{i}\top $
not a theorem, there is an atom valuation encodable as a conjunction
$\varphi $
such that
$\varphi \wedge \bigwedge _{i\in \mathcal {I}}\square _{i}\bot $
is consistent. The latter characterizes the point
$\boldsymbol {x}$
in
$\boldsymbol {X}_{\mathcal {L}}$
uniquely, as it has no outgoing relations. The point
$\boldsymbol {x}$
is clearly isolated. If
$\Lambda $
is exactly K, there are for each
$n\in \mathbb {N}$
only finitely many modally different models satisfying
$\psi _{n}=\bigwedge _{i\in \mathcal {{I}}}\left (\bigwedge _{m<n}\lozenge _{i}^{m}\top \wedge \neg \lozenge _{i}^{n}\top \right )$
; hence
$[\psi _{n}]$
is finite in
$\boldsymbol {X}_{\mathcal {L}}$
. This, together with the fact that
$(\boldsymbol {X}_{\mathcal {L}},\mathcal {T}_{\mathcal {L}})$
is Hausdorff, implies that any
$\boldsymbol {x}\in [\psi _{n}]$
is characterizable by
$\mathcal {L}$
making
$\boldsymbol {x}$
isolated (cf. Proposition 20).
For the second example, we turn to epistemic logic with common knowledge [Reference Halpern, Moses, Kameda, Misra, Peters and Santoro27, Reference Lehmann, Kameda, Misra, Peters and Santoro34]. Let
$(\Phi ,\mathcal {I})$
be a finite signature with
$\mathcal {I}=\{1,\ldots ,n,G\}$
. Let
$EQ$
be the class of pointed Kripke models for
$(\Phi ,\mathcal {I})$
where for each
$i\in \mathcal {I}\backslash \{G\}$
,
$R(i)$
is an equivalence relation and
$R(G)$
the transitive closure of
$\bigcup _{i\leq n}R(i)$
. Let
$\mathcal {L}$
be the language based on
$(\Phi ,\mathcal {I})$
and
$\mathsf {S5C}$
the appropriate multi-agent epistemic logic with common knowledge axioms. Then:
Proposition 24. The set of isolated points in
$(\boldsymbol {EQ}_{\mathcal {L}},\mathcal {T}_{\mathcal {L}})$
is infinite.
Proof This follows from Proposition 20 as every finite model of
$EQ$
is characterizable by a single formula (cf. [Reference van Benthem, Chatzidakis, Koepke and Pohlers7, Lemma 3.4] or [Reference Baltag and Moss3, Proposition 2.4]).
Proposition 24 is relevant to discussions concerning the attainability of common knowledge under unreliable communication [Reference Akkoyunlu, Ekanadham, Huber, Browne and Rodriguez-Rosell1, Reference Fagin, Halpern, Moses and Vardi21, Reference Fagin, Halpern, Moses and Vardi22, Reference Gray, Bayer, Graham and Seegmüller26, Reference Halpern and Moses28, Reference Yemini and Cohen44]. Agents seeking to attain common knowledge of
$\varphi $
have as target point
$\boldsymbol {x}$
that is characterized by
$\square _{G}\varphi $
, isolated by Proposition 20. Hence common knowledge must be attained in finite time if it is to be attained in the limit. By Corollary 22, common knowledge can be attained in the limit if the underlying language does not include a common knowledge operator. See also [Reference Klein, Rendsvig and Kraus32], which elaborates on this discussion.
8 Maps and model transformations
In dynamic epistemic logic, dynamics are introduced by transitioning between pointed Kripke models from some set X using a possibly partial map
$f:X\rightarrow X$
often referred to as a model transformer. A particularly rich class of such maps may be defined using multi-pointed action models with postconditions [Reference Baltag and Moss3, Reference van Benthem, van Eijck and Kooi11, Reference Bolander and Birkegaard13, Reference van Ditmarsch, Kooi, Bonanno, van der Hoek and Wooldridge18, Reference Klein and Rendsvig33, Reference Rendsvig, van der Hoek, Holliday and Wang38]. The class is Turing complete [Reference Bolander and Birkegaard13] (also without postconditions [Reference Klein and Rendsvig33]).
8.1 Action models and product update
A multi-pointed action model is a tuple
where
is a non-empty set of actions. The map
assigns an accessibility relation
$\mathsf {R}_{i}$
on
to each agent
$i\in \mathcal {I}$
. The map
assigns to each action a precondition, and the map
assigns to each action a postcondition,Footnote
5
which must be
$\top $
or a conjunctive clauseFootnote
6
over
$\Phi $
. Finally,
is a non-empty set of designated actions.Footnote
7
To obtain well-behaved total maps on modal spaces, we must invoke a set of mild, but non-standard, requirements: Let X be a set of pointed Kripke models. Call
$\Sigma {\scriptstyle \Gamma }$
precondition finite if the set
is finite (up to logical equivalence). This is needed for our proof of continuity. Call
$\Sigma {\scriptstyle \Gamma }$
exhaustive over X if for all
$x\in X$
, there is a
$\sigma \in \Gamma $
such that
$x\vDash pre(\sigma )$
. This condition ensures that the action model
$\Sigma {\scriptstyle \Gamma }$
is universally applicable on X. Finally, call
$\Sigma {\scriptstyle \Gamma }$
deterministic over X if
$X\vDash pre(\sigma )\wedge pre(\sigma ')\rightarrow \bot $
for any two actions
$\sigma ,\sigma '\in \Gamma ,\sigma \not =\sigma '$
. Together with exhaustivity, this condition ensures that the product of
$\Sigma {\scriptstyle \Gamma }$
and any
$Ms\in X$
is a (single-)pointed Kripke model, i.e., that the actual state after the updates is well-defined and unique.
Let
$\Sigma {\scriptstyle \Gamma }$
be exhaustive and deterministic over X and let
$Ms\in X$
. Then the product update of
$Ms$
with
$\Sigma {\scriptstyle \Gamma }$
, denoted
$Ms\otimes \Sigma {\scriptstyle \Gamma }$
, is the pointed Kripke model
with
Call
$\Sigma {\scriptstyle \Gamma }$
closing over X if for all
$x\in X$
,
$x\otimes \Sigma {\scriptstyle \Gamma }\in X$
. With exhaustivity and deterministicality, this ensures that
$\cdot \otimes \Sigma {\scriptstyle \Gamma }$
induces a well-defined total map on X.
8.2 Clean maps on modal spaces
If two pointed Kripke models x and y are
$\mathcal {L}$
-modally equivalent, then so are
$x\otimes \Sigma {\scriptstyle \Gamma }$
and
$y\otimes \Sigma {\scriptstyle \Gamma }$
for any product model
$\Sigma {\scriptstyle \Gamma }$
(cf. [Reference Baltag and Moss3]). Hence, action models applied using product update yield natural maps
$\cdot \otimes \Sigma {\scriptstyle \Gamma }$
on modal spaces
$\boldsymbol {X}_{\mathcal {L}}$
. The class of maps of interest in the present is the following:
Definition. Let
$\boldsymbol {X}_{\mathcal {L}}$
be a modal space. A map
$\boldsymbol {f}:\boldsymbol {X}_{\mathcal {L}}\rightarrow \boldsymbol {X}_{\mathcal {L}}$
is called clean if there exists a precondition finite, multi-pointed action model
$\Sigma {\scriptstyle \Gamma }$
closing, deterministic and exhaustive over X such that
$\boldsymbol {f}(\boldsymbol {x})=\boldsymbol {y}$
iff
$\boldsymbol {x}\otimes \Sigma {\scriptstyle \Gamma }=\boldsymbol {y}$
for all
$\boldsymbol {x}\in \boldsymbol {X}_{\mathcal {L}}$
.
The same clean map may be induced by several different action models:
Lemma 25. Let
$\boldsymbol {f}:\boldsymbol {X}_{\mathcal {L}}\rightarrow \boldsymbol {X}_{\mathcal {L}}$
be a clean map based on
$\Sigma {\scriptstyle \Gamma }$
. Then there exists a precondition finite, multi-pointed action model
$\Sigma '{\scriptstyle \Gamma '}$
deterministic over X that also induces
$\boldsymbol {f}$
such that for all
, either
$\vDash pre(\sigma )\wedge pre(\sigma ')\rightarrow \bot $
or
$pre(\sigma )=pre(\sigma ')$
.
Proof Let
$\Sigma {\scriptstyle \Gamma }$
be a precondition finite, multi-pointed action model
$\Sigma {\scriptstyle \Gamma }$
deterministic over X generating
$\boldsymbol {f}$
. We construct an equivalent action model,
$\Sigma '{\scriptstyle \Gamma '}$
, with the desired property. First note that for every finite set of formulas
$S=\{\varphi _{1},\ldots ,\varphi _{n}\}$
there is some finite
$S'=\{\psi _{1},\ldots ,\psi _{m}\}$
such that any
$\psi _{i}\neq \psi _{j}\in S'$
are mutually inconsistent and that for each
$\varphi \in S$
there is some (unique)
$J(\varphi )\subseteq S'$
with
$\vdash \bigvee _{\psi \in J(\varphi )}\psi \leftrightarrow \varphi $
. One such set
$S'$
can be obtained from
$\{\bigwedge _{k\leq n}\chi _{k}\colon \chi _{k}\in \{\varphi _{k},\neg \varphi _{k}\}\}$
by removing logical equivalents: The disjunction of all conjunctions with
$\chi _{k}=\varphi _{k}$
is equivalent with
$\varphi _{k}$
. By assumption,
is finite. Let
$S'$
and
$J(\varphi )$
be as stated. Construct
$\Sigma '{\scriptstyle \Gamma '}$
as follows: For every
and every
$\psi \in J(pre(\sigma ))$
, the set
contains a state
$e^{\sigma ,\psi }$
with
$pre(e^{\{\sigma ,\psi \}})=\psi $
and
$post(e^{\{\sigma ,\psi \}})=post(\sigma )$
. Let
$R'$
be given by
$(e^{\sigma ,\psi },e^{\sigma ',\psi '})\in R'(i)$
iff
$(\sigma ,\sigma ')\in R(i)$
. Finally, let
$\Gamma '=\{e^{\{\sigma ,\psi \}}\colon \sigma \in \Gamma \}$
. The resulting multi-pointed action model
$\Sigma '{\scriptstyle \Gamma '}$
is again precondition finite and deterministic over X while satisfying that for all
, either
$\vDash pre(\sigma )\wedge pre(\sigma ')\rightarrow \bot $
or
$pre(\sigma )=pre(\sigma ')$
. Moreover, for any
$x\in X$
, the models
$x\otimes \Sigma {\scriptstyle \Gamma }$
and
$x\otimes \Sigma '{\scriptstyle \Gamma '}$
are bisimilar witnessed by the relation connecting
and
iff
$s=s'$
and
$\sigma =\sigma '$
. Hence, the maps
$\boldsymbol {f},\ \boldsymbol {f'}:\boldsymbol {X}_{\mathcal {L}}\rightarrow \boldsymbol {X}_{\mathcal {L}}$
defined by
$\boldsymbol {x}\mapsto \boldsymbol {x\otimes \Sigma {\scriptstyle \Gamma }}$
and
$\boldsymbol {x}\mapsto \boldsymbol {x\otimes \Sigma '{\scriptstyle \Gamma '}}$
are identical.
8.3 Continuity of clean maps
We show that the metrics introduced earlier square well with respect to the analysis of dynamics induced by clean maps by showing the latter continuous in the induced topology. The proof is direct. An indirect proof may also constructed, as reduction axioms exist for clean maps [Reference Baltag and Moss3]. This, as shown in [Reference Rendsvig39, Paper VI], is sufficient for continuity.
Proposition 26. Any clean map
$\boldsymbol {f}:\boldsymbol {X}_{\mathcal {L}}\rightarrow \boldsymbol {X}_{\mathcal {L}}$
is uniformly continuous with respect to the metric topology generated by any
$d_{w}\in \mathcal {D}_{(X,D)}$
where D is finitely
$\mathcal {L}$
-representative with respect to X.
In the proof, we make use of the following lemma:
Lemma 27. Let
$(\boldsymbol {X}_{\mathcal {L}},d_{w})$
be a metric space,
$d_{w}\in \mathcal {D}_{(X,D)}$
for D finitely
$\mathcal {L}$
-representative with respect to X. Then:
1. For every
$\epsilon>0$
, there are formulas
$\chi _{1},\ldots ,\chi _{l}\in \mathcal {L}$
such that every
$\boldsymbol {x}\in \boldsymbol {X}_{\mathcal {{L}}}$
satisfies some
$\chi _{i}$
, and whenever
$\boldsymbol {x}\vDash \chi _{i}$
and
$\boldsymbol {z}\vDash \chi _{i}$
for some
$i\leq l$
, then
$d_{w}(\boldsymbol {y},\boldsymbol {z})<\epsilon $
.2. For every
$\varphi \in \mathcal {L}$
, there is a
$\delta $
such that for all
$\boldsymbol {x}\in \boldsymbol {X}_{\mathcal {{L}}}$
, if
$\boldsymbol {x}\vDash \varphi $
and
$d_{w}(\boldsymbol {x},\boldsymbol {y})<\delta $
, then
$\boldsymbol {y}\vDash \varphi $
.
Proof of Lemma 27
For 1., note that there is some
$n>0$
for which
$\sum _{k=n}^{\infty }w(\varphi _{k})<\epsilon $
. Enumerate the subsets of
$\{1,\ldots ,n-1\}$
by
$J_{1},\ldots ,J_{2^{n-1}}$
. For each
$i\in \{1,\ldots ,2^{n-1}\}$
let the formula
$\chi _{i}$
be
$\bigwedge _{j\in J_{i}}\varphi _{j}\wedge \bigwedge _{j\not \in J_{i}}\neg \varphi _{j}$
. Then each
$\boldsymbol {x}\in \boldsymbol {X}_{\mathcal {{L}}}$
must satisfy some
$\chi _{i}$
with
$i\leq 2^{n-1}$
. Moreover, whenever
$\boldsymbol {y}\vDash \chi _{i}$
and
$\boldsymbol {z}\vDash \chi _{i}$
,
$d_{w}(\boldsymbol {y},\boldsymbol {z})=\sum _{k=1}^{\infty }w(\varphi _{k})d_{k}(\boldsymbol {y},\boldsymbol {z})=\sum _{k=n}^{\infty }w(\varphi _{k})d_{k}(\boldsymbol {y},\boldsymbol {z})<\epsilon $
.
For 2., let
$\varphi \in \mathcal {L}$
be given. Since D is finitely
$\mathcal {L}$
-representative w.r.t. X, there is
$\{\psi _{i}\}_{i\in I}\subseteq D$
finite such that for all sets
$S=\{\psi _{i}\}_{i\in J}\cup \{\neg \psi _{i}\}_{i\in I\setminus J}$
with
$J\subseteq I$
either
$\varphi $
or
$\neg \varphi $
is entailed by S in X. Then
$\delta :=\min _{i\in I}w(\psi _{i})$
yields the desired.
Proof of Proposition 26
We show that
$\boldsymbol {f}$
is uniformly continuous, using the
$\varepsilon $
–
$\delta $
formulation of continuity. Assume that
$\epsilon>0$
is given. We find a
$\delta>0$
such that for all
$\boldsymbol {x},\boldsymbol {y}\in \boldsymbol {X}_{\mathcal {L}} \ d_{w}(\boldsymbol {x},\boldsymbol {y})<\delta $
implies
$d_{w}(\boldsymbol {f(x)},\boldsymbol {f(y)})<\epsilon $
. By Lemma 27.1, there exist
$\chi _{1},\ldots ,\chi _{l}$
such that
$f(\boldsymbol {x})\vDash \chi _{i}$
and
$f(\boldsymbol {y})\vDash \chi _{i}$
implies
$d_{w}(\boldsymbol {f(x)},\boldsymbol {f(y)})<\epsilon $
and for every
$\boldsymbol {x}\in \boldsymbol {X}_{\mathcal {L}}$
there is some
$i\leq l$
with
$\boldsymbol {f(x)}\vDash \chi _{i}$
. We use
$\chi _{1},\ldots ,\chi _{l}$
to find a suitable
$\delta $
:
Claim. There is a function
$\boldsymbol {\delta }:\mathcal {L}\rightarrow (0,\infty )$
such that for any
$\varphi \in \mathcal {L}$
, if
$\boldsymbol {f}(\boldsymbol {x})\vDash \varphi $
and
$d_{w}(\boldsymbol {x},\boldsymbol {y})<\boldsymbol {\delta }(\varphi )$
, then
$\boldsymbol {f}({\kern1.2pt}\boldsymbol {y})\vDash \varphi $
.
Clearly, setting
$\delta =\min \{\boldsymbol {\delta }(\chi _{i})\colon i\leq l\}$
yields a
$\delta $
with the desired property. Hence the proof is completed by a proof of the claim. The claim is shown by constructing the function
$\boldsymbol {\delta }:\mathcal {L}\rightarrow (0,\infty )$
. This construction will proceed by induction over the complexity of
$\varphi $
. To begin with, fix a precondition finite, multi-pointed action model
$\Sigma {\scriptstyle \Gamma }$
closing, deterministic, and exhaustive over X such that
$\boldsymbol {f}(\boldsymbol {x})=\boldsymbol {y}$
iff
$\boldsymbol {x}\otimes \Sigma {\scriptstyle \Gamma }=\boldsymbol {y}$
. To be explicit, the function
$\boldsymbol {\delta }:\mathcal {L}\rightarrow (0,\infty )$
we construct depends on this action model. More precisely,
$\boldsymbol {\delta }$
depends on the set
. The below construction of
$\boldsymbol {\delta }$
is a simultaneous induction over all multi-pointed action models that are closing, deterministic, and exhaustive over X with set of preconditions exactly
. By Lemma 25, we can assume that for all
it holds that
$pre(\sigma )=pre(\sigma ')$
or
$\vDash pre(\sigma )\wedge pre(\sigma ')\rightarrow \bot $
. By working with an extended language that contains
$\neg ,\wedge ,\vee ,\Box _{i}$
, and
$\lozenge _{i}$
as primitives, we can assume, without loss of generality, that all negations in
$\varphi $
immediately precede atoms.
If
$\varphi $
is an atom or negated atom: By Lemma 27.2, there exists for any
some
$\delta _{\sigma }$
such that whenever
$\boldsymbol {x}\vDash pre(\sigma )$
and
$d_{w}(\boldsymbol {x},\boldsymbol {y})<\delta _{\sigma }$
we also have that
$\boldsymbol {y}\vDash pre(\sigma )$
. Likewise, there is some
$\delta _{0}$
such that whenever
$\boldsymbol {x}\vDash \varphi $
and
$d_{w}(\boldsymbol {x},\boldsymbol {y})<\delta _{0}$
we also have that
$\boldsymbol {y}\vDash \varphi $
. By assumption, the set
is finite. Let
. We can thus set
$\boldsymbol {\delta }(\varphi )=\min (S)$
. To see that this
$\boldsymbol {\delta }$
is as desired, assume
$\boldsymbol {f}(\boldsymbol {x})\vDash \varphi $
. Let
$x=Ms\in \boldsymbol {x}$
. There is a unique
$\sigma \in \Gamma $
in the deterministic, multi-pointed action model
$(\Sigma ,\Gamma )$
such that
$(s,\sigma )$
is the designated state of
$x\otimes \Sigma {\scriptstyle \Gamma }$
. In particular, we have that
$x\vDash pre(\sigma )$
. By our choice of
$\boldsymbol {\delta }(\varphi )$
, we get that
$d_{w}(\boldsymbol {x},\boldsymbol {y})<\boldsymbol {\delta }(\varphi )$
implies
$\boldsymbol {y}\vDash pre(\sigma )$
. For
$y=Nt\in \boldsymbol {y}$
, we thus have that
$(t,\sigma )$
is the designated state of
$Nt\otimes \Sigma {\scriptstyle \Gamma }$
. Moreover, we have
$\boldsymbol {x}\vDash \varphi \Leftrightarrow \boldsymbol {y}\vDash \varphi $
. Together, these imply that
$\boldsymbol {f}(\boldsymbol {Nt})\vDash \varphi $
, i.e.,
$\boldsymbol {f}({\kern1.2pt}\boldsymbol {y})\vDash \varphi $
.
If
$\varphi $
is
$\varphi _{1}\wedge \varphi _{2}$
, set
$\boldsymbol {\delta }(\varphi )=\min (\boldsymbol {\delta }(\varphi _{1}),\boldsymbol {\delta }(\varphi _{2})\,)$
. To show that this is as desired, assume
$\boldsymbol {f}(\boldsymbol {x})\vDash \varphi _{1}\wedge \varphi _{2}$
. We thus have
$\boldsymbol {f}(\boldsymbol {x})\vDash \varphi _{1}$
and
$\boldsymbol {f}(\boldsymbol {x})\vDash \varphi _{2}$
. By induction, this implies that whenever
$d_{w}(\boldsymbol {x},\boldsymbol {y})<\boldsymbol {\delta }(\varphi )$
, we have
$\boldsymbol {f}(\boldsymbol {y})\vDash \varphi _{1}$
and
$\boldsymbol {f}(\boldsymbol {y})\vDash \varphi _{2}$
and hence
$\boldsymbol {f}(\boldsymbol {y})\vDash \varphi _{1}\wedge \varphi _{2}$
.
If
$\varphi $
is
$\varphi _{1}\vee \varphi _{2}$
, set
$\delta (\varphi )=\min (\boldsymbol {\delta }(\varphi _{1}),\boldsymbol {\delta }(\varphi _{2})\,)$
. To show that this is as desired, assume
$\boldsymbol {f}(\boldsymbol {x})\vDash \varphi _{1}\vee \varphi _{2}$
. We thus have
$\boldsymbol {f}(\boldsymbol {x})\vDash \varphi _{1}$
or
$\boldsymbol {f}(\boldsymbol {x})\vDash \varphi _{2}$
. By induction, this implies that whenever
$d_{w}(\boldsymbol {x},\boldsymbol {y})<\boldsymbol {\delta }(\varphi )$
we have
$\boldsymbol {f}(\boldsymbol {y})\vDash \varphi _{1}$
or
$\boldsymbol {f}(\boldsymbol {y})\vDash \varphi _{2}$
and hence
$\boldsymbol {f}(\boldsymbol {y})\vDash \varphi _{1}\vee \varphi _{2}$
.
If
$\varphi $
is
$\lozenge _{r}\varphi _{1}$
: By Lemma 27.1, there are
$\chi _{1},\ldots ,\chi _{l}$
such that every
$\boldsymbol {x}\in \boldsymbol {X}_{\mathcal {L}}$
satisfies some
$\chi _{i}$
and whenever
$\mathbf {z}\vDash \chi _{i}$
and
$\mathbf {z'}\vDash \chi _{i}$
for some
$i\leq l$
we have
$d_{w}(\mathbf {z},\mathbf {z'})<\boldsymbol {\delta }(\varphi _{1})$
.
Now, let
. By assumption, F is finite. By Lemma 27.2, for each
$\psi \in F$
there is some
$\delta _{\psi }$
such that
$\boldsymbol {x}\vDash \psi $
and
$d_{w}(\boldsymbol {x},\boldsymbol {y})<\delta _{\psi }$
implies
$\boldsymbol {y}\vDash \psi $
. Set
$\boldsymbol {\delta }(\varphi )=\min \{\delta _{\psi }\colon \psi \in F\}.$
To show that this is as desired, assume
$\boldsymbol {f}(\boldsymbol {x})\vDash \lozenge _{r}\varphi _{1}$
and let
$\boldsymbol {y}$
be such that
$d_{w}(\boldsymbol {x},\boldsymbol {y})<\boldsymbol {\delta }(\varphi )$
. We have to show that
$\boldsymbol {f}(\boldsymbol {y})\vDash \lozenge _{r}\varphi _{1}.$
Let
$x=Ms\in \boldsymbol {x}$
and let the designated state of
$x\otimes \Sigma {\scriptstyle \Gamma }$
be
$(s,\sigma )$
. Since
$x\otimes \Sigma {\scriptstyle \Gamma }\vDash \lozenge _{r}\varphi _{1}$
, there is some
$(s',\sigma ')$
in
with
$(s,\sigma )R_{r}(s',\sigma ')$
. In particular
$x\vDash \lozenge _{r}(pre(\sigma ')\wedge \chi _{i})$
for
and some
$i\leq l$
. Thus also
$\boldsymbol {y}\vDash \lozenge _{r}(pre(\sigma ')\wedge \chi _{i})$
. Hence, for
$y=Nt\in \boldsymbol {y}$
, there is some
accessible from y’s designated state t that satisfies
$pre(\sigma ')\wedge \chi _{i}.$
By determinacy and the fact that
$\vDash pre(\sigma )\wedge pre(\sigma ')\rightarrow \bot $
whenever
$pre(\sigma )\neq pre(\sigma ')$
, there is a unique
$\tilde {\sigma }\in \Gamma $
with
$pre(\tilde {\sigma })=pre({\sigma '})$
. Let
$\Gamma '=\Gamma \backslash \{\tilde {\sigma }\}\cup \{\sigma \}$
. Then,
$\Sigma {\scriptstyle \Gamma '}$
is a precondition finite, multi-pointed action model deterministic over X. Let
$\boldsymbol {f}'$
be the model transformer induced by
$\Sigma {\scriptstyle \Gamma '}$
. As
$\boldsymbol {f}'$
has the same set
as
$\boldsymbol {f}$
, our induction hypothesis applies to
$\boldsymbol {f}'$
. Consider the models
$Ms'$
and
$Nt'$
. We have that
$Ms'\vDash \chi _{i}$
and
$Nt'\vDash \chi _{i}$
jointly imply
$d_{w}(\boldsymbol {Ms'},\boldsymbol {Nt'})<\boldsymbol {\delta }(\varphi _{1})$
which, in turn, implies that
$\boldsymbol {f}'(\boldsymbol {Ms'})\vDash \varphi _{1}$
iff
$\boldsymbol {f}'(\boldsymbol {Nt'})\vDash \varphi _{1}$
. In particular, we obtain that
. Since
$(t,\sigma )R_{r}(t',\sigma ')$
this implies that
$\boldsymbol {f}(\boldsymbol {y})\vDash \lozenge _{r}\varphi _{1}.$
If
$\varphi $
is
$\square _{r}\varphi _{1}$
: The construction is similar to the previous case. We only elaborate on the relevant differences. Again, there are some
$\chi _{1},\ldots ,\chi _{l}$
such that every
$\boldsymbol {x}\in \boldsymbol {X}_{\mathcal {L}}$
satisfies some
$\chi _{i}$
and whenever
$\boldsymbol {z}\vDash \chi _{i}$
and
$\boldsymbol {z}'\vDash \chi _{i}$
for some
$i\leq l$
we have
$d_{w}(\boldsymbol {z},\boldsymbol {z}')<\boldsymbol {\delta }(\varphi _{1})$
.
Now, let
and let
. Again, F is finite and for each
$\psi \in F$
there is some
$\delta _{\psi }$
such that
$\boldsymbol {x}\vDash \psi $
and
$d_{w}(\boldsymbol {x},\boldsymbol {y})<\delta _{\psi }$
implies
$\boldsymbol {y}\vDash \psi $
. Set
$\delta (\varphi )=\min \{\delta _{\psi }\colon \psi \in F\}.$
To show that this is as desired, assume
$\boldsymbol {f}(\boldsymbol {x})\vDash \square _{r}\varphi _{1}$
and let
$\boldsymbol {y}$
be such that
$d_{w}(\boldsymbol {x},\boldsymbol {y})<\boldsymbol {\delta }(\varphi )$
. We have to show that
$\boldsymbol {f}(\boldsymbol {y})\vDash \square _{r}\varphi _{1}.$
Let
$Ms\in \boldsymbol {x}$
and
$Nt\in \boldsymbol {y}$
, let
$(t,\sigma )$
be the designated state of
$Nt\otimes \Sigma {\scriptstyle \Gamma }$
and assume there is some
$(t',\sigma ')$
in
with
$(t,\sigma )R^{\prime }_{r}(t',\sigma ')$
. We have to show that
$\varphi _{1}$
holds at
. To this end, note that by construction,
$t'$
satisfies
$pre(\sigma ')\wedge \chi _{i}$
, for some
$i\leq l$
. By the choice of
$\boldsymbol {\delta }(\varphi )$
, there is some
with
$sR_{r}s'$
that also satisfies
$pre(\sigma ')\wedge \chi _{i}$
. Hence
$(s',\sigma ')$
is in
and
$(s,\sigma )R_{r}(s',\sigma ')$
. By assumption we have
and by an argument similar to the last case we get
, which is what we had to show. Hence
$\boldsymbol {f}(\boldsymbol {y})\vDash \square _{r}\varphi _{1}$
.
Corollary 28. Any clean map
$\boldsymbol {f}:\boldsymbol {X}_{\mathcal {L}}\rightarrow \boldsymbol {X}_{\mathcal {L}}$
is continuous with respect to the Stone(-like) topology
$\mathcal {T}_{\mathcal {L}}$
.
Corollary 28 only provides sufficient conditions for continuity, not necessary ones. Not every continuous map
$\boldsymbol {f}:\boldsymbol {X}_{\mathcal {L}}\rightarrow \boldsymbol {X}_{\mathcal {L}}$
is also clean. In general, there need not be any multi-pointed action model
$\Sigma {\scriptstyle \Gamma }$
with
$\boldsymbol {f}(\boldsymbol {x})=\boldsymbol {x}\otimes \Sigma {\scriptstyle \Gamma }$
for all
$\boldsymbol {x}\in \boldsymbol {X}_{\mathcal {L}}$
. For example, let
$\mathcal {L}$
be build from infinitely many atoms
$\Phi $
and let
$\boldsymbol {g}:\boldsymbol {X}_{\mathcal {L}}\rightarrow \boldsymbol {X}_{\mathcal {L}}$
be the map that flips the truth value of every atom at every state, so
is mapped to
with
for every atom
$p\in \Phi $
. Then
$\boldsymbol {g}$
is not representable by a multi-pointed action model. To see this, consider any single-state model
$\boldsymbol {y}$
. The unique worlds of
$\boldsymbol {g}(\boldsymbol {y})$
and
$\boldsymbol {y}$
differ on the truth values of infinitely many atoms, but any multi-pointed action model can only change finitely many atoms’ truth values, as postconditions are assumed finite.
Moreover, we conjecture that there exist continuous maps
$\boldsymbol {f}:\boldsymbol {X}_{\mathcal {L}}\rightarrow \boldsymbol {X}_{\mathcal {L}}$
that are representable by multi-pointed action models without being clean maps. In particular, the assumption of precondition finiteness in the proof of Proposition 26 may be replaceable by a weaker condition. Defining continuity locally in a point
$\boldsymbol {x}\in \boldsymbol {X}_{\mathcal {L}}$
may also permit relaxing the condition of exhaustivity.
Acknowledgments
We thank Johan van Benthem and Kristian K. Olesen for discussions that have significantly affected the present work. Much of this work was conducted while D. Klein was affiliated with the Department of Philosophy, University of Bayreuth, and the Department of Political Science, University of Bamberg, and while R. K. Rendsvig was affiliated with the Department of Philosophy, Lund University, and the Center for Information and Bubble Studies, University of Copenhagen. The Center for Information and Bubble Studies is funded by the Carlsberg Foundation.
Open access
