[ct/1] Natural Transforms, Products, Free Categories

Paris, Chennai

For the product set $X \times Y$, given $W, f, g$, and projections $p : X \times Y \mapsto X$, $q : X \times Y \mapsto Y$, the following diagram commutes:

$$ \begin{xy} \xymatrix{ & W \ar@{.>}[d]|{\exists! h} \ar[dl]_f \ar[dr]^g & \\ X & X \times Y \ar[l]_p \ar[r]^q & Y } \end{xy} $$

The unique function $h$ is given by $hw = \langle fw, gw \rangle$ for every $w \in W$.

The correspondence $h \mapsto \langle ph, qh \rangle = \langle f, g \rangle$ is given by the bijection:
$$\text{hom}(W, X \times Y) \cong \text{hom}(\langle W, W \rangle, \langle X, Y \rangle)$$

We write $\text{hom}(\langle U, V \rangle, \langle X, Y \rangle)$ for the pair of arrows $U \rightarrow X$ and $V \rightarrow Y$. The construction involves two additional constructions: $\Delta W = \langle W, W \rangle$ and $\langle X, Y \rangle \rightarrow X \times Y$. $\Delta$ is said to be left adjoint to the product $X \times Y$.

The one-point object $1 = \{0\}$ serves as identity for the "cartesian product" operation:
$$1 \times X \xrightarrow{\lambda} X \xleftarrow[]{\rho} X \times 1$$

given by $\lambda : \langle 0, x \rangle \rightarrow x$, $\rho : \langle x, 0 \rangle \rightarrow x$.

Monoid and group

A monoid is a set $M$ equipped with $\mu : M \times M \rightarrow M$ and $\eta : 1 \rightarrow M$ such that the following diagrams commute:

$$ \begin{xy} \xymatrix{ M \times M \times M \ar[r]^{1 \times \mu}\ar[d]^{\mu \times 1} & M \times M \ar[d]^{\mu} \\ M \times M \ar[r]^{\mu} & M } \end{xy} $$
$$ \begin{xy} \xymatrix{ 1 \times M \ar[r]^{\eta \times 1}\ar[d]^\lambda & M \times M \ar[d]^\mu & M \times 1 \ar[l]_{1 \times \eta}\ar[d]^\rho \\ M & M & M } \end{xy} $$

This means that $\mu \circ (\eta \times 1) = \lambda$ and $\mu \circ (1 \times \eta) = \rho$.

Writing it out in terms of the elements, we get the familiar associativity axioms:

$$ \begin{xy} \xymatrix{ \langle x, y, z \rangle \ar@{|->}[r]\ar@{|->}[d] & \langle xy, z \rangle \ar@{|->}[d] \\ \langle x, yz \rangle \ar@{|->}[r] & x(yz) = xy(z) } \end{xy} $$

and the identity axioms:

$$ \begin{xy} \xymatrix{ \langle 0, x \rangle \ar@{|->}[r]\ar@{|->}[d] & \langle u, x \rangle \ar@{|->}[d] \\ x \ar@{}[r]|{=} & ux } \end{xy} \begin{xy} \xymatrix{ \langle x, u \rangle \ar@{|->}[d] & \langle x, 0 \rangle \ar@{|->}[l]\ar@{|->}[d] \\ xu \ar@{}[r]|{=} & x } \end{xy} $$

Then a category can be defined as a monoid with "product over $O$":
$$A \times_0 A = \{\langle f, g \rangle \mid f, g \in A; \text{dom } f = \text{cod } g\}$$

We describe a group as a monoid with the additional operation $\eta : M \rightarrow M$ corresponding to $x \rightarrow x^{-1}$:

$$ \begin{xy} \xymatrix{ M \ar[d]\ar[r]^\delta & M \times M \ar[r]^{1 \times \eta} & M \times M \ar[d]^\lambda \\ 1 \ar[rr] & & M } \end{xy} \begin{xy} \xymatrix{ x \ar@{|->}[d]\ar@{|->}[r] & \langle x, x \rangle \ar@{|->}[r] & \langle x, x^{-1} \rangle \ar@{|->}[d] \\ 0 \ar@{|->}[rr] & & xx^{-1} = u } \end{xy} $$

Equivalently, a group is a category with one object, and in which every arrow has a two-sided inverse under composition.

$\Delta$ is a category with objects all finite ordinals, and arrows all order-preserving functions. From algebraic topology, it is called the simplicial category.


A functor is a morphism of categories. Let $T : B \rightarrow C$ be a functor of two categories. Then, the object function assigns to each object $b \in B$, an object $Tb \in C$; the arrow function assigns each arrow $b \rightarrow b' \in B$ to the arrow $Tb \rightarrow Tb' \in C$, in such a way that:
$$T_c(1) = 1_{Tc} \quad T(f \circ g) = Tf \circ Tg$$

the latter whenever $f \circ g$ is defined in $B$.

They arise naturally in algebraic topology, where we have a topological space $X$ lifted to a homology group $H_n(X)$; topological spaces map to abelian groups as $A : \textbf{Top} \rightarrow \textbf{Ab}$. In algebra, a forgetful functor would erase the group structure yielding $B : \textbf{Grp} \rightarrow \textbf{Set}$.

A functor is full when it is surjective, faithful when it is injective, fully faithful when it is bijective, in set-theoretic terms.

Functors also satisfy the law of associativity of compositions, just like the category does.


A subcategory $S$ of category $C$ includes some of the arrows in $C$, and:

  1. For each arrow $f$, the objects $\text{dom } f, \text{codom } f$
  2. For each object $s$, the identity arrow
  3. For each pair of arrows $s \rightarrow s' \rightarrow s''$, the composition of arrows

Natural transformation

A natural transformation is a morphism of functors. Given two functors $S, T : B \rightarrow C$, let $\tau : S \overset{\bullet}{\rightarrow} T$ be an NT. Then, every arrow $f : b \rightarrow b' \in S$ is mapped to $\tau_b = \tau b : Sb \rightarrow Sb' \in C$, so the following diagram commutes:

$$ \begin{xy} \xymatrix{ Sb \ar[r]^{\tau_b}\ar[d]^{Sf} & Tb \ar[d]^{Tf} \\ Sb' \ar[r]^{\tau_{b'}} & Tb' } \end{xy} $$

If we think of $S$ as giving a picture in $C$ of all objects and arrows in $B$, we get the following commutative diagrams:

$$ \begin{xy} \xymatrix{ a \ar[dd]^h\ar[dr]^f & \\ & b \ar[dl]^g \\ c & } \end{xy} \begin{xy} \xymatrix{ Sa \ar[rr]^{\tau_a}\ar[dr]^{Sf}\ar[dd]^{Sh} & & Ta \ar[dr]^{Tf}\ar[dd]|{\hole} & \\ & Sb \ar[rr]^<<<<<{\tau_b}\ar[dl]^{Sg} & & Tb \ar[dl]^{Tg} \\ Sc \ar[rr]^{\tau_c} & & Tc & } \end{xy} $$

$\tau_a, \tau_b, \tau_c$ are called the components of the NT. An NT with all components $\tau b$ invertible in $C$ is called a natural isomorphism. In this case, the the inverses $(\tau b)^{-1}$ are components of the NT $\tau^{-1} : T \rightarrow S$.

The determinant is an NT $\tau : \textbf{CRng} \overset{\bullet}{\rightarrow} \textbf{Grp}$. Let $\text{det}_K M$ be the determinant of matrix $M$ with entries in commutative ring $K$. $\text{det}_K$ is a morphism $\text{GL}_n K \overset{\bullet}{\rightarrow} K^*$ of groups.

$$ \begin{xy} \xymatrix{ \text{GL}_n K \ar[r]^{\text{det}_K}\ar[d]_{\text{GL}_n f} & K^* \ar[d]^{f^*} \\ \text{GL}_n K' \ar[r]_{\text{det}_{K'}} & K'^{*} } \end{xy} $$

For group $G$, the transform $p_G = G/[G, G]$ to the factor-commutator group defines a transform $p$ from the identity functor on $\textbf{Grp}$ to the factor-commutator functor $\textbf{Grp} \rightarrow \textbf{Ab} \rightarrow \textbf{Grp}$. Moreover, $p$ is natural, because the following diagram commutes:

$$ \begin{xy} \xymatrix{ G\ar[r]^{p_G}\ar[d]^f & G/[G, G]\ar[d]^{f'} \\ H\ar[r]^{p_H} & H/[H, H] } \end{xy} $$

The double character group yields an example in $\textbf{Ab}$. Let $D$ denote the character group of $G$ so that $D(G) = \text{hom}(G, \mathbb{R}/\mathbb{Z})$ is the set of all homomorphisms $G \rightarrow \mathbb{R}/\mathbb{Z}$ with the familiar group structure, so that $\mathbb{R}/\mathbb{Z}$ is the additive group of real numbers modulo $1$. Each arrow $f : G \rightarrow G'$ determines an arrow $Df : DG' \rightarrow DG$, in the opposite direction, in $\textbf{Ab}$, with $(D f) t = tf : G' \rightarrow \mathbb{R}/\mathbb{Z}$ for each $t$; for composable arrows $D (g \circ f) = Df \circ Dg$. For this reason, $D$ is a contravariant functor on $\textbf{Ab}$ to $\textbf{Ab}$. However, the twice iterated character group $G \mapsto D(DG)$ and identity $I(G) = G$ are both functors $\textbf{Ab} \rightarrow \textbf{Ab}$. For each group $G$, there is a homomorphism:
$$\tau_G : G \rightarrow D(DG)$$

obtained in the familar way: To each $g \in G$, assign the function $\tau_G : DG \rightarrow \mathbb{R}/\mathbb{Z}$ given for any character $t \in DG$, $t \mapsto tg$. Thus, $(\tau_G g) t = g(t)$, and $\tau : I \overset{\bullet}{\rightarrow} DD$ is an NT.

Equivalence between categories is defined to be the pair of functors $S : D \rightarrow C, T : C \rightarrow D$, along with the natural isomorphisms $I_C \cong T \circ S, I_D \cong S \circ T$. This allows us to compare categories which are "alike" but of different "sizes".

Monics, epis, and zeros

Arrow $e : a \rightarrow b \in C$ is invertible if there exists $e' : b \rightarrow a \in C$ with $e'e = 1_a, ee' = 1_b$. If $e'$ is unique, $e' = e^{-1}$, and the isomorphism $a \cong b$ holds.

For arrow $m : a \rightarrow b$, $m \circ a = m \circ b \implies a = b$ is the left cancelation property, and $m$ is termed monic. $a \circ m = b \circ m \implies a = b$ is the right cancelation property, and $m$ is termed epi. In $\mathbf{Set}$, monic arrows are injections and epi arrows are surjections.

For arrow $h : a \rightarrow b$, arrow $r : b \rightarrow a$ is right inverse if $hr = 1_b$; $r$ is termed as the section of $h$. Similarly, for $l : b \rightarrow a$, $lh = 1_a$, $l$ is termed as the retraction of $h$.

If, for each object $a \in C$, there exists exactly one arrow $a \rightarrow t$, $t$ is termed as the terminal object. On the other hand, for each object $a \in C$, there exists exactly one arrow $i \rightarrow a$, $i$ is termed as the initial object. In $\mathbf{Set}$, the empty set is initial, and any one-point set is terminal. An object which is both initial and final is called the null object $z \in C$; then there exists a unique arrow $a \rightarrow z \rightarrow b$, for any two objects $a, b \in C$ called the zero arrow.

A groupoid is a category in which all morphisms are invertible. An example would be the fundamental groupoid $\pi(X)$, from algebraic topology. A groupoid is said to be connected if there is an arrow between any two objects in the groupoid.


  1. $\textbf{Rng}$ is the category of all small rings
  2. $\textbf{Top}$ is the category of topological spaces, where objects are the set of small topological spaces, and morphisms are continuous maps between spaces
  3. $\textbf{Toph}$ is the category of topological spaces, where objects are the set of small topological spaces, and morphisms are homotopies
  4. $\textbf{Set}_*$ is the small category of pointed sets
  5. $\textbf{Top}_*, \textbf{Toph}_*$ are the categories of small pointed topological spaces; in the latter, morphisms are homotopies with a fixed basepoint $*$
  6. $\mathbf{R-Mod}$ is the category of small left R-modules
  7. $\mathbf{Vec}_F$ is the category of vector spaces
  8. $\mathbf{Rel}$ is the category of small sets, where morphisms are binary relations
  9. A concrete category is the pair $\langle C, U \rangle$, where $C$ is a category, and $U$ is a faithful functor $U : C \rightarrow \textbf{Set}$


$\text{hom}(a, b)$ is used to denote the set of all morphisms from $a$ to $b$. A small category can be defined in terms of hom-sets, with the following data:

  1. Objects $a, b, c, \ldots$
  2. For every pair of objects $\langle a, b \rangle$, a function associating $\text{hom}(a, b)$ to the pair
  3. For every triple $\langle a, b, c \rangle$, the composition axiom:
$$ \begin{xy} \xymatrix{ \text{hom}(c, d) \times \text{hom}(b, c) \times \text{hom}(a, b) \ar[r]\ar[d] & \text{hom}(b, d) \times \text{hom}(a, b) \ar[d] \\ \text{hom}(c, d) \times \text{hom}(a, c) \ar[r] & \text{hom}(a, d) } \end{xy} $$
  1. For every object $b$, $1_b \in \text{hom}(b, b)$; the identity axiom

An Ab-category or preaddive category is a category in which hom-sets are additive abelian groups, and composition is bilinear: given $f, f' : a \rightarrow b$, $g, g' : b \rightarrow c$,
$$(f + f') \circ (g + g') = f \circ g + f \circ g' + f' \circ g + f' \circ g'$$

$\textbf{Ab}, \textbf{R-Mod}, \textbf{Mod-R}$ are all Ab-categories. $\textbf{Ab-cat}$ is used the denote the category of all small Ab-categories.


We define $C^{op}$ to be the opposite category, with the same objects as $C$, and directions of arrows reversed. For each $f : a \rightarrow b \in C$, is an $f^{op} : b \rightarrow a \in C^{op}$. Also $f^{op} g^{op} = (gf)^{op}$. The assignments $A \mapsto A^{op}$ and $F \mapsto F^{op}$ define a covariant functor $\textbf{Cat} \rightarrow \textbf{Cat}$.

The opposite functor $F^{op} : B^{op} \rightarrow A^{op}$ is defined in the usual way. A functor $S : A^{op} \rightarrow B$ can be defined in terms of $A$ as $\bar{S}$, a contravariant functor. Then, $\bar{S}(m \circ n) = \bar{S}(n) \circ \bar{S}(m)$.

Hom-sets provide an example of covariant and contravariant functors. For each object $a \in C$, the object function of the covariant hom-functor sends:
$$C(a, -) = \text{hom}(a, -) : C \rightarrow \mathbf{Set}$$

and the arrow function sends each arrow $k : b \rightarrow b'$ to:
$$\text{hom}(a, k) : \text{hom}(a, b) \rightarrow \text{hom}(a, b')$$

For each object $b \in C$, the object function of the contravariant hom-functor sends:
$$C(-, b) = \text{hom}(-, b) : C^{op} \rightarrow \mathbf{Set}$$

and the arrow function sends each arrow $g : a \rightarrow a'$ to:
$$\text{hom}(g, b) : \text{hom}(a', b) \rightarrow \text{hom}(a, b)$$

To simplify the noation, introduce $k_*$ for "composition with k on the left" or "composition induced by k", and $g^*$ for "composition with g" on the right:
$$k_* f = k \circ f \quad g^* f = f \circ g$$

For $k : a \rightarrow a'$ and $g : b \rightarrow b'$, we have:

$$ \begin{xy} \xymatrix{ \text{hom}(a', b) \ar[r]^{k^*}\ar[d]^{g_*} & \text{hom}(a, b) \ar[d]^{g_*} \\ \text{hom}(a', b') \ar[r]^{k^*} & \text{hom}(a, b') } \end{xy} $$

Product structure

$P_1$ along with $X$ and $Y$ defines a product. There exists a unique morphism between $P_1$ and $P_2$ preserving the product structure.

$$ \begin{xy} \xymatrix{ P_2 \ar@/_/[ddr]_N \ar@{.>}[dr]|{\exists!} \ar@/^/[drr]^M \\ & P_1 \ar[d]^Q \ar[r]_P & X \\ & Y & } \end{xy} $$

$P, Q$ are functors called projections of $P_1$ onto $X$ and $Y$. Elements of $P_1$ are pairs $\langle x, y \rangle$. $P, Q$ are said to be universal among functors to $X$ and $Y$.

Let $U : X \rightarrow Y, V : X' \rightarrow Y'$ be two functors; then $U \times V : X \times Y \rightarrow X' \times Y'$ is the product of two functors, and we yield the following commutative diagram:

$$ \begin{xy} \xymatrix{ X \ar[d]^{U} & X \times Y \ar[l]_P\ar[r]^Q\ar@{.>}[d]|{U \times V} & Y \ar[d]^{V} \\ X' & X' \times Y' \ar[l]_{P'}\ar[r]^{Q'} & Y' } \end{xy} $$

Thus, $\times$ is a pair of functions, assigning to each pair of categories $\langle X, Y \rangle$, the category $X \times Y$, and to each pair of functors $\langle U, V \rangle$, the functor $U \times V$. Moreover, when $U \circ U'$ and $V \circ V'$ are defined, we have $(U \times U') \circ (V \times V') = UU' \times VV'$. This makes $\times$ into a functor:
$$\times : \textbf{Cat} \times \textbf{Cat} \rightarrow \textbf{Cat}$$

Functor $S : B \times C \rightarrow D$ is defined to be a bifunctor or a functor in two variable objects. Hom-sets may be described as bifunctors $\text{hom} : C^{op} \times C \rightarrow \textbf{Set}$.

Consider an NT $\alpha$ between bifunctors $S, S' : B \times C \rightarrow D$. Let $\alpha$ be a function which assigns to every pair of objects $b \in B, c \in C$, the arrow $\alpha(b, c) : S(b, c) \rightarrow S'(b, c)$. $\alpha$ is called natural in $b$ if, for every $c \in C$:
$$\alpha(-, c) : S(-, c) \overset{\bullet}{\rightarrow} S'(-, c)$$

For bifunctors $S, S'$, $\alpha$ is an NT of bifunctors $\alpha : S \rightarrow S'$, iff $\alpha(b, c)$ is natural in $b$ for every $c \in C$ and natural in $c$ for every $b \in B$.

Consider the product category $C \times \textbf{2}$, where $\textbf{2}$ is the category of the two-point set $\{0, 1\}$:

$$ \begin{xy} \xymatrix{ & & \bullet \ar[dr] & \\ C \times 1 & \bullet \ar[rr]\ar[ur] & & \bullet \\ & & \bullet \ar[dr]\ar@{.>}[uu] & \\ C \times 0 & \bullet \ar[rr]\ar[ur]\ar[uu] & & \bullet \ar[uu] } \end{xy} $$

Here $T_0, T_1 : C \rightarrow C \times \mathbf{2}$ are functors from "bottom" to "top". $T_0 f = \langle f, 0 \rangle$, $T_1 f = \langle f, 1 \rangle$. If $\uparrow : 0 \rightarrow 1$ denotes the unique non-identity arrow in $\mathbf{2}$, then $T_0, T_1$ are defined by:
$$\mu : T_0 \overset{\bullet}{\rightarrow} T_1 \quad \mu c = \langle c, \uparrow \rangle$$

for any object $c$. It maps "bottom" to "top", and is natural. We call $\mu$ the universal natural transform from $C$.

Functor category

Consider functors $R, S, T : C \rightarrow B$ and NTs $\sigma : R \overset{\bullet}{\rightarrow} S, \tau : S \overset{\bullet}{\rightarrow} T$. Define $(\tau \bullet \sigma) c = \tau c \circ \sigma c$, which are components of the NT $\tau \bullet \sigma : R \overset{\bullet}{\rightarrow} T$. To show that $\tau \bullet \sigma$ is natural, let $f : c \rightarrow c' \in C$ in the commutative diagram:

$$ \begin{xy} \xymatrix{ Rc \ar[r]^{Rf}\ar[d]^{\sigma_c}\ar@/_2pc/[dd]_{(\tau \bullet \sigma) c} & Rc' \ar[d]^{\sigma_{c'}}\ar@/^2pc/[dd]^{(\tau \bullet \sigma) c'} \\ Sc \ar[r]^{Sf}\ar[d]^{\tau_c} & Sc' \ar[d]^{\tau_{c'}} \\ Tc \ar[r]^{Tf} & Tc' } \end{xy} $$

The functor category may be written as $B^C = \text{Funct}(C, B)$, with objects the functors $T : C \rightarrow B$, and morphisms the NTs between two such functors. The hom-set for this category is:
$$\text{Nat}(S, T) = B^C(S, T) = \{\tau \mid \tau : S \overset{\bullet}{\rightarrow} T\}$$

If $B = \{0, 1\}$, the category $\{0, 1\}^C$ is isomorphic to the powerset of $C$, $\mathscr{P}C$. For any category $B$, $B^1$ is isomorphic to $B$, and $B^2$ is the category whose objects are arrows $f : a \rightarrow b$ of $B$, and whose arrows $f \rightarrow f'$ are those that, along with pair $\langle h, k \rangle$, make the following diagram commute:

$$ \begin{xy} \xymatrix{ a \ar[r]^h\ar[d]^f & a' \ar[d]^{f'} \\ b \ar[r]^k & b' } \end{xy} $$

Category of all categories

Given three categories and four NTs, we have:

$$ \begin{xy} \xymatrix{ A \ar@<-2ex>[r] \ar[r]_{\downarrow \tau} \ar@<2ex>[r]_{\downarrow \sigma} & B \ar@<-2ex>[r]\ar[r]_{\downarrow \tau'} \ar@<2ex>[r]_{\downarrow \sigma'} & C } \end{xy} $$

The vertical and horizontal composities satisfy the interchange law:

$$ (\tau' \bullet \sigma') \circ (\tau \bullet \sigma) = (\tau' \circ \tau) \bullet (\sigma' \circ \sigma) $$

The collection of all NTs is the set of arrows of two different categories under two different operations of composition, $\circ$ and $\bullet$, which satisfy the above interchange law. Moreover, any arrow that is identity for the composition $\circ$ is also identity for the composition $\bullet$. To prove this, notice that objects for the horizontal composition $\circ$ are the categories, for vertical composition, the functors. Notice that the objects and arrows of $C$ may be written as $c : \textbf{1} \rightarrow C$ and $f : \textbf{2} \rightarrow C$. Then, the symbols such as $\sigma \circ c = \sigma c$ have their accepted meaning in a situation such as:

$$ \begin{xy} \xymatrix{ \textbf{1}\ar[r]^c & C \ar@<1ex>[r]_{\downarrow \sigma}\ar@<-1ex>[r] & B } \end{xy} $$

Comma category

If $b$ is an object of category $C$, $(b \downarrow C)$ is a category in which objects are objects of $\langle f, c \rangle$, where $f : b \rightarrow c$, and arrows $h : \langle f, c \rangle \rightarrow \langle f', c' \rangle$, such that $h \circ f = f'$:

$$ \begin{xy} \xymatrix{ & b \ar[ld]_f \ar[rd]^{f'} & \\ c \ar[rr]^h & & c' } \end{xy} $$

Example: If $\mathbf{*}$ denotes a one-point set, $(\mathbf{*} \downarrow \mathbf{Set})$ denotes the category of pointed sets.

If $b$ is an object of category $C$, and $S : D \rightarrow C$ a functor, the category $(b \downarrow S)$ of objects under $b$ has as objects pairs $\langle f, d \rangle$, where $d \in \text{Obj } D$ and $f : b \rightarrow Sd$, and arrows $h : \langle f, d \rangle \rightarrow \langle f', d' \rangle$ all those arrows $h : f \rightarrow f'$ such that $Sh \circ f = f'$:

$$ \begin{xy} \xymatrix{ & b \ar[ld]_f \ar[rd]^{f'} & \\ Sd \ar[rr]^{Sh} & & Sd' } \end{xy} $$

Consider $C \xleftarrow{T} A \xrightarrow{S} B$ where $S$ and $T$ are NTs. Then the category $(T \downarrow S)$, also written as $(T, S)$ is called the comma category. It has as objects triples $\langle c, b, f \rangle$, and as arrows $\langle c, b, f \rangle \rightarrow \langle c', b', f' \rangle$ all pairs $\langle k, h \rangle$ of arrows $k : c \rightarrow c'$, $h : b \rightarrow b'$ such that $f' \circ Tk = Sh \circ f$:

$$ \begin{xy} \xymatrix{ Tc \ar[r]^{Tk}\ar[d]_f & Tc' \ar[d]^{f'} \\ Sb \ar[r]^{Sh} & Sb' } \end{xy} $$

We get the following diagram when we consider projections of the comma category:

$$ \begin{xy} \xymatrix{ & & \langle c, b, f : Tc \rightarrow Sb \rangle \ar@{|->}[d]\ar@{|->}[lld]\ar@{|->}[rrd] & & \\ b \ar@{|->}[r] & Sb & (f : Tc \rightarrow Sb) \ar@{|->}[l]\ar@{|->}[r] & Tc & c \ar@{|->}[l] } \end{xy} $$

Graphs and free categories

A graph may be pictured, like a category, with objects as vertices and arrows as edges, except that there are no identity or composite arrows; for this reason, it may be called a precategory.

A directed graph is a set of objects $O$ and a set $A$ of arrows $f$ such that there exists a pair of arrows:

$$ \begin{xy} \xymatrix{ A \ar@<-.5ex>[r]_{\partial_1} \ar@<.5ex>[r]^{\partial_0} & O & \partial_0 f = \text{dom } f & \partial_1 f = \text{codom } f } \end{xy} $$

A morphism between graphs $D : G \rightarrow G'$ is a pair of functions $D_O : O \rightarrow O'$ and $D_A : A \rightarrow A'$ such that:
$$D_O \partial_0 f = \partial_0 D_A f \quad D_O \partial_1 f = \partial_1 D_A f$$

A forgetful functor $U : \textbf{Cat} \rightarrow \textbf{Grph}$ is defined as follows: for every $F : C \rightarrow C'$, there exists $UF : UC \rightarrow UC'$.

Let $O$ be a fixed set. An O-graph has O as its objects; a morphism $D$ of $O$-graphs will be one with $D_O : O \rightarrow O$ as identity. If $A$ and $B$ are two $O$-graphs, then product over $O$ is defined as:
$$A \times_O B = \{\langle f, g \rangle \mid \partial_0 f = \partial_1 g, f \in A, g \in B\}$$

The definitions $\partial_0 \langle f, g \rangle = f, \partial_1 \langle f, g \rangle = g$ make this a graph.

A category with objects $O$ may be described as an O-graph equipped with the two morphisms $c : A \times_O A \rightarrow A$ and $i : O \rightarrow A$, composition and identity, such that the following commute:

$$ \begin{xy} \xymatrix{ A \times_O A \times_O A \ar[r]^{c \times 1}\ar[d]^{1 \times c} & A \times_O A \ar[d]^c \\ A \times_O A \ar[r]^c & A } \end{xy} \begin{xy} \xymatrix{ O \times_O A \ar[r]^{i \times 1}\ar[d]^\cong & A \times_O A \ar[d]^c & A \times_O O \ar[l]_{1 \times i}\ar[d]^\cong \\ A & A & A } \end{xy} $$

A free category may be "generated by a graph" $G$ having the same set of objects $O$, and morphisms composition on edges of the graph, and this is written as $C_G$. Given $D : B \rightarrow C$, we get the following diagram in terms of underlying graphs:

$$ \begin{xy} \xymatrix{ G \ar[r]\ar[dr] & UB \ar@{.>}[d]|{\exists! UD} \\ & UC } \end{xy} $$

There is a bijective correspondence between categories and their underlying graphs:
$$\textbf{Cat}(C_G, B) \cong \textbf{Grph}(C, UB)$$

Quotient category

Let $C$ be a category and $R_{a, b}$ be a relation defined on the hom-set. Then, quotient category $C/R$ is defined in terms of a universal functor $Q$:

$$ \begin{xy} \xymatrix{ C \ar[r]^Q \ar[d]_H & C/R \ar@{.>}[dl]|{\exists! P} \\ D & } \end{xy} $$

If $C = \textbf{Top}$, and $fRf'$ is the homotopy equivalence between $f$ and $f'$, then quotient category $C/R$ is $\textbf{Toph}$ with objects topological spaces and arrows homotopy classes of continuous maps. If $C$ is a free category generated by a graph $G$, $C/R$ is said to have generators $G$ and relations $R$.