Clone (algebra)

From Wikipedia, the free encyclopedia

In universal algebra, a clone is a set C of 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 κ.

[edit] Category Theory

William Lawvere's PhD thesis introduced the concept of Lawvere theory, which is the categorical equivalent of a clone.

[edit] References

1. ^ Denecke, Klaus. Menger algebras and clones of terms, East-West Journal of Mathematics 5 2 (2003),179-193.

• 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