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 π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 κ.
[edit] References
- ^ 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.
