nLab
generators and relations

Generators and relations

Idea

A mathematical structure is said to be presented by generators and relations if it is obtained from a structure freely generated by a set of generators by imposing relations among these generators.

For instance an associative algebra AA may be obtained by imposing on the tensor algebra of the underlying vector space (which is the free algebra on that vector space) the product relations, which identify the formal juxtaposition of two elements with their intended product. This is for instance how Clifford algebras or universal enveloping algebras are traditionally defined.

Similarly a group presentation specifies a group in terms of a set of generators and relations. The study of group presentations form and important part of combinatorial group theory.

But the concept of generators and relations is very general and applies to all kinds of structures. Below we discuss a general formalization using concepts from category theory and universal algebra.

Definition

Let CC be a category, TT a monad on CC, and AA a TT-algebra. A presentation of AA by generators and relations is a coequalizer diagram

TRTGA T R \; \rightrightarrows \; T G \to A

in the category C TC^T of TT-algebras. Here GCG\in C is the object of generators and RCR\in C is the object of relations.

The TT-algebra map TGAT G \to A corresponds to a unique morphism GAG\to A in CC, which we think of as the “inclusion” of the generators into AA (though in general it need not be any kind of monomorphism). Similarly, the TT-algebra maps TRTGT R \;\rightrightarrows\; T G correspond to unique morphisms RTGR \;\rightrightarrows\; T G in CC, which we think of as a binary relation on TGT G (though in general, the maps need not be jointly monic either).

This definition can be generalised to any concrete category with free objects, not necessarily monadic.

Examples

Monads on Set

The classical case is when C=C=Set. Then GG and RR are sets, and a presentation of a TT-algebra by generators and relations amounts to first constructing the free TT-algebra TGT G on the generators, then specifying (via the maps RTGR \;\rightrightarrows\; T G) a set of pairs of elements of TGT G to be identified (the relations). The presented TT-algebra AA is the quotient set by these relations.

Probably the most classical case is when TT is the free group monad on SetSet.

Categories

Cat (to be precise, Str Cat) is the category of algebras for a monad on the category of quivers. Therefore, we have a notion of a presentation of a category by generators and relations.

Theories and Monads

Lawvere theories, operads, and even (accessible) monads can be realized as the algebras for monads on some categories. Thus, we can talk about presentations of these sorts of objects by generators and relations. In this context, each “generator” is an operation, and each “relation” is an axiom that the operations must satisfy. For instance, the usual definition of a group in terms of binary, nullary, and unary operations satisfying associativity, unitality, and inversion axioms can be regarded as a presentation of the Lawvere theory (or monad) of groups by generators and relations.

Existence

Theorem

Every TT-algebra has a presentation by generators and relations.

Proof

For any TT-algebra AA, the following diagram is a coequalizer:

T 2AμTaTAaA T^2 A \; \underoverset{\mu}{\T a}{\rightrightarrows}\; T A \xrightarrow{a} A

where a:TAAa\colon T A \to A is the structure map of the TT-algebra AA and μ\mu is the multiplication of the monad TT.

This particular presentation is of importance in the monadicity theorem.

However, in practice one is usually interested in more “economical” presentations where GG and RR are smaller than AA. For example, for monads over Set, when GG and RR are finite sets, then we say that AA is finitely presented.

Remarks

Note that knowing only the category of TT-algebras does not suffice to determine the notion of “presentation by generators and relations”; we also have to exhibit it as the category of algebras for a monad TT on some other category CC. Often the choice of CC is obvious, but there are cases in which the same category can be realized as the category of algebras for multiple monads on multiple different categories, yielding different notions of “generators and relations”. For example, the category of finitary monads on SetSet (= Lawvere theories) can be realized as monadic over the category of finitary endofunctors of Set, or over the category of \mathbb{N}-indexed sets.

Categorifications

If CC is an n-category and TT a suitable sort of monad, then we have a similar notion except that coequalizers must be replaced by (nn-truncated) codescent objects?, i.e. geometric realization.

Revised on July 1, 2013 22:21:22 by Urs Schreiber (131.174.42.143)