nLab
presentation of a category by generators and relations

Contents

Idea

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.

Definition

Let GG be a directed graph, and let RR be a function that assigns to each pair a,ba,b of objects of the free category F(G)F(G) a binary relation R a,bR_{a,b} on the hom-set F(G)(a,b)F(G)(a,b). The category with generators GG and relations RR 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)/RF(G)/R. For a category CC, an isomorphism CF(G)/RC\to F(G)/R is called a presentation of CC.

Properties

Writing can:F(G)F(G)/Rcan\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:F(G)DS\colon F(G)\to D that respects the relation RR (fR a,bgf R_{a,b}g implies S(f)=S(g)S(f)=S(g)), there exists a unique functor S:F(G)/RDS'\colon F(G)/R\to D with S=ScanS = S'\circ can.

Examples

  1. Every category CC has a presentation by generators and relations: Take GG as the underlying graph of CC, and for objects aa, bb, let R a,bR_{a,b} be the relation on F(G)(a,b)F(G)(a,b) consisting of all pairs of paths from aa to bb in GG whose arrows have the same composition in CC. However, there are sometimes more economical presentations for a category, as the following example shows.

  2. The augmented simplex category Δ a\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 Δ a\Delta_a follows from the fact that the arrows of Δ a\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 Δ a\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 (Δ a) inj(\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.

2-cells

A useful way to think of the relations is as being 2-cells between parallel pairs of arrows, thus if a,ba, b are objects, and (u,v)R a,b(u,v)\in R_{a,b}, we think of (u,v)(u,v) as a 2-cell (initially from uu to vv). 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.

References

  • 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.

Revised on February 24, 2012 21:17:18 by Tim Porter (95.147.237.232)