FOM: Trad.vers.Funct.Algebra #2

[Walter Felscher]

Traditional versus Functorial Algebra  # 2


1.  Tools from traditional algebra

An algebra in the traditional sense is a set together with a
sequence V of operations, called its basic operations; the
signature S of the algebra then is the sequence of the
arities of these operations. In what follows, it often
suffices to restrict oneself to the set of U=im(V) of basic
operations, and most developments remain correct also for
infinitary operations where the aritites are cardinals.

Let T be a term algebra of signature S on countably many
generators. Pairs <t,t'> of terms are called equations, and
such equation holds in an algebra A if h(t)=h(t') for every
homomorphism h from T to A . A class _A of algebras is
called equational (or a variety) if there is a set M of
equations such that _A consists of all algebras in which the
equations from M hold.


1.1.  Equivalences

The phenomenon of the different descriptions of Boolean
algebras is a particular instance of an equivalence. Let _A
be a class of algebras of some signature with operations U ,
and let _A' be a second class of algebras of some possibly
different signature and with basic operations U'.

a. _A and _A' are called equationally (Malcev: rationally)
   equivalent: there is a bijection from _A onto _A' which
   preserves underlying sets and, for term algebras T and T'
   of the respective signatures, there is

   for every u in U a term t' which, if A' corresponds to A ,
   induces in A' the operation u of A ,

   for every u' in U' a term t which, if A corresponds to A',
   induces in A the operation u' of A' ;

   [observe that t' or t may have more variables than u or u'] .

b. _A and _A' are called functorially equivalent: there is a
   bijective functor G from the category of _A onto that of
   _A' which commutes with the underlying-set functors and
   preserves the hom-sets.

Equational equivalence implies functorial equivalence.
Conversely, functorial equivalence implies equational
equivalence, provided both _A and _A' contain functionally
free algebras in the sense of Tarski . (Recall that an
algebra A in a class _A is called functionally free if every
equation holding in A holds in all algebras of _A ; such
are, for instance, the free algebras on countably many
generators in _A .)


1.2.  Superposition

Let E be a set, let E^m be its m-th power with the projection
maps pr_(m,i) ; an m-ary operation on E shall be a function from
E^m to E . If g_0, ...  g_(n-1) are n m-ary operations on E
then their product [g_0, ... g_(n-1)] is the function from
E^m to E^n acting upon a in E^m as

      [g_0, ... g_(n-1)](a) = <g_0(a), ... g_(n-1)(a)>  ;

the name 'product' is justified since, making use of the
projection functions pr_(n,i) from E^n to E , the above becomes

      pr_(n,i)([g_0, ... g_(n-1)](a)) = g_i(a)  .

If h is a further function from E^n to E then the composition
(denoted by # ) of maps

      h # [g_0, ... g_(n-1)]

is a function from E^m to E , called the superposition of h
with g_0, ... g_(n-1); this name is justified since

      (h # [g_0, ... g_(n-1)]) (a)
         =  h ( [g_0, ... g_(n-1)](a) )
         =  h ( g_0(a), ... g_(n-1)(a) ) .

Assume now that E is the underlying set of an algebra A and
that f is a map from that algebra to another one, B , which
is homomorphic with respect to the operations h_A, g_A_0, ...
g_A_(n-1) and h_B, g_B_0, ... g_B_(n-1) . Then f is also
homomorphic with respect to their superposition:

    f( h_A # [g_A_0, ... g_A_(n-1)] (a))
        =  f( h_A ( g_A_0(a), ... g_A_(n-1)(a) ))
        =  h_B ( f (g_A_0(a)), ... f (g_A_(n-1)(a)) )
        =  h_B ( g_B_0 (f#a), ... g_B_(n-1) (f#a) )
        =  (h_B # [g_B_0, ... g_B_(n-1)]) (f#a)   .


1.3.  The algebras P(D,m) and H(D,m)

Let D be an algebra of signature S with underlying set E ;
let P(D,m) be the power of D with exponent E^m .  By the
traditional definition of powers of algebras, if u_D is a
basic operation of D then the corresponding basic operation
u_P_m of P(D,m) acts as

(%)   u_P_m ( l_0, ... l_(n-1)) = u_D # [l_0, ... l_(n-1)]  .

Let H(D,m) be the subalgebra of P(D,m) generated by the
m-ary projection maps pr_(m,i). If d is in E^m then let p_d
be the projection (or evaluation) homomorphism at d from
P(D,m) to D ; p_d maps the elements l of P(D,m), being m-ary
operations on E, to their evaluations l(d). Restricted to
H(D,m), p_d remains a homomorphism.

It follows from 1.2. that homomorphisms of D are also
homomorphic for the operations in H(D,m).


1.4.  H(D,m)  and the equations Q(D,m)

Let D be as above, and let T_m be a term algebra of
signature S on the generators x_0 ,...x_(m-1).  I shall
construct a homomorphism q_m from T_m onto H(D,M) such that
the set Q(D,m) of T_m - equations holding in D is the
congruence relation induced by q_m on T_m .

Every homomorphism h from T_m to D is uniquely determined by
its value d_i for x_i ; if d is in E^m then let h_d be the
homomorphism determined by this sequence of values.

Let q_m be the homomorphism from T_m onto H(D,m) sending
x_i into the projection map pr_(m,i) from E^m to E ; so q_m
maps terms t from T_m to m-ary operations t_D on E . For d
in E^m the homomomorphism h_d is the composition p_d # q_m

  of q_m from T_m to H(D,m)
          followed by the evaluation p_d from H(D,m) to D

since x_i under this map goes first into pr_(m,i) and then
into d_i . Now if operations l, l' in H(D,m) are distinct
then l(d), l'(d) are distinct for at least one d in E^m.
Hence if t, t' are terms such that for every d in E^m

  h_d(t) = h_d(t') , i.e.  p_d (q_m(t)) = p_d (q_m(t'))

then q_m(t)=q_m(t') . Consequently, the equation <t,t'> holds in
D if, and only if, q_m(t)=q_m(t') .


1.5.  Clones

A clone on a set E shall be a subset of the union of all
m-ary operations E , m = 0,1,2,... , which contains all
projections pr_(m,i) , is closed under superposition, and
which contains a 0-ary operation provided it contains its
m-ary extension to a constant operation.

For a set U of finitary operations on E , the clone CL(E,U)
generated by U shall be the smallest clone on E containing U.

In view of 1.2.  , I also obtain the members of CL(E,U) as
the E-valued maps in

   the smallest set B(E,U) of maps containing U and all
   projections, and closed under composition and the
   formation of product functions.

In other words, they are the morphisms ending in E^1 of the

   category B(E,U) with objects E^0, E^1, ...  , in which
   E^m is the m-th power of E^1 with projections pr_(m,i),
   and which is the smallest such category containg U .