Abstract clones


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

L = ∐n∈ℕ Ln

where each set Ln of n-ary symbols is an object of C with a chosen basis of n elements 1n = (ei,n)i<nLnn. Thus, ∀n∈ℕ, Ln = Ci<n L1.

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(n), where φE(n) : Ln × EnE is defined taking as ⃖φE(n) the inverse of Mor(Ln,E) ∋ ff⚬1n which is bijective to En because 1n 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:
  1. Each ei,n acts as the i-th projection from En to E, i.e. ∀i<n, ∀uEn, ei,nu = ui.
  2. n∈ℕ, ⃖φE(n) : En → Mor(Ln,E).
This implies (for all objects E, F),

Mor(E,F) ⊂ MorL(E,F)
n∈ℕ, Mor(Ln,E) = MorL(Ln,E).

Let us recall the proof of MorL(Ln,E) ⊂ Mor(Ln,E) previously seen for n=1. From 1n being a basis of Ln and IdLn ∈ Mor(Ln,Ln), comes
  1. xLn, x = x⋅1n
Thus ∀f∈MorL(Ln,E), (∀xLn, f(x) = f(x⋅1n) = x⋅ (f⚬1n) ∴ f = ⃖φE(n)(f⚬1n) ∈ Mor(Ln,E).∎

3. implies that 1n generates Ln in the sense that 〈1nLn = Ln ∴ 〈1nL = Ln.

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 (Ln)n∈ℕ, called an abstract clone. It defines on L a structure of typed algebra with types Ln and operations 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 MorL :

n,p∈ℕ, ∀sLp, ∀xLnp, ∀uMn, (sx) ⋅ u = s ⋅ ((xiu)i<p)

The variety of L is the category of all L-modules with Mor = MorL.
A typed algebra L = ∐n∈ℕ Ln with such symbols, is an abstract clone if each Ln satisfies the above axioms 1., 2. and 3. extending to L the axioms of monoid for L1:
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∈ℕ 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 ei,n):

n∈ℕ, 〈1nL = Ln.

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.

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 C2 that is R0,21,2) because this indeed implies the above universal formula in any representation. In particular, it implies R0,31,3), i.e. ∀x,y,z, R(x,y).
In fact these are equivalent, but the reason for the converse implication (R0,31,3)⇒R0,21,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 xCi and yCj is an equation expressed in Cij .
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 = ∩xC Pol {x}. We have Pol Pol C = C.

For any p<n, Pol Cn ⊂ Pol Cp 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.
kC0, Pol{k} ∩ C0 = {k}.

The multiplication monoid in an abstract clone

Elements of C1 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)↦ax will be called multiplication. The multiplication between scalars forms a monoid, with 1 as identity element:
1⋅x = x
a,bC1,∀x  (ab)⋅x = a⋅(bx)

The multiplication is right distributive over any operation : for example if #∈C2,
a,bC1,∀x, (a#b)⋅x =(ax)#(bx)
However, the left distributivity formula (∀x,y, a⋅(x#y) = (ax)#(ay)) means that # commutes with a.
Similarly for constants (nullary operations) : as any constant symbol kC0 can be interpreted both in C1 and in any other representation, both are related by
x, kx = k
The same works for any constant, i.e. defined by a term that does not depend on any "variable". For example, if #∈C2 and k,k'∈C0, we have k#k'∈C0, thus
x, (k#k')⋅x = k#k'.
Conversely, if C0≠Ø and an element kC1 satisfies ∀xC1, kx = k then for any k'∈C0 , the element kk' ∈ C0 satisfies kk' = k in C1, so that k is the image in C1 of kk'∈C0.
As already argued above on the correspondence between interpretations of formulas, if two constants k,k'∈C0 commute by multiplication in C1 then they are equal in C1 (k = kk' = k'⋅k = k'∈C1) and thus also in C0 (k = kk = k'⋅k = k'∈C0).
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, ∀#∈C2, ∀x,
x#k = (1⋅x)#(kx) = (1#k)⋅ x
  x#x = (1⋅x)#(1⋅x) = (1#1)⋅ x

Proposition.  C0 ∩ Pol C1 ⊂ Pol C.

Proof. Let kC0∩ Pol C1 , i.e. ∀aC1, ak=ka=k.
Let n∈ℕ and xCn. 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

Next section : Rings

Back to Set theory and foundations homepage