TheInfoList

Universal algebra (sometimes called general algebra) is the field of
mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It has no generally ...
that studies
algebraic structure In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It ...
s 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.

# Basic idea

In universal algebra, an algebra (or algebraic
structure A structure is an arrangement and organization of interrelated elements in a material object or system A system is a group of Interaction, interacting or interrelated elements that act according to a set of rules to form a unified whole. A sy ...
) is a set ''A'' together with a collection of operations on ''A''. An ''n''- ary operation on ''A'' is a function that takes ''n'' elements of ''A'' and returns a single element of ''A''. Thus, a 0-ary operation (or ''nullary operation'') can be represented simply as an element of ''A'', or a '' constant'', often denoted by a letter like ''a''. A 1-ary operation (or ''
unary operation In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It ...
'') is simply a function from ''A'' to ''A'', often denoted by a symbol placed in front of its argument, like ~''x''. A 2-ary operation (or ''
binary operation In mathematics, a binary operation or dyadic operation is a calculation that combines two elements (called operands) to produce another element. More formally, a binary operation is an Operation (mathematics), operation of arity two. More specif ...
'') is often denoted by a symbol placed between its arguments, like ''x'' ∗ ''y''. Operations of higher or unspecified ''
arity Arity () is the number of arguments or operands taken by a function or operation in logic Logic (from Ancient Greek, Greek: grc, wikt:λογική, λογική, label=none, lit=possessed of reason, intellectual, dialectical, argumentati ...
'' are usually denoted by function symbols, with the arguments placed in parentheses and separated by commas, like ''f''(''x'',''y'',''z'') or ''f''(''x''1,...,''x''''n''). Some researchers allow infinitary operations, such as $\textstyle\bigwedge_ x_\alpha$ where ''J'' is an infinite
index set In mathematics, an index set is a set whose members label (or index) members of another set. For instance, if the elements of a Set (mathematics), set may be ''indexed'' or ''labeled'' by means of the elements of a set , then is an index set. The ...
, thus leading into the algebraic theory of
complete latticeIn mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It ha ...
s. One way of talking about an algebra, then, is by referring to it as an algebra of a certain type $\Omega$, where $\Omega$ is an ordered sequence of natural numbers representing the arity of the operations of the algebra.

## Equations

After the operations have been specified, the nature of the algebra is further defined by
axiom An axiom, postulate or assumption is a statement that is taken to be true, to serve as a premise or starting point for further reasoning and arguments. The word comes from the Greek ''axíōma'' () 'that which is thought worthy or fit' or 'tha ...

s, which in universal algebra often take the form of identities, or equational laws. An example is the
associative In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). ...
axiom for a binary operation, which is given by the equation ''x'' ∗ (''y'' ∗ ''z'') = (''x'' ∗ ''y'') ∗ ''z''. The axiom is intended to hold for all elements ''x'', ''y'', and ''z'' of the set ''A''.

# Varieties

A collection of algebraic structures defined by identities is called a Variety (universal algebra), variety or equational class. Some authors consider varieties to be the main focus of universal algebra. Restricting one's study to varieties rules out: * Quantification (logic), quantification, including universal quantification ($\forall$) except before an equation, and existential quantification ($\exists$), as well as predicate logic * Finitary relation, relations other than equality, in particular inequality (mathematics), inequalities, both and Order theory, order relations The study of equational classes can be seen as a special branch of model theory, typically dealing with structures having operations only (i.e. the signature (logic), type can have symbols for functions but not for Finitary relation, relations other than equality), and in which the language used to talk about these structures uses equations only. Not all
algebraic structure In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It ...
s in a wider sense fall into this scope. For example, ordered groups involve an ordering relation, so would not fall within this scope. The class of field (mathematics), fields is not an equational class because there is no type (or "signature") in which all field laws can be written as equations (inverses of elements are defined for all ''non-zero'' elements in a field, so inversion cannot be added to the type). One advantage of this restriction is that the structures studied in universal algebra can be defined in any category theory, category that has ''finite product (category theory), products''. For example, a topological group is just a group in the category of topological spaces.

## Examples

Most of the usual algebraic systems of mathematics are examples of varieties, but not always in an obvious way, since the usual definitions often involve quantification or inequalities.

### Groups

As an example, consider the definition of a group (mathematics), group. Usually a group is defined in terms of a single binary operation ∗, subject to the axioms: * associative, Associativity (as in the #Equations, previous section): ''x'' ∗ (''y'' ∗ ''z'')  =  (''x'' ∗ ''y'') ∗ ''z'';   formally: ∀''x'',''y'',''z''. ''x''∗(''y''∗''z'')=(''x''∗''y'')∗''z''. * Identity element: There exists an element ''e'' such that for each element ''x'', one has ''e'' ∗ ''x''  =  ''x''  =  ''x'' ∗ ''e'';   formally: ∃''e'' ∀''x''. ''e''∗''x''=''x''=''x''∗''e''. * Inverse element: The identity element is easily seen to be unique, and is usually denoted by ''e''. Then for each ''x'', there exists an element ''i'' such that ''x'' ∗ ''i''  =  ''e''  =  ''i'' ∗ ''x'';   formally: ∀''x'' ∃''i''. ''x''∗''i''=''e''=''i''∗''x''. (Some authors also use the "Closure (mathematics), closure" axiom that ''x'' ∗ ''y'' belongs to ''A'' whenever ''x'' and ''y'' do, but here this is already implied by calling ∗ a binary operation.) This definition of a group does not immediately fit the point of view of universal algebra, because the axioms of the identity element and inversion are not stated purely in terms of equational laws which hold universally "for all ..." elements, but also involve the existential quantifier "there exists ...". The group axioms can be phrased as universally quantified equations by specifying, in addition to the binary operation ∗, a nullary operation ''e'' and a unary operation ~, with ~''x'' usually written as ''x''−1. The axioms become: * Associativity: . * Identity element: ; formally: ∀''x''. ''e''∗''x''=''x''=''x''∗''e''. * Inverse element:   formally: ∀''x''. ''x''∗~''x''=''e''=~''x''∗''x''. To summarize, the usual definition has: * a single binary operation (signature (logic), signature (2)) * 1 equational law (associativity) * 2 quantified laws (identity and inverse) while the universal algebra definition has: * 3 operations: one binary, one unary, and one nullary (signature (logic), signature (2,1,0)) * 3 equational laws (associativity, identity, and inverse) * no quantified laws (except outermost universal quantifiers, which are allowed in varieties) A key point is that the extra operations do not add information, but follow uniquely from the usual definition of a group. Although the usual definition did not uniquely specify the identity element ''e'', an easy exercise shows it is unique, as is each inverse element. The universal algebra point of view is well adapted to category theory. For example, when defining a group object in category theory, where the object in question may not be a set, one must use equational laws (which make sense in general categories), rather than quantified laws (which refer to individual elements). Further, the inverse and identity are specified as morphisms in the category. For example, in a topological group, the inverse must not only exist element-wise, but must give a continuous mapping (a morphism). Some authors also require the identity map to be a closed inclusion (a cofibration).

### Other examples

Most algebraic structures are examples of universal algebras. * Ring (mathematics), Rings, semigroups, quasigroups, groupoids, Magma (mathematics), magmas, Loop (algebra), loops, and others. * Vector spaces over a fixed field and module (mathematics), modules over a fixed ring are universal algebras. These have a binary addition and a family of unary scalar multiplication operators, one for each element of the field or ring. Examples of relational algebras include semilattices, lattice (order), lattices, and Boolean algebras.

# Basic constructions

We assume that the type, $\Omega$, has been fixed. Then there are three basic constructions in universal algebra: homomorphic image, subalgebra, and product. A homomorphism between two algebras ''A'' and ''B'' is a function ''h'': ''A'' → ''B'' from the set A to the set B such that, for every operation ''f''''A'' of A and corresponding ''f''''B'' of B (of arity, say, ''n''), ''h''(''f''''A''(''x''1,...,''x''''n'')) = ''f''''B''(''h''(''x''1),...,''h''(''x''''n'')). (Sometimes the subscripts on ''f'' are taken off when it is clear from context which algebra the function is from.) For example, if ''e'' is a constant (nullary operation), then ''h''(''e''''A'') = ''e''''B''. If ~ is a unary operation, then ''h''(~''x'') = ~''h''(''x''). If ∗ is a binary operation, then ''h''(''x'' ∗ ''y'') = ''h''(''x'') ∗ ''h''(''y''). And so on. A few of the things that can be done with homomorphisms, as well as definitions of certain special kinds of homomorphisms, are listed under the entry Homomorphism. In particular, we can take the homomorphic image of an algebra, ''h''(''A''). A subalgebra of ''A'' is a subset of ''A'' that is closed under all the operations of ''A''. A product of some set of algebraic structures is the cartesian product of the sets with the operations defined coordinatewise.

# Some basic theorems

* The isomorphism theorems, which encompass the isomorphism theorems of groups, Ring (mathematics), rings, Module (mathematics), modules, etc. * Variety (universal algebra)#Birkhoff's theorem, Birkhoff's HSP Theorem, which states that a class of algebras is a variety (universal algebra), variety if and only if it is closed under homomorphic images, subalgebras, and arbitrary direct products.

# Motivations and applications

In addition to its unifying approach, universal algebra also gives deep theorems and important examples and counterexamples. It provides a useful framework for those who intend to start the study of new classes of algebras. It can enable the use of methods invented for some particular classes of algebras to other classes of algebras, by recasting the methods in terms of universal algebra (if possible), and then interpreting these as applied to other classes. It has also provided conceptual clarification; as J.D.H. Smith puts it, ''"What looks messy and complicated in a particular framework may turn out to be simple and obvious in the proper general one."'' In particular, universal algebra can be applied to the study of monoids, ring (algebra), rings, and lattice (order), lattices. Before universal algebra came along, many theorems (most notably the isomorphism theorems) were proved separately in all of these classes, but with universal algebra, they can be proven once and for all for every kind of algebraic system. The 1956 paper by Higgins referenced below has been well followed up for its framework for a range of particular algebraic systems, while his 1963 paper is notable for its discussion of algebras with operations which are only partially defined, typical examples for this being categories and groupoids. This leads on to the subject of higher-dimensional algebra which can be defined as the study of algebraic theories with partial operations whose domains are defined under geometric conditions. Notable examples of these are various forms of higher-dimensional categories and groupoids.

## Constraint satisfaction problem

Universal algebra provides a natural language for the constraint satisfaction problem, constraint satisfaction problem (CSP). CSP refers to an important class of computational problems where, given a relational algebra and an existential sentence (mathematical logic), sentence $\varphi$ over this algebra, the question is to find out whether $\varphi$ can be satisfied in . The algebra is often fixed, so that refers to the problem whose instance is only the existential sentence $\varphi$. It is proved that every computational problem can be formulated as for some algebra . For example, the graph coloring, ''n''-coloring problem can be stated as CSP of the algebra $\big\left(\, \neq\big\right)$, i.e. an algebra with $n$ elements and a single relation, inequality. The dichotomy conjecture (proved in April 2017) states that if is a finite algebra, then is either P (complexity), P or NP-completeness, NP-complete.

# Generalizations

Universal algebra has also been studied using the techniques of category theory. In this approach, instead of writing a list of operations and equations obeyed by those operations, one can describe an algebraic structure using categories of a special sort, known as Lawvere theory, Lawvere theories or more generally algebraic theory, algebraic theories. Alternatively, one can describe algebraic structures using monad (category theory), monads. The two approaches are closely related, with each having their own advantages. In particular, every Lawvere theory gives a monad on the category of sets, while any "finitary" monad on the category of sets arises from a Lawvere theory. However, a monad describes algebraic structures within one particular category (for example the category of sets), while algebraic theories describe structure within any of a large class of categories (namely those having finite product (category theory), products). A more recent development in category theory is operad theory – an operad is a set of operations, similar to a universal algebra, but restricted in that equations are only allowed between expressions with the variables, with no duplication or omission of variables allowed. Thus, rings can be described as the so-called "algebras" of some operad, but not groups, since the law $g g^ = 1$ duplicates the variable ''g'' on the left side and omits it on the right side. At first this may seem to be a troublesome restriction, but the payoff is that operads have certain advantages: for example, one can hybridize the concepts of ring and vector space to obtain the concept of associative algebra, but one cannot form a similar hybrid of the concepts of group and vector space. Another development is partial algebra where the operators can be partial functions. Certain partial functions can also be handled by a generalization of Lawvere theories known as essentially algebraic theory, essentially algebraic theories. Another generalization of universal algebra is model theory, which is sometimes described as "universal algebra + logic".

# History

* Graph algebra * Term algebra * Clone (algebra), Clone * Universal algebraic geometry * Simple universal algebra

# References

* Bergman, George M., 1998.
An Invitation to General Algebra and Universal Constructions
' (pub. Henry Helson, 15 the Crescent, Berkeley CA, 94708) 398 pp. . * Birkhoff, Garrett, 1946. Universal algebra. ''Comptes Rendus du Premier Congrès Canadien de Mathématiques'', University of Toronto Press, Toronto, pp. 310–326. * Burris, Stanley N., and H.P. Sankappanavar, 1981.

' Springer-Verlag. ''Free online edition''. * Cohn, Paul Moritz, 1981. ''Universal Algebra''. Dordrecht, Netherlands: D.Reidel Publishing. ''(First published in 1965 by Harper & Row)'' * Freese, Ralph, and Ralph McKenzie, 1987.
Commutator Theory for Congruence Modular Varieties
1st ed. London Mathematical Society Lecture Note Series, 125. Cambridge Univ. Press. . Free online second edition''. * Grätzer, George, 1968. ''Universal Algebra'' D. Van Nostrand Company, Inc. * Higgins, P. J
Groups with multiple operators
Proc. London Math. Soc. (3) 6 (1956), 366–416. * Higgins, P.J., Algebras with a scheme of operators. ''Mathematische Nachrichten'' (27) (1963) 115–132. * Hobby, David, and Ralph McKenzie, 1988.
The Structure of Finite Algebras
' American Mathematical Society. . ''Free online edition.'' * Jipsen, Peter, and Henry Rose, 1992.

', Lecture Notes in Mathematics 1533. Springer Verlag. . ''Free online edition''. * Pigozzi, Don.
General Theory of Algebras
'. ''Free online edition.'' * Smith, J.D.H., 1976. ''Mal'cev Varieties'', Springer-Verlag. * Alfred North Whitehead, Whitehead, Alfred North, 1898.
A Treatise on Universal Algebra
', Cambridge. (''Mainly of historical interest.'')