As in the title, my goal is to find the left/right invertible morphisms and mono/epimorphisms in the Rel category. I am quite new to categorical concepts, I tried to do this an exercise, I have found easier ways to do this using Yoneda Lemma (which I am not quite familiar with, see here). My reason of interest was to better study binary relations since I did not have a dedicated lessons at college and wanted to get familiar with categorical concepts on more familiar, easier categories.
Since Rel is a self-dual dagger category, by sending a relation to its converse (denote the converse of $R$ by $R^T = \left\{ (b, a) \vert (a, b) \in R \right\}$), it is enough to study left invertible morphisms and monomorphisms.
Notations:
• A relation $R \subseteq A \times B$ is total iff $\forall a \in A \colon \exists b \in B \colon (a, b) \in R$ iff $R^T \circ R \supseteq \text{id}_A$
• A relation $R \subseteq A \times B$ is surjective iff $\forall b \in B \colon \exists a \in A \colon (a, b) \in R$ iff $R \circ R^T \supseteq \text{id}_B$
• A relation $R \subseteq A \times B$ is univalent iff $\forall a \in A \colon \forall b1, b2 \in B \colon ((a, b1) \in R \text{ and } (a, b2) \in R) \implies b1 = b2$ iff $R \circ R^T \subseteq \text{id}_B$
• A relation $R \subseteq A \times B$ is injective iff $\forall b \in B \colon \forall a1, a2 \in A \colon ((a1, b) \in R \text{ and } (a2, b) \in R) \implies a1 = a2$ iff $R^T \circ R \subseteq \text{id}_A$
If $S$ and $R$ are morphisms, then:
• If $S \circ R$ is total then $R$ is total
• If $S \circ R$ is surjective then $S$ is surjective
• If $S \circ R$ is univalent then $S \vert_{\text{Range}(R)}$ is univalent
• If $S \circ R$ is injective then $R \vert^{\text{Domain}(S)}$ is injective
where $\text{Range}(R) = \left\{b | (a, b) \in R \right\}$ and $\text{Domain}(S) = \left\{ a | (a, b) \in S \right\}$
A morphism in $R \subseteq A \times B$ Rel is left invertible if there is a morphism $S \subseteq B \times A$ such that $S \circ R = \text{id}_A$. From the properties above it is clear that $R$ must be total. We do not need $R$ to be injective, even though the properties above may lead use to believe that. Here is a counterexample: $$ A = \left\{ x, y \right\}, B = \left\{ 1, 2, 3 \right\}, R = \left\{ (x,1),(x,2),(y,1),(y,3) \right\}, S = \left\{ (2, x), (3, y) \right\}, $$
We need $R$ to be total, but to be injective on "a small enough subset of $B$".
Say a relation $R$ has property $P$ iff $$\forall a \in A \colon \exists b \in B \colon \forall a' \in A \colon ((a, b) \in R \text{ and } (a', b) \in R) \implies a = a'$$ If $R$ is total this is strictly weaker than injectivity since it requires for any element $a$ of $A$ to exist a special "exclusive" element of $a$, $b_a$ in $B$ such that no other $a'$ from $A$ is in relation to $b_a$.
I will prove that $R$ has property $P$ iff it is left invertible.
"$\implies$"Start by defining $C = \text{ choose one exclusive element for each } a \in A$ (using the axiom of choice).
Then $S \subseteq B \times A, \, S = \left\{ (b, a) | b \in C \text{ and } (a, b) \in R \right\}$. By construction $S \circ R = \text{id}_A$.
"$\impliedby$" If $S \circ R = \text{id}_A$, then $R$ is total and $R \vert^{\text{Domain}(S)}$ is injective which is enough to prove $R$ has property $P$.
Now for monomorphisms. Let $R \subseteq A \times B$ be a monomorphism, i.e. for any $S_1, S_2 \subseteq C \times A, R \circ S_1 = R \circ S_2 \implies S_1 = S_2$.
I claim $R$ is a monomorphism iff it has property $P$.
"$\impliedby$" If $R$ has property $P$ then $R$ is left invertible then the conclusion is trivial (multiply by the left inverse).
"$\implies$" Assume $R$ is mono. Assume for the sake of contradiction that $R$ does not have property $P$, i.e. $$\exists a \in A \colon \forall b \in R[\{a\}] \colon \exists a' \in A \colon (a, b) \in R \text{ and } (a', b) \in R \text{ and } a \neq a' \iff R[\{a\}] \subseteq R[A \setminus \{a\}]$$ Take $C = \{!\}$ a singleton set and take $S$ with $S[C]=A$ and $T$ with $T[C]=A \setminus \{a\}$. Therefore $R \circ S = R[A] = R[A \setminus \{a\}]=R \circ T$. Since $R$ is mono we have $S=T$ contradiction.
Since Rel is self dual, $R$ is left invertible/mono iff $R^T$ is right invertible/epic. $R$ is total iff $R^T$ is surjective and $R$ is univalent iff $R^T$ is injective. So one could dually define the property $P$.
Does this in-between property of injectivity and univalence have a consacrated name? I have looked it up but did not find any names for this property, and it seems an important one for the category Rel. Is it possible to define such a property like $P$ so that it is not needed to be total? Like a strictly weaker version of $P$ such that injectivity implies $P$? Are there names also for the dual notion of $P$?
Are such properties relevant for this category? I feel like it should be an important property, but I did not found anything.
