Information Technology Reference
In-Depth Information
M
M
satisfy (
n
)and(
b
). Below we just show the claim
We claim that
and
M
M
is similar.
for model
; the proof for the case
N
(
t
).
For (
b
): As
N
(
t
) consists of all subsets of the domain, it is clear that (
b
)holds
for
N
(
t
). As for
N
(
s
), if
s
For (
n
): It is clear that
S
∈
N
(
s
)and
S
∈
∈
X
,then
X
must be either
{
s
}
or
{
s, t
}
.Then
S
\
X
must be either
{
t
}
or
∅
, respectively. But
∅
,
{
t
}∈
N
(
s
), so
{
u
∈M|
S
\
X/
∈
N
(
u
)
N
(
s
).
We continue by demonstrating the expressivity result. Notice that
}
=
∅∈
{
s
}
∈
/
N
(
s
)
s
,t
}∈
N
(
s
). Similar to the proof of Prop. 2, we show that
s
and
{
p
but
s
M
,s
) are distinguished by an
ML
-formula
p
.
Moreover, also similar to the proof of Prop. 2, we can show that: for all
p
. Therefore (
M
,s
)and(
M
,s
M
,s
) cannot be
˕
∈
CL
,
M
,s
˕
iff
˕
. Therefore (
M
,s
)and(
distinguished by a
CL
-formula.
Proposition 4.
CL
is less expressive than
ML
on the class of models satisfying
(4)
or
(5)
.
M
=
S
,N
,V
Proof.
Consider the following models
M
=
S, N, V
and
:
-
S
=
{s, t}
,
S
=
{s
,t
}
-
N
(
s
)=
,
N
(
s
)=
s
}
s
,t
}}
,
N
(
t
)=
{∅
,
{
s
}
,
{
s, t
}}
,
N
(
t
)=
{{
t
}}
{{
,
{
t
}
∅}
-
V
(
p
)=
{{
,
,
V
(
p
)=
∅
∅
s
,t
}{
s
}
t
}∅
∅{
s, t
}{
s
}{
t
}
{
{
s
:
¬
p
t
:
¬
p
s
:
¬
p
t
:
¬
p
M
M
Based on the three observations below, we obtain the statement.
M
satisfy (4) and (5). Below we just show the claim for model
-
M
and
M
;
M
is similar.
the proof for the case
•
For (4): suppose that
X
∈
N
(
s
). Then
X
=
∅
or
X
=
{
s
}
or
X
=
{
s, t
}
.
Observe that
{
u
|
X
∈
N
(
u
)
}
=
{
s
}∈
N
(
s
). Similarly, we can show that
(4) applies to
N
(
t
).
•
For (5): suppose that
X/
∈
N
(
s
). Then
X
=
{
t
}
{
u
|
X/
∈
.Observethat
N
(
u
)
}
=
{
s
}∈
N
(
s
). Similarly, we can show that (5) applies to
N
(
t
).
M
,s
) are distinguished by an
ML
-formula
p
:since
p
M
=
-
(
M
,s
)and(
p
;since
p
M
=
N
(
s
), we get
M
,s
∅∈
N
(
s
), we have
M
,s
∅
∈
/
p
.
p
can distinguish (
M
,s
)and(
M
,s
).
Therefore
M
,s
) cannot be distinguished by any
CL
-formulas. That is, for
-
(
M
,s
)and(
M
,s
all
˕
∈
CL
,
M
,s
˕
iff
˕
. The proof is similar to the corresponding
part of Prop. 2.
