Epimorphisms of relations

Question

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.

Answer 1

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$.

Answer 2

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.

Answer 3

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.