# Mono's and Epi's in the category Rel?

Sorry to ask such a trivial question, but I can't find the answer anywhere.

Question. What are the monomorphisms/epimorphisms in Rel?

Furthermore, what's the standard terminology for describing these ideas?

Here's my attempt at an answer, although I had to invent my own terminology. Let us write $f^{-1}$ for the converse of $f$, and $xy$ for the ordered pair $(x,y)$. Then we have:

Definition. For all relations $f : X \rightarrow Y$, define the following.

1. $f$ is total iff for all $x \in X$ there exists $y \in Y$ such that $xy \in f$.
2. $f$ is a tube (aka partial function) iff for all $x \in X$ and all $y,\bar{y} \in Y$ such that $xy \in f$ and $x\bar{y} \in f$, it holds that $y=\bar{y}$.
3. $f$ is cototal iff $f^{-1}$ is total.
4. $f$ is a cotube iff $f^{-1}$ is a tube.

Note that under these definitions, a function is a total tube. (In other words, a function is a total partial function. However, this is a very awkward wording.)

Anyway, under these definitions, I would expect that:

• The monomorphisms in Rel are precisely the total cotubes.
• The epimorphism in Rel are precisely the cototal tubes.

Once again, sorry if this is a very basic question, but I can't find the answer anywhere.

-
I think you might need to go back to the definition of "monomorphisms". It is supposed to be left-cancellative with respect to the composition operation. I'd say I expect monomorphisms to be injective functions, but I could be wrong. –  Tunococ Apr 4 '13 at 2:30

This is the kind of thing that is better worked out as an exercise than written anywhere explicitly in the literature, I think. Anyway...

The functor $\text{Hom}(1, -)$ preserves all limits, so it preserves monomorphisms (exercise, or see this blog post). It sends a relation $R : X \to Y$ to the induced direct image map $R_{\ast} : 2^X \to 2^Y$ on subsets, so in particular a monomorphism in $\text{Rel}$ needs to induce an injective such map. $\text{Hom}(1, -)$ is also faithful, so it reflects monomorphisms (exercise, or see this blog post). Thus a monomorphism is precisely a relation $R$ such that $R_{\ast}$ is injective.

In particular, $R_{\ast}$ needs to send each element of $X$ to distinct non-empty subsets of $Y$ (so $R$ is total in your terminology). This condition is necessary but not sufficient. Moreover, $R$ is not necessarily a cotube in your terminology. As a counterexample, consider

$$R : \{ 1, 2 \} \to \{ 3, 4, 5 \}$$

given by $R_{\ast}(1) = \{ 3, 4 \}, R_{\ast}(2) = \{ 4, 5 \}$ and extending by union. This counterexample also shows that $R$ is not necessarily a function.

Now, $\text{Rel}$ is a dagger category. The dagger (transpose) operation in any dagger category interchanges monomorphisms and epimorphisms, so we obtain a complete description of epimorphisms as well (in terms of the functor $\text{Hom}(-, 1)$ and inverse images, to be more explicit).

-
Thanks. Can I have hint for working out which monos split? –  goblin Apr 4 '13 at 9:07