FOM: Trad.vers.Funct.Algebra # 3

[Walter Felscher]

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
associative law

   ( 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
then means

  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) .