Clone (algebra) explained

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

• C contains all the projections, defined by,
• 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 all j, then the n-ary operation is in C.

The question whether clones should contain nullary operations or not is not treated uniformly in the literature. The classical approach as evidenced by the standard monographs^{[2] [3] [4]} on clone theory considers clones only containing at least unary operations. However, with only minor modifications (related to the empty invariant relation) most of the usual theory can be lifted to clones allowing nullary operations.^[5] The more general concept^[6] includes all clones without nullary operations as subclones of the clone of all at least unary operations and is in accordance with the custom to allow nullary terms and nullary term operations in universal algebra. Typically, publications studying clones as abstract clones, e.g. in the category theoretic setting of Lawvere's algebraic theories, will include nullary operations.^{[7] [8]}

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 by simply taking the clone itself as source for the signature σ so that the algebra has the whole clone as its fundamental operations.

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 (there are two if nullary operations are considered). The lattice of clones on a two-element set is countable,^[3] and has been completely described by Emil Post^[9] (see Post's lattice,^[3] which traditionally does not show clones with nullary operations). Clones on larger sets do not admit a simple classification; there are continuum-many clones on a finite set of size at least three,^{[10] [3]} and 2^2κ (even just maximal,^{[11] [3]} i.e. precomplete) clones on an infinite set of cardinality κ.^{[12] [3]}

Abstract clones

Philip Hall introduced the concept of abstract clone.^[13] 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

References

• Book: Algebras, Lattices, Varieties. Ralph N.. McKenzie. Ralph McKenzie. George F.. McNulty. Walter F.. Taylor. Wadsworth & Brooks/Cole Advanced Books & Software. Monterey, CA. I. 1987. 978-0-534-07651-1.
• F. William. Lawvere. Functorial semantics of algebraic theories. Columbia University. PhD. 1963. Available online at Reprints in Theory and Applications of Categories

Notes and References

1. Menger algebras and clones of terms. Klaus. Denecke. East–West Journal of Mathematics. 2003. 5. 2. 1513-489X. 179.
2. Book: Funktionen- und Relationenalgebren. Ein Kapitel der diskreten Mathematik.. Reinhard. Pöschel. Lev A.. Kalužnin. Lev Kaluznin. German. 15. 1979. VEB Deutscher Verlag der Wissenschaften. Berlin. Mathematische Monographien.
3. Book: Clones in Universal Algebra. Ágnes. Szendrei. Ágnes Szendrei. 99. Séminaire de Mathématiques Supérieures. Presses de l'Université de Montréal. Montréal, QC. 1986. 978-2-7606-0770-5.
4. Book: Function Algebras on Finite Sets. A basic course on many-valued logic and clone theory.. Dietlinde. Lau. Springer. Berlin. 2006. 978-3-540-36022-3. Springer Monographs in Mathematics. 10.1007/3-540-36023-9.
5. Clones with Nullary Operations. Mike. Behrisch. John. Power. Cai. Wingfield. Electronic Notes in Theoretical Computer Science. 2014. 3–35. 303. 1571-0661. 10.1016/j.entcs.2014.02.002. free.
6. Book: Algebras, Lattices, Varieties. Ralph N.. McKenzie. Ralph McKenzie. George F.. McNulty. Walter F.. Taylor. Wadsworth & Brooks/Cole Advanced Books & Software. Monterey, CA. I. 1987. 978-0-534-07651-1. 143.
7. All clones are centralizer clones. Věra. Trnková. Věra Trnková. Jiří. Sichler. 61. 1. 77–95. Algebra Universalis. 2009. 0002-5240. 10.1007/s00012-009-0004-4. 10.1.1.525.167.
8. On clones determined by their initial segments. Věra. Trnková. Věra Trnková. Jiří. Sichler. 49. 3. Cahiers de Topologie et Géométrie Différentielle Catégoriques. 2008. 1245-530X.
9. Book: The two-valued iterative systems of mathematical logic. Emil Leon. Post. Emil Leon Post. Princeton University Press. Princeton, N. J.. Annals of Mathematics Studies. 5. 1941. 0004195. viii+122.
10. ru:О существовании k-значных замкнутых классов, не имеющих конечного базиса. O suščestvovanii k-značnyx zamknutyx klassov, ne imejuščix konečnogo bazisa. On the existence of k-valued closed classes having no finite basis. Юрий Иванович Янов (Jurij Ivanovič Janov). Альберт Абрамович Мучник (Aľbert Abramovič Mučnik). Doklady Akademii Nauk SSSR. 127. 1. 1959. 44–46. 0108458. 0100.01001. 0002-3264. Russian.
11. The set of maximal closed classes of operations on an infinite set A has cardinality 2^2|A|. Ivo G.. Rosenberg. Archiv der Mathematik. 27. 1976. 6. 562. Springer (Birkhäuser). Basel. 0003-889X. 0429700. 0345.02010. 10.1007/BF01224718.
12. Some maximal closed classes of operations on infinite sets. Ivo G.. Rosenberg. Mathematische Annalen. 212. 1974. 2. 158. Springer. Berlin/Heidelberg. 0025-5831. 0351964. 0281.08001. 10.1007/BF01350783.
13. Book: Paul Moritz. Cohn. Paul Cohn. Universal Algebra. 2nd. 1981. D. Reidel Publishing Co.. Dordrecht-Boston, Mass.. 6. Mathematics and its Applications. 978-90-277-1254-7. 127.