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

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

## Functor

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](/at/1#homology) \(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.

## Subcategory

A subcategory \(S\) of category \(C\) includes some of the arrows in \(C\), and:

- For each arrow \(f\), the objects \(\text{dom } f, \text{codom } f\)
- For each object \(s\), the identity arrow
- 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]^{Sb} & 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](/la#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 by, 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.

## Examples

- \(\textbf{Rng}\) is the category of all small rings
- \(\textbf{Top}\) is the category of topological spaces, where objects are the set of small topological spaces, and morphisms are continuous maps between spaces
- \(\textbf{Toph}\) is the category of topological spaces, where objects are the set of small topological spaces, and morphisms are homotopies
- \(\textbf{Set}_*\) is the small category of pointed sets
- \(\textbf{Top}_*, \textbf{Toph}_*\) are the categories of small pointed topological spaces; in the latter, morphisms are homotopies with a fixed basepoint \(*\)
- \(\mathbf{R-Mod}\) is the category of small left R-modules
- \(\mathbf{Vec}_F\) is the category of vector spaces
- \(\mathbf{Rel}\) is the category of small sets, where morphisms are binary relations
- 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}\)

## Hom-Sets

\(\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:

- Objects \(a, b, c, \ldots\)
- For every pair of objects \(\langle a, b \rangle\), a function associating \(\text{hom}(a, b)\) to the pair
- 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} \]

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

## Duality

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 morhpism \(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 homotopy equivalence, \(C/R = \textbf{Toph}\) with objects as spaces and arrows homotopies between them. \(C/R\), as generated by a free category \(C\), is said to have generators \(G\) and relations \(R\).