Generalizing the context of our first definition, a variety
is a category made of all L-algebras satisfying conditions eventually expressible
like this one of being modules, but without assuming L to be a clone: the objects (or other sets) with basis
that L is made of, need not be one per arity; they need not belong to the given category
(but are seen as additional objects to this category for making sense of the basis), and even
need not be algebras (as happened with terms with respect to algebras). Instead, with a simple algebraic language L, conditions may be
expressed by a list of axioms made of ∀ over equalities of L-terms.
As will be shown, such categories are still qualified as varieties in the sense of
having a clone ∐n∈ℕ Ln, and being
identifiable with the variety of this clone; L may differ from it, but generates it in
the sense that each L-algebra Ln is L-generated by
(the image of) its basis, i.e. is the set of all symbols definable by n-ary L-terms
(where the role of the symbols of variable is played by the symbols
∀n∈ℕ, 〈1n〉L = Ln.
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).
The axioms of module of abstract clones,
say that this algebra satisfies all Cn, with the interpretation of symbols from
Cn coincides with the expression of this satisfaction.
The satisfaction 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
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