Clone (algebra)

In universal algebra, a clone is a set C of finitary operations on a set A such that

• C contains all the projections π_kⁿ: Aⁿ → A, defined by π_kⁿ(x₁, …,x_n) = x_k,
• C is closed under (finitary multiple) composition (or "superposition"^[1]): if f, g₁, …, g_m are members of C such that f is m-ary, and g_j is n-ary for every j, then the n-ary operation h(x₁, …,x_n) := f(g₁(x₁, …,x_n), …, g_m(x₁, …,x_n)) is in C.

Given an algebra in a signature σ, the set of operations on its carrier definable by a σ-term (the term functions) is a clone. Conversely, every clone can be realized as the clone of term functions in a suitable algebra.

If A and B are algebras with the same carrier such that every basic function of A is a term function in B and vice versa, then A and B have the same clone. For this reason, modern universal algebra often treats clones as a representation of algebras which abstracts from their signature.

There is only one clone on the one-element set. The lattice of clones on a two-element set is countable, and has been completely described by Emil Post (see Post's lattice). Clones on larger sets do not admit a simple classification; there are continuum clones on a finite set of size at least three, and 2^2κ clones on an infinite set of cardinality κ.

Abstract clones

Philip Hall introduced the concept of abstract clone.^[2] An abstract clone is different from a concrete clone in that the set A is not given. Formally, an abstract clone comprises

• a set C_n for each natural number n,
• elements π_k,n in C_n for all k≤n, and
• a family of functions ∗:C_m × (C_n)^m→C_n for all m and n

such that

• c ∗ (π_1,n,...,π_n,n) = c
• π_k,m ∗ (c₁,...,c_m) = c_k
• c ∗ (d₁ ∗ (e₁,...,e_n),...,d_m∗ (e₁,...,e_n)) = (c ∗ (d₁,...d_m)) ∗ (e₁,...,e_n).

Any concrete clone determines an abstract clone in the obvious manner.

Any algebraic theory determines an abstract clone where C_n is the set of terms in n variables, π_k,n are variables, and ∗ is substitution. Two theories determine isomorphic clones if and only if the corresponding categories of algebras are isomorphic. Conversely every abstract clone determines an algebraic theory with an n-ary operation for each element of C_n. This gives a bijective correspondence between abstract clones and algebraic theories.

Every abstract clone C induces a Lawvere theory in which the morphisms m→n are elements of (C_m)ⁿ. This induces a bijective correspondence between Lawvere theories and abstract clones.

See also

• Term algebra

Notes

1. Denecke, Klaus. Menger algebras and clones of terms, East-West Journal of Mathematics 5 2 (2003), 179-193.
2. P. M. Cohn. Universal algebra. D Reidel, 2nd edition, 1981. Ch III.

References

• Ralph N. McKenzie, George F. McNulty, and Walter F. Taylor, Algebras, Lattices, Varieties, Vol. 1, Wadsworth & Brooks/Cole, Monterey, CA, 1987.
• F. William Lawvere: Functorial semantics of algebraic theories, Columbia University, 1963. Available online at Reprints in Theory and Applications of Categories