9
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • $\begingroup$ 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... $\endgroup$
    – R. van Dobben de Bruyn
    Sep 25 at 11:55
  • $\begingroup$ 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. $\endgroup$
    – seldon
    Sep 25 at 13:25
  • 2
    $\begingroup$ 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. $\endgroup$
    – Peter LeFanu Lumsdaine
    Sep 25 at 16:11
  • $\begingroup$ @PeterLeFanuLumsdaine ah, yes, of course :) $\endgroup$
    – seldon
    Sep 26 at 8:39

3 Answers 3

Reset to default
8
$\begingroup$

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

Improve this answer
$\endgroup$
5
  • 3
    $\begingroup$ 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! $\endgroup$
    – Peter LeFanu Lumsdaine
    Sep 25 at 16:21
  • 1
    $\begingroup$ I hope all category theory papers are safe! 🔥 $\endgroup$
    – Martin Brandenburg
    Sep 25 at 16:45
  • 1
    $\begingroup$ @MartinBrandenburg: Back at the office now; can confirm nothing burned, presumably was just a test… $\endgroup$
    – Peter LeFanu Lumsdaine
    Sep 26 at 9:36
  • $\begingroup$ 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! $\endgroup$
    – seldon
    Sep 26 at 9:57
  • 1
    $\begingroup$ @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$. $\endgroup$
    – Peter LeFanu Lumsdaine
    Sep 26 at 10:05
5
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ 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). $\endgroup$
    – Peter LeFanu Lumsdaine
    Sep 26 at 8:06
  • $\begingroup$ Indeed.. I was too hasty. Thanks for pointing this out! $\endgroup$
    – seldon
    Sep 26 at 8:43
4
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Nice, thanks a lot! $\endgroup$
    – seldon
    Sep 26 at 8:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.