The Clowder Project

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.

• •

  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.

• •

  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.

• •

  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.

• •

  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.

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.

• •

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

• •

  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\} $.

• •

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

• •

  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.

• •

  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.

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

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.

• •

  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.

• •

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

• •

  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.

• •

  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.

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.

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.

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.

• •

  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.

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

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

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.

We will prove this by showing:

• •

  Step 1: Item 1$\iff $Item 2.

• •

  Step 2: Item 2$\iff $Item 3.

• •

  Step 3: Item 3$\iff $Item 4$\iff $Item 5$\iff $Item 6.