[ct/2] Universal Arrows, Yoneda Lemma, Limits


Paris, Chennai

Universal arrow

Let $S : A \rightarrow B$ be a functor. For the objects $a \in A, b \in B$, the universal arrow from $b$ to $S$ is defined as the pair $\langle r, u \rangle$ with object $r \in A$ and morphism $u : b \rightarrow Sr$:

$$ \begin{xy} \xymatrix{ b \ar[r]^u \ar@{}[d]|{=} & Sr \ar@{.>}[d]|{\exists!} \\ b \ar[r]^f & Sa } \end{xy} $$

Said differently, every arrow $f$ factors uniquely through $u$.

Examples:

  1. $\textbf{Vec}_K$ is defined as the vector space over field $K$. The forgetful functor $U : \textbf{Vec}_K \rightarrow \textbf{Set}$ is a function sending a vector space to its underlying elements. For any set $X$, there exists a $\textbf{Vec}_X$ with $X$ as the basis. This fact is illustrated by the function $j : X \rightarrow U(V_X)$, and there also exists $k : X \rightarrow U(W)$ obtained by linear transformation. This makes $j$ a universal functor.
  2. Free category $C$ over graph $G$ is given by the universal functor $k : C \rightarrow UG$. Similarly, we have universal functors for a free group or free R-module on a given set of generators.
  3. For integral domain $D$ and field of quotients $Q(D)$, there exists a monomorphism $j : D \rightarrow Q(D)$. The universal (forgetful) functor $\langle Q(D), j \rangle$ maps $\textbf{Fld} \rightarrow \textbf{Dom}_m$, from the category of fields to the category of domains, provided we take the arrows of $\textbf{Dom}_m$ to be monomorphisms of integral domains.

A universal element of functor $H : D \rightarrow \textbf{Set}$ is defined to be the pair $\langle r, e \rangle$ consisting of $r \in D$, $e \in Hr$, such that $\langle d, x \rangle$ consisting of $Hr \in D$ and arrow $f : r \rightarrow d$ implies that $(Hf)e = x$.

Consider the equivalence relation $E$ on set $S$, and the projection $p : S \rightarrow S/E$ sending every element in the set to its E-equivalence class:

$$ \begin{xy} \xymatrix{ S \ar@{}[d]|{=}\ar[r]^p & S/E \ar[d]^g \\ S \ar[r]^f & X } \end{xy} $$

This states that $\langle S/E, p \rangle$ is a universal element under the functor $H : \textbf{Set} \rightarrow \textbf{Set}$.

$f : G \rightarrow G/N$, the morphism that sends each group to its quotient group, is another example of the universal element for the functor $H : \textbf{Grp} \rightarrow \textbf{Set}$.

Relationship between universal arrow and universal element: An element $e$ can be considered universal arrow $H : \textbf{*} \rightarrow Hr \in \textbf{Ens}$ from the one-point set $\textbf{*}$; then $\langle r, e \rangle$ from $\{\textbf{*}\}$ to $H$ is a universal element. If $G : A \rightarrow B$ is a functor, then the pair $\langle r, u : b \rightarrow Sr \rangle$ is a universal arrow if $\langle r, u \in C(b, Sr) \rangle$ is a universal element of the functor $H = C(b, S-)$.

Projections $p : a \times b \rightarrow a$ and $q : a \times b \rightarrow b$ give us another example of universal arrows. Given any other pair of arrows $f : c \rightarrow a$, $g : \rightarrow b$, and $h : c \rightarrow a \times b$, we get $ph = f$ making $\langle p, q \rangle$ a universal pair. To make it a universal arrow, consider the diagonal functor $\Delta C = C \times C$ so that the pair $\langle f, g \rangle : \Delta c \rightarrow \langle a, b \rangle$; then $\langle p, q \rangle$ is a universal arrow from $\Delta$ to $a \times b$.

Yoneda lemma

The concept of universality can be formulated in terms of hom-sets as follows. Given functor $S: A \rightarrow B$, the pair $\langle r, u : b \rightarrow Sr \rangle$ for $r \in A$ is universal if and only if the function $g : r \rightarrow a$ and the composition $Sg \circ u : b \rightarrow Sa$ satisfies the bijection of hom-sets $A(r, a) \cong B(b, Sa)$. This is natural in $A$. If $A, B$ have small hom-sets, then the functor $B(b, S-)$ to $\textbf{Set}$ is isomorphic to the covariant hom-functor $A(r, -)$. Such isomorphisms are called representations.

Let $D$ be a category with small hom-sets. Then, representation of functor $K : D \rightarrow \textbf{Set}$, given $r \in D$, is the pair $\langle r, \psi \rangle$ such that:
$$\psi : D(r, -) \cong K$$

$r$ is called representing object, and $K$ is termed representable, when such a representation exists. A representation is hence just a covariant hom-functor $D(r, -)$.

Let $D$ be a category with small hom-sets, $r \in D$, and $\textbf{*}$ denote the one-point set. If $\langle r, u \rangle: \textbf{*} \rightarrow Kr$ is a universal arrow from $\textbf{*}$ to $K : D \rightarrow \textbf{Set}$, then function $\psi$ which, for every object of $D$, sends the arrow $g : r \rightarrow d$ to $K(g)(u\textbf{*}) \in Kd$ is a representation of $K$.

A universal arrow from $b$ to $S : A \rightarrow B$ can be written as the natural isomorphism $A(r, a) \cong B(b, Sa)$, or equivalently as representation of the functor $B(b, S-) : A \rightarrow \textbf{Set}$, or equally well as the universal element of the same functor.

Informally speaking, the Yoneda lemma states that an object can be recovered by knowing the maps into it. Formally, given category $D$ with small hom-sets, $r \in D$, functor $K : D \rightarrow \textbf{Set}$, there is a bijection:
$$\text{Nat}(D(r, -), K) \cong Kr$$

which sends each NT $D(r, -) \overset{\bullet}{\rightarrow} K$ to $\alpha_r 1_r$, the identity $r \rightarrow r$. The proof is indicated as:

$$ \begin{xy} \xymatrix{ D(r, r)\ar[r]^{\alpha_r}\ar[d]_{K(d, f)} & K(r)\ar[d]^{K(f)} & r \ar[d]^f\\ D(r, d)\ar[r]^{\alpha_d} & K(d) & d } \end{xy} $$

The bijection $y : \text{Nat}(D(r, -), K) \cong Kr$ is the natural isomorphism $N \overset{\bullet}{\rightarrow} E : \textbf{Set}^D \times D \rightarrow \textbf{Set}$. The object function $r \mapsto D(r, -)$ and the arrow function:
$$(f : s \rightarrow r) \mapsto D(f, -) : D(r, -) \mapsto D(s, -)$$

define a fully faithful functor $Y : D^{op} \rightarrow \textbf{Set}^{D}$, and this is called the Yoneda functor.

Coproducts and colimits

For any category $C$, the diagonal functor $\Delta : C \rightarrow C \times C$ is given by the object mapping $\Delta : c \rightarrow \langle c, c \rangle$ and morphism mapping $\Delta : f \rightarrow \langle f, f \rangle$. A universal arrow from object $\langle a, b \rangle$ to $\Delta$, given by $\langle a, b \rangle \rightarrow \langle c, c \rangle$ is called the coproduct diagram. When such a diagram exists, object $c$ is written as $a \sqcup b$:

$$ \begin{xy} \xymatrix{ a\ar[r]^i\ar[dr]_f & a \sqcup b \ar@{.>}[d]|{\exists! h} & b\ar[l]_j\ar[dl]^g \\ & d & } \end{xy} $$

The assignment $\langle f, g \rangle \mapsto h$ is a bijection that is natural in $d$:
$$C(a, d) \times C(b, d) \cong C(a \sqcup b, d)$$

Examples include the disjoint union in $\textbf{Set}$, wedge product in $\textbf{Top}_*$, and the tensor product in $\textbf{CRng}$.

For infinite coproducts, replace $C^2$ with $C^X$, for any set $X$:
$$C(\sqcup_x a_x, c) \cong \prod_x C(a_x, c)$$

If $a_x = b$ for all x, copower $\sqcup_X b$ is written as $X \bullet b$:
$$C(X \bullet b, c) \cong C(b, c)^X$$

If $C$ has a null object such that $0: b \rightarrow z \rightarrow c$ is the zero arrow, cokernel of $f : a \rightarrow b$ is given by $u : b \rightarrow c$:

$$ \begin{xy} \xymatrix{ a\ar[r]^f & b \ar[r]^u\ar[dr]_h & c\ar@{.>}[d]|{\exists! h'} & uf = 0 \\ & & d & hf = 0 } \end{xy} $$

Given a pair of arrows $f, g : a \rightarrow b$, coequalizer $u$ can be defined as:

$$ \begin{xy} \xymatrix{ a\ar@<-.5ex>[r]_f\ar@<.5ex>[r]^g & b \ar[r]^u\ar[dr]_h & c\ar@{.>}[d]|{\exists! h'} & uf = ug \\ & & d & hf = hg } \end{xy} $$

Let $\downarrow \downarrow$ represent a category $C$ with two objects and two non-identity arrows between them. Then, functor category $C^{\downarrow \downarrow}$ can be formed:

$$ \begin{xy} \xymatrix{ a\ar@<-.5ex>[r]_f\ar@<.5ex>[r]^g\ar[d]_h & b\ar[d]^k \\ a'\ar@<-.5ex>[r]_{f'}\ar@<.5ex>[r]^{g'} & b' } \end{xy} $$

Having defined the diagonal functor $\Delta : C \rightarrow C^{\downarrow \downarrow}$, and object $c \in C$, consider:

$$ \begin{xy} \xymatrix{ a\ar@<-.5ex>[r]_f\ar@<.5ex>[r]^g\ar[d]_{kf} & b\ar[d]^k \\ c\ar@<-.5ex>[r]_1\ar@<.5ex>[r]^1 & c } \end{xy} $$

In other words, $k$ coequalizes $f, g$. A coequalizer of pair $\langle f, g \rangle$ is simply a universal arrow $\langle f, g \rangle \rightarrow \Delta$.

As an example, coequalizer in $\textbf{Set}$ for the set of functions $f, g : X \rightarrow Y$ is simply the projection $Y \rightarrow Y/E$ where $E$ is the least equivalence relation $E \subset Y \times Y$.

Given $f : a \rightarrow b, g : a \rightarrow c$, pushout is defined as the pair $\langle f, g \rangle$ such that:

$$ \begin{xy} \xymatrix{ \langle f, g \rangle \ar[d] & b\ar[d]^h & a\ar[d]^{hf = kg}\ar[l]_f\ar[r]^g & c\ar[d]^k \\ \Delta(s)& s & s\ar[l]_1\ar[r]^1 & s } \end{xy} $$

The coproduct over $a$, also called cocartesian square or fibered sum is written as:
$$r = b \sqcup_a c = b \sqcup_{\langle f, g \rangle} c$$

The pushout of $\langle f, g \rangle$ always exists in $\textbf{Set}$; it is the disjoint union $a \sqcup b$ with elements identified with $fx$ and $gx$, for $x \in a$.

For $f: a \rightarrow b \in C$, the cokernel pair is defined as the pair of pushout of $f$ along with $f$. Indeed, there is some $r$ so that $u, v : b \rightarrow r$ are parallel arrows:

$$ \begin{xy} \xymatrix{ a\ar[r] & b\ar@<-.5ex>[r]_u\ar@<.5ex>[r]^v\ar@<-.5ex>[dr]_f\ar@<.5ex>[dr]^g & r\ar@{.>}[d]|{\exists! t} \\ & & s } \end{xy} $$

Let $C$ be a category, and $J$ be an index category. The diagonal functor
$$\Delta : C \rightarrow C^J$$

sends each object $c$ to the constant functor $\Delta c$ - the functor which has the same value $c$ for each object $i \in J$, and the value $1_c$ at each arrow of $J$. Given $f : c \rightarrow c'$, $\Delta f : \Delta c \overset{\bullet}{\rightarrow} \Delta c'$ is an NT. Arrows $F : J \rightarrow C$ correspond to objects of $C^J$. The universal arrow $\langle r, u \rangle$ from $F$ to $\Delta$ is called a colimit (or direct limit, inductive limit) diagram for $F$; it consits of an object $r \in C$, usually written $r = \underset{\longrightarrow}{\text{Lim }} F$, or $r = \text{Colim } F$, along with an NT $u : F \overset{\bullet}{\rightarrow} \Delta r$ which is universal among NTs $\tau : F \overset{\bullet}{\rightarrow} \Delta c$. Pictorially, the following diagram commutes:

$$ \begin{xy} \xymatrix{ F_1\ar[d]^{\tau_1}\ar[r] & F_2\ar[d]^{\tau_2}\ar[r] & F_3\ar[d]^{\tau_3}\ar@<-.5ex>[r]\ar@<.5ex>[r] & F_4\ar[d]^{\tau_4} & F_5\ar[d]^{\tau_5}\ar[l] \\ c\ar@{}[r]|{=} & c\ar@{}[r]|{=} & c\ar@{}[r]|{=} & c\ar@{}[r]|{=} & c } \end{xy} $$

$\tau : F \overset{\bullet}{\rightarrow} \Delta c$ is often written as $\tau : F \overset{\bullet}{\rightarrow} c$, and is called the cone of $F$ to the base $c$:

$$ \begin{xy} \xymatrix{ F_i\ar[r]^{F_u}\ar[dr]_{\tau_i} & F_j\ar[d]^{\tau_j}\ar[r]^{F_v} & F_k\ar[dl]^{\tau_k} \\ & c & } \end{xy} $$

Alternatively, colimit of $F : J \rightarrow C$ consists of object $\underset{\longrightarrow}{\text{Lim }} F \in C$ along with the cone $\mu : F \overset{\bullet}{\rightarrow} \Delta (\underset{\longrightarrow}{\text{Lim }} F)$, from base $F$ to the vertex $\underset{\longrightarrow}{\text{Lim }} F$, which is a universal cone (or limiting cone).

As an example, consider $J = \omega = \{0 \rightarrow 1 \rightarrow 2 \rightarrow \ldots\}$, and functor $F : \omega \rightarrow \textbf{Set}$ which maps every arrow in $\omega$ to an inclusion map (subset in set). This functor is simply the inclusion $F_0 \subset F_1 \subset F_2 \subset \ldots$. The union $U$ of all sets, with cone given by inclusion map $F_n \rightarrow U$, is $\underset{\longrightarrow}{\text{Lim }} F$. For $J$ small, any $J \rightarrow \textbf{Set}$ has a colimit.

Limits and products

The notion of a limit is dual to that of a colimit. Let $C$ be a category, $J$ be an index set, and $\Delta : C \rightarrow C^J$ be a diagonal functor. Limit of functor $F : J \rightarrow C$ is defined as the universal arrow $\langle r, \nu \rangle$ from $\Delta$ to $F$; it consists of object $r \in C$, $r = \underset{\longleftarrow}{\text{Lim }} F = \text{Lim } F$, called the limit object (or projective limit, inverse limit) of $F$, and the NT $\nu : \Delta r \overset{\bullet}{\rightarrow} F$, which is universal among $\tau : \Delta c \overset{\bullet}{\rightarrow} F$ for $c \in C$. $\tau : c \overset{\bullet}{\rightarrow} F$ is then called cone to base $F$ from vertex $c$, pictured as:

$$ \begin{xy} \xymatrix{ c\ar[d]_{\tau_i}\ar[dr]|{\hole}_{\tau_j}\ar[r]^t & \underset{\longleftarrow}{\text{Lim }} F = \text{Lim } F\ar[d]^{\nu_j}\ar[dl]_{\nu_i} \\ F_i\ar[r]_{Fu} & F_j } \end{xy} $$

The properties of limits and colimits may be pictured as:

$$ \begin{xy} \xymatrix{ \underset{\longleftarrow}{\text{Lim }} F\ar[r]^\nu & F\ar@{}[d]|{=}\ar[r]^\mu & \underset{\longrightarrow}{\text{Lim }} F\ar@{.>}[d] \\ c\ar[r]^\tau\ar@{.>}[u] & F\ar[r]^\sigma & c } \end{xy} $$

For a discrete category $J = \{1, 2\}$ and category $C$, limit of functor $F : \{1, 2\} \rightarrow C$ consisting of pairs $\langle a, b \rangle$, is called product of $a, b$ and written as $a \times b$. Then, we have projections $p, q$ defined as:
$$a \xleftarrow{p} a \times b \xrightarrow{q} b$$

They form a cone with vertex $a \times b$, and we have the bijection of sets natural in $c$:
$$C(c, a \times b) \cong C(c, a) \times C(c, b)$$

We then define $h = (f, g) : c \rightarrow a \times b$, and $f, g$ are called the components of $h$. In $\textbf{Cat}, \textbf{Grp}, \textbf{Top}$, this corresponds to direct product.

Infinite products. When $J$ is a set (= discrete category, category with all arrows identities), $F : J \rightarrow C$ is simply a $J$-indexed family of objects $a_i \in C$, while cone with vertex $c$ and base $a_j$ is a $J$-indexed family of arrows $f_j : c \rightarrow a_j$. We have $f : c \rightarrow \prod_j a_j$ and the following bijection of sets natural in $c$:
$$\prod_j C(c, a_j) \cong C(c, \prod_j a_j)$$

Products over any small set exist in $\textbf{Set}$, $\textbf{Grp}$, and $\textbf{Top}$; they are simply cartesian products.

If factors in a product are all equal, $a_j = b$ for all $j$, then $\prod_j a_j = \prod_j b$ is called power, and is written as $\prod_j b = b^J$. The following bijection of sets is natural in $c$:
$$C(c, b)^J \cong C(c, b^J)$$

Given $J = \downarrow \downarrow$ and functor $F : \downarrow \downarrow \rightarrow C$ defined by parallel arrows $f, g : a \rightarrow b$, the limit point $d \in F$, when it exists, is called an equalizer or difference kernel of $f$ and $g$:

$$ \begin{xy} \xymatrix{ d\ar[r]^e & a\ar@<-.5ex>[r]_g\ar@<.5ex>[r]^f & b } \end{xy} $$

The limit arrow $e$ amounts to cone $a \leftarrow d \rightarrow b$ from vertex $d$. In $\textbf{Set}$, equalizer always exists; $d$ is the set $d \in b \mid fx = gx$, and $e : d \rightarrow b$ is an injection of this subset of $b$ into $b$. In $\textbf{Ab}$, the equalizer $d$ is kernel of difference homomorphism $f - g : a \rightarrow b$. Any equalizer $e$ is necessarily a monic.

For $J : \rightarrow \bullet \leftarrow$, functor $F : (\rightarrow \bullet \leftarrow) \rightarrow C$ is a pair of arrows $b \xrightarrow{g} a \xleftarrow{f} d$. The cone of such a functor is a pair of arrows from vertex $c$ in the following diagram:

$$ \begin{xy} \xymatrix{ c\ar@/_/[ddr]\ar@{.>}[dr]|{\exists!}\ar@/^/[drr] \\ & b \times_a d\ar[d]^p\ar[r]_q & d\ar[d]_f \\ & b\ar[r]^g & a } \end{xy} $$

The diagram also illustrates the universal cone formed by $c \rightarrow b \times_a d$, and the square is called pullback square. The product $b \times_a d$ is then called pullback or fibered product.

In $\textbf{Top}$, if $g : d \rightarrow a$ is a "fiber map" with base $a$, and $f$ is a continuous map into the base, then projection $p$ of the pullback is the induced fiber map. When it exists, the pullback of a pair of equal arrows $b \rightarrow a \leftarrow b$ is called the kernel pair of $f$. A limit of the empty functor in $C$ is a terminal object of $C$.

Categories with finite products

A category is said to have finite products if, for any finite number of objects $c_1, c_2, \ldots c_n$, there exists a product object $c_1 \times c_2 \times \ldots c_n$ and projections $p_i : c_1 \times c_2 \times \ldots c_n \rightarrow c_i$ for $i = 1 \ldots n$, with the usual universal property.

If $C$ has a terminal object $t$ and products $a \leftarrow a \times b \rightarrow b$ for any two objects $a, b$, then $C$ has all finite products. The products provide, by $\langle a, b \rangle \mapsto a \times b$, the bifunctor $C \times C \rightarrow C$. For any three objects, we have the isomorphism natural in $a, b, c$:
$$\alpha = \alpha_{a, b, c} : (a \times b) \times c \cong a \times (b \times c)$$

For any object $a$, there are isomorphisms natural in $c$:
$$\rho_a = \rho : t \times a \cong a \quad \lambda_a = \lambda : a \times t \cong a$$

The proof can be expressed as a commutative diagram:

$$ \begin{xy} \xymatrix{ & & b \\ a & a \times (b \times c)\ar[l]\ar[r]\ar[ur]\ar[dr] & b \times c\ar[u]\ar[d] \\ & & c } \end{xy} $$

The dual result holds for a coproduct. A coproduct diagram consists of $m$ injections $i_j : a_j \rightarrow a_1 \sqcup a_2 \sqcup \ldots \sqcup a_m$ and a map $f: a_1 \sqcup a_2 \sqcup \ldots \sqcup a_n \rightarrow c$ determined by its $m$ cocomponents $f \circ i_j : f_j = a_j \rightarrow c$ for $j = 1, 2, \ldots m$. If $C$ has both finite products and finite coproducts, the arrows
$$a_1 \sqcup \ldots \sqcup a_m \rightarrow b_1 \times \ldots \times b_n$$

from coproducts to products is determined uniquely by an $m \times n$ matrix of arrows $f_{jk} = p_k f i_j : a_j \rightarrow b_k$. In any category with a null object $z$ and the zero arrow $a \rightarrow b$ through $z$, finite coproducts, and finite products, there is a canonical arrow of the coproduct to the product:
$$a_1 \sqcup \ldots \sqcup a_n \rightarrow a_1 \times \ldots \times a_n$$

This arrow is precisely the identity matrix of order $n$. It may be an isomorphism (in $\textbf{Ab}, \textbf{R-Mod}$), a proper monic (in $\textbf{Top}, \textbf{Set}$), or a proper epi (in $\textbf{Grp}$).

Groups in categories

Let $C$ be a category with finite products and terminal object $c$. Then, a monoid is defined by the triple $\langle c, \mu : c \times c \rightarrow c, \eta : t \rightarrow c \rangle$ such that the following diagrams commute:

$$ \begin{xy} \xymatrix{ c \times (c \times c)\ar[r]^\alpha\ar[d]^{1 \times \mu} & (c \times c) \times c\ar[r]^{\mu \times 1} & c \times c\ar[d]^\mu \\ c \times c\ar[rr]^{\mu} & & c } \end{xy} $$

$$ \begin{xy} \xymatrix{ t \times c\ar[r]^{\eta \times 1}\ar[d]^\lambda & c \times c\ar[d]^\mu & c \times t\ar[l]_{1 \times \eta}\ar[d]^\rho \\ c\ar@{}[r]|{=} & c\ar@{}[r]|{=} & c } \end{xy} $$

where $\alpha$ is the associativity morphism. A group is then defined by the triple $\langle c, \mu, \eta \rangle$ together with the operation $\zeta : c \rightarrow c$ such that the following diagram commutes (with $\delta_c$ the diagonal):

$$ \begin{xy} \xymatrix{ c\ar[r]^{\delta_c}\ar[d] & c \times c\ar[r]^{1 \times \zeta} & c \times c\ar[d]^\mu \\ t\ar[rr]^\eta & & c } \end{xy} $$

This suggests that $\zeta$ sends each element $c$ to its right inverse. One can draw similar diagrams for any algebraic system.

If $C$ is a category with finite products, then object $c$ is a group iff the hom-functor $C(-, c)$ is a group in the functor category $\textbf{Set}^{C^{op}}$. Each multiplication $\mu$ of $C$ determins a corresponding multiplication $\bar{\mu}$ in the hom-set $C(-, c) : C^{op} \rightarrow \textbf{Set}$ as the composite

$$ C(-, c) \times C(-, c) \xrightarrow{\theta} C(-, c \times c) \xrightarrow{\nu} C(-, c) $$

where $\nu = \mu_* = C(-, \mu)$, while the first natural isomorphism is given by the definition of the product object $c \times c$. Conversely, given any natural $\nu$, the Yoneda lemma proves that there is a unique $\mu : c \times c \rightarrow c$ such that $\nu = \mu_*$. A diagram chase shows that $\mu$ is associative only if $\bar{\mu}$ is.

Colimits of representatable functors

Any functor $K : D \rightarrow \textbf{Sets}$, from a small category $D$ to the category of Sets, can be represented, in a canoical way, by the colimit of a diagram of representable functors $\text{hom}(d, -)$, where $d \in D$. First, given $K$, we construct a diagram category for the colimit $J$, the "category of elements" of $K$; that is the comma category $1 \downarrow K$ of object pairs $(d, x)$, with $d \in D, x \in K(d)$ as objects, and arrows $f : (d, x) \rightarrow (d', x')$, those arrows $f: d \rightarrow d'$ for which $K(f)x = x'$. Then, $K$ is the colimit of the diagram on $1 \downarrow K$ given by the functor
$$M : J^D \rightarrow \textbf{Sets}^D$$

which sends each object $(d, x)$ to the hom-functor $D(d, -)$, and each arrow $f$ to the induced NT $f_* : D(d', -) \rightarrow D(d, -)$. Then, the Yoneda isomorphism on $\textbf{Sets}^D$ yields a cone over base $M$ to $K$:
$$y^{-1} : K(D) \rightarrow \text{Nat}(D(d, -), K)$$

and we get the following diagram:

$$ \begin{xy} \xymatrix{ J\ar[d]^M & (d, x)\ar[d] & (d', x')\ar[d]\ar[l]_{f_*} \\ \textbf{Sets}^D & D(d, -)\ar[d]_{y^{-1}x}\ar[dr]_{y^{-1}x'}|{\hole} & D(d', -)\ar[d]^{y^{-1}z'}\ar[dl]_{y^{-1}z}\ar[l]_{f_*} \\ & K\ar@{.>}[r]_\theta & L } \end{xy} $$

This cone to $K$ is colimiting over $D(d, -)$. Consider any other cone from $D(d, -)$ to the vertex $L$; by the Yoneda lemma, this is an NT $D \rightarrow \textbf{Sets}$, given by $y^{-1}z : D(d, -) \rightarrow L$, as well as by $y^{-1}z' : D(d', -) \rightarrow L$, for some $z \in L(D), fz = z'$. To show that the cone to $K$ is universal, construct an NT $\theta : K \rightarrow L$ and set $\theta_d x = z$. Since $f(y^{-1}z) = y^{-1}(fz) = y^{-1}z'$, $\theta$ is natural.

For small category $C$, the contravariant functor $F : C^{op} \rightarrow \textbf{Sets}$ is called a presheaf, and the category of these functors is written as $\hat{C}$. This terminology comes from the case when $C$ is a category of open subsets $U$ of a topological space, and $F$ smooth functions; then, for the inclusion $V \subset U$, we have the map $F(U) \rightarrow F(V)$.