Varieties

This page is a draft (gathering pieces of previously written texts, to be reworked later)

Varieties

Take an algebraic language L, an L-equational system (K,b), and an L-algebra E. In the category of L-systems, the condition for E to be a b-module comes down to the surjectivity of Hom(b, E), since its injectivity is ensured. This is equivalent to the existence of an operation ⋅ : K × E^V → E such that ⋅⃖ = Hom(b, E)^-1.
Denoting ∀u∈E^V, h_u = ⋅⃖(u), this contains 2 conditions :

∀u∈E^V, h_u⚬b = u ∧ h_u∈Mor(K,E).

More explicitly,

∀x∈V, ∀u∈E^V, b(x) ⋅ u = u_x
∀u∈E^V, ∀(t,k)∈K, k ⋅ u = φ_E(^Lh_u(t))

1. can also be written ∀x∈V, ⋅⃗(b(x)) = π_x : E^V → E.

A class C of L-algebras is called a variety if there is a set of L-equational systems such that C is the class of all L-algebras which are modules for all equational systems in this set.

For any variety C, any product of algebras in C is also in C.
Any subalgebra F of an algebra E in C, is also in C. Indeed for any L-equational system (K,b), if E is a b-module then ∀u∈F^V,

(h_u ∈ Mor_L(K,E) ∧ F∈Sub_LE) ∴ h_u*(F) ∈ Sub_L K.
h_u[Im b] = Im h_u⚬b = Im u ⊂ F
〈Im b〉_L = K
∴ Im h_u ⊂ F.

Any set of L-equational systems can be packed into one, so that any variety is the set of all L-algebras which are modules for a fixed one. This can be seen by presenting these equational systems by copies forming a family (K_i,b_i) such that

b_i = Id_{V_i} : V_i ↪ V
V_i = V ⋂ K_i
∀i≠j, K_i ⋂ K_j ⊂ V
V = ⋃_i V_i

Then, defining K = ⋃_i K_i with K = ⋃_i K_i fits. The above mentioned defect about different arities with unused variables disappears, even if generalized to the use of multiple types. Actually the list of types interpreted as nonempty in all members of a variety of typed L-algebras, cannot differ from that in the class of all typed L-algebras.

Other definition

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∈ℕ L_n, and being identifiable with the variety of this clone; L may differ from it, but generates it in the sense that each L-algebra L_n 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 e_i,n):

∀n∈ℕ, 〈1_n〉_L = L_n.

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) if, equivalently,

∀u ∈M^B, ∃f∈Mor_L(K,M), f_|B=u
∃f∈Mor_L(K,M^{M^B}),∀b ∈B, f(b)=π_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 C_n, with the interpretation of symbols from C_n coincides with the expression of this satisfaction.

The condition defined by an equational system 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 interesting category).

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∈M^B,

∀b∈B, b ⋅ u = u_b
∀s∈L, ∀x∈ K^n_s, s_K(x) ⋅ u = s_M((x_j ⋅ u)_{j<n_s})

Between any two L-algebras M,N that satisfy (K,B), any g∈Mor_L(M,N) is also a K-morphism because ∀k∈K, ∀u ∈M^B,
(f∈Mor_L(K,M) ∧ f_|B=u ∧ k_M(u)=f(k))
⇒ (g০f∈Mor_L(K,N) ∧ (g০f)_|B=g০u ∧ g(k_M(u)))=(g০f)(k))
⇒ g(k_M(u)) = k_N(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∈ B^n_s, gives it an image k = s_K(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∈M^B, k_M(u) = s_M(u০x).
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 conditions (K_i,B_i)_i∈I is called a variety.

If the family (K_i,B_i)_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 (⋃_i∈I K_i)-algebras. However, two questions remain:

Each K_i was only an L-algebra, not necessarily satisfying (K_j, B_j). Can we replace (K_i,B_i) by some (K'_i,B'_i) where K'_i satisfies all (K_j,B_j), but that remains equivalent as a predicate on the class of algebras satisfying all (K_j,B_j) 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 by B).
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 ∈Mor_L(A,M), has an initial object (A',φ), called the quotient of A by the family of conditions defining the variety.

Proof.

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 p_h∈Mor_L(A,A/h).
Let φ =∏_h_∈_H p_h and A' = Im φ ⊂ P =∏_h_∈_H A/h.
A' satisfies all (K_i,B_i)_i∈I because it is a subalgebra of a product P of L-algebras that do.
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∈Mor_L(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 ∈Mor_L(A',A/h) is the restriction of the canonical projection of P on its factor A/h, and j = (f/h) ∈ Mor_L(A/h,M). Indeed,
g০φ = j০π_h০φ = j০p_h = f. ∎

Now we can answer the previous questions.
First, to replace (K_i,B_i) by some (K'_i,B'_i) where K'_i satisfies all (K_j,B_j) : we just need to take as K'_i the quotient of K_i by this family of conditions.
If the restriction of this quotient φ to B_i 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∈M^B_i , u(b)=x≠u(b')=x' and ∃f∈Mor_L(K_i,M), f_|B=u thus ∃g∈Mor_L(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 (K_i,B_i) and (K'_i,B'_i) as predicates on the class of algebras satisfying all (K_j,B_j) 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 (K",B") 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 (K,B); let us verify (K',B'), still assuming that we have a bijection v from B" to B' :∀u ∈M^B', since M satisfies (K",B"), the map u০v ∈M^B" is extensible as a morphism f ∈ Mor_L(K",M). Since (K",B") satisfies (K',B'), the map v^-1 from B' to B" is extensible as g∈Mor_L(K',K"). Thus f০g∈Mor_L(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 conditions.

Next : Polymorphisms and invariants