Clone (algebra)

Last updated

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

Contents

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] : 4–5  The more general concept [6] includes all clones without nullary operations as subclones of the clone of all at least unary operations [5] : 5  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, [9] [10] [3] : 39  and has been completely described by Emil Post [11] [10] (see Post's lattice, [3] : 37  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, [12] [3] : 39  and 22κ (even just maximal, [10] [3] : 39  i.e. precomplete) clones on an infinite set of cardinality κ. [9] [3] : 39 

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

such that

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

Notes

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

Related Research Articles

<span class="mw-page-title-main">Boolean algebra (structure)</span> Algebraic structure modeling logical operations

In abstract algebra, a Boolean algebra or Boolean lattice is a complemented distributive lattice. This type of algebraic structure captures essential properties of both set operations and logic operations. A Boolean algebra can be seen as a generalization of a power set algebra or a field of sets, or its elements can be viewed as generalized truth values. It is also a special case of a De Morgan algebra and a Kleene algebra.

<span class="mw-page-title-main">Field (mathematics)</span> Algebraic structure with addition, multiplication, and division

In mathematics, a field is a set on which addition, subtraction, multiplication, and division are defined and behave as the corresponding operations on rational and real numbers. A field is thus a fundamental algebraic structure which is widely used in algebra, number theory, and many other areas of mathematics.

In mathematics, a finitary relation over a sequence of sets X1, ..., Xn is a subset of the Cartesian product X1 × ... × Xn; that is, it is a set of n-tuples (x1, ..., xn), each being a sequence of elements xi in the corresponding Xi. Typically, the relation describes a possible connection between the elements of an n-tuple. For example, the relation "x is divisible by y and z" consists of the set of 3-tuples such that when substituted to x, y and z, respectively, make the sentence true.

<span class="mw-page-title-main">Monoid</span> Algebraic structure with an associative operation and an identity element

In abstract algebra, a branch of mathematics, a monoid is a set equipped with an associative binary operation and an identity element. For example, the nonnegative integers with addition form a monoid, the identity element being 0.

<span class="mw-page-title-main">Quasigroup</span> Magma obeying the Latin square property

In mathematics, especially in abstract algebra, a quasigroup is an algebraic structure that resembles a group in the sense that "division" is always possible. Quasigroups differ from groups mainly in that the associative and identity element properties are optional. In fact, a nonempty associative quasigroup is a group.

<span class="mw-page-title-main">Semigroup</span> Algebraic structure consisting of a set with an associative binary operation

In mathematics, a semigroup is an algebraic structure consisting of a set together with an associative internal binary operation on it.

Universal algebra is the field of mathematics that studies algebraic structures themselves, not examples ("models") of algebraic structures. For instance, rather than take particular groups as the object of study, in universal algebra one takes the class of groups as an object of study.

In mathematics, a transcendental extension is a field extension such that there exists an element in the field that is transcendental over the field ; that is, an element that is not a root of any univariate polynomial with coefficients in . In other words, a transcendental extension is a field extension that is not algebraic. For example, and are both transcendental extensions of

In mathematics, a closure operator on a set S is a function from the power set of S to itself that satisfies the following conditions for all sets

In mathematics, a pointed set is an ordered pair where is a set and is an element of called the base point, also spelled basepoint.

In mathematics, a multicategory is a generalization of the concept of category that allows morphisms of multiple arity. If morphisms in a category are viewed as analogous to functions, then morphisms in a multicategory are analogous to functions of several variables. Multicategories are also sometimes called operads, or colored operads.

In universal algebra and mathematical logic, a term algebra is a freely generated algebraic structure over a given signature. For example, in a signature consisting of a single binary operation, the term algebra over a set X of variables is exactly the free magma generated by X. Other synonyms for the notion include absolutely free algebra and anarchic algebra.

In universal algebra and in model theory, a structure consists of a set along with a collection of finitary operations and relations that are defined on it.

<span class="mw-page-title-main">Operation (mathematics)</span> Addition, multiplication, division, ...

In mathematics, an operation is a function from a set to itself. For example, an operation on real numbers will take in real numbers and return a real number. An operation can take zero or more input values to a well-defined output value. The number of operands is the arity of the operation.

In logic, a functionally complete set of logical connectives or Boolean operators is one that can be used to express all possible truth tables by combining members of the set into a Boolean expression. A well-known complete set of connectives is { AND, NOT }. Each of the singleton sets { NAND } and { NOR } is functionally complete. However, the set { AND, OR } is incomplete, due to its inability to express NOT.

Boolean algebra is a mathematically rich branch of abstract algebra. Stanford Encyclopaedia of Philosophy defines Boolean algebra as 'the algebra of two-valued logic with only sentential connectives, or equivalently of algebras of sets under union and complementation.' Just as group theory deals with groups, and linear algebra with vector spaces, Boolean algebras are models of the equational theory of the two values 0 and 1. Common to Boolean algebras, groups, and vector spaces is the notion of an algebraic structure, a set closed under some operations satisfying certain equations.

In logic, especially mathematical logic, a signature lists and describes the non-logical symbols of a formal language. In universal algebra, a signature lists the operations that characterize an algebraic structure. In model theory, signatures are used for both purposes. They are rarely made explicit in more philosophical treatments of logic.

<span class="mw-page-title-main">Post's lattice</span>

In logic and universal algebra, Post's lattice denotes the lattice of all clones on a two-element set {0, 1}, ordered by inclusion. It is named for Emil Post, who published a complete description of the lattice in 1941. The relative simplicity of Post's lattice is in stark contrast to the lattice of clones on a three-element set, which has the cardinality of the continuum, and a complicated inner structure. A modern exposition of Post's result can be found in Lau (2006).

Informally in mathematical logic, an algebraic theory is a theory that uses axioms stated entirely in terms of equations between terms with free variables. Inequalities and quantifiers are specifically disallowed. Sentential logic is the subset of first-order logic involving only algebraic sentences.

In universal algebra and lattice theory, a tolerance relation on an algebraic structure is a reflexive symmetric relation that is compatible with all operations of the structure. Thus a tolerance is like a congruence, except that the assumption of transitivity is dropped. On a set, an algebraic structure with empty family of operations, tolerance relations are simply reflexive symmetric relations. A set that possesses a tolerance relation can be described as a tolerance space. Tolerance relations provide a convenient general tool for studying indiscernibility/indistinguishability phenomena. The importance of those for mathematics had been first recognized by Poincaré.

References

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.