Let be a directed graph, and let be a function that assigns to each pair of objects of the free category a binary relation on the hom-set . The category with generators and relations is the quotient category (as defined in Mac Lane or Mitchell, for example – this is not the nLab definition due to issues of evil) . For a category , an isomorphism is called a presentation of .
Writing for the canonical functor, it follows from the universal property of the quotient category that for any functor that respects the relation ( implies ), there exists a unique functor with .
Every category has a presentation by generators and relations: Take as the underlying graph of , and for objects , , let be the relation on consisting of all pairs of paths from to in whose arrows have the same composition in . However, there are sometimes more economical presentations for a category, as the following example shows.
The augmented simplex category 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 follows from the fact that the arrows of 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 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 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 are objects, and , we think of as a 2-cell (initially from to ). 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.