Clone (algebra)

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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

  • C contains all the projections πkn: AnA, defined by πkn(x1, …,xn) = xk,
  • C is closed under (finitary multiple) composition (or "superposition"[1]): if f, g1, …, gm are members of C such that f is m-ary, and gj is n-ary for every j, then the n-ary operation h(x1, …,xn) := f(g1(x1, …,xn), …, gm(x1, …,xn)) 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 22κ clones on an infinite set of cardinality κ.

Abstract clones[edit]

P 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 Cn for each natural number n,
  • elements πk,n in Cn for all kn, and
  • a family of functions ∗:Cm × (Cn)mCn for all m and n

such that

  • c ∗ (π1,n,...,πn,n) = c
  • πk,m ∗ (c1,...,cm) = ck
  • c ∗ (d1 ∗ (e1,...,en),...,dm∗ (e1,...,en)) = (c ∗ (d1,...dm)) ∗ (e1,...,en).

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

Any algebraic theory determines an abstract clone where Cn 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 Cn. This gives a bijective correspondence between abstract clones and algebraic theories.

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

References[edit]

  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.
  • 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