Universal algebra

Last updated

Universal algebra (sometimes called general 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.

Contents

Basic idea

In universal algebra, an algebra (or algebraic structure ) 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 ) 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 ) is often denoted by a symbol placed between its arguments, like x  y. Operations of higher or unspecified arity are usually denoted by function symbols, with the arguments placed in parentheses and separated by commas, like f(x,y,z) or f(x1,...,xn). Some researchers allow infinitary operations, such as where J is an infinite index set, thus leading into the algebraic theory of complete lattices. One way of talking about an algebra, then, is by referring to it as an algebra of a certain type , where 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 axioms, which in universal algebra often take the form of identities, or equational laws. An example is the associative 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 or equational class. Some authors consider varieties to be the main focus of universal algebra.[ citation needed ]

Restricting one's study to varieties rules out:

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 type can have symbols for functions but not for relations other than equality), and in which the language used to talk about these structures uses equations only.

Not all algebraic structures 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 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 that has finite 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. Usually a group is defined in terms of a single binary operation ∗, subject to the axioms:

  • Associativity (as in the previous section): x  (y  z)  =  (x  y)  z;   formally: ∀x,y,z. x∗(yz)=(xy)∗z.
  • Identity element: There exists an element e such that for each element x, one has e  x  = x  = x  e;   formally: ∃ex. ex=x=xe.
  • 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: ∀xi. xi=e=ix.

(Some authors also use the "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: x ∗ (yz)  = (xy) ∗ z.
  • Identity element: ex = x = xe; formally: ∀x. ex=x=xe.
  • Inverse element: x ∗ (~x)  = e = (~x) ∗ x  formally: ∀x. x∗~x=e=~xx.

To summarize, the usual definition has:

  • a single binary operation (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 (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.

Examples of relational algebras include semilattices, lattices, and Boolean algebras.

Basic constructions

We assume that the type, , 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 fA of A and corresponding fB of B (of arity, say, n), h(fA(x1,...,xn)) = fB(h(x1),...,h(xn)). (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(eA) = eB. 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

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, rings, and 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 (CSP). CSP refers to an important class of computational problems where, given a relational algebra A and an existential sentence over this algebra, the question is to find out whether can be satisfied in A. The algebra A is often fixed, so that CSPA refers to the problem whose instance is only the existential sentence .

It is proved that every computational problem can be formulated as CSPA for some algebra A. [1]

For example, the n-coloring problem can be stated as CSP of the algebra , i.e. an algebra with elements and a single relation, inequality.

The dichotomy conjecture (proved in April 2017) states that if A is a finite algebra, then CSPA is either P or NP-complete. [2]

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 theories or more generally algebraic theories. Alternatively, one can describe algebraic structures using monads. The two approaches are closely related, with each having their own advantages. [3] 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 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 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 theories. [4]

Another generalization of universal algebra is model theory, which is sometimes described as "universal algebra + logic". [5]

History

In Alfred North Whitehead's book A Treatise on Universal Algebra, published in 1898, the term universal algebra had essentially the same meaning that it has today. Whitehead credits William Rowan Hamilton and Augustus De Morgan as originators of the subject matter, and James Joseph Sylvester with coining the term itself. [6] :v

At the time structures such as Lie algebras and hyperbolic quaternions drew attention to the need to expand algebraic structures beyond the associatively multiplicative class. In a review Alexander Macfarlane wrote: "The main idea of the work is not unification of the several methods, nor generalization of ordinary algebra so as to include them, but rather the comparative study of their several structures." [7] At the time George Boole's algebra of logic made a strong counterpoint to ordinary number algebra, so the term "universal" served to calm strained sensibilities.

Whitehead's early work sought to unify quaternions (due to Hamilton), Grassmann's Ausdehnungslehre, and Boole's algebra of logic. Whitehead wrote in his book:

"Such algebras have an intrinsic value for separate detailed study; also they are worthy of comparative study, for the sake of the light thereby thrown on the general theory of symbolic reasoning, and on algebraic symbolism in particular. The comparative study necessarily presupposes some previous separate study, comparison being impossible without knowledge." [6]

Whitehead, however, had no results of a general nature. Work on the subject was minimal until the early 1930s, when Garrett Birkhoff and Øystein Ore began publishing on universal algebras. Developments in metamathematics and category theory in the 1940s and 1950s furthered the field, particularly the work of Abraham Robinson, Alfred Tarski, Andrzej Mostowski, and their students. [8]

In the period between 1935 and 1950, most papers were written along the lines suggested by Birkhoff's papers, dealing with free algebras, congruence and subalgebra lattices, and homomorphism theorems. Although the development of mathematical logic had made applications to algebra possible, they came about slowly; results published by Anatoly Maltsev in the 1940s went unnoticed because of the war. Tarski's lecture at the 1950 International Congress of Mathematicians in Cambridge ushered in a new period in which model-theoretic aspects were developed, mainly by Tarski himself, as well as C.C. Chang, Leon Henkin, Bjarni Jónsson, Roger Lyndon, and others.

In the late 1950s, Edward Marczewski [9] emphasized the importance of free algebras, leading to the publication of more than 50 papers on the algebraic theory of free algebras by Marczewski himself, together with Jan Mycielski, Władysław Narkiewicz, Witold Nitka, J. Płonka, S. Świerczkowski, K. Urbanik, and others.

Starting with William Lawvere's thesis in 1963, techniques from category theory have become important in universal algebra. [10]

See also

Footnotes

  1. Bodirsky, Manuel; Grohe, Martin (2008), Non-dichotomies in constraint satisfaction complexity (PDF)
  2. Zhuk, Dmitriy (2017). "The Proof of CSP Dichotomy Conjecture". arXiv: 1704.01914 [cs.cc].
  3. Hyland, Martin; Power, John (2007), The Category Theoretic Understanding of Universal Algebra: Lawvere Theories and Monads (PDF)
  4. Essentially algebraic theory in nLab
  5. C.C. Chang and H. Jerome Keisler (1990). Model Theory. Studies in Logic and the Foundation of Mathematics. 73 (3rd ed.). North Holland. p. 1. ISBN   0444880542.
  6. 1 2 George Grätzer (1968). M.H. Stone and L. Nirenberg and S.S. Chern (ed.). Universal Algebra (1st ed.). Van Nostrand Co., Inc.
  7. Alexander Macfarlane (1899) Review:A Treatise on Universal Algebra (pdf), Science 9: 324–8 via Internet Archive
  8. Brainerd, Barron (Aug–Sep 1967) "Review of Universal Algebra by P. M. Cohn", American Mathematical Monthly 74(7): 878–880.
  9. Marczewski, E. "A general scheme of the notions of independence in mathematics." Bull. Acad. Polon. Sci. Ser. Sci. Math. Astronom. Phys. 6 (1958), 731–736.
  10. Lawvere, William F. (1964), Functorial Semantics of Algebraic Theories (PhD Thesis)

Related Research Articles

Boolean algebra (structure) 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.

In algebra, a homomorphism is a structure-preserving map between two algebraic structures of the same type. The word homomorphism comes from the Ancient Greek language: ὁμός meaning "same" and μορφή meaning "form" or "shape". However, the word was apparently introduced to mathematics due to a (mis)translation of German ähnlich meaning "similar" to ὁμός meaning "same". The term "homomorphism" appeared as early as 1892, when it was attributed to the German mathematician Felix Klein (1849–1925).

Group (mathematics) Algebraic structure with one binary operation

In mathematics, a group is a set equipped with an operation that combines any two elements to form a third element while being associative as well as having an identity element and inverse elements. These three conditions, called group axioms, hold for number systems and many other mathematical structures. For example, the integers together with the addition operation form a group. The formulation of the axioms is, however, detached from the concrete nature of the group and its operation. This allows one to handle entities of very different mathematical origins in a flexible way, while retaining essential structural aspects of many objects in abstract algebra and beyond. The ubiquity of groups in numerous areas—both within and outside mathematics—makes them a central organizing principle of contemporary mathematics.

Monoid 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.

Power set Mathematical set containing all subsets of a given set

In mathematics, the power set of a set S is the set of all subsets of S, including the empty set and S itself. In axiomatic set theory, the existence of the power set of any set is postulated by the axiom of power set. The powerset of S is variously denoted as P(S), 𝒫(S), P(S), (S), ℘(S), or 2S. The notation 2S, meaning the set of all functions from S to a given set of two elements, is used because the powerset of S can be identified with, equivalent to, or bijective to the set of all the functions from S to the given two elements set.

In mathematics, especially in abstract algebra, a quasigroup is an algebraic structure resembling a group in the sense that "division" is always possible. Quasigroups differ from groups mainly in that they are not necessarily associative.

Semigroup

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

In mathematics, specifically category theory, adjunction is a relationship that two functors may have. Two functors that stand in this relationship are known as adjoint functors, one being the left adjoint and the other the right adjoint. Pairs of adjoint functors are ubiquitous in mathematics and often arise from constructions of "optimal solutions" to certain problems, such as the construction of a free group on a set in algebra, or the construction of the Stone–Čech compactification of a topological space in topology.

In mathematics, an algebraic structure consists of a nonempty set A, a collection of operations on A of finite arity, and a finite set of identities, known as axioms, that these operations must satisfy.

Magma (algebra) Algebraic structure with a binary operation

In abstract algebra, a magma, binar or, rarely, groupoid is a basic kind of algebraic structure. Specifically, a magma consists of a set equipped with a single binary operation that must be closed by definition. No other properties are imposed.

In category theory, a branch of mathematics, a monad is an endofunctor, together with two natural transformations required to fulfill certain coherence conditions. Monads are used in the theory of pairs of adjoint functors, and they generalize closure operators on partially ordered sets to arbitrary categories.

A lattice is an abstract structure studied in the mathematical subdisciplines of order theory and abstract algebra. It consists of a partially ordered set in which every two elements have a unique supremum and a unique infimum. An example is given by the natural numbers, partially ordered by divisibility, for which the unique supremum is the least common multiple and the unique infimum is the greatest common divisor.

In universal algebra, a variety of algebras or equational class is the class of all algebraic structures of a given signature satisfying a given set of identities. For example, the groups form a variety of algebras, as do the abelian groups, the rings, the monoids etc. According to Birkhoff's theorem, a class of algebraic structures of the same signature is a variety if and only if it is closed under the taking of homomorphic images, subalgebras and (direct) products. In the context of category theory, a variety of algebras, together with its homomorphisms, forms a category; these are usually called finitary algebraic categories.

<i>F</i>-algebra

In mathematics, specifically in category theory, F-algebras generalize the notion of algebraic structure. Rewriting the algebraic laws in terms of morphisms eliminates all references to quantified elements from the axioms, and these algebraic laws may then be glued together in terms of a single functor F, the signature.

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.

In mathematics and abstract algebra, a relation algebra is a residuated Boolean algebra expanded with an involution called converse, a unary operation. The motivating example of a relation algebra is the algebra 2X² of all binary relations on a set X, that is, subsets of the cartesian square X2, with RS interpreted as the usual composition of binary relations R and S, and with the converse of R as the converse relation.

Boolean algebra is a mathematically rich branch of abstract algebra. 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 zero or more operations satisfying certain equations.

In mathematics, particularly in abstract algebra, a semigroup with involution or a *-semigroup is a semigroup equipped with an involutive anti-automorphism, which—roughly speaking—brings it closer to a group because this involution, considered as unary operator, exhibits certain fundamental properties of the operation of taking the inverse in a group: uniqueness, double application "cancelling itself out", and the same interaction law with the binary operation as in the case of the group inverse. It is thus not a surprise that any group is a semigroup with involution. However, there are significant natural examples of semigroups with involution that are not groups.

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.

References