nLab variety of algebras

Redirected from "word problem".

Idea

The notion of variety of algebras is a classical notion from universal algebra that subsumes nearly all of the usual kinds of algebraic objects, such as groups, rings, vector spaces (over a fixed field), and so on. Those algebraic objects that do not form a variety of algebras, such as fields, can still usually be easily described as a subcategory of some variety of algebras (in this case, commutative rings).

A variety of algebras is not to be confused with an algebraic variety, although in fact there is a connection: both concepts are (roughly speaking) given by a set of equations, but an algebraic variety is the set of elements (of a fixed generic structure) that satisfy the equations, while a variety of algebras is the class of structures in which every element satisfies the equations.

Definitions

A signature (in this context) is a set, whose elements are called operations, to each of which is assigned a cardinal number (0,1,2,0, 1, 2, \ldots) called its arity. A signature is finitary if its set of operations is finite (in the strictest sense for the purposes of constructive mathematics) and every arity is finite (so a natural number); similar definitions apply to other arity classes. Given a signature σ\sigma and a set VV, whose elements are called variables1, a word (in σ\sigma using VV) is a (well-founded directed 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 oo has as many branches away from the root as the arity of oo. An axiom (in σ\sigma using VV) is a pair of such words; we write the axiom consisting of the words vv and ww as v=wv = w or v=w\vdash v = w. A theory (in our sense) consists of a signature σ\sigma and a set of axioms in σ\sigma. An algebraic theory is finitary if its signature is finitary and its set of equational axioms is finite (Kuratowski-finite in constructive mathematics); analogous remarks apply to other arity classes.

A variety of algebras is given precisely by a theory in this sense, but it is more usual to think of the variety as being the class (or category) of models, so we continue with the definitions.

Given a theory TT, a model or algebra of TT consists of a set AA together with, for each operation of TT with arity κ\kappa, a function to AA from its κ\kappath cartesian power A κA^\kappa such that, for each axiom v=w\vdash v = w and each assignment of elements of AA to the variables in that axiom, the equation holds that is given by applying the operations to the elements of AA as indicated by the trees defining vv and ww (the meaning of which we hope is obvious). We say that AA carries the operations and satisfies the axioms.

Given a algebras AA and BB of the same (quasi)-algebraic theory, a homomorphism from AA to BB consists of a function f:ABf\colon A \to B such that, for each operation, the diagram

A κ f κ B n A f B \array { A^\kappa & \stackrel{f^\kappa}\rightarrow & B^n \\ \downarrow & & \downarrow \\ A & \stackrel{f}\rightarrow & B }

commutes. We say that ff preserves the operations.

It is fairly straightforward to define a model (and homomorphisms) in any cartesian monoidal category CC, replacing Set in the two paragraphs above. But note that the operations and axioms still form sets, not objects of CC; the theory TT is independent of the modelling category. In any case, given any theory TT and any cartesian monoidal category CC, the models of TT in CC (as objects) and the homomorphisms between them (as morphisms) form a category, which is the variety of TT-algebras in CC.

Generalisations

A sorted variety or many-sorted variety is a generalisation. A sorted signature or many-sorted signature consists of a set, whose elements are called sorts, together with operations and arities as before, except that now an arity is a list of input sorts instead of merely a natural number (the length of the list) together with one output sort. Each variable in an axiom comes equipped with a sort, which we may also classify as an output sort; then each branch in (the tree reprsenting) a word must link output sort to input sort. The root of a word gives the entire word a sort; the two words in an equational axiom must have the same sort. Then a model of a sorted variety consists of one set for each sort, and the rest should be obvious. A sorted variety is finitary if it satisfies the finitarity conditions of a variety and its set of sorts is also finite. An ordinary variety as above may be called unsorted or single-sorted to avoid invoking the red herring principle; it is the same thing as a sorted variety with exactly one sort.

Another generalisation is a quasivariety. While an axiom in a variety gives an equation, an axiom in a quasivariety is a Horn clause, stating that one equation (the consequent) holds whenever each equation in some set of equations (the premises) holds. A Horn clause is finitary if this set of premises is (Kuratowski)-finite; a quasivariety is finitary if it satisfies the fintarity conditions of a variety and additionally each Horn clause is finitary. An ordinary variety is a quasivariety in which each Horn clause has an empty set of premises.

Examples

For each definition of an appropriate algebraic object, there is a corresponding variety of algebras, a few of which are given below:

  • The variety of groups is given by a theory with three operations m,e,im,e,i (traditionally called multiplication, identity, and inverse), with respective arities 2,0,12,0,1 (so multiplication is a binary operation, identity is a nullary operation, and inverse is a unary operation). There are five axioms, given by the following pairs of trees (with their traditional names):

    • associative law:
      (1) m m z x y= m x m y z \array { & & & & m \\ & & & \nearrow & & \nwarrow \\ & & m & & & & z \\ & \nearrow & & \nwarrow \\ x & & & y } \;\;\;=\;\;\; \array { & & m \\ & \nearrow & & \nwarrow \\ x & & & & m \\ & & & \nearrow & & \nwarrow \\ & & y & & & & z }
    • right unit law:
      (2) m x e=x \array { & & m \\ & \nearrow & & \nwarrow \\ x & & & & e } \;\;\;=\;\;\; \array { x }
    • left unit law:
      (3) m e x=x \array { & & m \\ & \nearrow & & \nwarrow \\ e & & & & x } \;\;\;=\;\;\; \array { x }
    • right inverse law:
      (4) m x i x=e \array { & & m \\ & \nearrow & & \nwarrow \\ x & & & & i \\ & & & & \uparrow \\ & & & & x } \;\;\;=\;\;\; \array { e }
    • left inverse law:
      (5) m i x x=e \array { & & m \\ & \nearrow & & \nwarrow \\ i & & & & x \\ \uparrow \\ x } \;\;\;=\;\;\; \array { e }

    Then a model of this variety is a set AA together with functions m:A 2Am\colon A^2 \to A, e:1Ae\colon 1 \to A (which may be identified with an element of AA), and i:AAi\colon A \to A such that, for all x,y,zx,y,z in AA, m(m(x,y),z)=m(x,m(y,z))m(m(x,y),z) = m(x,m(y,z)), m(e,x)=xm(e,x) = x, m(x,e)=xm(x,e) = x, m(x,i(x))=em(x,i(x)) = e, and m(i(x),x)=em(i(x),x) = e. In other words, an algebra in this variety is simply a group. Similarly, a homomorphism of such algebras is simply a group homomorphism. Also, an algebra in this variety in the category CC is a group object in CC.

Note that it is not necessary to draw explicit trees; these can be recovered from the succinct equations like m(m(x,y),z)=m(x,m(y,z))m(m(x,y),z) = m(x,m(y,z)); we will do this below.

  • The variety of monoids is given by a subtheory of the theory of groups. It has only the operations m,em,e and the axioms (1),(2),(3). An algebra in this theory is a monoid, and a homomorphism of such algebras is a monoid homomorphism (including the condition that it preserve the identity).

  • There is no variety of cancellative monoids, but there is a quasivariety of them. In addition to the axioms for a monoid, we have an axiom stating that the equation x=yx = y follows from the equation m(x,z)=m(y,z)m(x,z) = m(y,z), which we write succinctly as m(x,z)=m(y,z)x=ym(x,z) = m(y,z) \vdash x = y.

  • The variety of abelian groups is given by a supertheory of the theory of groups. In addition to the operations and axioms of the variety of groups, it has an additional axiom, the commutative law: m(x,y)=m(y,x)m(x,y) = m(y,x).

  • The variety of (associative unital) rings has five operations a,z,n,m,ea,z,n,m,e, with respective arities 2,0,2,0,12,0,2,0,1, and ten axioms. Five of these axioms are those of groups, applied to a,z,na,z,n in place of m,e,im,e,i; three of these axioms are those of monoids (applied to m,em,e as before). The remaining two axioms are:

    • left distributive law: m(x,a(y,z))=a(m(x,y),m(x,z))m(x,a(y,z)) = a(m(x,y),m(x,z)),
    • right distributive law: m(a(x,y),z)=a(m(x,z),m(y,z))m(a(x,y),z) = a(m(x,z),m(y,z)).
  • There is no variety or quasivariety of fields; the elements with multiplicative inverses are not identified by an equation. One can, however, define fields as certain rings and then get the correct notion of field homomorphism as a ring homomorphism between rings that happen to be fields.

  • The variety of (real) vector spaces has infinitely many operations and axioms (so is not finitary). First, there are operations a,z,na,z,n with the arities and axioms of an abelian group (as with rings). In addition, there is one operation m rm_r of arity 11 for each real number rr, satisfying these axioms:

    • left distributive law: for each real number rr, m r(a(x,y))=a(m r(x),m r(y))m_r(a(x,y)) = a(m_r(x),m_r(y)),
    • right distributive law: for each real number rr and real number ss, m r+s(x)=a(m r(x),m r(y))m_{r+s}(x) = a(m_r(x),m_r(y)) (where r+sr + s is the sum of rr and ss as real numbers),
    • associative law: for each real number rr and real number ss, m rs(x)=m r(m s(x))m_{r s}(x) = m_r(m_s(x)) (where rsr s is the product of rr and ss as real numbers),
    • unit law: m 1(x)=xm_1(x) = x (where 11 the real number 1).
  • There is a similar variety of vector spaces over any given ground field, but there is no variety of vector spaces over arbitrary fields, since we would have to specify the field as well as the vector space. The problem is not really that there is no variety of fields; there is no variety of (left) modules over arbitrary commutative rings either. However, there is a sorted variety of modules over arbitrary rings, with two types, one for the ring and one for the module. Even though this variety includes the non-finitary variety of real vector spaces, it is itself a finitary sorted variety.

As algebraic theories

A variety of algebras is one way to look at an algebraic theory.

As a logical theory, everything that we wish to say can be said in (typed or untyped, to match the variety) cartesian logic (although one might want to use something stronger, such as full classical or intuitionistic predicate logic with equality). We use one function symbol (of matching arity) for each operation, and each axiom in the variety becomes an axiom in the logic, a universally quantified equation. Then the models of this logical theory are the same as the algebras in the variety.

As a Lawvere theory, an untyped finitary variety of algebras defines a category LL whose objects are of the form A nA^n for nn a natural number. The morphisms of the category are those which are necessary to make A nA^n the nn-fold product of AA, along with one morphism for each operation in the variety. Each axiom of the variety corresponds to a commutative diagram, and LL is freely generated by these as a sketch. Then the models of the variety in a cartesian monoidal category CC are the same as the product-preserving functors from LL to CC. Conversely, any locally small (and hence small) cartesian monoidal category whose objects are all of the form A nA^n may be thought of as a Lawvere theory and defines an untyped variety of algebras, with operation for each morphism to AA and one axiom for each commutative diagram. (This can all be generalised to sorted varieties as well.)

A variety of algebras can be seen as a cartesian version of a (typed or untyped) operad; whereas an operad has models in any symmetric monoidal category, a variety of algebras has models only in a cartesian monoidal category.

A variety of algebras is traditionally identified with its category MM of models in SetSet (or even with simply the class of objects of this category), but it then becomes unclear what an algebra in the variety would be in some other category CC. However, it is worth noting that MM is always an algebraic category; see below for the construction of free objects.

Free algebras

Given a variety VV and a cartesian monoidal category CC (such as SetSet), let C VC^V be the category of algebras in VV in CC, with homomorphisms as morphisms. There is an obvious forgetful functor U:C VCU\colon C^V \to C; CC is a cocomplete WW-pretopos (or if CC is just a WW-pretopos if VV is finitary), then UU has a left adjoint, the free functor F:CC VF\colon C \to C^V. In fact, this adjunction is monadic; we can identify the models of VV in CC with the modules/algebras of the monad UFU \circ F.

Given an object AA of CC, we construct the free algebra F(A)F(A) as follows. First, let W(A)W(A) be the inductive type in CC given by the signature of VV, that is the initial algebra of the endofunctor A oA #oA \mapsto \sum_o A^{\#o}, where oo ranges over the operations of VV and #o\#o is the arity of oo. Then each axiom specifies an internal binary relation on W(A)W(A); the colimit of these is F(A)F(A). Note that, if CC is SetSet and AA is a set, then W(A)W(A) consists precisely of the words (defined as trees above) with variables from AA.

The word problem for a variety VV consists of deciding, whenever AA is a finite set, whether two elements of W(A)W(A) are equal in F(A)F(A). As a problem in algorithmic decidability, the word problem can be very difficult; for example, it is:

even though each of these is a supertheory of the next.

Literature

  • Jiří Adámek, F.W. Lawvere, J. Rosický, On the duality between varieties and algebraic theories, Algebra universalis 2003, 49:1, pp 35–49 doi

  1. For a finitary signature, we may without loss of generality use the set V{x 0,x 1,x 2,}V \coloneqq \{x_0, x_1, x_2, \ldots\}, effectively the set of natural numbers, as the only set of variables; similar remarks apply to other arity classes.

Last revised on January 25, 2024 at 23:49:35. See the history of this page for a list of all contributions to it.