Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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

1 Answer 1

up vote 4 down vote accepted

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

share|improve this answer
    
Thanks. Can I have hint for working out which monos split? –  goblin Apr 4 '13 at 9:07

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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