FOM: Trad.vers.Funct.Algebra # 3
walter.felscher at uni-tuebingen.de
Fri Mar 20 09:36:18 EST 1998
Traditional versus Functorial Algebra # 3
2. From B-algebras to equational classes
2.1. Diagrams B and their algebras B(m)
Recall that a diagram B is a category with objects b_0, b_1, ... ,
in which b_m is the m-th power of b_1 with projections
p_(m,i). As B[m,1] I denote the set of all morphisms from
b_m to b_1 , as B[;1] the union of all B[m,1]. Recall that
a B-algebra is a product-preserving functor F from B into
the category of sets; the image of b_1 under F being called
the set underlying F .
Let B be a diagram and let U be a set of morphisms in B[;1] ,
and assume that U generates B in the sense that B is its
smallest subdiagram containing U . Then every morphism in B
arises, from the projections and the members u of U , under
repeated composition and formation of product maps. The
( f # [g_0, ... g_(n-1)] ) # [h_0, ... h_(m-1)]
= f # [g_0 # [h_0, ... h_(m-1)] , ... g_(n-1) # [h_0, ... h_(m-1)] ]
holds as follows from the definition of product maps. Hence
every morphism in B[m,1], which is not a projection, arises
from the projections p_(m,i) under repeated formation of
(*) u # [k_0, ... k_(n-1)] , u in U
from morphisms k_i in B[m,1] already obtained this way.
Arranging the set U into a sequence, I obtain a corresponding
sequence S of arities. In particular, (*) shows that
the set B[m,1] can be made into an algebra H(m) of signature
S which is generated by the p_(m,i).
2.2. The class C_B of algebras determined by a diagram B
Let F be a B-algebra, E its underlying set. If u in U
starts from e_n , then F(u) is an n-ary operation, and I
obtain an algebra C = C_F of signature S on E with the F(u)
as basic operations. Let _C(B) be the class of algebras C_F
arising from B-algebras F this way.
Further, if F and E are as above then the functor F
preserves the identity (*). Thus F restricted to B[m,1] is a
map f from H(m) to P(D,m) with f (p_(m,i)) = pr_(m,i) and
f ( u # [k_0, ... k_(n-1)] )
= F ( u # [k_0, ... k_(n-1)] )
= F(u) # [F(k_0), ... F(k_(n-1))]
= F(u) # [f(k_0), ... f(k_(n-1))]
Since F(u) is the basic operation u_C of C , this is
u_C # [f(k_0), ... f(k_(n-1))] ,
and by 1.3.(%) this is
u_P ( f(k_0), ... f(k_(n-1))
with the basic operation u_P of P(C,m). Hence the map f
is a homomorphism f_C_m from H(m) onto H(C,m) .
2.3 C_B is equational
Let now T be a term algebra of signature S on the generators
x_0, ... , and let T_m be its subalgebra generated by the
first m of the x_i . Let Q(B,m) be the set of T_m - equations
identified by the homomorphism r_m from T_m to H(m) defined
as sending x_i to p_(m,i); let Q(B) be the union of the
Q(B,m). I shall show that _C(B) is the equational class
defined by Q(B).
So let C=C_F arise from F and E . Now the composition f_C_m # r_m
of r_m from T_m to H(m) followed by f_C_m from H(m) to H(C,m)
is the homomorphism q_m from T_m to H(C,m) since both maps
coincide on the generators x_i . Thus the equations
identified by r are also identified by q_m ; hence the
equations from Q(B,m) hold in C .
Conversely, let D be an algebra in which the equations
Q(B,m) hold. Thus the congruence relation Q(B,m) induced by
r_m is contained in the congruence relation induced by q_m ,
and there are homomorphisms f_m from H(m) to H(D,m) such
that f_m # r_m = q_m ; in particular
f_m ( p_(m,i)) = f_m ( r_m( x_i)) = q_m (x_i) = pr_(m,i) .
With E the set underlying D , I define the map F from B
into sets by
F(b_m) = E^m , F(a) = f_m(a) if a is in B[m,1]
and if a = [a_0, ... a_(n-1)] is in B[m,n] with a_i in B[m,1]
then I define
F(a) = [ f_m (a_0), ... f_m (a_(n-1)) ] .
If the basic operation u is n-ary, hence u in H(n), then
u = u # [p_(n,0), ... p(n,n-1)] = u_H_n (p_(n,0), ... p(,n,n-1) )
implies f_n (u) = u_P_n (pr_(n,0), ... pr_(n,n-1)) for the
basic operation u_P_n of H(D,n) defined in 1.3. ; hence
f_n (u) = u_D for the basic operation u_D of D .
So in order to see that D is the algebra C_F , it remains to
be shown that F is actually a functor.
Recall the definition (*) of the basic operation u_H_m of
H(m); that f_m is homomorphic with respect to u_H_M and u_P_M
f_m ( u # [k_0, ... k_(n-1)] )
= f_m ( u_H_m (k_0, ... k_(n-1)) )
= u_P_m (f_m(k_0), ... f_m(k_(n-1)) )
= f_m (u) # [f_m(k_0), ... f_m(k_(n-1)) ] .
Now a computation at the end of 1.2. did show that a homomorphism
with respect to basic operations is also homomorpic with respect
to all their superpositions, and in 2.1 it was shown that
every morphism c in B(m) is such superposition of the form (*).
Working with the operations induced by c in B(m) and H(D,m),
I therefore obtain analogously
f_m ( c # [k_0, ... k_(n-1)] )
= f_m (c) # [f_m(k_0), ... f_m(k_(n-1)) ] .
Now if a is in B[m,n] and a' is in B[n,k] then a'# a in B[m,k] is
(&) a'# a = [(p_(k,0) # a') # a , ... (p_(k,k-1) # a') # a ] , hence
F (a'# a) = [ F((p_(k,0) # a') # a) , ... F((p_(k,k-1) # a') # a) ]
= [ F((p_(k,0) # a')) # F(a) , ... F((p_(k,k-1) # a')) # F(a) ]
= [ (F(p_(k,0)) # F(a')) # F(a) , ... (F(p_(k,k-1)) # F(a')) # F(a) ]
In analogy with (&), F(a') # F(a) is
[(pr_(k,0) # F(a')) # F(a) , ... (pr_(k,k-1) # F(a')) # F(a) ] ,
and so F(p_(k,i)) = pr_(k,i) implies F(a'# a) = F(a') # F(a) .
More information about the FOM