Birkhoff's HSP Theorem
   HOME

TheInfoList



OR:

In
universal algebra Universal algebra (sometimes called general algebra) is the field of mathematics that studies algebraic structures in general, not specific types of algebraic structures. For instance, rather than considering groups or rings as the object of stud ...
, a variety of algebras or equational class is the
class Class, Classes, or The Class may refer to: Common uses not otherwise categorized * Class (biology), a taxonomic rank * Class (knowledge representation), a collection of individuals or objects * Class (philosophy), an analytical concept used d ...
of all
algebraic structure In mathematics, an algebraic structure or algebraic system consists of a nonempty set ''A'' (called the underlying set, carrier set or domain), a collection of operations on ''A'' (typically binary operations such as addition and multiplicatio ...
s of a given
signature A signature (; from , "to sign") is a depiction of someone's name, nickname, or even a simple "X" or other mark that a person writes on documents as a proof of identity and intent. Signatures are often, but not always, Handwriting, handwritt ...
satisfying a given set of identities. For example, the
groups A group is a number of persons or things that are located, gathered, or classed together. Groups of people * Cultural group, a group whose members share the same cultural identity * Ethnic group, a group whose members share the same ethnic iden ...
form a variety of algebras, as do the
abelian group In mathematics, an abelian group, also called a commutative group, is a group in which the result of applying the group operation to two group elements does not depend on the order in which they are written. That is, the group operation is commu ...
s, the rings, the
monoid In abstract algebra, a monoid is a set equipped with an associative binary operation and an identity element. For example, the nonnegative integers with addition form a monoid, the identity element being . Monoids are semigroups with identity ...
s 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,
subalgebra In mathematics, a subalgebra is a subset of an algebra, closed under all its operations, and carrying the induced operations. "Algebra", when referring to a structure, often means a vector space or module equipped with an additional bilinear opera ...
s, and (direct) products. In the context of
category theory Category theory is a general theory of mathematical structures and their relations. It was introduced by Samuel Eilenberg and Saunders Mac Lane in the middle of the 20th century in their foundational work on algebraic topology. Category theory ...
, a variety of algebras, together with its homomorphisms, forms a
category Category, plural categories, may refer to: General uses *Classification, the general act of allocating things to classes/categories Philosophy * Category of being * ''Categories'' (Aristotle) * Category (Kant) * Categories (Peirce) * 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 Algebraic varieties are the central objects of study in algebraic geometry, a sub-field of mathematics. Classically, an algebraic variety is defined as the solution set, set of solutions of a system of polynomial equations over the real number, ...
, which means a set of solutions to a
system of polynomial equations A system of polynomial equations (sometimes simply a polynomial system) is a set of simultaneous equations where the are polynomials in several variables, say , over some Field (mathematics), field . A ''solution'' of a polynomial system is a se ...
. 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 Universal algebra (sometimes called general algebra) is the field of mathematics that studies algebraic structures in general, not specific types of algebraic structures. For instance, rather than considering groups or rings as the object of stud ...
; there is also a more specific sense of algebra, namely as
algebra over a field In mathematics, an algebra over a field (often simply called an algebra) is a vector space equipped with a bilinear map, bilinear product (mathematics), product. Thus, an algebra is an algebraic structure consisting of a set (mathematics), set to ...
, i.e. a
vector space In mathematics and physics, a vector space (also called a linear space) is a set (mathematics), set whose elements, often called vector (mathematics and physics), ''vectors'', can be added together and multiplied ("scaled") by numbers called sc ...
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 In mathematics, the natural numbers are the numbers 0, 1, 2, 3, and so on, possibly excluding 0. Some start counting with 0, defining the natural numbers as the non-negative integers , while others start with 1, defining them as the positive in ...
(0, 1, 2, ...) called its ''arity''. Given a signature ''σ'' and a set ''V'', whose elements are called ''variables'', a ''word'' is a finite
rooted tree In graph theory, a tree is an undirected graph in which any two vertices are connected by path, or equivalently a connected acyclic undirected graph. A forest is an undirected graph in which any two vertices are connected by path, or equi ...
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 . 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 such that for each axiom 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 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 Category, plural categories, may refer to: General uses *Classification, the general act of allocating things to classes/categories Philosophy * Category of being * ''Categories'' (Aristotle) * Category (Kant) * Categories (Peirce) * Category ( ...
where the objects are algebras of that theory and the morphisms are homomorphisms.


Examples

The class of all
semigroup In mathematics, a semigroup is an algebraic structure consisting of a set together with an associative internal binary operation on it. The binary operation of a semigroup is most often denoted multiplicatively (just notation, not necessarily th ...
s 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 A group is a number of persons or things that are located, gathered, or classed together. Groups of people * Cultural group, a group whose members share the same cultural identity * Ethnic group, a group whose members share the same ethnic iden ...
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 Fields may refer to: Music *Fields (band), an indie rock band formed in 2006 * Fields (progressive rock band), a progressive rock band formed in 1971 * ''Fields'' (album), an LP by Swedish-based indie rock band Junip (2010) * "Fields", a song by ...
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 semigroup In mathematics, a cancellative semigroup (also called a cancellation semigroup) is a semigroup having the cancellation property. In intuitive terms, the cancellation property asserts that from an equality of the form ''a''·''b'' = ''a''·''c'', ...
s 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 In mathematics, a quasivariety is a class of algebraic structures generalizing the notion of variety by allowing equational conditions on the axioms defining the class. __TOC__ Definition A ''trivial algebra'' contains just one element. A qua ...
as the implication defining the cancellation property is an example of a
quasi-identity In universal algebra, a quasi-identity is an implication of the form :''s''1 = ''t''1 ∧ … ∧ ''s'n'' = ''t'n'' → ''s'' = ''t'' where ''s''1, ..., ''s'n'', ''t''1, ..., ''t'n'', ''s'', and ''t'' are terms built up from variable ...
.


Birkhoff's variety theorem

Given a class of algebraic structures of the same signature, we can define the notions of homomorphism,
subalgebra In mathematics, a subalgebra is a subset of an algebra, closed under all its operations, and carrying the induced operations. "Algebra", when referring to a structure, often means a vector space or module equipped with an additional bilinear opera ...
, and product.
Garrett Birkhoff Garrett Birkhoff (January 19, 1911 – November 22, 1996) was an American mathematician. He is best known for his work in lattice theory. The mathematician George Birkhoff (1884–1944) was his father. Life The son of the mathematician Ge ...
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 variety 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 that are groups is not a subvariety of the variety of semigroups. The class of monoids that 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 group In mathematics, an abelian group, also called a commutative group, is a group in which the result of applying the group operation to two group elements does not depend on the order in which they are written. That is, the group operation is commu ...
s is a subvariety of the variety of groups because it consists of those groups satisfying , with no change of signature. The
finitely generated abelian group In abstract algebra, an abelian group (G,+) is called finitely generated if there exist finitely many elements x_1,\dots,x_s in G such that every x in G can be written in the form x = n_1x_1 + n_2x_2 + \cdots + n_sx_s for some integers n_1,\dots, n ...
s 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 Category, plural categories, may refer to: General uses *Classification, the general act of allocating things to classes/categories Philosophy * Category of being * ''Categories'' (Aristotle) * Category (Kant) * Categories (Peirce) * Category ( ...
, a subvariety ''U'' of ''V'' is a
full subcategory In mathematics, specifically category theory, a subcategory of a category ''C'' is a category ''S'' whose objects are objects in ''C'' and whose morphisms are morphisms in ''C'' with the same identities and composition of morphisms. Intuitivel ...
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 that satisfies the following
universal property In mathematics, more specifically in category theory, a universal property is a property that characterizes up to an isomorphism the result of some constructions. Thus, universal properties can be used for defining some objects independently fro ...
: given any algebra ''A'' in ''V'' and any map , there exists a unique ''V''-homomorphism such that . This generalizes the notions of
free group In mathematics, the free group ''F'S'' over a given set ''S'' consists of all words that can be built from members of ''S'', considering two words to be different unless their equality follows from the group axioms (e.g. ''st'' = ''suu''− ...
,
free abelian group In mathematics, a free abelian group is an abelian group with a Free module, basis. Being an abelian group means that it is a Set (mathematics), set with an addition operation (mathematics), operation that is associative, commutative, and inverti ...
,
free algebra In mathematics, especially in the area of abstract algebra known as ring theory, a free algebra is the noncommutative analogue of a polynomial ring since its elements may be described as "polynomials" with non-commuting variables. Likewise, the ...
,
free module In mathematics, a free module is a module that has a ''basis'', that is, a generating set that is linearly independent. Every vector space is a free module, but, if the ring of the coefficients is not a division ring (not a field in the commu ...
etc. It has the consequence that every algebra in a variety is a homomorphic image of a free algebra.


Category theory

Besides varieties, category theorists use two other frameworks that are equivalent in terms of the kinds of algebras they describe: finitary monads and Lawvere theories. We may go from a variety to a finitary monad as follows. A category with some variety of algebras as objects and homomorphisms as morphisms is called a finitary algebraic category. For any finitary algebraic category ''V'', the
forgetful functor In mathematics, more specifically in the area of category theory, a forgetful functor (also known as a stripping functor) "forgets" or drops some or all of the input's structure or properties mapping to the output. For an algebraic structure of ...
has a
left adjoint In mathematics, specifically category theory, adjunction is a relationship that two functors may exhibit, intuitively corresponding to a weak form of equivalence between two related categories. Two functors that stand in this relationship are k ...
, namely the functor that assigns to each set the free algebra on that set. This adjunction is monadic, meaning that the category ''V'' is equivalent to the
Eilenberg–Moore category In category theory, a branch of mathematics, a monad is a triple (T, \eta, \mu) consisting of a functor ''T'' from a category to itself and two natural transformations \eta, \mu that satisfy the conditions like associativity. For example, if F, ...
Set''T'' for the monad . Moreover the monad ''T'' is finitary, meaning it commutes with filtered colimits. The monad is thus enough to recover the finitary algebraic category. Indeed, finitary algebraic categories are precisely those categories equivalent to the Eilenberg-Moore categories of finitary monads. Both these, in turn, are equivalent to categories of algebras of Lawvere theories. Working with monads permits the following generalization. One says a category is an algebraic category if it is monadic over 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 algebra Sigma ( ; uppercase Σ, lowercase σ, lowercase in word-final position ς; ) is the eighteenth letter of the Greek alphabet. In the system of Greek numerals, it has a value of 200. In general mathematics, uppercase Σ is used as an operato ...
s 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 The theory of accessible categories is a part of mathematics, specifically of category theory. It attempts to describe categories in terms of the "size" (a cardinal number) of the operations needed to generate their objects. The theory originates i ...
.


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 In mathematics, and more precisely in semigroup theory, a variety of finite semigroups is a class of semigroups satisfying specific algebraic properties. Those classes can be defined in two distinct ways, using either algebraic notions or topologi ...
. 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. Namely, a class of finite monoids is a variety of finite monoids if and only if it can be defined by a set of profinite identities. Pseudovarieties are of particular importance in the study of finite
semigroup In mathematics, a semigroup is an algebraic structure consisting of a set together with an associative internal binary operation on it. The binary operation of a semigroup is most often denoted multiplicatively (just notation, not necessarily th ...
s and hence in
formal language theory In logic, mathematics, computer science, and linguistics, a formal language is a set of string (computer science), strings whose symbols are taken from a set called "#Definition, alphabet". The alphabet of a formal language consists of symbol ...
. Eilenberg's theorem, often referred to as the ''variety theorem'', describes a natural correspondence between varieties of
regular language In theoretical computer science and formal language theory, a regular language (also called a rational language) is a formal language that can be defined by a regular expression, in the strict sense in theoretical computer science (as opposed to ...
s and pseudovarieties of finite semigroups.


See also

*
Quasivariety In mathematics, a quasivariety is a class of algebraic structures generalizing the notion of variety by allowing equational conditions on the axioms defining the class. __TOC__ Definition A ''trivial algebra'' contains just one element. A qua ...


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