Birkhoff's HSP Theorem

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 $\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; the axiom consisting of the words $v$ and $w$ is written as $v = w$.

A ''theory'' consists of 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$. The class of algebras of a given theory $T$ is called a ''variety of algebras''.

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, identity and inverse form one suitable set of identities:

:$x(yz) = (xy)z$
:$1 x = x 1 = x$
:$x x^ = x^ 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 (see below).

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.

One direction of the equivalence mentioned above, namely that a class of algebras satisfying some set of identities must be closed under the HSP operations, follows immediately from the definitions. Proving the converse—classes of algebras closed under the HSP operations must be equational—is more difficult.

Using the easy direction of Birkhoff's theorem, we can for example verify the claim made above, that the field axioms are not expressible 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 $\langle\mathbb Z,+\rangle$ and does not contain its subalgebra (more precisely, submonoid) $\langle\mathbb N,+\rangle$.

However, 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 $f\circ i = 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$

has a left adjoint $F\colon \mathbf\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^$ for the monad $T=GF$.

The monad $T\colon \mathbf\to\mathbf$ 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$. 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.E.g. Banaschewski, B. (1983), "The Birkhoff Theorem for varieties of finite algebras", ''Algebra Universalis'', Volume 17(1): 360-368, DOI 10.1007/BF01194543

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

Notes

External links

Two monographs available free online:
*Stanley N. Burris and H.P. Sankappanavar (1981),
A Course in Universal Algebra.
' Springer-Verlag. . roof of Birkhoff's Theorem is in II§11.*Peter Jipsen and Henry Rose (1992),
Varieties of Lattices
', Lecture Notes in Mathematics 1533. Springer Verlag. .

{{Authority control

Universal algebra