Let L an algebraic language, and K an L-algebra
generated by a finite subset B⊂K. We shall say that
an L-algebra M satisfies (K,B)
In the category of L-algebras that satisfy (K,B),
B is a basis
of K (this f is necessarily unique
because K is generated by B).
This condition is equivalent to : for any equality between terms
found true in K where the list of free variables is B
(or whose interpretation is a bijection with B), M
also satisfies this equality written under universal quantifiers.
Indeed, the morphism f is defined by mapping any element of
K, value of any term with variables in B, into the
element of M defined by the same term; for this to be
coherent, 2 terms with the same value in K should also have
the same value in M.
Conversely, any formula made of universal quantifiers over an
equality of terms t=t', is equivalent to the
satisfaction of some (K,B), that is the quotient of
the algebra of all terms with the same variables, by the relation of
being obtainable from each other by replacements of occurrences of t
and t' as subterms.
Except if it is a statement of equality between 2 variables; to
avoid such exceptions we may need to modify our above definition by
seeing B not as a subset of K but as a family of
elements of K ; this essentially differs only when this
family is not injective, but the M satisfying such
conditions must be empty or singletons, which do not form a very
A module or representation of an abstract clone C,
is any C-algebra M satisfying all Cn,
and where the interpretation of all n-ary symbols (from Cn)
coincides with the expression of the satisfaction of Cn
Thus, these L-algebras are also K-algebras where K
is seen as a set of symbols with a common set B of arguments
(thus a common arity). The interpretation of K in an L-algebra
M satisfying (K,B) is characterized (we may say
"recursively defined") by the condition of the above f ,
namely (using similar notations to those of group action which are a
particular case): ∀u∈MB,
Between any two L-algebras M,N that satisfy
(K,B), any g∈MorL(M,N)
is also a K-morphism
because ∀k∈K, ∀u ∈MB,
- ∀b∈B, b ⋅ u = ub
- ∀s∈L, ∀x∈ Kns,
sK(x) ⋅ u = sM((xj
(f∈MorL(K,M) ∧ f|B=u
⇒ (g০f∈MorL(K,N) ∧ (g০f)|B=g০u
⇒ g(kM(u)) = kN(g০u)
Conversely, any s∈L with the
same arity (or even lower arity) has an image in K with the
same interpretation in this category.
Namely, any x∈ Bns,
gives it an image k = sK(x),
that is "replacing the variables of s by those from B
by the substitution x". Thus, for any L-algebra M
satisfying (K,B),∀u∈MB, kM(u)
If x is bijective then this substitution is inversible, so
that the interpretations of k and s are just copies
of each other.
If x is just injective, we can still redefine s from
k by mapping the missing variables, i.e. in (B
\ Im x),
either to those of s or to constants in L : this can
be done except if s was a constant and we are removing it as
well as all constant symbols from L, therefore admitting Ø
in the category, where no constant symbol can be interpreted.
So, in this category, the set K of operations "already
contains" any symbol from L with the same arity.
The class of all L-algebras satisfying any given family of
is called a variety.
If the family (Ki,Bi)i∈I
encompasses all arities (at least those present in L), then
we may as well forget L and reinterpret the L-algebras
in this variety, as L'-algebras where L'=⋃i∈I
Ki. However, two questions remain:
- Each Ki was only an L-algebra, not
necessarily satisfying (Kj,
Can we replace (Ki,Bi) by
some (K'i,B'i) where K'i
satisfies all (Kj,Bj), but
that remains equivalent as a predicate on the class of algebras
satisfying all (Kj,Bj) for j≠i
- Can two conditions (K,B) and (K',B')
with the same arity (B and B' are in bijection)
be fused into one ?
These questions will be positively answered below.
Some stability properties of varieties
We can easily verify that:
Any subalgebra of an L-algebra satisfying (K,B)
also satisfies (K,B) (because K is generated
Any product of L-algebras satisfying (K,B)
also satisfies (K,B).
Now comes the hard stuff:
Theorem. For any L-algebra A and any
variety V of L-algebras, the category of all (M,f)
where M is an L-algebra in V and f
∈MorL(A,M), has an initial object (A',φ), called the quotient of A by the
family of conditions defining the variety.
Let H be the set of all equivalence relations h
on A such that A/h is an L-algebra in V,
with the canonical projection ph∈MorL(A,A/h).
Now we can answer the previous questions.
Let φ =∏h∈H ph
and A' = Im φ ⊂ P =∏h∈H
A' satisfies all (Ki,Bi)i∈I
because it is a subalgebra of a product P of L-algebras
To verify that (A',φ) is an initial object in this
category, let (M,f) be another object. We need to
show that there is a unique morphism g from (A',φ) to (M,f), i.e. g∈MorL(A',M)
such that g০φ=f.
In the work on quotients (2.9) we saw the existence of a unique g
such that g০φ=f, written g=f/φ with domain Im φ = A', provided that
~φ ⊂~f . The
condition of uniqueness here is Im φ = A'. The existence
is obtained as g=j০πh, where h
= ~f , πh ∈MorL(A',A/h)
is the restriction of the canonical projection of P on its
factor A/h, and j = (f/h) ∈
g০φ = j০πh০φ = j০ph = f.
First, to replace (Ki,Bi) by
some (K'i,B'i) where K'i
satisfies all (Kj,Bj) : we just
need to take as K'i the quotient of Ki
by this family of conditions.
If the restriction of this quotient φ to Bi
was not injective, then only trivial algebras (empty or singletons)
would satisfy all conditions. Indeed:
If there is an L-algebra M with elements
x≠x' and satisfying all conditions then for all b≠b'
in B, ∃u∈MBi ,
f|B=u thus ∃g∈MorL(K'i,M),
g০φ=f, and φ(b)≠φ(b') because f(b)≠f(b').
Now assuming it injective, the arity is preserved; the verification
of equivalence of the conditions (Ki,Bi)
and (K'i,B'i) as predicates on
the class of algebras satisfying all (Kj,Bj)
for j≠i , is straightforward and left to the reader.
Now for fusing several conditions (K,B) and (K',B')
with the same arity into one: just take the quotient
of (K,B) by the condition (K',B'). For
the same reason as the previous question, any algebra satisfying
both will satisfy (K",B").
Any M satisfying (K",B") will satisfy
let us verify (K',B'), still assuming that we have a
bijection v from B" to B' :∀u ∈MB',
since M satisfies (K",B"), the map u০v
∈MB" is extensible as a morphism f
Since (K",B") satisfies (K',B'), the map
v-1 from B' to B" is extensible as
g∈MorL(K',K"). Thus f০g∈MorL(K',M)
is an extension of u.∎
In fact, when B and B' are in bijection, the
quotient of (K,B) by both conditions (K,B)
and (K',B') (plus any list of other conditions), is
isomorphic to the quotient of (K',B') by the same
Next : Polymorphisms