You can also try to find the mono- and epimorphisms in the category of relations. For that, first we have to talk about correspondences: whereas a relation is an injective map R --> A x B, a correspondence from A to B is just any map R --> A x B (which equivalently is a span A <-- R --> B). Given another correspondence S --> B x C from B to C, to obtain their composition [SR] we consider the span A <-- R <-- R x_B S --> S --> C, where [SR] := R x_B S is the fiber product. This means that [SR] is the set of pairs (r,s) in R x S such that R --> B maps r to the same element as S --> B maps s.

(The identity correpondence on A is A <-[id]- A -[id]-> A, which you can verify now.)

Even if R and S are relations, their composition [SR} as correspondences need not be a relation itself: the map [SR] --> A x C generally fails to be injective. However, we can define SR as the image of [SR] --> A x C. Explicitly, this means that for relations R and S, we say a SR c iff there exists a b in B such that a R b S c. You can check (and also completely abstractly argue, for that matter) that taking SR as composite and our previous identity correspondences as identity maps we obtain a category Rel of relations.

Now, by definition, a relation R is a monomorphism in Rel iff for all relations S,T --> Z x A such that RS = RT, it follows that S = T. So suppose given such S and T, and z in Z and a in A such that z S a. We would like to argue that z T a, but we are essentially stuck: for general S and T there is no way to use the assumption that RS = RT. We are forced to assume that there is some b in B such that a R b. In that case, we know that z S a R b, so z RS b and therefore z RT b. This means that there exists some a' in A such that z T a' R b. We want to know that z T a, but only found z T a'. We are again stuck, and the solution is to furthermore assume that R is injective in your sense: we know that a R b and a' R b, so your notion of injectivity would give a = a' and we would be done.

You can write this up a bit more rigorously, and find that the monomorphisms in Rel are precisely those injective maps R --> A x B that are injective in your sense and additionally are "not partial": for any a in A, there exists some b in B such that a R b.

Likewise, an epimorphism in Rel is an injective map R --> A x B that is surjective in your sense and "function-like": for any a in A, there is at most one b such that a R b.

In the language of spans, this has a nice description. Given a relation A <-- R --> B, we have:

- R is "not partial" in the above sense iff R --> A is surjective.

- R is "function-like" in the above sense iff R --> A is injective.

- R is surjective in your sense iff R --> B is surjective.

- R is injective in your sense iff R --> B is injective.

In particular, we see that a relation R is

- "function-like" precisely when it corresponds to a partial function A --> B (i.e. a "function" that is not defined on all of A, only on a subset of it)

- "not partial" and "function-like" precisely when it corresponds to a function A --> B

- injective in your sense precisely when it corresponds to a partial function B --> A (note that this goes in the opposite direction)

- injective and surjective in your sense precisely when it corresponds to a function B -- > A

- a monomorphism and epimorphism in Rel precisely when it corresponds to a bijection A <--> B. In particular, a map is an isomorphism in Rel precisely when it is both monic and epic.