Abstract clones

Clones

Putting all arities together gives an algebraic language called the clone of C:

L = ∐_n∈ℕ L_n

where each set L_n of n-ary symbols is an object of C with a chosen basis of n elements 1_n = (e_i,n)_i<n ∈ L_nⁿ. Thus, ∀n∈ℕ, L_n = ^C∐_i<n L₁.

Depending on C, a clone may exist or not, but it is essentially unique, serving as the maximal algebraic language for objects of C.

Each object E of C, gets the L-algebra structure φ_E = ∐_n∈ℕ φ_E⁽ⁿ⁾, where φ_E⁽ⁿ⁾ : L_n × Eⁿ → E is defined taking as ⃖φ_E⁽ⁿ⁾ the inverse of Mor(L_n,E) ∋ f ↦ f⚬1_n which is bijective to Eⁿ because 1_n is a basis in C. This definition is expressible by both axioms which extend to clones those defining the action of an egg in a category:

Each e_i,n acts as the i-th projection from Eⁿ to E, i.e. ∀i<n, ∀u∈Eⁿ, e_i,n ⋅ u = u_i.
∀n∈ℕ, ⃖φ_E⁽ⁿ⁾ : Eⁿ → Mor(L_n,E).

This implies (for all objects E, F),

Mor(E,F) ⊂ Mor_L(E,F)
∀n∈ℕ, Mor(L_n,E) = Mor_L(L_n,E).

Let us recall the proof of Mor_L(L_n,E) ⊂ Mor(L_n,E) previously seen for n=1. From 1_n being a basis of L_n and Id_{L_n} ∈ Mor(L_n,L_n), comes

∀x∈L_n, x = x⋅1_n

Thus ∀f∈Mor_L(L_n,E), (∀x∈L_n, f(x) = f(x⋅1_n) = x⋅ (f⚬1_n) ∴ f = ⃖φ_E⁽ⁿ⁾(f⚬1_n) ∈ Mor(L_n,E).∎

3. implies that 1_n generates L_n in the sense that 〈1_n〉_{L_n} = L_n ∴ 〈1_n〉_L = L_n.

Abstract clones and varieties

A clone L may be conceived independently of C (like monoids are independent of their actions), as the small concrete category made of the sequence of objects (L_n)_n∈ℕ, called an abstract clone. It defines on L a structure of typed algebra with types L_n and operations

Constant symbols e_i,n
An L-algebra structure on each L_n, that is a sequence of operations we shall abusively denote the same • : L_p × L_n^p → C_n for each p∈ℕ.

Generalizing the concept of action to such a typed algebra, an L-module (or representation of L), is an L-algebra M satisfying the above 1. and 2. where 2. uses Mor_L :

∀n,p∈ℕ, ∀s∈L_p, ∀x∈L_n^p, ∀u∈Mⁿ, (s•x) ⋅ u = s ⋅ ((x_i ⋅ u)_i<p)

The variety of L is the category of all L-modules with Mor = Mor_L.
A typed algebra L = ∐_n∈ℕ L_n with such symbols, is an abstract clone if each L_n satisfies the above axioms 1., 2. and 3. extending to L the axioms of monoid for L₁:

1. and 2. make L_n an L-module.
As 3. was seen to imply ∀M, ∀f∈Mor_L(L_n,M), f = ⃖φ_M⁽ⁿ⁾(f⚬1_n), it completes making 1_n a basis of L_n, equivalently in the small category L with its L-morphisms or in its whole variety.

As will be seen later, the general concept of variety will use algebraic languages that do not need to be abstract clones, and not even typed algebras. Roughly speaking, a variety is a category of algebras which has a clone and is equivalent to the variety of this clone. But other equivalent definitions are possible.

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.

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.

An equivalent condition for an algebraic language to be an abstract clone is that there exists a class of interpretations (algebras), such that this language is stable by definitions by terms, while any two symbols keeping the same interpretation throughout this class are confused.

Correspondences between interpretations of formulas

Formulas can be expressed to relate elements in an abstract clone as if they operated on an unknown module M, using universal quantifiers on the variables in M . Namely, a formula R of equality «t = t'» between 2 n-ary terms t,t', can be written (for example with n=2):

∀x,y, R(x,y)

to actually mean the relation in C₂ that is R(π_0,2,π_1,2) because this indeed implies the above universal formula in any representation. In particular, it implies R(π_0,3,π_1,3), i.e. ∀x,y,z, R(x,y).
In fact these are equivalent, but the reason for the converse implication (R(π_0,3,π_1,3)⇒R(π_0,2,π_1,2)) has a subtlety, that is the same already faced to represent an operation symbol in an algebra with higher arity. In other words, to deduce (∀x,y, R(x,y)) from (∀x,y,z, R(x,y)) we need to choose a value for z. We may set it as equal to x or y, except if n=0 when they are not available, but then we can use any available symbol of constant instead (there will be, since terms not using variables must use constants).

Centralizers in abstract clones

We can generalize the concept of centralizer (or commutant), which was defined on monoids, to the case of abstract clones. It is directly obtained by abstracting with the above trick, the definition of the Galois connection Pol-Pol between sets of operations, where the condition of commutation between x∈C_i and y∈C_j is an equation expressed in C_ij .
So, the centralizer Pol X of any subset X of an abstract clone C, is a sub-clone of C.
The center of C, is the centralizer of C itself, Pol C = ∩_x_∈_C Pol {x}. We have PolPol C = C.

For any p<n, Pol C_n ⊂ Pol C_p because all p-ary operations are represented among n-ary operations, with equivalence of formulas between p-ary and n-ary views for the above reason.
∀k∈C₀, Pol{k} ∩ C₀ = {k}.

The multiplication monoid in an abstract clone

Elements of C₁ will be called scalars. The unit element of the clone, is the scalar π_0,1 that will be simply denoted 1. The operation that applies any scalar a to any element x of any representation, (a,x)↦a⋅x will be called multiplication. The multiplication between scalars forms a monoid, with 1 as identity element:

∀a∈C₁,	a⋅1=a
∀x,	1⋅x = x
∀a,b∈C₁,∀x,	(a⋅b)⋅x = a⋅(b⋅x)

The multiplication is right distributive over any operation : for example if #∈C₂,

∀a,b∈C₁,∀x, (a#b)⋅x =(a⋅x)#(b⋅x)

However, the left distributivity formula (∀x,y, a⋅(x#y) = (a⋅x)#(a⋅y)) means that # commutes with a.
Similarly for constants (nullary operations) : as any constant symbol k∈C₀ can be interpreted both in C₁ and in any other representation, both are related by

∀x, k⋅x = k

The same works for any constant, i.e. defined by a term that does not depend on any "variable". For example, if #∈C₂ and k,k'∈C₀, we have k#k'∈C₀, thus

∀x, (k#k')⋅x = k#k'.

Conversely, if C₀≠Ø and an element k ∈C₁ satisfies ∀x∈C₁, k⋅x = k then for any k'∈C₀ , the element k⋅k' ∈ C₀ satisfies k⋅k' = k in C₁, so that k is the image in C₁ of k⋅k'∈C₀.
As already argued above on the correspondence between interpretations of formulas, if two constants k,k'∈C₀ commute by multiplication in C₁ then they are equal in C₁ (k = k⋅k' = k'⋅k = k'∈C₁) and thus also in C₀ (k = k⋅k = k'⋅k = k'∈C₀).
Every term in the language C (i.e. without ⋅ nor 1) with only one variable, is reducible to a scalar multiplying the variable : for example, ∀#∈C₂, ∀x,

∀k∈C₀,	x#k = (1⋅x)#(k⋅x) = (1#k)⋅ x
	x#x = (1⋅x)#(1⋅x) = (1#1)⋅ x

Proposition. C₀ ∩ Pol C₁ ⊂ Pol C.

Proof. Let k∈C₀∩ Pol C₁, i.e. ∀a∈C₁, a⋅k=k⋅a=k.
Let n∈ℕ and x∈C_n. The commutation relation between k and x is verified as
x(k,...,k) = x(1⋅k,...,1⋅k) = x(1,...,1)⋅k = k
∎

Examples of varieties

The above gives two examples of varieties

That of all L-algebras for any given algebraic language L; its clone is the sequence of term algebras with each finite arity.
That of all monoids; its clone is made of free monoids.

Next section : Rings

Back to Set theory and foundations homepage