Variety (universal algebra)

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".
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, which means a set of solutions to a system of polynomial equations. 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 bilinear 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 formula_1 and a set formula_2, 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 formula_3 has as many branches away from the root as the arity of formula_3. An "equational law" is a pair of such words; we write the axiom consisting of the words formula_5 and formula_6 as formula_7.
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 formula_8, an "algebra" of formula_8 consists of a set formula_10 together with, for each operation formula_3 of formula_8 with arity formula_13, a function formula_14 such that for each axiom formula_7 and each assignment of elements of formula_10 to the variables in that axiom, the equation holds that is given by applying the operations to the elements of formula_10 as indicated by the trees defining formula_5 and formula_6. We call the class of algebras of a given theory formula_8 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 formula_8, say formula_10 and formula_23, a "homomorphism" is a function formula_24 such that
for every operation formula_3 of arity formula_13. 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:
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, identity and inverse form one suitable set of identities:
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 do not 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. However, they do form a quasivariety as the implication defining the cancellation property is an example of a quasi-identity.
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.
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 more difficult.
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 do not 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. The class of monoids which are groups contains formula_32 and does not contain its subalgebra (more precisely, submonoid) formula_33.
However, the class of abelian groups is a subvariety of the variety of groups because it consists of those groups satisfying formula_34 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 FS on S". This means that there is an injective set map "i" : "S" → "FS" 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" : "FS" → "A" such that formula_35.
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 formula_2 is a finitary algebraic category (i.e. the category of a variety of algebras, with homomorphisms as morphisms) then the forgetful functor
has a left adjoint formula_38, namely the functor that assigns to each set the free algebra on that set. This adjunction is "strictly monadic", in that the category formula_2 is isomorphic to the Eilenberg–Moore category formula_40 for the monad formula_41.
The monad formula_42 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 formula_43. 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.
External links.
Two monographs available free online: