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 πkn: An → A, 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
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 Cn for each natural number n,
- elements πk,n in Cn for all k≤n, and
- a family of functions ∗:Cm × (Cn)m→Cn 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 m→n are elements of (Cm)n. This induces a bijective correspondence between Lawvere theories and abstract clones.
See also
References
- ↑ Denecke, Klaus. Menger algebras and clones of terms, East-West Journal of Mathematics 5 2 (2003),179-193.
- ↑ 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
