# An application of Yoneda Lemma

I'm trying to solve the following exercise:

Prove that $Eq(X \rightrightarrows Y) = X \times_{X \times X}(X \times_Y X)$ whenever the right-hand side exists.

(it's understood that there are 2 morphisms from $X$ to $Y$ on the left-hand side, and some morphisms need to be understood by the context on the right-hand side).

I managed to give a direct proof, but it's very cumbersome. The intuition behind my proof is what happens in Set. The proof when working in Set is easier than the general case.

My feeling is that the Yoneda Lemma can be used here to reduce this problem from a general category to Set.

More specifically, it's the Yoneda embedding that seems useful, but I get confused over and over again trying to apply it. Can you show me how it's done?

-
Please explain your notation. Are $X,Y$ objects of a category? What kind of category? What is $Eq$? Is it the equalizer? What do you mean by $\times_Y$? – Loronegro Feb 10 '12 at 17:36
@Loronegro Notation is completely standard. I doubt, anyone unfamiliar with it would be able to answer the question, anyway. – Grigory M Feb 10 '12 at 18:39
@GrigoryM Instead of your very helpful comment, maybe you can write the references of the standard category books where the pullback is denoted in this way. – Loronegro Feb 11 '12 at 4:53

The following is an easy corollary of the Yoneda lemma: if $\textrm{Hom}(C, A) \cong \textrm{Hom}(C, B)$ naturally in $C$, then $A \cong B$ in the original category. However, in order to use this to solve your problem, we need the following somewhat non-trivial fact: there is a bijection $$\textrm{Hom}(C, \varprojlim A_\bullet) \cong \varprojlim \textrm{Hom}(C, A_\bullet)$$ naturally in $C$. In words, this is the claim that the Yoneda embedding $y : \mathcal{C} \to [\mathcal{C}^\textrm{op}, \textbf{Set}]$ preserves all limits.

Now, suppose we have a parallel pair $X \rightrightarrows Y$ and that $E \to X$ is their equaliser. Then, by limit preservation, for each $C$, the induced diagram $$\textrm{Hom}(C, E) \to \textrm{Hom}(C, X) \rightrightarrows \textrm{Hom}(C, Y)$$ is an equaliser diagram. But that implies $$\textrm{Hom}(C, E) \cong \textrm{Hom}(C, X) \mathbin{\times_{\textrm{Hom}(C, X \times X)}} \left( \textrm{Hom}(C, X) \mathbin{\times_{\textrm{Hom}(C, Y)}} \textrm{Hom}(C, X) \right)$$ Unfortunately, that isn't the end of the story. We need to show that this bijection is natural in $C$, but once that is done, it follows by the preservation of limits that $$E \cong X \times_{X \times X} \left( X \times_Y X \right)$$

To be honest, just proving it directly using the various universal properties is morally and conceptually the same and does not involve an unholy mess of notation.

-
This "non-trivial fact" is trivial because it is just a reformulation of the definition of the limit. – Martin Brandenburg Mar 2 '12 at 8:49
it also follows from "right adjoints commute with limits" – Rodrigo Jan 30 '14 at 21:51
@ZhenLin, isn't part of the statement of Yoneda lemma that "this bijection" is natural in $C$ (in your penultimate paragraph). What do you mean exactly that is left to show? – Rodrigo Jan 31 '14 at 0:48

Here is a proof using the various universal properties, in case you're interested.

First of all, we need to introduce some notation for the various morphisms involved in constructing the right hand side. Given arrows $f,g: X \to Y$, we let $X \times_{Y} Y$ be their pullback. This comes equipped with arrows $h_1, h_2: X \times_Y X \to X$ such that $$f \circ h_1 = g \circ h_2.$$ By the universal property of products, there is an arrow $h: X \times_Y X \to X \times X$ such that $$h_1 = p_1 \circ h \text{ and } h_2 = p_2 \circ h,$$ where $p_1,p_2 : X \times X \to X$ are the projections. Let $\Delta: X \to X \times X$ be the map induced from two copies of the arrow $\operatorname{id}_X: X \to X$; it follows that $\Delta$ satisfies $$p_1 \circ \Delta = \operatorname{id}_X = p_2 \circ \Delta.$$

We now take the pullback of $h$ and $\Delta$, which is the right hand side $R:= X \times_{X \times X} (X \times_{Y} X)$. Again there are arrows $k_1: R \to X \times_Y X$ and $k_2: R \to X$ such that $$h \circ k_1 = \Delta \circ k_2.$$

Now, if $R$ is going to be the equalizer of $f$ and $g$, we need to identify an arrow $R \to X$, and the obvious one is $k_2$ (there is another one too, but they can be shown to be equal), and hence we must first show that $f \circ k_2 = g \circ k_2$. We have (using the various formulae above) \begin{align*} f \circ k_2 &= f \circ \operatorname{id}_X \circ k_2 = f \circ p_1 \circ \Delta \circ k_2 = f \circ p_1 \circ h \circ k_1 \\ &= f \circ h_1 \circ k_1 = g \circ h_2 \circ k_1 = g \circ p_2 \circ h \circ k_1 = g \circ p_2 \circ \Delta \circ k_2 \\ &= g \circ \operatorname{id}_X \circ k_2 = g \circ k_2 \end{align*} which proves the result.

We next show that the pair $(R,k_2)$ has the universal property of the equalizer of $f$ and $g$. Suppose that we are given a morphism $q: Q \to X$ such that $f \circ q = g \circ q$. We must show that there exists a unique $\eta: Q \to R$ such that $q = k_2 \circ \eta$. By the universal property of the pullback $X \times_Y X$, there exists a unique $\xi: Q \to X \times_Y X$ such that $q = h_1 \circ \xi = h_2 \circ \xi$. It follows that \begin{align*} p_1 \circ \Delta \circ q &= q = h_1 \circ \xi = p_1 \circ h \circ \xi \\ p_2 \circ \Delta \circ q &= q = h_2 \circ \xi = p_2 \circ h \circ \xi \end{align*}
and hence $\Delta \circ q = h \circ q$ by the universal property of the product $X \times X$ (uniqueness of the induced map). It follows, by the universal property of $R$ (a pullback) that there exists a (unique) $\eta: Q \to R$ such that $\xi = k_1 \circ \eta$ and $q = k_2 \circ \eta$, and the latter formula is precisely what we need, but we need to show that $\eta$ is the unique arrow satisfying $q = k_2 \circ \eta$. So, suppose that $q = k_2 \circ \bar{\eta}$. It suffices to show that $\xi = k_1 \circ \bar{\eta}$ also. The arrow $\xi$ was the unique one satisfying $q = h_1 \circ \xi = h_2 \circ \xi$, so we show that these two formulas are satisfied for $k_1 \circ \bar{\eta}$. This is easy: $$h_1 \circ k_1 \circ \bar{\eta} = p_1 \circ h \circ k_1 \circ \bar{\eta} = p_1 \circ \Delta \circ k_2 \circ \bar{\eta} = k_2 \circ \bar{\eta} = q$$ and, similarily, $h_2 \circ k_1 \circ \bar{\eta} = q$. Hence $k_1 \circ \bar{\eta} = \xi$, and hence $\eta = \bar{\eta}$ by uniqueness. This proves that $Eq(f,g) \cong X \times_{X \times X} (X \times_Y X)$.

-