Variety (universal algebra)

This article is about a class of algebraic structures of the same signature. For the set of solutions to a system of polynomial equations, see Algebraic variety.

In the mathematical subject of universal algebra, a variety of algebras 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.

A covariety is the class of all coalgebraic structures of a given signature.

Terminology

A variety of algebras should not be confused with an algebraic variety. Intuitively, a variety of algebras is a collection of algebras, defined by a set of equations that must be identically satisfied in each algebra, while an algebraic variety is a collection of elements from a single algebra, defined by a set of equations that these elements must satisfy. The two are named alike by analogy, but they are formally quite distinct and their theories have little in common.

The term "variety of algebras" refers to algebras in the general sense of universal algebra; there is also a more specific sense of algebra, namely as algebra over a field, i.e. a vector space equipped with a multiplication.

Definition

A signature (in this context) is a set, whose elements are called operations, each of which is assigned a natural number (0, 1, 2,...) called its arity. Given a signature $\sigma$ and a set $V$, whose elements are called variables, a word is a finite planar rooted tree in which each node is labelled by either a variable or an operation, such that every node labelled by a variable has no branches away from the root and every node labelled by an operation $o$ has as many branches away from the root as the arity of $o$. An equational law is a pair of such words; we write the axiom consisting of the words $v$ and $w$ as $v=w$.

A theory is a signature, a set of variables and a set of equational laws. Any theory gives a variety of algebras as follows. Given a theory $T$, an algebra of $T$ consists of a set $A$ together with, for each operation $o$ of $T$ with arity $n$, a function $o_{A}\colon A^{n}\to A$ such that for each axiom $v=w$ and each assignment of elements of $A$ to the variables in that axiom, the equation holds that is given by applying the operations to the elements of $A$ as indicated by the trees defining $v$ and $w$. We call the class of algebras of a given theory $T$ a variety of algebras.

However, ultimately more important than this class of algebras is the category of algebras and homomorphisms between them. Given two algebras of a theory $T$, say $A$ and $B$, a homomorphism is a function $f\colon A\to B$ such that

$f(o_{A}(a_{1},\dots ,a_{n}))=o_{B}(f(a_{1}),\dots ,f(a_{n}))$

for every operation $o$ of arity $n$. Any theory gives a category where the objects are algebras of that theory and the morphisms are homomorphisms.

Examples

The class of all semigroups forms a variety of algebras of signature (2), meaning that a semigroup has a single binary operation. A sufficient defining equation is the associative law:

$x(yz)=(xy)z.$

The class of groups forms a variety of algebras of signature (2,0,1), the three operations being respectively multiplication (binary), identity (nullary, a constant) and inversion (unary). The familiar axioms of associativity, inverse and identity form one suitable set of identities:

$x(yz)=(xy)z$

$1x=x1=x$

$xx^{-1}=x^{-1}x=1.$

The class of rings also forms a variety of algebras. The signature here is (2,2,0,0,1) (two binary operations, two constants, and one unary operation).

If we fix a specific ring R, we can consider the class of left R-modules. To express the scalar multiplication with elements from R, we need one unary operation for each element of R. If the ring is infinite, we will thus have infinitely many operations, which is allowed by the definition of an algebraic structure in universal algebra. We will then also need infinitely many identities to express the module axioms, which is allowed by the definition of a variety of algebras. So the left R-modules do form a variety of algebras.

The fields do not form a variety of algebras; the requirement that all non-zero elements be invertible cannot be expressed as a universally satisfied identity.

The cancellative semigroups also don't form a variety of algebras, since the cancellation property is not an equation, it is an implication that is not equivalent to any set of equations.

Birkhoff's theorem

Given a class of algebraic structures of the same signature, we can define the notions of homomorphism, subalgebra, and product. Garrett Birkhoff proved that 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 arbitrary products. This is a result of fundamental importance to universal algebra and known as Birkhoff's theorem or as the HSP theorem. H, S, and P stand, respectively, for the operations of homomorphism, subalgebra, and product.

It is easy to see that the class of algebras satisfying some set of identities will be closed under the HSP operations. Proving the converse—classes of algebras closed under the HSP operations must be equational—is harder.

Using Birkhoff's theorem, we can for example verify the claim made above, that the field axioms are not expressable by any possible set of identities: the product of fields is not a field, so fields don't form a variety.

Subvarieties

A subvariety of a variety of algebras V is a subclass of V that has the same signature as V and is itself a variety, i.e., is defined by a set of identities.

Notice that although every group becomes a semigroup when the identity as a constant is omitted (and/or the inverse operation is omitted), the class of groups does not form a subvariety of the variety of semigroups because the signatures are different. Similarly, the class of semigroups which are groups is not a subvariety of the variety of semigroups. Indeed, the class of monoids which are groups contains $\langle \mathbb {Z} ,+\rangle$ and does not contain its subalgebra (more precisely, submonoid) $\langle \mathbb {N} ,+\rangle$.

On the other hand the class of abelian groups is a subvariety of the variety of groups because it consists of those groups satisfying $xy=yx,$ with no change of signature. The finitely generated abelian groups do not form a subvariety, since by Birkhoff's theorem they don't form a variety, as an arbitrary product of finitely generated abelian groups is not finitely generated.

Viewing a variety V and its homomorphisms as a category, a subvariety U of V is a full subcategory of V, meaning that for any objects a, b in U, the homomorphisms from a to b in U are exactly those from a to b in V.

Free objects

Suppose V is a non-trivial variety of algebras, i.e. V contains algebras with more than one element. One can show that for every set S, the variety V contains a free algebra F_S on S. This means that there is an injective set map i : S → F_S which satisfies the following universal property: given any algebra A in V and any map k : S → A, there exists a unique V-homomorphism f : F_S → A such that fi = k.

This generalizes the notions of free group, free abelian group, free algebra, free module etc. It has the consequence that every algebra in a variety is a homomorphic image of a free algebra.

Category theory

If $V$ is a finitary algebraic category (i.e. the category of a variety of algebras, with homomorphisms as morphisms) then the forgetful functor

$G\colon V\to {\mathbf {Set}}$

has a left adjoint $F\colon {\mathbf {Set}}\to V$, namely the functor that assigns to each set the free algebra on that set. This adjunction is strictly monadic, in that the category $V$ is isomorphic to the Eilenberg–Moore category ${\mathbf {Set}}^{T}$ for the monad $T=GF$.

The monad $T\colon {\mathbf {Set}}\to {\mathbf {Set}}$ is thus enough to recover the finitary algebraic category, which allows the following generalization. One says a category is an algebraic category if it is monadic over ${\mathbf {Set} }$. This is a more general notion than "finitary algebraic category" because it admits such categories as CABA (complete atomic Boolean algebras) and CSLat (complete semilattices) whose signatures include infinitary operations. In those two cases the signature is large, meaning that it forms not a set but a proper class, because its operations are of unbounded arity. The algebraic category of sigma algebras also has infinitary operations, but their arity is countable whence its signature is small (forms a set).

Every finitary algebraic category is a locally presentable category.

Pseudovariety of finite algebras

Since varieties are closed under arbitrary direct products, all non-trivial varieties contain infinite algebras. Attempts have been made to develop a finitary analogue of the theory of varieties. This led, e.g., to the notion of variety of finite semigroups. This kind of variety uses only finitary products. However, it uses a more general kind of identities.

A pseudovariety is usually defined to be a class of algebras of a given signature, closed under the taking of homomorphic images, subalgebras and finitary direct products. Not every author assumes that all algebras of a pseudovariety are finite; if this is the case, one sometimes talks of a variety of finite algebras. For pseudovarieties, there is no general finitary counterpart to Birkhoff's theorem, but in many cases the introduction of a more complex notion of equations allows similar results to be derived.

Pseudovarieties are of particular importance in the study of finite semigroups and hence in formal language theory. Eilenberg's theorem, often referred to as the variety theorem, describes a natural correspondence between varieties of regular languages and pseudovarieties of finite semigroups.

See also

• Quasivariety

External links

Two monographs available free online:

• Stanley N. Burris and H.P. Sankappanavar (1981), A Course in Universal Algebra. Springer-Verlag. ISBN 3-540-90578-2. [Proof of Birkhoff's Theorem is in II§11.]
• Peter Jipsen and Henry Rose (1992), Varieties of Lattices, Lecture Notes in Mathematics 1533. Springer Verlag. ISBN 0-387-56314-8.