What are the end and coend of Hom in Set?

Question

A functor $F$ of the form $C^{op} \times C \to D$ may have an end $\int_c F(c, c)$ or a coend $\int^c F(c, c)$, as described for example in nLab or Categories for Programmers. I'm trying to get an intuition for this using concrete examples, and the most obvious example of such an $F$ is the Hom functor on the category of sets. However, trying to calculate the coend has not gotten me very far, although I suspect that the equivalence class of an endomorphism is related to its eventual image.

Is there a nice description of the end and coend in this case?

And (extra credit) are there other good candidates for the first nontrivial concrete example of an end or coend?

Answer 1

The end is pretty easy. An element of the end is a choice of endomorphism $\alpha_S$ for each set $S$, such that the endomorphisms commute with all functions: for any $f: S \to T$, $f \circ \alpha_S = \alpha_T \circ f$. It's clear that $\text{id}$, the collection of identity maps, is such an element. Also, if we choose $S = \{*\}$ then it's clear that $\alpha_T$ must fix every $t \in T$. So the end has only the single element $\text{id}$.

The coend (as others have said) is harder. But here's a pretty good description. I think it's equivalent to @Kyle Miller's, but with some details filled in.

We have the functor $\operatorname{Hom}: \operatorname{Set}^{\operatorname{op}} \times \operatorname{Set} \to \operatorname{Set}$. The coend $\int^S \operatorname{Hom}(S, S)$ would be a set with maps $i_X: \operatorname{Hom}(X, X) \to \int^X$ for all $X$, which is a universal cowedge. For the "universal" part, we just take $\coprod_X \operatorname{Hom}(X, X)$. For "cowedge", we need the square from $\operatorname{Hom}(Y, X) \to \int^S$ to commute for any $f: X \to Y$. That is, $i_X \cdot (- \cdot f) = i_Y \cdot (f \cdot -)$, where $- \cdot f: \operatorname{Hom}(Y, X) \to \operatorname{Hom}(X, X) $ and $f \cdot -: \operatorname{Hom}(Y, X) \to \operatorname{Hom}(Y, Y)$. The cowedge condition gives a relation between endomorphisms of sets: if we have endomorphisms $\phi$ of $X$ and $\psi$ of $Y$, and if they are related via functions $f:X \to Y$ and $g: Y \to X$ such that $gf = \phi$ and $fg = \psi$, we will say $\phi W \psi$. Then $\int^S$ would be $\coprod_X \operatorname{Hom}(X, X) / \sim$, where $\sim$ is the equivalence relation generated by $W$. So our main goal is to describe $\sim$. (Here we are taking a coproduct over a proper class, but we will ignore size issues throughout.)

Here's a description of $\sim$. Fix an endomorphism $\sigma$ in $\operatorname{Set}$. We'll describe the equivalence class $[\sigma]$ under $\sim$.

Some endomorphisms are conjugate: for endomorphisms $\phi_0$, $\phi_1$ of $X_0$, $X_1$ respectively, we will say $\phi_0 \simeq \phi_1$ if there is an isomorphism $\alpha: X_0 \to X_1$ such that $\phi_1 = \alpha \phi_0 \alpha^{-1}$. For $i \ge 0$, define $D^i$ as all $\phi$ such that $\phi | _{\phi^i[X] \to \phi^i[X]} \simeq \sigma$ (where $\phi: X \to X$). Then define $D = \bigcup_i D^i$.

I claim that $[\sigma] = D$. First we show $[\sigma] \subseteq D$. Clearly $\sigma \in D^0$. So it's enough to show that for $i \ge 0$, if $\phi \in D^i$ and $\phi W \psi$, then $\psi \in D^{i + 1}$. So suppose we have $X$, $Y$, $f$, $g$ witnessing $\phi W \psi$. Take $\bar X = \phi^i[X]$ and $\bar \phi = \phi | _{\bar X \to \bar X}$, so $\bar \phi \simeq \sigma$. Take $\bar Y = f[\bar X]$, and note $g[\bar Y] = \bar X$, so we can define $\bar f = f | _{\bar X \to \bar Y}$ and $\bar g = g | _{\bar Y \to \bar X}$. Then $\bar \phi = g | _{f[\bar X]} f | _{\bar X} = \bar g \bar f$. Since $\bar \phi$ is an automorphism, $\bar f$ is mono; and $\bar f$ is epi by construction, and therefore an isomorphism. And $\bar g = \bar \phi {\bar f}^{-1}$ is also an isomorphism.

Now take $\bar \psi = \psi | _{\bar Y \to \bar Y}$. Not surprisingly, $\bar \psi = f | _{gf[\bar X]} g | _{f[\bar X]} = \bar f \bar g$. Note that $\psi^{i + 1} = f \phi^i g$. So we have $\psi^{i + 1}[Y] \subseteq f \phi^i[X] = f[\bar X]$. But also $\psi^{i + 1}[Y] \supseteq f \phi^i g[\bar Y] = f \phi^i[\bar X] = f[\bar X]$. So $\psi^{i + 1}[Y] = f[\bar X] = \bar Y$. Now $\psi | _{\psi^{i + 1}[Y] \to \psi^{i + 1}[Y]} = \psi | _{\bar Y \to \bar Y} = \bar \psi = \bar f \bar g \simeq \bar g(\bar f \bar g){\bar g}^{-1} = \bar \phi \simeq \sigma$. This means $\psi \in D^{i + 1}$ as required, so $[\sigma] \subseteq D$.

To show $D \subseteq [\sigma]$, we need to show that all $D^i \subseteq [\sigma]$, so again we work by induction. If $\phi \in D^0$, then $\phi \simeq \sigma$, so $\alpha \phi \alpha^{-1}$ for some $\alpha$; then taking $f = \alpha \phi$ and $g = \alpha^{-1}$, we see that $\phi W \sigma$. So $D^0 \subseteq [\sigma]$. Now suppose $D^i \subseteq [\sigma]$ for some $i \ge 0$, and $\psi \in D^{i + 1}$. I claim there is a $\phi \in D^i$ with $\phi W \psi$; this gives $\psi \in [\sigma]$, so $D^{i + 1} \subseteq [\sigma]$ as required.

Say $\psi: Y \to Y$. Take $X = \psi[Y]$, and the epi-mono factorization $f: X \hookrightarrow Y$, $g = \psi | _{Y \to \psi[Y]}$ of $\psi = fg$. Take $\phi = gf = \psi | _{X \to X}$. We get $\phi^i[X] = \psi^i[X] = \psi^{i + 1}[Y]$, so $\phi | _{\phi^i[X]} = \psi | _{\psi^{i + 1}[Y]}$. Since $\psi | _{\psi^{i + 1}[Y]} \simeq \sigma$, we get $\phi | _{\phi^i[X]} \simeq \sigma$ and $\phi \in D^i$, as required. So $D \subseteq [\sigma]$, and $D = [\sigma]$. Q.E.D.

In particular, it's easy to describe the two simplest elements of $\int^S$. If $\sigma$ is the endomorphism of the empty set, then it's easy to check that $[\sigma]$ is just the one element $\{\sigma\}$. And if $\sigma$ is the endomorphism of a singleton, then $[\sigma]$ is the class of endomorphisms $\phi$ which are "eventually constant" in the sense that some $\phi^i$ is constant.

The argument also works in $\operatorname{FinSet}$. In this case, the iterated image $\phi[X], \phi^2[X], ...$ eventually settles on a stable subset, so we find that $\phi \sim \sigma$ for an automorphism $\sigma$ of that subset. This means $\int^S$ is the set of conjugacy classes of permutations, or the set of integer partitions.

This appears to be the only reasonably complete answer to the original question.

EDITED to add the coend description.

Answer 2

Playing with the universal property, you get that the set $\int_c\hom_{\cal C}(c,c)$ is the set of natural transformations $\text{id}_{\cal C} \Rightarrow \text{id}_{\cal C}$. I think the easiest way to see this is using the description of $\int_c\hom_{\cal C}(c,c)$ as an equalizer of a pair of maps. Give it a try!

For what concerns the coend... it's not easy: the quotient you have to perform on $\coprod_c\hom_{\cal C}(c,c)$ can vary a lot as the structure of $\cal C$ varies.

Many times I believed I found a general formula, but then a counterexample popped out!

Answer 3

The most important example of an end is $\int_{c : \mathcal{C}} \mathcal{D} (F c, G c)$, where $F$ and $G$ are functors $\mathcal{C} \to \mathcal{D}$. If you unfold the definition you will find that it is the set of natural transformations $F \Rightarrow G$. In particular, for $F = G = \textrm{id}_\mathcal{C}$, you obtain the fact that $\int_{c : \mathcal{C}} \mathcal{C} (c, c)$ is the set of natural transformations $\textrm{id}_\mathcal{C} \Rightarrow \textrm{id}_\mathcal{C}$, which you might call the set of natural endomorphisms for short.

The coend $\int^{c : \mathcal{C}} \mathcal{C} (c, c)$ is a stranger thing. It has to do with factorisations of endomorphisms. In general, given $H : \mathcal{C}^\textrm{op} \times \mathcal{C} \to \textbf{Set}$, the coend $\int^{c : \mathcal{C}} H (c, c)$ is the disjoint union $\coprod_{c \in \operatorname{ob} \mathcal{C}} H (c, c)$ modulo the smallest equivalence relation $\sim$ such that, given $x \in H (b, a)$ and $f \in \mathcal{C} (a, b)$, we have $H (f, \textrm{id}_a) x \sim H (\textrm{id}_b, f) x$. For $H (b, a) = \mathcal{C} (b, a)$, this amounts to taking the set of all endomorphisms in $\mathcal{C}$ modulo the smallest equivalence relation $\sim$ such that, given $x : b \to a$ and $f : a \to b$ in $\mathcal{C}$, $x \circ f \sim f \circ x$.

If $\mathcal{C}$ is a groupoid then we can describe the equivalence relation explicitly: given automorphisms $y : a \to a$ and $z : b \to b$ in $\mathcal{C}$, $y \sim z$ if and only if there is an isomorphism $f : a \to b$ such that $f \circ y = z \circ f$. Indeed, if $f \circ y = z \circ f$, then $y = (f^{-1} \circ z) \circ f$ and $z = f \circ (f^{-1} \circ z)$, i.e. $x = f^{-1} \circ z$ in the earlier formula gives us $y \sim z$. So we may think of $\int^{c : \mathcal{C}} \mathcal{C} (c, c)$ as the set of conjugacy classes of automorphisms in $\mathcal{C}$, if $\mathcal{C}$ is a groupoid. If $\mathcal{C}$ is a group considered as a one-object groupoid, then this really is the set of conjugacy classes as defined in elementary group theory.

Answer 4

The coend $c=\int^{X:\mathrm{Set}}\hom(X,X)$ seems to be rather subtle, but there is something that can be said. We have a family of maps $\omega_X:\hom(X,X)\to e$ for every set $X$, and these satisfy for all sets $X$ and $Y$ and functions $f:X\to Y$ and $g:Y\to X$ that $\omega_X(g\circ f)=\omega_Y(f\circ g)$. So the coend is the "universal trace" for sets.

Recall that given $f:X\to X$ that it factors as $f=i\circ s$ with $s:X \to f(X)$ a surjection and $i:f(X)\to X$ the inclusion. Hence, $\omega_X(f)=\omega_X(i\circ s)=\omega_{f(X)}(s\circ i)$. We can restrict the domain of $s$ to $\operatorname{im} f$, giving $f|_{f(X)}$, and so we have that $$\omega_X(f)=\omega_{f(X)} (f|_{f(X)\to f(X)}).$$ For all $f:X\to X$, let $rf=f|_{f(X)\to f(X)}$ be this restriction, and for $n\in\mathbb{N}$ let $r^nf$ be the $n$-fold iterated restriction. Hence, we have for all $n\in\mathbb{N}$ that $$\omega_X(f) = \omega_{f^n(X)}(r^nf).$$ If $X$ is finite, this iterated restriction eventually stabilizes to a bijection, which we will call $\operatorname{core}(f)$. (In fact, in this case its domain $\bigcap_n f^n(X)$ equals $\{x\in X\mid \exists n>0, f^n(x)=x\}$, the set of all elements on which the monoid generated by $f$ acts on with finite order. Infinite sets are more complicated. One thing you can prove is that $f(\bigcap_n f^n(X))=\bigcap_n f^n(X)$ if every fiber of $f$ is finite, a sort of variant of Konig's lemma.) When $f:X\to X$ is a bijection, then given any other bijection $g:X\to X$ we have that $\omega_X(f)=\omega_X(g\circ f\circ g^{-1})$, and so $\omega_X(f)$ gives an invariant of the conjugacy class of $f$. That is, $\omega_X$ can only see the cycle type of $f$.

If we restrict to $\mathrm{FinSet}$, then what we can use as a model for the coend is the set of all multisets of positive natural numbers, where $\omega_X(f)$ maps to the multiset consisting of all the cycle lengths in $\operatorname{core}(f)$.

For general sets, it seems to me that the coend can be described as $\coprod_{X:\mathrm{Set}}\hom(X,X)$ modulo this $r$ operator and conjugation. I'm not sure there's too much more we can say here -- things would be easier if we could just restrict $f$ to $\bigcap_n f^n(X)$, but the coend is telling us rich information about the behavior when $n$ is near infinity, not just when it's "at" infinity.