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.
- $f$ is total iff for all $x \in X$ there exists $y \in Y$ such that $xy \in f$.
- $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}$.
- $f$ is cototal iff $f^{-1}$ is total.
- $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.
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).