=Paper=
{{Paper
|id=None
|storemode=property
|title=A Logic Related to Minimal Knowledge
|pdfUrl=https://ceur-ws.org/Vol-635/paper12.pdf
|volume=Vol-635
|dblpUrl=https://dblp.org/rec/conf/at/0001U09
}}
==A Logic Related to Minimal Knowledge==
https://ceur-ws.org/Vol-635/paper12.pdf
A Logic Related to Minimal Knowledge ?
David Pearce1 and Levan Uridia2
1
Universidad Politcnica de Madrid, Spain, david.pearce@upm.es
2
Universidad Rey Juan Carlos, uridia@ia.urjc.es
Abstract. We introduce and study a modal logic wK4F which is closely
related to the logic S4F that is important in the context of epistemic
logics for representing and reasoning about an agent’s knowledge. It is
obtained by adding the axiom F to the modal logic wK4, or dropping
from S4F the T axiom. We show that wK4F is sound and complete
with respect to the class of all minimal topological spaces i.e. topological
spaces with only three open sets. We characterize the rooted frames of the
logic wK4F by quadruples of natural numbers and in the same fashion
we give a characterization of p-morphic images of rooted wK4F frames.
1 Introduction
In epistemic logic and formalisms for representing an agent’s knowledge, the
paradigm of minimal knowledge has played an important role [1]. S4F is a re-
flexive normal modal logic first introduced and studied by Segerberg [2]. Later
its importance for knowledge representation and reasoning was discovered by
Truszczynski [3] and Schwarz and Truszczynski [4] who used it to investigate
the idea of minimal knowledge. They showed that the nonmonotonic version of
the logic S4F captures, under some intuitive encodings, several important ap-
proaches to knowledge representation and reasoning. They include disjunctive
logic programming under answer set semantics [5], (disjunctive) default logic [6];
[7], the logic of grounded knowledge [8], the logic of minimal belief and nega-
tion as failure [10] and the logic of minimal knowledge and belief [4]. Recently,
Truszczynski [11] and Cabalar [12] have revived the study of S4F in the context
of a general approach to default reasoning.
In terms of Kripke models, S4F is captured by frames consisting of two
clusters of points connecting by an accessibility relation:
second floor r2 W2
first floor r1 W1
?
Partially supported by the MCICINN projects TIN2006-15455-CO3 and CSD2007-
00022.
142
The points in each cluster, W1 , W2 , are reflexive. In this paper we study a logic
closely related to S4F , called wK4F . It is obtained by dropping from S4F the
T axiom and therefore the condition of reflexivity on points; so, while the basic
picture is the same, some points in W1 , W2 are now irreflexive.
Since S4F and wK4F are closely related, many results about the latter
can be transferred to the former. In this paper we examine wK4F , prove a
completeness theorem and show that there is a close relation between wK4F
and the class of minimal topological spaces. We leave for future work the study
of the non-monotonic variant of wK4F as well as multi-modal versions that
may be used to represent common knowledge. However we point out that by a
standard translation technique there is a natural embedding of wK4F into S4F .
The embedding is obtained by so called splitting translation the main clause of
which is given by Sp(φ) = φ ∧ φ.
The paper is organized in the following way. In section 2 we present the syntax
and kripke semantics of the modal logic wK4F . We prove the completeness and
finite model property with respect to given semantics. In section 3 we give the
characterization of finite one-step, weak-transitive frames and their bounded
morphisms in terms of quadruples of natural numbers. In section 4 we prove the
main theorem of the paper, which states that wK4F is the complete and sound
logic of all minimal topological spaces. The last section gives the conclusion and
questions for future work.
2 The modal logic wK4F
Following Tarski’s suggestion to treat modality as the derivative of the topolog-
ical space, Esakia [13] introduced the modal logic wK4 as the modal logic of all
topological spaces, with the desired (derivative operator) interpretation of the
modal ♦. The modal logic wK4F is a normal modal logic obtained by adding
the axiom weak-F to the modal logic wK4. wK4F is a weaker logic then S4F
discussed in Segerberg [2]. In particular we get the modal logic S4F by adding
axiom T to the logic wK4F . Thus in this sense wK4F is of interest for S4F
also as some results are easily carried over and simplified from one to another.
2.1 syntax
Definition 2.11 The normal modal logic wK4F is defined in a standard modal
language with an infinite set of propositional letters p, q, r.. and connectives
∨, ∧, , ¬,
• The axioms are all classical tautologies plus the following axioms:
> ↔ >,
(p ∧ q) ↔ p ∧ q,
p ∧ p → p,
p ∧ ♦(q ∧ ¬p) → (q ∨ ♦q).
• The rules of inference are: Modus ponens, Substitution and Necessitation.
143
2.2 Kripke semantics
The Kripke semantics for the modal logic wK4F is provided by one-step, weak-
transitive Kripke frames. Below we give the definition of these frames.
Definition 2.21 We will say that a relation R ⊆ W × W is weak-transitive if
(∀x, y, z)(xRy ∧ yRz ∧ x 6= z ⇒ xRz).
Of course every transitive relation is weakly-transitive also. Moreover it is
not difficult to see that weakly-transitive relations differ from transitive ones
just by the occurrence of irreflexive points in clusters. As one can see, the frame
in the picture is weakly transitive, but not transitive.
The picture represents the diagramatic view
of kripke structure. Irreflexive points are col-
ored by grey and reflexive points are uncol- x y
ored. Arrows represent the relation between
two distinct points. So as we can see yRx pic. 1
and xRy, but y 6 Ry, which contradicts tran-
sitivity, but not weak transitivity as y = y.
Definition 2.22 We will say that a relation R ⊆ W × W is a one-step relation
if the following two conditions are satisfied:
1)(∀x, y, z)((xRy ∧ yRz) ⇒ (yRx ∨ zRy)),
2)(∀x, y, z)((xRy ∧ ¬(yRx) ∧ xRz) ⇒ (zRx ∨ (zRy ∨ yRz))).
As the reader can see the first condition restricts the ”strict” height of the
frame to two. Where informally by ”strict” we mean that the steps are not
counted within a cluster. So for example we cannot have the situation on the
left hand side of the picture below, while we can have the situations in the middle
and on the right hand side.
The second condition is more complicated. Nevertheless it is not too hard to
verify that it restricts the ”strict” width of the frame to one. So again we cannot
have for example the figure on the right hand side, while the figures in the middle
and on the left are allowed. Here we cheat slightly as indeed the frame is not
allowed to fork as in the picture on the right, but condition 2) does not restrict
the reversed fork i.e. frame with two points on the bottom and one on the top.
So strict width does not effect points on the bottom.
144
For the sake of completeness we will just briefly recall the main definitions
in modal logic, like: Kripke frame, satisfaction and validity of modal formulas.
Definition 2.23 The pair (W, R), with W an arbitrary set (set of possible
worlds) and R ⊆ W × W is called a Kripke frame.
If we additionally have a third component V : P rop × W → {0, 1}, then we
say that we have a Kripke model M = (W, R, V ) (where P rop denotes the set of
all propositional letters).
The satisfaction and validity of a modal formula are defined inductively. We
just state the base and modal cases here.
Definition 2.24 For a given kripke model M = (W, R, V ) the satisfaction of a
formula at a point w ∈ W is defined inductively as follows: w p iff V (p, w) = 1,
the boolean cases are standard, w φ iff (∀v)(wRv ⇒ v φ).
Note: From the definition of ♦, (♦φ ≡ ¬¬φ) it follows that w ♦φ iff
(∃v)(wRv ∧ v φ).
So far we defined the modal logic wK4F syntactically and we gave the defini-
tion of one-step and weakly-transitive Kripke frames. The following two propo-
sitions link these two things. The proof uses standard modal logic completeness
techniques, so we will not enter into all the details.
Proposition 2.25 The modal logic wK4F is sound w.r.t. the class of all one-
step and weakly-transitive Kripke frames.
Proof. We give the proof only for the fourth axiom of the modal logic wK4F .
The proofs for other axioms are analogous. The reader may also consult [13].
Take an arbitrary, weakly-transitive, one-step frame (W, R). Take an arbi-
trary valuation V and assume at some point w ∈ W that w p ∧ ♦(q ∧ ¬p).
By the definition of satisfaction this implies that w p and there exists w0 such
that wRw0 , w0 q and it is not the case that w0 Rw as much as w0 ¬p. Now
take an arbitrary v such that wRv. By the second condition in the definition
of one-step relation we have that either vRw or vRw0 ∧ w0 Rv. If v = w0 we
immediately have that v q since w0 q. In case v 6= w0 we have two subcases
vRw0 ∧ w0 Rv or vRw ∧ wRv. In both cases by weak-transitivity of the relation
R we have at least vRw0 , which implies that v ♦q and hence w (q ∨ ♦q).
Proposition 2.26 The modal logic wK4F is complete w.r.t. the class of all
finite, one-step and weakly-transitive Kripke frames.
Proof. We do not give the details here as far as the proof uses standard tech-
niques given in [13]. First we take the canonical model for wK4F and then apply
the minimal filtration to it.
145
3 The class of finite, rooted, weakly-transitive and
one-step Kripke frames and their bounded morphisms.
We have seen that the class of finite, weakly-transitive and one-step Kripke
frames fully captures the modal logic wK4F . This class can be reduced to a
smaller class of frames which are rooted. In this section we characterise finite,
rooted, weakly-transitive and one-step Kripke frames and their bounded mor-
phisms in terms of quadruples of natural numbers.
S cone of a set A ⊆ W in a Kripke frame (W, R) is
Definition 3.07 The upper
defined as a set R(A) = {y : x ∈ A&xRy}.
Definition 3.08 A Kripke frame (W, R) is called rooted if there exists a point
w ∈ W such that the upper cone R({w}) = W ; w is called the root of the frame.
Note 1. The root is not necessarily unique. For example on the first picture both
x and y are roots.
Let N 4 be the set of all quadruples of natural numbers and let N 4 =
4
N − {(n, m, 0, 0)|n, m ∈ N }. The following theorem states that the set of fi-
nite, rooted, one-step, weakly-transitive frames can be viewed as the set N 4 .
Let K denote the class of all rooted, finite, one-step, weakly-transitive frames
considered up to isomorphism.
Theorem 3.09 There is a one-to-one correspondence between the set K and the
set N 4 .
Proof. We know that any one-step frame has ”strict” width one and ”strict”
height less than or equal to two (We didn’t give the formal definition of ”strict”
height and width, but it should be clear from the intuitive explanation after the
definitions 2.22 and 2.21 what we mean by this). If additionally we have that the
frame is rooted, the case where width is greater than one at the bottom is also
restricted. It is not difficult to verify that any such frame (W, R) is of the form
(W1 , W2 ), where W1 ∪ W2 = W , W1 ∩ W2 = ∅ and (∀u ∈ W1 , ∀v ∈ W2 )(uRv).
Besides because of the weak-transitivity, we have that (∀u, u0 ∈ W1 )(u 6= u0 ⇒
uRu0 ) and the same for every two points v, v 0 ∈ W2 . We will call W1 the first
floor and W2 the second floor of the frame (W, R). Pictorially any rooted,
weak-transitive and one-step Kripke frame can be represented as in the picture
below.
second floor i2 r2 W2
first floor i1 r1 W1
Note 2. It is possible that W1 or W2 is equal to ∅ i.e. the frame has only one
floor. In this case we treat the only floor of the frame as the second floor.
146
Now let us describe how to construct the function from K to N 4 . With every
frame (W, R) ∈ N 4 we associate the quadruple (i1 , r1 , i2 , r2 ), where i1 is the
number of irreflexive points in W1 , r1 is the number of reflexive points in W1 , i2
is the number of irreflexive points in W2 and r2 is the number of reflexive points
in W2 . We will call the quadruple (i1 , r1 , i2 , r2 ) the characteriser of the frame
(W, R). In case the frame (W, R) has only one floor, by note 2 above it is treated
as the frame (∅, W ). Hence it’s characteriser has the form (0, 0, i, r). Now it is
clear that the correspondence described above defines a function from the set K
to the set N 4 . Let us denote this function by Ch.
claim 1: Ch is injective. Take any two distinct finite, rooted, weakly-transitive,
one-step Kripke frames (W, R) and (W 0 , R0 ). That they are distinct in K means
that they are non-isomorphic i.e. either |W | 6= |W 0 | or R 6' R0 . In the first case
it is immediate that Ch(W, R) 6= Ch(W 0 , R0 ) since |W | = i1 + i2 + r1 + r2 . In
the second case we have three subcases:
1) |W1 | 6= |W10 |. In this subcase i1 + r1 6= i01 + r10 and hence Ch(W, R) 6=
Ch(W 0 , R0 ).
2) The number of reflexive (irreflexive) points in |W1 | differs from the num-
ber of reflexive (irreflexive) points in |W10 |. In this subcase i1 6= i01 and again
Ch(W, R) 6= Ch(W 0 , R0 ).
3) The number of reflexive (irreflexive) points in |W2 | differs from the number
of reflexive (irreflexive) points in |W20 |. This case is analogous to the previous.
It is straightforward to see that if none of these cases above occur i.e. |W | =
|W 0 |, |W1 | = |W10 |, |{w|w ∈ W1 ∧ wRw}| = |{w0 |w0 ∈ W10 ∧ w0 R0 w0 }| and
|{w|w ∈ W2 ∧ wRw}| = |{w0 |w0 ∈ W2 ∧ w0 R0 w0 }| then (W, R) is isomorphic to
(W 0 R0 ) and hence (W, R) = (W 0 , R0 ) in K.
claim 2: Ch is surjective. Take any quadruple (i1 , r1 , i2 , r2 ) ∈ N 4 . Let us show
that the pre-image Ch−1 ((i1 , r1 , i2 , r2 )) is not empty. Take the frame (W, R) =
(W1 , W2 ), where |W1 | = i1 + r1 , |W2 | = i2 + r2 , W1 contains i1 irreflexive and
r1 reflexive points and |W2 | contains i2 irreflexive and r2 reflexive points. Then
by the definition of Ch, we have that Ch(W, R) = (i1 , r1 , i2 , r2 ).
Definition 3.010 The function f between two frames (W, R) and (W 0 , R0 ) is
called a bounded morphism if the following two conditions are satisfied:
(1) wRv ⇒ f (w)R0 f (v),
(2) f (w)R0 v 0 ⇒ (∃v ∈ W )(wRv ∧ f (v) = v 0 ).
The bijection given in theorem 3.09 can be extended to bounded morphisms.
In the following theorems we characterise the bounded morphisms between two
finite, rooted, weakly-transitive, one-step frames in terms of conditions on the
quadruples of natural numbers. We split the proof into three different theorems
to make it much more readable; besides each case is interesting on its own. In the
first theorem we will give the characterisation for frames with the characterisers
(0, 0, i, r) i.e. for frames with only one floor, then we will give the characterisa-
tions for frames where one has two floors and the second is one floor frame and
the third theorem will give the condition for frames where both have two floors.
We will omit zeroes in the quadruple (0, 0, i, r) and just write it as (i, r).
147
Theorem 3.011 The finite, rooted, weakly-transitive, one-step frame (W 0 , R0 )
with the characteriser (i0 , r0 ) is a bounded morphic image of the finite, rooted,
weakly-transitive, one-step frame (W, R) with the characteriser (i, r) iff the fol-
lowing conditions are satisfied:
r0 = 0 ⇒ (i, r) = (i0 , r0 ),
i ≥ i0 ,
2 × (r0 − r) ≤ i − i0 .
Note that the operation minus is defined within the natural numbers i.e. n−m = 0
if m > n.
Proof. For the left to right direction assume f : (W, R) (W 0 , R0 ). This means
that i + r ≥ i0 + r0 , sincef is a surjection. First let us state some general obser-
vations which will help in proving the theorem.
• for every irreflexive point w0 ∈ W 0 , we have that f −1 (w0 ) is one
irreflexive point. Assume not. Then either f −1 (w0 ) contains some reflexive
point w ∈ W , or it contains at least two irreflexive points u, v ∈ W . In the first
case we have wRw but not f (w)R0 f (w), so we obtain a contradiction. In the
second case we have uRv ∧ vRu but not f (v)R0 f (u) and again this contradicts f
being a bounded morphism. Now we are ready to begin the proof of the theorem.
Let us check that all conditions are satisfied.
case 1 Assume r0 = 0 but (i, r) 6= (i0 , r0 ). So either r 6= 0 or i 6= i0 . In both
cases we get a contradiction by the above observation, as reflexive points cannot
be mapped to irreflexive ones and also two irreflexive points can not be mapped
to one irreflexive point.
case 2 Assume i < i0 . Then there is at least one point v 0 ∈ W 0 such that
−1 0
f (v ) = ∅. The reason is that there are not enough irreflexive points in W to
cover all irreflexive points in W 0 . And we know (by above remarks) we cannot
map reflexive points to irreflexive ones. So we get a contradiction.
case 3 Assume 2 × (r0 − r) > i − i0 . This means that r0 > r. So there are
r − r reflexive points in W 0 with the pre-image not containing a reflexive point.
0
But then there is at least one reflexive point w0 ∈ W 0 such that f −1 (w0 ) con-
tains less than 2 irreflexive points. This is because by assumption there are not
enough pairs of irreflexive points in W for all reflexive points with pre-image
not containing reflexive ones. But this gives a contradiction because either f is
not surjective (in case f −1 (w0 ) = ∅) or f is not a bounded morphism (in case
f −1 (w0 ) = v with v irreflexive).
Now let us prove the converse direction. Let us enumerate points in W in the
following way: Let w1 , ...wr be the reflexive points and v1 , ...vi irreflexive points.
Let us use the same enumeration for points in W 0 with the difference that we
add 0 to every point. So for example w10 is the reflexive and v20 is the irreflexive
point in W 0 . In case r0 = 0 we know that (i, r) = (i0 , r0 ) and we can take f to
be bijection mapping wi to wi0 .
148
In case r0 6= 0 we distinguish two subcases.
case 1 When r > r0 . Let us define f : W → W 0 in the following way:
f (vj ) = vj0 for j ∈ {1, .., i01 },
f (wj ) = wj0 for j ∈ {1, .., r10 − 1},
f (vi0 +1 ) = f (vi0 +2 ) = ... = f (vi ) = f (wr0 +1 ) = .. = f (wr ) = wr0 .
case 2 When r ≤ r0 . Let us define f : W → W 0 in the following way:
f (vj ) = vj0 for j ∈ {1, .., i0 },
f (wj ) = wj0 for j ∈ {1, .., r},
0
f (vi0 +2k−1 ) = f (vi0 +2k ) = wr+k for k ∈ {1, .., r0 − r − 1},
f (vi0 +2(r0 −r)−1 ) = f (vi0 +2(r0 −r) ) = .. = f (vi ) = wr0 .
In other words we send each reflexive point wj ∈ W to the reflexive point
wj0 ∈ W 0 and each irreflexive point vj ∈ W to the irreflexive point vj0 ∈ W 0 .
Inasmuch as we have that i ≥ i0 and r ≤ r0 , there may be left some irreflexive
points in W on which we have not yet defined f and also some reflexive points
in W 0 which have no pre-image, so we associate to every pair of such irreflexive
points one reflexive point which has no pre-image. We continue this process until
we are left with only one reflexive point without pre-image (we know this exists
by the condition r0 6= 0) and associate to it all the remaining irreflexive points on
which f was not defined. The condition 2 × (r − r0 ) ≤ i0 − i guarantees that there
are at least two such irreflexive points left. It is easy to check that f defined in
the following way is indeed a bounded morphism.
Now let us consider the case, where the first frame has two floors, while the
second is a one floor frame. Note that the only difference from the conditions
in 3.011 is that we require that the second frame contains at least one reflexive
point. This is because we want to map all first floor points of the first frame to
this particular reflexive point.
Theorem 3.012 The finite, rooted, weakly-transitive, one-step frame (W 0 , R0 )
with the characteriser (i0 , r0 ) is a bounded morphic image of the finite, rooted,
weak-transitive, one-step frame (W, R) with the characteriser (i1 , r1 , i2 , r2 ), where
i1 + r1 > 0 and i2 + r2 > 0 iff the following conditions are satisfied:
r0 6= 0,
i2 ≥ i0 ,
2 × (r0 − r2 ) ≤ i2 − i0 .
Proof. Assume r0 = 0. This means that all points in (W 0 , R0 ) are irreflexive.
Now as (W, R) has two floors we can represent it as a pair (W1 , W2 ) where both
sets are non-empty. This implies that there are at least two points u ∈ W1 and
v ∈ W2 , such that f (u) ∈ W 0 and f (v) ∈ W 0 . Since (W 0 , R0 ) is a cluster, we
have that f (u)R0 f (v) and f (v)R0 f (u). But this contradicts the property that f
is a bounded morphism. This is because not Ru while f (v)R0 f (u) and as f (u)
149
is irreflexive there does not exist a point w ∈ W , with u 6= w and f (w) = f (v)
(see the first observation in the proof of lemma 3.011).
Assume i2 < i0 . Again by first observation in the proof of lemma 3.011 we
know that the pre-image of the irreflexive point cannot be reflexive. This means
that there exists a point u0 ∈ W 0 , such that, u0 is irreflexive and f −1 (u0 ) ∩ W2 =
∅. Different from the analogous case in the proof of lemma 3.011 the possibility
arises that some irreflexive point u ∈ W1 is mapped to the point u0 . Let us show
that this cannot happen. Assume u ∈ W1 and f (u) = u0 . As u is a first floor
point, there exists some v ∈ W2 with uRv. As f is bounded morphism we have
that f (u)R0 f (v). As (W 0 , R0 ) is a cluster we have that f (v)R0 f (u) as well. Now
we get a contradiction as there is no successor of v which is mapped to f (u) = u0 .
Assume the third condition does not hold. This means that 2 × (r0 − r2 ) >
i2 − i0 . In this case we have that there is at least one point u0 ∈ W 0 such that
u0 is reflexive and f −1 (u0 ) ∩ W2 is either the empty set or it contains only one
point u with u 6 Ru. This gives a contradiction, since u0 R0 u0 while there is no
successor v of u with f (u) = u0 .
For the converse direction we construct f : W W in the following way:
f|W1 = v 0 , where v 0 is an arbitrary reflexive point in W 0 (we know that such a
point exists from the first condition of the lema). f|W2 is constructed in exact
analogy with the construction in 3.011.
And at last we can give the characterisation for the case where both frames
have two floors.
Theorem 3.013 The finite, rooted, weakly-transitive, one step-frame (W 0 , R0 )
with the characteriser (i01 , r10 , i02 , r20 ), where i01 + r10 > 0 and i02 + r20 > 0 is a
bounded morphic image of the finite, rooted, weakly-transitive, one step-frame
(W, R) with the characterisers (i1 , r1 , i2 , r2 ), where i1 + r1 > 0 and i2 + r2 > 0
iff the following hold:
r10 = 0 ⇒ (i1 , r1 ) = (i01 , r10 ),
r20 = 0 ⇒ (i2 , r2 ) = (i02 , r20 ),
i1 ≥ i01 ,
i2 ≥ i02 ,
2 × (r10 − r1 ) ≤ i1 − i01 ,
2 × (r20 − r2 ) ≤ i2 − i02 .
The operation minus is defined within the natural numbers i.e. n − m = 0 if
m > n.
Proof. The theorem follows from the previous theorem and the following obser-
vation:
• If (W 0 , R0 ) is a two floor frame i.e. i01 + r10 > 0 and i02 + r20 > 0
then (W, R) is also two floor frame. Assume not. Then there exist points
w, v ∈ W such that vRw and f (v) 6 R0 f (w) as f (v) is a second floor point while
f (w) is a first floor point.
150
• points from the second floor cannot be mapped to points on the
first floor. For the contradiction assume that the point f (w) is a first floor
point while w is a second floor point. This means that there exists v 0 ∈ W 0 such
that f (w)R0 v 0 and not v 0 R0 f (w). Then as f is a bounded morphism there exists
v ∈ W such that wRv and f (v) = v 0 . As w is a second floor point, wRv ⇔ vRw
and we get a contradiction as we have vRw while not f (v)R0 f (w).
• points from the first floor cannot be mapped to the points on the
second floor. For the contradiction assume that the point f (w) is a second floor
point while w is a first floor point. Now either there is another point w1 ∈ W
on the first floor with f (w1 ) also on the first floor or all points including w from
the first floor of W are mapped to the second floor of W 0 . In the first case wRw1
and not f (w)Rf (w1 ) so we get a contradiction. In the second case we get that f
is not surjective inasmuch as both frames were supposed to be two floor frames
so there is at least one point on the first floor in W 0 left with empty pre-image.
This is because by above observation second floor points cannot be mapped to
first floor points.
The converse direction is proved just by repetition of the case for one floor
frames for the other floor.
4 Connection with minimal topological spaces
In this section we show that that the modal logic wK4F is the modal logic of
minimal topological spaces. A topological space is minimal if it has only three
open sets. It is well known that there is a bijection between Alexandrof spaces
and weakly transitive, irreflexive Kripke frames. It is also well known that this
bijection preserves modal formulas. In this section we show that the special case
of this correspondence for minimal topological spaces gives one step, irreflexive
and weakly transitive relations as a counterpart. As a corollary it follows that
the logic wK4F is sound and complete w.r.t. the class of minimal topological
spaces.
Theorem 4.014 There is a one-to-one correspondence between the class of ir-
reflexive, weakly-transitive, finite, rooted, one-step Kripke frames and the class
of all finite minimal topological spaces.
Proof. Assume (W, R) is a finite, rooted, weakly transitive and one step rela-
tional structure and besides R is irreflexive. (Note that as the frame is irreflexive
its characteriser has the form (i1 , 0, i2 , 0), where i1 + i2 = |W |.) Let W1 be the
first floor and W2 the second floor of the frame, then the topology we construct
is {W, ∅, W2 }. It is immediate that the space (W, ΩR ), where ΩR = {W, ∅, W2 },
is a minimal topological space.
Let us show that the correspondence we described is injective. Take two
arbitrary distinct irreflexive, finite, rooted, weakly transitive frames (W, R) and
(W 0 , R0 ). As they are distinct, either W 6= W 0 or R 6= R0 . In the first case it is
immediate that (W, ΩR ) 6= (W 0 , ΩR0 ). In the second case as both R and R0 are
irreflexive the second floors are not the same, so W2 6= W20 and hence ΩR 6= ΩR0 .
151
For surjectivity take an arbitrary minimal topological space (W, Ω), where
Ω = {W, ∅, W0 } for some subset W0 ⊆ W . Take the frame (W, R), where R =
(W0 ×W0 −{(w, w)|w ∈ W0 })∪(−W0 ×−W0 −{(w, w)|w ∈ −W0 })∪{(w, w0 )|w ∈
−W0 , w0 ∈ W0 }. In words every two distinct points are related in W0 by R and
the same in the complement −W0 = W − W0 , besides every point from the −W0
is related to every point from W0 . what we get is the rooted two step relation
which is weakly transitive, with the second floor equal to W0 . As we didn’t allow
wRw for any point w ∈ W , the relation R is also irreflexive.
Now we will give the definition of a derived set (or set of accumulation points)
of a set in a topological space. This definition is needed to give the semantics of
modal formulas in arbitrary topological spaces.
Definition 4.015 Given a topological space (W, Ω) and a set A ⊆ W we will
say that w ∈ W is an accumulation point of A if for every neighborhood Uw of
w the following holds: Uw ∩ A − {w} 6= ∅. The set of all accumulation points of
A will be denoted by der(A) and will be called the derived set of A.
Derived sets serve to give the semantics of the diamond modality in an arbi-
trary topological space. Below we give the definition of satisfaction in a derived
set topological semantics of modal logic.
Definition 4.016 A topological model (W, Ω, V ) is a triple, where (W, Ω) is a
topological space and V : P rop → P (W ) is a valuation function. Satisfaction of
a modal formula in a topological model (W, Ω, V ) at a point w ∈ W is defined
by:
w p iff w ∈ V (p),
w ♦p iff w ∈ der(V (p)),
boolean cases are standard. Validity in a frame and class of frames of a formula
is defined in a standard way.
Fact 4.017 Let (W, R) be a finite, weakly transitive and irreflexive frame and
let (W, ΩR ) be its Allexandrof space. For every modal formula α the following
holds:
(W, R) α iff (W, ΩR ) α.
Note that here on the left hand side denotes the validity in Kripke frames while
on the right hand side it denotes the validity in topological frames in derived set
semantics.
Theorem 4.018 The modal logic wK4F is sound and complete with respect to
the class of all minimal topological spaces.
Proof. Proof. Soundness can be checked directly so we do not prove it here. For
completeness assume 0 φ. By theorem 2.26 there exists a finite, one-step, weak-
transitive frame (W, R) which falsifies φ. Assume that Ch(W, R) = (i1 , r1 , i2 , r2 ).
152
By theorems 3.011, 3.012 and 3.013 there exists a one-step, weak-transitive frame
(W 0 , R0 ) such that R0 is irreflexive and (W, R) is p-morphic image of (W 0 , R0 ).
For example such a frame could be (W 0 , R0 ) = Ch−1 (i1 + 2 × r1 , 0, i2 + 2 × r2 , 0).
The surjection immediately yelds that (W 0 , R0 ) 1 φ. Now the result immediately
follows from theorem 4.014, and the fact 4.017.
5 Conclusions
We have characterised the logic wK4F and established its relation to minimal
topological spaces. The logic is closely related to the model logic S4F that
has been shown to capture several important kinds of knowledge representation
systems and, in its non-monotonic version, can be viewed as a logic of minimal
knowledge. In future work we plan to study the non-monotonic version of wK4F
and its relation to S4F in more detail. It may also be interesting to consider
multi-model versions and their suitability for modeling common knowledge.
References
1. Fagin, R., Halpern J.Y., Moses Y., and Vardi M.Y. Reasoning about Knowledge.
Published by MIT Press, 1995.
2. Segerberg, K. An Essay in Classical Modal Logic. volume 13 of Filosofiska Studier.
Uppsala: Filosofiska Foreningen och Filosofiska Institutionen vid Uppsala Univer-
sitet.
3. Truszczynski, M. Embedding Default Logic into Modal Nonmonotonic Logics.
LPNMR 1991, 151-165.
4. Truszczynski, M.,Schwarz G. Minimal Knowledge Problem: A New Approach.
Artif. Intell. 67(1), 113-141, 1994.
5. Gelfond M., Lifschitz V. Classical Negation in Logic Programs and Disjunctive
Databases. New Generation Computing, vol. 9, 365-385, 1991.
6. Reiter R. A logic for default reasoning. Artificial Intelligence, 13:81-132, 1980.
7. M. Gelfond, V. Lifschitz, H. Przy-musinska, and M. Truszcynski. Disjunctive de-
faults. In Second International Conference on Principles of Knowledge Represen-
tation and Reasoning, KR ’91, Cambridge, MA, 1991.
8. Lin F., Shoham Y. Epistemic semantics for fixed-points nonmonotonic logics. In
Rohit Parikh, editor. Theoretical Aspects of Reasoning about Knowledge: Proc, of
the Third Conf, pages 111-120, 1990.
9. Lin F., Shoham Y. Epistemic semantics for fixed-points nonmonotonic logics. In
Rohit Parikh, editor. Theoretical Aspects of Reasoning about Knowledge: Proc, of
the Third Conf, pages 111-120, 1990.
10. Lifschitz V. Minimal Belief and Negation as Failure. Artificial Intelligence, vol.
70, 53-72, 1994.
11. Truszczynski, M. The Modal Logic S4F , the Default Logic, and the Logic Here-
and-There. In Proceedings of the 22nd National Conference on Artificial Intelli-
gence (AAAI 2007). AAAI Press, 2007.
12. Cabalar, P., and Lorenzo, D. New Insights on the Intuitionistic Interpretation of
Default Logic. In R. López de Mántaras and L. Saitta (eds), ECAI 2004, IOS Press
2004, 798–802.
13. Esakia, L. Weak transitivity - restitution. Logical Studies 2001, vol 8, 244-255.
153