Database Reference
In-Depth Information
in
dom
, with
U
=
dom
∪
SK
) and hence we obtain analogous (dual) case to the
previous one.
Let us show that the
weak
excluded middle holds for
TA
∈
Ob
DB
sk
for which
instead the excluded middle does not hold:
Example 48
Let us consider a continuation of Example
47
where
A
=
can(
I
,D)
has two infinite binary relations
R
1
and
R
2
:
R
1
=
r
can(
I
,
D
)
R
2
=
s
can(
I
,
D
)
a,b
b,ω
0
b,ω
1
ω
1
,ω
2
ω
1
,ω
3
ω
3
,ω
4
ω
3
,ω
5
ω
5
,ω
6
...
...
Let us consider a unary but infinite relation
=
0
,
1
,...
=
,...
∈
R
ω
4
i
|
i
=
ω
0
,
ω
4
,
ω
8
Υ
,
⊕¬
∪¬
so that
R/
∈
TA
, and
R/
∈
TA
TA
=
T(TA
TA)
(the excluded middle does
not hold).
Let us show that, instead, the weak excluded middle is valid, so that
∈¬
⊕¬¬
T(
¬
∪¬¬
=
R
TA
TA
TA
TA).
Hence,
¬
TA
is a finite database with all finite relations with values in the finite set
dom
. However,
¬¬
TA
=
T(
{
TB
∈
Ob
DB
sk
|
TB
∩¬
TA
=⊥}
)
.Solet
\{
a,b
}
∩¬
0
us consider a database
TB
=
T(
{
R,
⊥}
)
∈
Ob
DB
sk
that satisfies
TB
TA
=⊥
and
R
∈
B
⊆
TB
, and hence
T
∩¬
=¬¬
R
∈
{
TB
∈
Ob
DB
sk
|
TB
TA
=⊥}
TA
(
¬
∪¬¬
T(
¬
∪¬¬
⊆
⊆
TA
TA)
TA
TA).
Consequently,
R
∈
T(
¬
TA
∪¬¬
TA)
=¬
TA
⊕¬¬
TA
=
Υ
.
It is well known that the logic of weak excluded middle is a strict intermediate
logic
KC
(called Jankov's or De Morgan logic as well).
It is (by Jankov's Theorem [
9
]) the strongest intermediate logic extending
IPC
that proves the same negation-free formulae as
IPC
and can be embedded into S4.2
modal logic where the accessibility relation
R
⊆
W
2
(a partial order) of the frame
is reflexive, transitive and
directed
(convergent) as well. That is, if
(a,b)
∈
R
and
∈
∈
∈
(a,c)
R
then there exists a
d
W
such that
(b,d),(c,d)
R
.
