Similarly to the presentation of groups by generators and relations, a category may be presented by a set of generating arrows subject to certain relations.
Let $G$ be a directed graph, and let $R$ be a function that assigns to each pair $a,b$ of objects of the free category $F(G)$ a binary relation $R_{a,b}$ on the hom-set $F(G)(a,b)$. The category with generators $G$ and relations $R$ is the quotient category (as defined in Mac Lane or Mitchell, for example – this is not the nLab definition due to issues of evil) $F(G)/R$. For a category $C$, an isomorphism $C\to F(G)/R$ is called a presentation of $C$.
Writing $can\colon F(G)\to F(G)/R$ for the canonical functor, it follows from the universal property of the quotient category that for any functor $S\colon F(G)\to D$ that respects the relation $R$ ($f R_{a,b}g$ implies $S(f)=S(g)$), there exists a unique functor $S'\colon F(G)/R\to D$ with $S = S'\circ can$.
Every category $C$ has a presentation by generators and relations: Take $G$ as the underlying graph of $C$, and for objects $a$, $b$, let $R_{a,b}$ be the relation on $F(G)(a,b)$ consisting of all pairs of paths from $a$ to $b$ in $G$ whose arrows have the same composition in $C$. However, there are sometimes more economical presentations for a category, as the following example shows.
The augmented simplex category $\Delta_a$ is generated by the face maps and the degeneracy maps, subject to the simplicial relations (see simplex category for details). The existence of a functor from the quotient category to $\Delta_a$ follows from the fact that the arrows of $\Delta_a$ do satisfy the simplicial relations, and the fact that this functor is an isomorphism may be verified using the unique decomposition of an arrow of $\Delta_a$ as the composition of degeneracies of decreasing index followed by the composition of face maps of increasing index (see the lemma on p. 177 of Mac Lane). Similarly, the subcategory $(\Delta_a)_{inj}$ consisting of all monics (injective monotone functions in our case) is generated by the face maps subject to the single simplicial relation involving only face maps.
A useful way to think of the relations is as being 2-cells between parallel pairs of arrows, thus if $a, b$ are objects, and $(u,v)\in R_{a,b}$, we think of $(u,v)$ as a 2-cell (initially from $u$ to $v$). In this way, one can encode rewriting systems of a certain kind in terms of the embryonic data for a 2-category. This is discussed more in the entry on computad, which are also called polygraphs.
Barry Mitchell, Introduction to Category Theory and Homological Algebra, in P. Salmon (Ed.), Categories and Commutative Algebra. Springer, 2010. pp. 108-112.
Barry Mitchell, Rings with several objects, Advances in Mathematics 8 (1972), 1–161.
Last revised on February 24, 2012 at 21:17:18. See the history of this page for a list of all contributions to it.