# Epimorphisms of relations

Let $$\bf Rel$$ be the category whose objects are sets and whose morphisms are relations.

What is an epimorphism in this category?

I have a sufficient condition, which is: $$R$$ is epic if the associated non-deterministic map $$A \to 2^B$$ is 'surjective on singletons'.

Another sufficient condition is for $$R$$ to be functional (i.e. total and single-valued) and surjective, since $${\bf Rel} = {\rm Kl}(P)$$, where $$P$$ is the covariant powerset monad: the left adjoint of the Kleisli adjunction sends functions to their graphs and, being a left adjoint, it preserves epimorphisms.

• What do you mean by the last paragraph? It's also true that $\mathbf{Vec}_k^{\text{fd}}$ is equivalent to its opposite category (via $\operatorname{Hom}_k(-,k)$), but that doesn't mean that all epimorphisms are monomorphisms... Sep 25 at 11:55
• You're right, I should've said 'endoepimorphism'. Indeed, that's true for finite dimensional vector spaces: surjectivity and injectivity imply each other for endomorphisms. Sep 25 at 13:25
• In your second condition, don’t you also need $R$ to be functional and surjective, in order to use the fact that the function-to-graph construction preserves epis? Which reduces your second condition to a special case of your first, I think. Sep 25 at 16:11
• @PeterLeFanuLumsdaine ah, yes, of course :) Sep 26 at 8:39

OP’s condition “$$\newcommand{\P}{\mathcal{P}}A \to \P B$$ is surjective on singletons” is indeed necessary and sufficient.

For this, I’ll first give a characterisation that holds just by abstract nonsense: $$R \subseteq A \times B \newcommand{\Rel}{\mathrm{Rel}}$$ is epi in $$\Rel$$ if and only if the associated map $$\check{R} : \P B \to \P A$$ is injective. To see this, note by duality it’s equivalent to show that such $$R$$ is mono precisely if $$\hat{R} : \P A \to \P B$$ is injective. For this, note that $$\hat{R}$$ is the image of $$R$$ under the “forgetful” functor $$\Rel \to \newcommand{\Set}{\mathrm{Set}}\Set$$ (seeing $$\Rel$$ as the Kleisli category of the covariant powerset monad). This functor is faithful, so it reflects monos, and it’s representable as $$\Rel(1,-)$$, so it preserves them.

So $$R \subseteq A \times B$$ is mono just if $$\hat{R} : \P A \to \P B$$ is injective, and dually, is epi just if $$\check{R} : \P B \to \P A$$ is injective. Now I claim injectivity of $$\check{R}$$ is equivalent to $$\bar{R} : A \to \P B$$ being surjective on singletons, or in other words, that for each $$b \in B$$, there’s some $$a \in A$$ that is related just to $$b$$ under $$R$$. Assuming $$\check{R}$$ is injective, we know that $$\check{R}(B \setminus \{b\}) \subsetneq \check{R}(B)$$, so taking some element of their difference, we get an element of $$A$$ related just to $$b$$. Conversely, assuming $$\bar{R} : A \to \P B$$ is surjective on singletons, then for any $$s,t \subseteq B$$, take some $$b$$ in their difference, and some $$a$$ related just to $$b$$; then $$\check{R}(s)$$ and $$\check{R}(t)$$ are distinguished by $$a$$.

• In fact, I realise afterwards this is equivalent to the map $A \to PB$ being surjective on singletons as OP proposes, so that condition is both necessary and sufficient after all. Unfortunately there’s just been a fire alarm in my office so I can’t give details now (cumbersome to edit from phone); can do so when back at computer unless someone else does first! Sep 25 at 16:21
• I hope all category theory papers are safe! 🔥 Sep 25 at 16:45
• @MartinBrandenburg: Back at the office now; can confirm nothing burned, presumably was just a test… Sep 26 at 9:36
• Thanks for the answer! Am I understanding this right that in this way you proved that $R$ is epi iff $\hat R$ is injective? That feels counterintuitive! Sep 26 at 9:57
• @seldon: Roughly but not exactly — note I’m distinguishing $\hat{R} :\newcommand{\pow}{\mathcal{P}} \pow A \to \pow B$ and $\check{R} = \widehat{R^T} : \pow B \to \pow A$ (for $R$ seen as a relation from $A$ to $B$). For intuition I’d say: seeing it as a Kleisli I think makes it reasonably intuitive that $R$ is monic just if $\hat{R}$ is injective; then by the self-duality of $\mathbf{Rel}$, $R$ is epic iff its transpose $R^T$ is monic, hence iff $\check{R}$ is injective. The switch between epic/injective comes because of the duality — $\check{R}$ is a contravariant functor applied to $R$. Sep 26 at 10:05

Also I guess it'd also be useful to reason by duality: since $$\bf Rel^{\rm op} = Rel$$, an endoepimorphism must necessarily also be a monomorphism.

This does not follow. Duality only tells us that a relation $$R : A \to B$$ is an epimorphism iff the transpose relation $$R^T : B \to A$$ is a monomorphism. Even if $$A = B$$ this doesn't imply that an endoepimorphism is a monomorphism, because relations are not generally equal to their transposes. The example of finite-dimensional vector spaces is misleading; it is true that an endomorphism of a finite-dimensional vector space is an epimorphism iff it's a monomorphism but it's not because of duality (which only tells you that $$T : V \to W$$ is an epimorphism iff $$T^{\ast} : W^{\ast} \to V^{\ast}$$ is a monomorphism).

In fact using the other answers it's not hard to construct an endoepimorphism in $$\text{Rel}$$ that is not a monomorphism; it suffices to construct a relation $$R : X \to X$$ on a set $$X$$ such that the induced map $$X \to 2^X$$ in one direction is surjective on singletons but not in the other direction. We can just take $$R$$ to be (the graph of) a function $$f : \mathbb{N} \to \mathbb{N}$$ which is surjective but not injective, e.g. $$f(n) = \lfloor \frac{n}{2} \rfloor$$ or similar.

• I guess what OP had in mind may have been that given the self-duality, characterising epis is equivalent to characterising monos (as I use in my answer). Sep 26 at 8:06
• Indeed.. I was too hasty. Thanks for pointing this out! Sep 26 at 8:43

I believe surjective on singletons is neccessary as well. For this we have to show that a relation $$f:X\to Y$$ that is not surjective on singletons is not an epimorphism.

Let $$a\in Y$$ be a point such that $$\{a\}$$ is not hit by the associated non-determininistic map $$F$$. If $$a$$ is not hit at all, e.g. for all $$x$$ we have $$a\notin F(x)$$, then postcomposing with the relation $$\{(a,a)\}:Y\to Y$$ and postcomposing with the empty relation give the same relation, so $$f$$ cannot be an epimorphism. So we can now assume otherwise and thus $$Y$$ has to have at least two elements, say $$Y=\{a\}\amalg Y'$$ with nonempty $$Y'$$.

Then we can postcompose with the relation $$g=\{(a,a)\}\cup Y'\times Y'$$ and with the relation $$g'=a\times Y\cup Y'\times Y'$$. We have for the nondeterministic map of both compositions $$g\circ f$$ and $$g'\circ f$$ that the image of $$x$$ is either empty, if $$F(x)$$ is empty, or it is $$Y'$$ if $$a\notin F(x)$$.

In the case where $$a\in F(x)$$ we get by assumption that $$F(x) =\{a\}\amalg Z$$ with nonempty $$Z$$. By definition of the composition of relations, the nondeterministic map of both compositions sends $$x$$ to $$Y$$.

Thus both compositions are the same relation and thus $$f$$ cannot be an epimorphism.

• Nice, thanks a lot! Sep 26 at 8:45