The Clowder Project

Firstly note that Item 2 and Item 3 are equivalent by Chapter 9: Constructions With Relations, of . We then claim that Item 1 and Item 2 are also equivalent:

• •

  Item 1$\implies $Item 2: Let $U,V\in \mathcal{P}\webleft (A\webright )$ and consider the diagram

  
  By Chapter 9: Constructions With Relations, , we have
  \begin{align*} R^{-1}\webleft (U\webright ) & = U\mathbin {\diamond }R,\\ R^{-1}\webleft (V\webright ) & = V\mathbin {\diamond }R. \end{align*}

  Now, if $U\mathbin {\diamond }R=V\mathbin {\diamond }R$, i.e. $R^{-1}\webleft (U\webright )=R^{-1}\webleft (V\webright )$, then $U=V$ since $R$ is assumed to be an epimorphism, showing $R^{-1}$ to be injective.

• •

  Item 2$\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}\webleft (U\webright )=U\mathbin {\diamond }R=V\mathbin {\diamond }R=R^{-1}\webleft (V\webright )$, then $U=V$. In particular, for each $x\in X$, we may consider the diagram
  
  for which we have $\webleft [x\webright ]\mathbin {\diamond }S\mathbin {\diamond }R=\webleft [x\webright ]\mathbin {\diamond }T\mathbin {\diamond }R$, implying that we have
  \[ S^{-1}\webleft (x\webright )=\webleft [x\webright ]\mathbin {\diamond }S=\webleft [x\webright ]\mathbin {\diamond }T=T^{-1}\webleft (x\webright ) \]

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

We can also prove this in a more abstract way, following [Yuan, Mono's and epi's in the category Rel?]:

• •

  Item 1$\implies $Item 2: Assume that $R$ is an epimorphism.

  • •

    We first notice that the functor $\mathrm{Rel}\webleft (-,\mathrm{pt}\webright )\colon \mathrm{Rel}^{\mathsf{op}}\to \mathsf{Sets}$ maps $R$ to $R^{-1}$ by Chapter 9: Constructions With Relations, .

  • •

    Since $\mathrm{Rel}\webleft (-,\mathrm{pt}\webright )$ preserves limits by , of , it follows by , of that $\mathrm{Rel}\webleft (-,\mathrm{pt}\webright )$ also preserves monomorphisms.

  • •

    That is: $\mathrm{Rel}\webleft (-,\mathrm{pt}\webright )$ sends monomorphisms in $\mathrm{Rel}^{\mathsf{op}}$ to monomorphisms in $\mathsf{Sets}$.

  • •

    The monomorphisms $\mathrm{Rel}^{\mathsf{op}}$ are precisely the epimorphisms in $\mathrm{Rel}$ by , of .

  • •

    Since $R$ is an epimorphism and $\mathrm{Rel}\webleft (-,\mathrm{pt}\webright )$ maps $R$ to $R^{-1}$, it follows that $R^{-1}$ is a monomorphism.

  • •

    Since the monomorphisms in $\mathsf{Sets}$ are precisely the injections (, of ), it follows that $R^{-1}$ is injective.

• •

  Item 2$\implies $Item 1: Assume that $R^{-1}$ is injective.

  • •

    We first notice that the functor $\mathrm{Rel}\webleft (-,\mathrm{pt}\webright )\colon \mathrm{Rel}^{\mathsf{op}}\to \mathsf{Sets}$ maps $R$ to $R^{-1}$ by Chapter 9: Constructions With Relations, .

  • •

    Since the monomorphisms in $\mathsf{Sets}$ are precisely the injections (, of ), it follows that $R^{-1}$ is a monomorphism.

  • •

    Since $\mathrm{Rel}\webleft (-,\mathrm{pt}\webright )$ is faithful, it follows by , of that $\mathrm{Rel}\webleft (,\mathrm{pt}\webright )$ reflects monomorphisms.

  • •

    That is: $\mathrm{Rel}\webleft (-,\mathrm{pt}\webright )$ reflects monomorphisms in $\mathsf{Sets}$ to monomorphisms in $\mathrm{Rel}^{\mathsf{op}}$.

  • •

    The monomorphisms $\mathrm{Rel}^{\mathsf{op}}$ are precisely the epimorphisms in $\mathrm{Rel}$ by , of .

  • •

    Since $R^{-1}$ is a monomorphism and $\mathrm{Rel}\webleft (-,\mathrm{pt}\webright )$ maps $R$ to $R^{-1}$, it follows that $R$ is an epimorphism.

We also claim that Item 2 and Item 4 are equivalent, following [Lumsdaine, Epimorphisms of relations]:

• •

  Item 2$\implies $Item 4: Since $B\setminus \left\{ b\right\} \subset B$ and $R^{-1}$ is injective, we have $R^{-1}\webleft (B\setminus \left\{ b\right\} \webright )\subsetneq R^{-1}\webleft (B\webright )$. So taking some $a\in R^{-1}\webleft (B\webright )\setminus R^{-1}\webleft (B\setminus \left\{ b\right\} \webright )$ we get an element of $A$ such that $R\webleft (a\webright )=\left\{ b\right\} $.

• •

  Item 4$\implies $Item 2: Let $U,V\subset B$ with $U\neq V$. Without loss of generality, we can assume $U\setminus V\neq \text{Ø}$; otherwise just swap $U$ and $V$. Let then $b\in U\setminus V$. By assumption, there exists an $a\in A$ with $R\webleft (a\webright )=\left\{ b\right\} $. Then $a\in R^{-1}\webleft (U\webright )$ but $a\not\in R^{-1}\webleft (V\webright )$, and thus $R^{-1}\webleft (U\webright )\neq R^{-1}\webleft (V\webright )$, showing $R^{-1}$ to be injective.

Finally, we prove the second part of the statement. So assume $R$ is a total epimorphism in $\mathsf{Rel}$ and consider the diagram

for each $b\in B$. Since $R$ is total, we have $a\sim _{S\mathbin {\diamond }R}0$ and $a\sim _{T\mathbin {\diamond }R}0$ for all $a\in A$, and no element of $A$ is related to $1$ by $S\mathbin {\diamond }R$ or $T\mathbin {\diamond }R$. Thus $S\mathbin {\diamond }R=T\mathbin {\diamond }R$, and since $R$ is an epimorphism, we have $S=T$. But by the definition of $T$, this implies $\mathrm{Im}\webleft (R\webright )=B$.