FOM: Trad.vers.Funct.Algebra #2
Walter Felscher
walter.felscher at uni-tuebingen.de
Fri Mar 20 09:34:56 EST 1998
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 .
More information about the FOM
mailing list