Database Reference
In-Depth Information
subalgebra
of
A
if
W
⊆
W
, the nullary operators are equal, and the other operators
of
A
are the restrictions of operators of
A
to
W
.
A
subuniverse
of
A
is a subset
W
of
W
which is closed under the operators of
A
, i.e., for any
n
-ary operation
W
.
Thus, if
A
is a subalgebra of
A
, then
W
is a subuniverse of
A
. The empty set may
be a subuniverse, but it is not the underlying carrier set of any subalgebra. If
A
has
nullary operators (constants) then every subuniverse contains them as well.
Given an algebra
A
,
Sub(
A
)
denotes the set of subuniverses of
A
, which is an
algebraic lattice. For
Y
W
,
o
i
∈
Σ
A
and
a
1
,...,a
n
∈
o
i
(a
1
,...,a
n
)
∈
⊆
W
we say that
Y generates
A
(or
Y
is a set of generators
{
of
A
)if
W
=
Sg(Y)
Z
|
Y
⊆
Z
and
Z
is a subuniverse of
A
}
.
Sg
is an alge-
braic closure operator on
W
: for any
Y
⊆
W
,let
F(Y)
=
Y
∪{
o
i
(b
1
,...,b
k
)
|
o
i
∈
, with
F
0
(Y)
Y
,
F
n
+
1
(Y)
F(F
n
(Y)),n
Σ
A
and
b
1
,...,b
k
∈
Y
}
=
=
≥
0, so that for
F
2
(Y)
a finitary
A
,
Y
⊆
F(Y)
⊆
⊆···
, and, consequently,
Sg(Y)
=
Y
∪
F(Y)
∪
F
2
(Y)
F
n
(Y)
for some
∪···
, and from this it follows that if
a
∈
Sg(Y)
then
a
∈
F
n
(Z)
, thus
a
n<ω
; hence for some
finite Z
⊆
Y
,
a
∈
∈
Sg(Z)
, i.e.,
Sg
is an alge-
braic closure operator.
The algebra
A
is
finitely generated
if it has a finite set of generators.
Let
X
be a set of variables. We denote by
X
the set of terms with variables
x
1
,x
2
,...
in
X
of a type
Σ
of algebras, defined recursively by:
•
T
All variables and constants (nullary functional symbols) are in
T
X
;
•
If
o
i
∈
Σ
,
n
=
ar(o
i
)
≥
1, and
t
1
,...,t
n
∈
T
X
then
o
i
(t
1
,...,t
n
)
∈
T
X
.
If
X
denotes the set of ground terms. Given a class
K
of alge-
bras of the same type (signature
Σ
), the term algebra
(
=∅
, then
T
∅
X, Σ)
is a free algebra
with the universal (initial algebra) property: for every algebra
A
T
=
(W,Σ)
∈
K
and map
f
W
that ex-
tends
f
to all terms (more in Sect.
5.1.1
). Given a term
t(x
1
,...,x
n
)
over
X
and
given an algebra
A
:
X
→
W
, there is a unique homomorphism
f
#
:
T
X
→
(W,Σ
A
)
of type
Σ
, we define a mapping
t
W
n
=
:
→
W
by: (i) if
t
is a variable
x
i
then
t(a
1
,...,a
n
)
a
i
is the
i
th projection map;
(ii) if
t
is of the form
o
i
(t
1
(x
1
,...,x
n
),...,t
k
(x
1
,...,x
n
))
, where
o
i
∈
=
Σ
, then
t(a
1
,...,a
n
)
o
i
(t
1
(a
1
,...,a
n
),...,t
k
(a
1
,...,a
n
))
. Thus,
t
is the
term function
on
A
corresponding to term
t
. For any subset
Y
=
W
,
Sg(Y)
=
t(a
1
,...,a
n
)
|
t
is
n
-ary term of type
Σ,n < ω,
and
a
1
,...,a
n
∈
Y
.
⊆
The product of two algebras of the same type
A
and
A
is the algebra
A
A
=
×
(W
×
W
,Σ
×
)
such that for any
n
-ary operator
o
i,
2
∈
Σ
×
and
(a
1
,b
1
),...,(a
n
,b
n
)
∈
o
i
(a
1
,...,a
n
), o
i
(b
1
,...,b
n
))
.In
what follows, if there is no ambiguity, we will write
o
i
(a
1
,...,a
n
)
for
W
,
n
W
×
≥
1,
o
i,
2
((a
1
,b
1
),...,(a
n
,b
n
))
=
(
o
i
(a
1
,...,a
n
)
as well, and
Σ
for
Σ
A
of any algebra
A
of this type
Σ
.
Given a
Σ
-algebra
A
with the carrier
W
, we say that an equivalence relation
Q
on
W
agrees with the
n
-ary operation
o
i
∈
Σ
if for
n
-tuples
(a
1
,...,a
n
),(b
1
,...,b
n
)
∈
W
n
=
1
,...,n
. We say that an equivalence relation
Q
on a
Σ
-algebra
A
is a
congruence
on
A
if it agrees with every operation in
Σ
.If
A
is a
Σ
-algebra and
Q
a congru-
ence on
A
then there exists a unique
Σ
-algebra on the quotient set
W/Q
of the
we have
(o
i
(a
1
,...,a
n
),o
i
(b
1
,...,b
n
))
∈
Q
whenever
(a
i
,b
i
)
∈
Q
for
i
