Database Reference
In-Depth Information
Thus, the closure operator
T
is algebraic for all objects in
DB
and, consequently, the
complete lattice
L
DB
=
,
⊕
⊗
(Ob
DB
,
,
)
is algebraic. Thus, the PO subcategory
DB
I
=
L
DB
(from Theorem
6
in Sect.
3.2.5
) is algebraic as well.
The algebraic property is very useful in order to demonstrate the properties of the
DB
category: in order to demonstrate the theorems in general, we need to extend the
inductive process of a proof beyond
ω
steps to the transfinite.
Zorn's lemma
(equivalent to the Axiom of Choice of the set theory) allows us to
do this. The database lattice
L
DB
=
,
⊕
(Ob
DB
,
,
⊗
)
is a (nonempty) poset with
⊆
the property that every chain
K
Ob
DB
(i.e., linearly ordered subset) has an upper
bound
K
=
K
(because this poset is
algebraic
)in
Ob
DB
. Hence, we can apply
Zorn's lemma which asserts that
L
DB
has a maximal element.
,
⊕
Remark
From the fact that
DB
I
=
L
DB
=
(Ob
DB
,
,
⊗
)
is an algebraic lattice,
=
{
we obtain for the total object
Υ
, i.e., it is the union of
all closed objects generated by only
finite
objects of
DB
and hence the union of all
compact
elements of
(
=
TΥ
TA
|
A
⊆
ω
Υ
}
C
,
⊆
)
.
Let
ω
be the category of natural numbers with the arrows
≤:
j
−→
k
correspond-
ing to the total order relation
j
≤
k
, i.e.,
ω
={
0
→
1
→
2
→···}
. An endofunctor
H
:
C
−→
D
is
ω
-
cocontinuous
if it preserves the colimits of functors
J
:
ω
−→
C
,
that is, when
H ColimJ
ColimHJ
(the categories
C
and
D
are thus supposed to
have these colimits).
Notice that a functor
J
:
ω
−→
C
is a diagram in
C
of the form
{
C
0
→
C
1
→
C
2
→···}
.For
ω
-cocontinuous endofunctors the construction of the
initial algebra
is inductive [
24
].
Proposition 53
For each simple object A in the category
DB
,
the “merging with
A” endofunctor Σ
A
=
A
⊕
_
:
DB
−→
DB
is ω-cocontinuous
.
Proof
Let us consider any chain in
DB
(all arrows are monomorphisms (i.e., “
”)
in a corresponding chain of the
Ob
DB
,
algebraic lattice), that is a diagram
D
,
0
Σ
A
⊥
0
1
Σ
A
⊥
0
2
···
0
Σ
A
,
⊥
0
0
0
where
⊥
={⊥}
(with the empty relation
⊥∈
A
, so that
Σ
A
⊥
=
A
⊕⊥
=
0
)
1
T(A
∪⊥
=
TA
) is the initial object in
DB
, with unique monic arrow
⊥
=
0
:
0
)
with
⊥
0
0
Σ
A
⊥
(Σ
A
⊥
1
1
0
)
⊥
→
(Σ
A
⊥
=⊥
and the consecutive arrows
n
=
:
Σ
A
⊥
(Σ
n
+
1
A
0
)
with
1
→
⊥
=
TA
, for all
n
≥
1, as representation of a functor
:
−→
J
ω
DB
. The endofunctor
Σ
A
preserves colimits because it is monotone
and
Σ
A
=
TA
is its fixed point, i.e.,
Σ
A
=
Σ
A
)
TA
=
T(A
∪
TA)
=
T(A
∪
=
Σ
A
(Σ
A
)
. Thus, the colimit
ColimJ
=
Σ
A
of the base diagram
D
, given by the
=
TA
. Thus
AColimJ
=
_
)
ω
0
functor
J
:
ω
−→
DB
, is equal to
ColimJ
=
(A
⊕
⊥
T(A
∪
ColimJ)
=
T(A
∪
TA)
=
T(TA)
=
TA
=
ColimΣ
A
J
(where
ColimΣ
A
J
is
a colimit of the diagram
Σ
A
D
).
