Take the 2-minute tour ×

I think I've found an error in Benjamin Pierce's Basic Category Theory for Computer Scientists proof of the Basic Limit Theorem. This usually means I've misunderstood something. Can you point out the flaw in the following reasoning?

Theorem: Let $\textbf{D}$ be a diagram in a category $\textbf{C}$, with sets $V$ of vertices and $E$ of edges. If every $V$-indexed and every $E$-indexed family of objects in $\textbf{C}$ has a product and every pair of arrows in $\textbf{C}$ has an equalizer then $\textbf{D}$ has a limit.

The proof proceeds roughly as follows:

Construct the product $\Pi_{I \in V}D_I$ of objects in $\textbf{D}$. Construct the product $\Pi_{(I \xrightarrow{e} J \in E)}D_J$. For any $\textbf{D}$-edge $D_e : D_I \rightarrow D_J$ there are two ways from $\Pi_{I\in V}D_I$ to any $D_J$. Those are $\pi_J$ and $D_e \circ \pi_I$. Form a family of arrows from each method. Each family induces a mediating arrow from $\Pi_{I\in V}D_I$ to $\Pi_{(I \xrightarrow{e} J \in E)}D_J$, call those $p$ and $q$. Select $e : X \rightarrow \Pi_{I\in V}D_I$ such that $e$ equalizes $p$ and $q$. $X$ is a limit of $\textbf{D}$.

This is nice and concise. My trouble is this: What if there are two $D_e : D_I \rightarrow D_J$? In that case, there are potentially many more than two ways from $\Pi_{I\in V}D_I$ to each $D_J$ and potentially many more than two mediating arrows $\Pi_{I\in V}D_I$ to $\Pi_{(I \xrightarrow{e} J \in E)}D_J$.

Note that this does not affect the proof: $\textbf{C}$ is assumed to be a small category, and no matter how many mediating arrows you have between the two products you can just keep stacking on equalizers until you've equalized them all (at which point you've constructed your limit).

However, there's no mention of this in the text, and it leaves me wondering whether I'm crazy and/or missing something obvious.

share|improve this question
But limits require that for any limit $X$ with arrow $f_i : X \rightarrow D_i$ in the limit and arrow $g : D_i \rightarrow D_j$ in the diagram, $f_j = g \circ f_i$. If we ignore extra $D_e : D_I \rightarrow D_J$ in the proof then it seems like there are arrows in the diagram (the ignored arrows) that could violate this equation. –  Nate Sep 13 '13 at 4:00
Note that $\prod_{I\to J}D_J$ has index set $E$. Thus, two edges $e_1:I_1\to J$ and $e_2:I_2\to J$ correspond to two "copies" of $D_J$ in that product. In particular, if $e_1$ and $e_2$ have the same domain $I$ they still induce two distinct copies of $D_J$. Moreover, $q$ distinguishes them. –  Karl Kronenfeld Sep 13 '13 at 4:05
@KarlKronenfeld, that's precisely what I was missing, thanks. Care to write up an answer? –  Nate Sep 13 '13 at 4:10
Nate, there is something I need you to clarify. What exactly are $I$ and $D_I$. My understanding was that both $I$ and $D_I$ were elements of $V$, but that seems to be false or at least not exactly true. –  Karl Kronenfeld Sep 13 '13 at 4:24
Oh, that was just me being sloppy when summarizing the proof in the book. In the book, $I$ and $J$ are the notation used when referring to elements of $V$ (i.e. only in the indexing of the products), while $D_I$ and $D_J$ are used when referring to objects of $\textbf{D}$ (which are indeed the same, unless I'm missing something). Sorry. I'll go back and edit. –  Nate Sep 13 '13 at 4:28

1 Answer 1

up vote 1 down vote accepted

$\DeclareMathOperator {\cod}{cod}$ Note about my notation: There is no loss of generality just to say that $V$ and $E$ consist of the objects and arrows (respectively) of the diagram $\mathbf D$. Thus, the product of objects is $P_1=\prod_{I\in V}I$ and the other product is $P_2=\prod_{e\in E}\cod(e)$, where I use $\cod(e)$ to refer to the codomain of $e$; if $e:I\to J$, then $\cod(e)=J$.

Now, you asked what happens to two arrows $e,e':I\to J$ in $\mathbf D$. Since they are different elements of $E$, they will represent different "copies" of $J$ in the product $P_2$. In category theory one uses projections to formalize the notion of "copies". Specifically, the projections $\pi_e$ and $\pi_{e'}$ from $P_2$ to $J$ allow us to differentiate between the instance of $J$ corresponding to $e$ and the instance of $J$ corresponding to $e'$.

Let's see how this works by examining the arrow $q$. It is defined by the property that $\pi_e\circ q=e\circ\pi_I$ for all $e\in E$. Thus, if $e,e'$ are as above, then $q$ must map into the coordinate $e$, so to say, by behaving like $e\circ\pi_I$. Likewise $q$ must map into the coordinate $e'$ by behaving like $e'\circ\pi_I$. Since $e\circ\pi_I$ and $e'\circ\pi_I$ can be completely different, so can $q$ in these two coordinates.

Notice that the equation $\cod e=J=\cod e'$ really has little impact on $q$. In fact, if I were to sum up the above paragraph, it would be: the arrows $e$ and $e'$ dictate the behavior of $q$, not their codomains.

share|improve this answer

Your Answer


