Warning 8.5.11.1.7 (02SE): Natural Conditions That Fail To Characterise Epimorphisms in $\mathsf{Rel}$

8.5.11 Epimorphisms and 2-Categorical Epimorphisms

Explanation 8.5.11.1.1 ▶ Epimorphisms in $\mathsf{Rel}$

In this section, we characterise:

•
The 1-categorical epimorphisms in $\mathsf{Rel}$, following , .
•
The 2-categorical epimorphisms in $\boldsymbol {\mathsf{Rel}}$, following Chapter 14: Types of Morphisms in Bicategories, Section 14.2.

More specifically:

•
Proposition 8.5.11.1.2 gives conceptual characterisations of the epimorphisms in $\mathsf{Rel}$.
•
Proposition 8.5.11.1.3 gives point-set characterisations of the epimorphisms in $\mathsf{Rel}$.
•
Warning 8.5.11.1.7 lists a few conditions that look natural but fail to characterise epimorphisms in $\mathsf{Rel}$.
•
Proposition 8.5.11.1.9 and Proposition 8.5.11.1.10 characterise the 2-categorical epimorphisms in $\boldsymbol {\mathsf{Rel}}$.¹

Essentially, an epimorphism $R\colon A\mathrel {\rightarrow \kern -9.5pt\mathrlap {|}\kern 6pt}B$ in $\mathsf{Rel}$ looks like this:

In particular:

1.
$R$ should contain a surjection $f\colon A\twoheadrightarrow B$.
2.
$R$ doesn’t need to be injective, so $R$ can map different elements of $A$ to the same element of $B$.
3.
$R$ can be non-functional, mapping elements of $A$ to multiple elements of $B$.
4.
$R$ can be non-total, so $R$ doesn’t need to be defined on all of $A$.
5.
For each $b\in B$, there must exist some $a\in A$ with $R(a)=\left\{ b\right\} $.

Moreover, if $R$ is functional, then being an epimorphism is equivalent to being surjective.

¹Summary: As it turns out, every 1-morphism in $\boldsymbol {\mathsf{Rel}}$ is representably faithful and most other notions of 2-categorical epimorphism agree with the usual (1-categorical) notion of epimorphism.

Proposition 8.5.11.1.2 ▶ Characterisations of Epimorphisms in $\mathsf{Rel}$ I

Let $R\colon A\mathrel {\rightarrow \kern -9.5pt\mathrlap {|}\kern 6pt}B$ be a relation. The following conditions are equivalent:¹

1.
The relation $R$ is an epimorphism in $\mathsf{Rel}$.
2.
The direct image function

\[ R_{!}\colon \mathcal{P}(A)\to \mathcal{P}(B) \]

associated to $R$ is surjective.
3.
The coinverse image function

\[ R_{-1}\colon \mathcal{P}(B)\to \mathcal{P}(A) \]

associated to $R$ is injective.
4.
The inverse image function

\[ R^{-1}\colon \mathcal{P}(B)\to \mathcal{P}(A) \]

associated to $R$ is injective.
5.
The codirect image function

\[ R_{*}\colon \mathcal{P}(A)\to \mathcal{P}(B) \]

associated to $R$ is surjective.
6.
The coinverse image functor

\[ R_{-1}\colon (\mathcal{P}(B),\subset )\to (\mathcal{P}(A),\subset ) \]

associated to $R$ is full.
7.
The inverse image functor

\[ R^{-1}\colon (\mathcal{P}(B),\subset )\to (\mathcal{P}(A),\subset ) \]

associated to $R$ is full.
8.
The direct image functor

\[ R_{!}\colon (\mathcal{P}(A),\subset )\to (\mathcal{P}(B),\subset ) \]

associated to $R$ is essentially surjective.
9.
The coinverse image functor

\[ R_{-1}\colon (\mathcal{P}(B),\subset )\to (\mathcal{P}(A),\subset ) \]

associated to $R$ is fully faithful.
10.
The inverse image functor

\[ R^{-1}\colon (\mathcal{P}(B),\subset )\to (\mathcal{P}(A),\subset ) \]

associated to $R$ is fully faithful.
11.
The codirect image functor

\[ R_{*}\colon (\mathcal{P}(A),\subset )\to (\mathcal{P}(B),\subset ) \]

associated to $R$ is essentially surjective.
12.
For each pair of relations $S,T\colon B\mathrel {\rightrightarrows \kern -9.5pt\mathrlap {|}\kern 6pt}X$, the following condition is satisfied:
- (★)
13.
There exists an injective function $f\colon B\hookrightarrow A$ satisfying the following conditions:²
1. (a)
  We have $\operatorname {\mathrm{Gr}}(f)\subset R^{\dagger }$.³
2. (b)
  The diagram
  commutes.⁴
14.
We have
In other words, we have

\[ U=\underbrace{\left\{ b\in B\ \middle |\ R^{-1}(b)\subset R^{-1}(U)\right\} }_{=R_{*}(R^{-1}(U))} \]

for each $U\in \mathcal{P}(B)$.
15.
We have
In other words, we have

\[ U=\underbrace{\left\{ b\in B\ \middle |\ \begin{aligned} & \text{there exists some $a\in R^{-1}(b)$}\\ & \text{such that we have $R(a)\subset U$}\end{aligned}\right\} }_{=R_{!}(R_{-1}(U))} \]

for each $U\in \mathcal{P}(B)$.

¹Item 4, Item 3, Item 7, and Item 6 unwind respectively to the following statements:
- •
  For each $U,V\in \mathcal{P}(B)$, if $R^{-1}(U)=R^{-1}(V)$, then $U=V$.
- •
  For each $U,V\in \mathcal{P}(B)$, if $R_{-1}(U)=R_{-1}(V)$, then $U=V$.
- •
  For each $U,V\in \mathcal{P}(B)$, if $R^{-1}(U)\subset R^{-1}(V)$, then $U\subset V$.
- •
  For each $U,V\in \mathcal{P}(B)$, if $R_{-1}(U)\subset R_{-1}(V)$, then $U\subset V$.
²We are assuming the axiom of choice for this item (Item 13).
³In other words, for each $b\in B$, we have $f(b)\in R^{-1}(b)$.
⁴In other words, for each $b\in B$, we have $R(f(b))=\left\{ b\right\} $.

Proof of Proposition 8.5.11.1.2.

We will prove this by showing:

•
Step 1: Item 4$\iff $Item 3 and Item 6$\iff $Item 7.
•
Step 2: Item 1$\iff $Item 2.
•
Step 3: Item 1$\iff $Item 4.
•
Step 4: Item 4$\iff $Item 7.
•
Step 5: Item 2$\iff $Item 8.
•
Step 6: Item 3$\iff $Item 9.
•
Step 7: Item 4$\iff $Item 10.
•
Step 8: Item 5$\iff $Item 11.
•
Step 9: Item 7$\iff $Item 12.
•
Step 10: Item 1$\iff $Item 13.
•
Step 11: Item 1$\iff $Item 14.
•
Step 12: Item 1$\iff $Item 15.

Step 1: Item 4$\iff $Item 3 and Item 6$\iff $Item 7

This follows from Item 17 of Proposition 8.7.3.1.3.

Step 2: Proof of Item 1$\iff $Item 2

We defer this proof to Corollary 8.5.11.1.6.

Step 3: First Proof of Item 1$\iff $Item 4

We claim that Item 1 and Item 4 are equivalent:

•
Item 1$\implies $Item 4: Let $U,V\in \mathcal{P}(B)$ and consider the diagram
By Remark 8.7.1.1.3, we have

\begin{align*} R^{-1}(U) & = U\mathbin {\diamond }R,\\ R^{-1}(V) & = V\mathbin {\diamond }R. \end{align*}

Now, if $U\mathbin {\diamond }R=V\mathbin {\diamond }R$, i.e. $R^{-1}(U)=R^{-1}(V)$, then $U=V$ since $R$ is assumed to be an epimorphism, showing $R^{-1}$ to be injective.
•
Item 4$\implies $Item 1: Conversely, suppose that $R^{-1}$ is injective, consider the diagram
and suppose that $S\mathbin {\diamond }R=T\mathbin {\diamond }R$. Note that, since $R^{-1}$ is injective, given a diagram of the form
if $R^{-1}(U)=U\mathbin {\diamond }R=V\mathbin {\diamond }R=R^{-1}(V)$, then $U=V$. In particular, for each $x\in X$, we may consider the diagram
for which we have $[x]\mathbin {\diamond }S\mathbin {\diamond }R=[x]\mathbin {\diamond }T\mathbin {\diamond }R$, implying that we have

\[ S^{-1}(x)=[x]\mathbin {\diamond }S=[x]\mathbin {\diamond }T=T^{-1}(x) \]

for each $x\in X$. Thus $S=T$ and $R$ is an epimorphism.

Step 3.5: Second Proof of Item 1$\iff $Item 4

A more abstract proof can also be given, following [Yuan, Mono's and epi's in the category Rel?]:

•
Item 1$\implies $Item 4: Assume that $R$ is an epimorphism.
- •
  We first notice that the functor $\mathrm{Rel}(-,\mathrm{pt})\colon \mathrm{Rel}^{\mathsf{op}}\to \mathsf{Sets}$ maps $R$ to $R^{-1}$ by Remark 8.7.3.1.2.
- •
  Since $\mathrm{Rel}(-,\mathrm{pt})$ preserves limits by , of , it follows by , of that $\mathrm{Rel}(-,\mathrm{pt})$ also preserves epimorphisms.
- •
  That is: $\mathrm{Rel}(-,\mathrm{pt})$ sends epimorphisms in $\mathrm{Rel}^{\mathsf{op}}$ to epimorphisms in $\mathsf{Sets}$.
- •
  The epimorphisms $\mathrm{Rel}^{\mathsf{op}}$ are precisely the epimorphisms in $\mathrm{Rel}$ by , of .
- •
  Since $R$ is an epimorphism and $\mathrm{Rel}(-,\mathrm{pt})$ maps $R$ to $R^{-1}$, it follows that $R^{-1}$ is an epimorphism.
- •
  Since the epimorphisms in $\mathsf{Sets}$ are precisely the injections (, of ), it follows that $R^{-1}$ is injective.
•
Item 4$\implies $Item 1: Assume that $R^{-1}$ is injective.
- •
  We first notice that the functor $\mathrm{Rel}(-,\mathrm{pt})\colon \mathrm{Rel}^{\mathsf{op}}\to \mathsf{Sets}$ maps $R$ to $R^{-1}$ by Remark 8.7.3.1.2.
- •
  Since the epimorphisms in $\mathsf{Sets}$ are precisely the injections (, of ), it follows that $R^{-1}$ is an epimorphism.
- •
  Since $\mathrm{Rel}(-,\mathrm{pt})$ is faithful, it follows by , of that $\mathrm{Rel}(,\mathrm{pt})$ reflects epimorphisms.
- •
  That is: $\mathrm{Rel}(-,\mathrm{pt})$ reflects epimorphisms in $\mathsf{Sets}$ to epimorphisms in $\mathrm{Rel}^{\mathsf{op}}$.
- •
  The epimorphisms $\mathrm{Rel}^{\mathsf{op}}$ are precisely the epimorphisms in $\mathrm{Rel}$ by , of .
- •
  Since $R^{-1}$ is an epimorphism and $\mathrm{Rel}(-,\mathrm{pt})$ maps $R$ to $R^{-1}$, it follows that $R$ is an epimorphism.

Step 4: Item 4$\iff $Item 7

We claim that Item 4 and Item 7 are equivalent:

•
Item 4$\implies $Item 7: We proceed in a few steps:
- •
  Let $U,V\in \mathcal{P}(B)$ such that $R^{-1}(U)\subset R^{-1}(V)$, assume $R^{-1}$ to be injective, and consider the set $U\cup V$.
- •
  Since $R^{-1}(U)\subset R^{-1}(V)$, we have
  
  \begin{align*} R^{-1}(U\cup V) & = R^{-1}(U)\cup R^{-1}(V)\\ & = R^{-1}(V), \end{align*}
  
  where we have used of for the first equality.
- •
  Since $R^{-1}$ is injective, this implies $U\cup V=V$.
- •
  Thus $U\subset V$, as we wished to show.
•
Item 4$\implies $Item 7: We proceed in a few steps:
- •
  Suppose Item 7 holds, and let $U,V\in \mathcal{P}(B)$ such that $R^{-1}(U)=R^{-1}(V)$.
- •
  Since $R^{-1}(U)=R^{-1}(V)$, we have $R^{-1}(U)\subset R^{-1}(V)$ and $R^{-1}(V)\subset R^{-1}(U)$.
- •
  By assumption, this implies $U\subset V$ and $V\subset U$.
- •
  Thus $U=V$, showing $R^{-1}$ to be injective.

Step 5: Item 2$\iff $Item 8

This follows from the fact that $\mathcal{P}(B)$ is locally posetal.

Step 6: Item 3$\iff $Item 9

This follows from the fact that $\mathcal{P}(A)$ is locally posetal.

Step 7: Item 4$\iff $Item 10

This follows from the fact that $\mathcal{P}(A)$ is locally posetal.

Step 8: Item 5$\iff $Item 11

This follows from the fact that $\mathcal{P}(B)$ is locally posetal.

Step 9: Item 7$\iff $Item 12

We claim that Item 7 and Item 12 are equivalent:

•
Item 7$\implies $Item 12: Let $U,V\in \mathcal{P}(B)$ and consider the diagram
By Remark 8.7.3.1.2, we have

\begin{align*} R^{-1}(U) & = U\mathbin {\diamond }R,\\ R^{-1}(V) & = V\mathbin {\diamond }R. \end{align*}

Now, if $U\mathbin {\diamond }R\subset V\mathbin {\diamond }R$, then $R^{-1}(U)\subset R^{-1}(V)$. By assumption, we then have $U\subset V$.
•
Item 12$\implies $Item 7: Consider the diagram
and suppose that $S\mathbin {\diamond }R\subset T\mathbin {\diamond }R$. Note that, by assumption, given a diagram of the form
if $R^{-1}(U)=R\mathbin {\diamond }U\subset R\mathbin {\diamond }V=R^{-1}(V)$, then $U\subset V$. In particular, for each $x\in X$, we may consider the diagram
for which we have $[x]\mathbin {\diamond }S\mathbin {\diamond }R\subset [x]\mathbin {\diamond }T\mathbin {\diamond }R$, implying that we have

\[ S^{-1}(x)=[x]\mathbin {\diamond }S\subset [x]\mathbin {\diamond }T=T^{-1}(x) \]

for each $x\in X$, implying $S\subset T$.

This finishes the proof.

Step 10: Item 1$\iff $Item 13

We defer this proof to Corollary 8.5.11.1.4.

Step 11: Item 1$\iff $Item 14

We defer this proof to Corollary 8.5.11.1.4.

Step 12: Item 1$\iff $Item 15

We defer this proof to Corollary 8.5.11.1.5.

Proposition 8.5.11.1.3 ▶ Characterisations of Epimorphisms in $\mathsf{Rel}$ II

Let $R\colon A\mathrel {\rightarrow \kern -9.5pt\mathrlap {|}\kern 6pt}B$ be a relation. The following conditions are equivalent:

1.
The relation $R$ is an epimorphism in $\mathsf{Rel}$.
2.
For each $b\in B$ and each $U\in \mathcal{P}(B)$, if $R^{-1}(b)\subset R^{-1}(U)$, then $b\in U$.
3.
For each $b\in B$, there exists some $a\in A$ such that $R(a)=\left\{ b\right\} $.

Moreover, if $R$ is an epimorphism, then it is surjective, and the converse holds if $R$ is functional.

Proof of Proposition 8.5.11.1.3.

We will prove this by showing:

•
Step 1: Item 1$\implies $Item 2.
•
Step 2: Item 2$\implies $Item 3.
•
Step 3: Item 3$\implies $Item 1.
•
Step 4: The second half of the statement of Proposition 8.5.11.1.2.

Step 1: Item 1$\implies $Item 2

We proceed in a few steps:

•
If $R$ is an epimorphism, then, by Item 4 of Proposition 8.5.11.1.2, the functor

\[ R^{-1}\colon (\mathcal{P}(A),\subset )\to (\mathcal{P}(B),\subset ) \]

is full.
•
As a result, given $b\in B$ and $U\in \mathcal{P}(B)$ such that $R^{-1}(b)\subset R^{-1}(U)$, it follows that $\left\{ b\right\} \subset U$.
•
Thus, we have $b\in U$.

Step 2: Item 2$\implies $Item 3

We proceed in a few steps:

•
Let $b\in B$ and consider the subset $U=B\setminus \left\{ b\right\} $.
•
Since $b\not\in U$, we have $R^{-1}(b)\centernot {\subset }R^{-1}(U)$ by the contrapositve of Item 2.
•
As a result, there must exist some $a\in R^{-1}(b)$ with $a\not\in R^{-1}(U)$.
•
In particular, we have $b\in R(a)$.
•
Moreover, the condition $a\not\in R^{-1}(U)=R^{-1}(B\setminus \left\{ b\right\} )$ means that, if $b'\in B\setminus \left\{ b\right\} $, then $b'\not\in R(a)$.
•
Thus $R(a)=\left\{ b\right\} $.

Step 3: Item 3$\implies $Item 1

We proceed in a few steps:

•
By the equivalence between Item 1 and Item 7 of Proposition 8.5.11.1.2, to show that $R$ is an epimorphism it suffices to prove that, for each $U,V\in \mathcal{P}(B)$, if $R^{-1}(U)\subset R^{-1}(V)$, then $U\subset V$.
•
So let $u\in U$ and assume $R^{-1}(U)\subset R^{-1}(V)$.
•
By assumption, there exists some $a\in A$ with $R(a)=\left\{ u\right\} $.
•
In particular, $a\in R^{-1}(U)$.
•
Since $R^{-1}(U)\subset R^{-1}(V)$, we also have $a\in R^{-1}(V)$.
•
Thus, there exists some $v\in V$ with $a\in R(v)$.
•
However, $R(a)=\left\{ u\right\} $, so we must in fact have $v=u$.
•
Therefore $u\in V$, showing that $U\subset V$.

Step 4: Proof of the Second Half of Proposition 8.5.11.1.3

We claim that $R$ being an epimorphism implies surjectivity, and the converse holds if $R$ is functional:

•
If $R$ Is an Epimorphism, Then $R$ Is Surjective: Consider the diagram
where $b\sim _{S}0$ for each $b\in B$ and where we have

\[ b\sim _{T}\begin{cases} 0 & \text{if $b\in \mathrm{Im}(R)$,}\\ 1 & \text{otherwise} \end{cases} \]

for each $b\in B$.
- •
  We claim that $S\mathbin {\diamond }R=T\mathbin {\diamond }R$:
  - •
    If $R(a)=\text{Ø}$, then
    
    \begin{align*} [S\mathbin {\diamond }R](a) & = \text{Ø}\\ [T\mathbin {\diamond }R](a) & = \text{Ø}\end{align*}
    
    by the definition of relational composition, so $[S\mathbin {\diamond }R](a)=[T\mathbin {\diamond }R](a)$.
  - •
    If $R(a)\neq \text{Ø}$, then we have $a\sim _{S\mathbin {\diamond }R}0$ and $a\sim _{T\mathbin {\diamond }R}0$ by the definition of $S$ and $T$, with no element of $A$ being related to $1$ by $S\mathbin {\diamond }R$ or $T\mathbin {\diamond }R$.
- •
  Now, since $R$ is an epimorphism, we have $S=T$.
- •
  However, by the definition of $T$, this implies $\mathrm{Im}(R)=B$.
- •
  Thus $R$ is surjective.
•
If $R$ Is Functional and Surjective, Then $R$ Is an Epimorphism: Let $U,V\in \mathcal{P}(B)$, consider the diagram
where $R_{-1}(U)=R_{-1}(V)$, and let $b\in U$.
- •
  By surjectivity, there exists some $a\in A$ such that $a\in R^{-1}(b)$.
- •
  Since $R_{-1}(U)=R_{-1}(V)$, if $R(a)\subset U$, then $R(a)\subset V$.
- •
  Since $R$ is functional, we have $R(a)=\left\{ b\right\} $, so $R(a)\subset U$.
- •
  Thus, $R(a)\subset V$, and $b\in V$.
- •
  A similar argument shows that if $b\in V$, then $b\in U$.
- •
  Thus $U=V$, showing $R_{-1}$ to be injective.
- •
  By the equivalence between Item 1 and Item 3 of Proposition 8.5.11.1.2, this shows $R$ to be an epimorphism.

This finishes the proof.

Corollary 8.5.11.1.4 ▶ Characterisations of Epimorphisms in $\mathsf{Rel}$ III

Item 1, Item 13, and Item 14 of Proposition 8.5.11.1.2 are indeed equivalent.

Proof of Corollary 8.5.11.1.4.

Item 1$\iff $Item 13

We claim that Item 3 of Proposition 8.5.11.1.3 is equivalent to Item 13 of Proposition 8.5.11.1.2:

•
Item 3 of Proposition 8.5.11.1.3$\implies $Item 13: By assumption, given $b\in B$, there exists some $a\in A$ such that $R(a)=\left\{ b\right\} $. Invoking the axiom of choice, we may pick one such $a$ for each $b\in B$, giving us our desired function $f\colon B\to A$. All the requirements listed in Item 13 then follow by construction.
•
Item 13$\implies $Item 3 of Proposition 8.5.11.1.3: Given $b\in B$, we may pick $a=f(b)$, in which case $R(f(b))$ will be equal to $\left\{ b\right\} $ by assumption.

By Proposition 8.5.11.1.3, Item 3 of Proposition 8.5.11.1.3 is equivalent to Item 1 of Proposition 8.5.11.1.3. Since Item 1 of Proposition 8.5.11.1.3 is exactly the same condition as Item 1 of Proposition 8.5.11.1.2, the result follows.

Item 1$\iff $Item 14

Indeed, we have

\begin{align*} [R_{*}\circ R^{-1}](U) & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}R_{*}(R^{-1}(U))\\ & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\left\{ b\in B\ \middle |\ R^{-1}(b)\subset R^{-1}(U)\right\} \end{align*}

for each $U\in \mathcal{P}(B)$. As a result, the condition $R_{*}\circ R^{-1}=\operatorname {\mathrm{id}}_{\mathcal{P}(B)}$ becomes

\[ \left\{ b\in B\ \middle |\ R^{-1}(b)\subset R^{-1}(U)\right\} =U, \]

which holds precisely when Item 2 of Proposition 8.5.11.1.3 does. By Proposition 8.5.11.1.3, that in turn holds precisely if Item 1 of Proposition 8.5.11.1.3 holds. Since Item 1 of Proposition 8.5.11.1.3 is exactly the same condition as Item 1 of Proposition 8.5.11.1.2, the result follows.

Corollary 8.5.11.1.5 ▶ Characterisations of Epimorphisms in $\mathsf{Rel}$ IV

Item 1 and Item 15 of Proposition 8.5.11.1.2 are indeed equivalent.

Proof of Corollary 8.5.11.1.5.

Item 1$\implies $Item 15

To show that $R$ is an epimorphism, we will prove that for each $b\in B$, there exists some $a\in A$ such that $R(a)=\left\{ b\right\} $. The will then follow from Item 3 of Proposition 8.5.11.1.3.

•
Let $b\in B$ and consider $U=\left\{ b\right\} $.
•
By assumption, we have $U=R_{!}(R_{-1}(U))$.
•
In particular, this means that $b\in R_{!}(R_{-1}(\left\{ b\right\} ))$.
•
Unwinding the definition, this means there exists some $a\in R^{-1}(b)$ such that $R(a)\subset \left\{ b\right\} $.
- •
  The condition $a\in R^{-1}(b)$ implies that $b\in R(a)$.
- •
  The condition $R(a)\subset \left\{ b\right\} $ implies that every element of $R(a)$ must be $b$.
•
For $R(a)$ to be a non-empty subset of $\left\{ b\right\} $, it must be the case that $R(a)=\left\{ b\right\} $.

This completes the proof.

Item 15$\implies $Item 1

We wish to show that for any $U\in \mathcal{P}(B)$, we have $U = R_{!}(R_{-1}(U))$. This requires proving two set inclusions.

•
$R_{!}(R_{-1}(U))\subset U$: Let $b\in R_{!}(R_{-1}(U))$.
- •
  By definition, there exists an $a\in A$ such that $a\in R^{-1}(b)$ and $R(a)\subset U$.
- •
  The condition $a\in R^{-1}(b)$ means that $b\in R(a)$.
- •
  Since $b\in R(a)$ and $R(a)\subset U$, it follows directly that $b\in U$.
- •
  Therefore, $R_{!}(R_{-1}(U))\subset U$.
•
$U\subset R_{!}(R_{-1}(U))$: Let $b \in U$.
- •
  By Item 3 of Proposition 8.5.11.1.3, there exists an element $a\in A$ such that $R(a)=\left\{ b\right\} $.
- •
  We must verify that this choice of $a$ places $b$ into the set $R_{!}(R_{-1}(U))$. This requires checking two conditions:
  - •
    $a\in R^{-1}(b)$: Since $R(a)=\left\{ b\right\} $, we have $b\in R(a)$, which is equivalent to $a\in R^{-1}(b)$.
  - •
    $R(a)\subset U$: Since $R(a)=\left\{ b\right\} $ and we assumed $b\in U$, we have $\left\{ b\right\} \subset U$, so the condition holds.
- •
  As both conditions are met, it follows that $b\in R_{!}(R_{-1}(U))$.
- •
  Therefore, $U\subset R_{!}(R_{-1}(U))$.

As both inclusions hold, we conclude that $U=R_{!}(R_{-1}(U))$, which is precisely the statement of Item 15.

Corollary 8.5.11.1.6 ▶ Characterisations of Epimorphisms in $\mathsf{Rel}$ V

Item 1 and Item 2 of Proposition 8.5.11.1.2 are indeed equivalent.

Proof of Corollary 8.5.11.1.6.

Item 1$\implies $Item 2

We proceed in a few steps:

•
Suppose that $R$ is an epimorphism, and let $V\in \mathcal{P}(B)$.
•
To show that $R_{!}$ is surjective, We must find a subset $U\in \mathcal{P}(A)$ such that $R_{!}(U)=V$.
•
By of Proposition 8.5.11.1.9, we have $R_{!}(R_{-1}(V))=V$.
•
Thus choosing $U=R_{-1}(V)$ shows $R_{!}$ to be surjective.

Item 2$\implies $Item 1

We proceed in a few steps:

•
Suppose $R_{!}$ is surjective, let $b\in B$ and Consider the singleton set $\left\{ b\right\} \in \mathcal{P}(B)$.
•
By the surjectivity of $R_{!}$, there must exist some subset $U\in \mathcal{P}(A)$ such that $R_{!}(U)=\left\{ b\right\} $. By definition, we have

\[ R_{!}(U)=\bigcup _{a\in U}R(a). \]
•
The equality $\bigcup _{a\in U}R(a)=\left\{ b\right\} $ implies that for every $a\in U$, we must have $R(a)\subset \left\{ b\right\} $, and that there must exist at least one $a\in U$ for which $R(a)$ is non-empty.
•
Combining these, there must exist at least one $a\in U$ such that $R(a)=\left\{ b\right\} $.
•
By Item 3 of Proposition 8.5.11.1.3, $R$ is an epimorphism.

This finishes the proof.

ゴ

Warning 8.5.11.1.7 ▶ Natural Conditions That Fail To Characterise Epimorphisms in $\mathsf{Rel}$

The following conditions are equivalent and imply $R$ is an epimorphism, but the converse may fail. Thus, they are not equivalent to $R$ being an epimorphism:

1.
The relation $R$ is a surjective partial function.
2.
The diagram
commutes. In other words, we have

\[ R_{!}(R^{-1}(b))=\left\{ b\right\} \]

for each $b\in B$.
3.
We have
In other words, we have

\[ U=\underbrace{\left\{ b\in B\ \middle |\ R^{-1}(b)\cap R^{-1}(U)\neq \text{Ø}\right\} }_{=R_{!}(R^{-1}(U))} \]

for each $U\in \mathcal{P}(B)$.
4.
We have
In other words, we have

\[ U=\underbrace{\left\{ b\in B\ \middle |\ R(R^{-1}(b))\subset U\right\} }_{=R_{*}(R_{-1}(U))} \]

for each $U\in \mathcal{P}(B)$.

ゴ

Proof of Warning 8.5.11.1.7.

First, note that the relation depicted in Explanation 8.5.11.1.1 is not a surjective partial function, but it is an epimorphism in $\mathsf{Rel}$ by Proposition 8.5.11.1.3, the next proposition. Moreover, partial surjective functions are epimorphisms by Proposition 8.5.11.1.3. For the rest of the proposition, we proceed by showing:

•
Step 1: Item 1$\iff $Item 2.
•
Step 2: Item 2$\implies $Item 3.
•
Step 3: Item 3$\implies $Item 2.
•
Step 4: Item 2$\implies $Item 4.
•
Step 5: Item 4$\implies $Item 1.

Step 1: Item 1$\iff $Item 2

Note that we have

\[ R_{!}(R^{-1}(b))\mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\left\{ b'\in B\ \middle |\ R^{-1}(b')\cap R^{-1}(b)\neq \text{Ø}\right\} . \]

We now claim Item 1 and Item 2 are equivalent:

•
Item 1$\implies $Item 2: We proceed in a few steps:
- •
  Since $R$ is functional, $R^{-1}(b)$ has at most one element.
- •
  Since $R$ is surjective, $R^{-1}(b)$ has at least one element.
- •
  Thus, $R^{-1}(b)$ is a singleton.
- •
  The set $R(R^{-1}(b))$ will then be precisely $\left\{ b\right\} $.
•
Item 2$\implies $Item 1: We claim $R$ is functional and surjective.
- •
  Functionality. The inclusion
  
  \[ R_{!}(R^{-1}(b))\subset \left\{ b\right\} \]
  
  implies that if $a\in R(b')$ and $a\in R(b)$, then $b=b'$. Thus $R$ must be functional.
- •
  Surjectivity. The inclusion
  
  \[ \left\{ b\right\} \subset R_{!}(R^{-1}(b)) \]
  
  implies $R^{-1}(b)\neq \text{Ø}$, so $R$ must be surjective.
Since $R$ is functional and surjective, it is a surjective partial function.

Step 2: Item 2$\implies $Item 3

We have

\begin{align*} [R_{!}\circ R^{-1}](U) & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}R_{!}(R^{-1}(U))\\ & = R_{!}\left(R^{-1}\left(\bigcup _{u\in U}\left\{ u\right\} \right)\right)\\ & = R_{!}\left(\bigcup _{u\in U}R^{-1}(\left\{ u\right\} )\right)\\ & = \bigcup _{u\in U}R_{!}(R^{-1}(\left\{ u\right\} ))\\ & = \bigcup _{u\in U}\left\{ u\right\} \\ & = U \end{align*}

for each $U\in \mathcal{P}(B)$, where we have used:

•
Item 5 of Proposition 8.7.3.1.3 for the third equality.
•
Item 5 of Proposition 8.7.1.1.4 for the fourth equality.
•
Item 2 of this proposition for the fifth equality.

Step 3: Item 3$\implies $Item 2

Taking $U=\left\{ b\right\} $ gives $R_{!}(R^{-1}(b))=\left\{ b\right\} $.

Step 4: Item 2$\implies $Item 4

We have

\begin{align*} R_{*}(R_{-1}(U)) & = \left\{ b\in B\ \middle |\ R(R^{-1}(b))\subset U\right\} \\ & = \left\{ b\in B\ \middle |\ \left\{ b\right\} \subset U\right\} \\ & = U. \end{align*}

Step 5: Item 4$\implies $Item 1

Suppose that for each $U\in \mathcal{P}(B)$, we have $R_{*}(R_{-1}(U))=U$. We must show that $R$ is functional and surjective.

•
Functionality: We show that if $b,b'\in R(a)$, then $b=b'$.
- •
  Consider the singleton set $U=\left\{ b\right\} $. By the assumed identity, we have
  
  \[ \left\{ b\right\} =\left\{ b\in B\ \middle |\ R(R^{-1}(b))\subset \left\{ b\right\} \right\} . \]
- •
  Since $b$ is an element of the set on the left-hand side, it must satisfy the membership condition on the right-hand side. Thus, we have $R(R^{-1}(b))\subset \left\{ b\right\} $.
- •
  By assumption, $b\in R(a)$, which implies $a\in R^{-1}(b)$.
- •
  By assumption, we also have $b'\in R(a)$.
- •
  Since $a\in R^{-1}(b)$, it follows that the image of $a$ is contained in the image of the set $R^{-1}(b)$, i.e., $R(a)\subset R(R^{-1}(b))$.
- •
  Combining these steps, we have $b'\in R(a)\subset R(R^{-1}(b))$.
- •
  As we established that $R(R^{-1}(b))\subset \left\{ b\right\} $, we must have $b'\in \left\{ b\right\} $.
- •
  Therefore, $b'=b$, which shows $R$ to be functional.
•
Surjectivity: We show that for each $b\in B$, the preimage set $R^{-1}(b)$ is non-empty.
- •
  Consider the empty set $U=\text{Ø}$. By the assumed identity, we have
  
  \[ \text{Ø}=\left\{ b\in B\ \middle |\ R(R^{-1}(b))\subset \text{Ø}\right\} . \]
- •
  The identity thus states that there is no element $b\in B$ for which $R(R^{-1}(b))$ is the empty set.
- •
  In other words, for each $b\in B$, we must have $R(R^{-1}(b))\neq \text{Ø}$.
- •
  The image of a set $R(S)$ is empty iff the set $S$ is empty.
- •
  Therefore, the condition $R(R^{-1}(b))\neq \text{Ø}$ is equivalent to the condition $R^{-1}(b)\neq \text{Ø}$.
- •
  Thus, $R$ is surjective.

Since $R$ is both functional and surjective, it is a surjective partial function. This finishes the proof.

Remark 8.5.11.1.8 ▶ Epimorphisms in $\mathsf{Rel}$ Give Rise to Antichains

Taking the contrapositive of Item 2 of Proposition 8.5.11.1.3 and letting $U=\left\{ b'\right\} $ shows that the subset

\[ \left\{ R^{-1}(b)\in \mathcal{P}(A)\ \middle |\ b\in B\right\} \]

of $\mathcal{P}(A)$ forms an antichain in $\mathcal{P}(A)$. The converse however, fails.

Proposition 8.5.11.1.9 ▶ Characterisations of 2-Categorical Epimorphisms in $\boldsymbol {\mathsf{Rel}}$ I

Every 1-morphism in $\boldsymbol {\mathsf{Rel}}$ is corepresentably faithful.

Proof of Proposition 8.5.11.1.9.

A relation $R\colon A\mathrel {\rightarrow \kern -9.5pt\mathrlap {|}\kern 6pt}B$ will be corepresentably faithful in $\boldsymbol {\mathsf{Rel}}$ iff, for each $X\in \operatorname {\mathrm{Obj}}(\boldsymbol {\mathsf{Rel}})$, the functor

\[ R^{*}\colon \mathbf{Rel}(B,X)\to \mathbf{Rel}(A,X) \]

given by precomposition by $R$ is faithful. This happens iff the morphism

\[ R^{*}_{S,T}\colon \operatorname {\mathrm{Hom}}_{\mathbf{Rel}(B,X)}(S,T)\to \operatorname {\mathrm{Hom}}_{\mathbf{Rel}(A,X)}(S\mathbin {\diamond }R,T\mathbin {\diamond }R) \]

is injective for each $S,T\in \operatorname {\mathrm{Obj}}(\mathbf{Rel}(B,X))$.

However, since $\boldsymbol {\mathsf{Rel}}$ is locally posetal, the Hom-set $\operatorname {\mathrm{Hom}}_{\mathbf{Rel}(B,X)}(S,T)$ is either empty or a singleton, As a result, the map $R^{*}_{S,T}$ will necessarily be injective in either of these cases.

Proposition 8.5.11.1.10 ▶ Characterisations of 2-Categorical Epimorphisms in $\boldsymbol {\mathsf{Rel}}$ II

Let $R\colon A\mathrel {\rightarrow \kern -9.5pt\mathrlap {|}\kern 6pt}B$ be a relation. The following conditions are equivalent:

1.
The morphism $R\colon A\mathrel {\rightarrow \kern -9.5pt\mathrlap {|}\kern 6pt}B$ is an epimorphism in $\mathsf{Rel}$.
2.
The 1-morphism $R\colon A\mathrel {\rightarrow \kern -9.5pt\mathrlap {|}\kern 6pt}B$ is corepresentably full in $\boldsymbol {\mathsf{Rel}}$.
3.
The 1-morphism $R\colon A\mathrel {\rightarrow \kern -9.5pt\mathrlap {|}\kern 6pt}B$ is corepresentably fully faithful in $\boldsymbol {\mathsf{Rel}}$.
4.
The 1-morphism $R\colon A\mathrel {\rightarrow \kern -9.5pt\mathrlap {|}\kern 6pt}B$ is pseudoepic in $\boldsymbol {\mathsf{Rel}}$.
5.
The 1-morphism $R\colon A\mathrel {\rightarrow \kern -9.5pt\mathrlap {|}\kern 6pt}B$ is corepresentably essentially injective in $\boldsymbol {\mathsf{Rel}}$.
6.
The 1-morphism $R\colon A\mathrel {\rightarrow \kern -9.5pt\mathrlap {|}\kern 6pt}B$ is corepresentably conservative in $\boldsymbol {\mathsf{Rel}}$.