The Clowder Project

We will prove this by showing:

• •

  Step 1: Item 2$\iff $Item 5 and Item 5$\iff $Item 7.

• •

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

• •

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

• •

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

• •

  Step 5: Item 1$\iff $Item 4.

• •

  Step 6: Item 2$\iff $Item 8.

• •

  Step 7: Item 3$\iff $Item 9.

• •

  Step 8: Item 4$\iff $Item 10.

• •

  Step 9: Item 5$\iff $Item 11.

• •

  Step 10: Item 6$\iff $Item 12.

• •

  Step 11: Item 1$\iff $Item 13.

• •

  Step 12: Item 1$\iff $Item 14.

• •

  Step 13: Item 1$\iff $Item 15.

• •

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

  
  By Remark 8.7.1.1.3, we have
  \begin{align*} R_{!}(U) & = R\mathbin {\diamond }U,\\ R_{!}(V) & = R\mathbin {\diamond }V. \end{align*}

  Now, if $R\mathbin {\diamond }U=R\mathbin {\diamond }V$, i.e. $R_{!}(U)=R_{!}(V)$, then $U=V$ since $R$ is assumed to be a monomorphism, showing $R_{!}$ to be injective.

• •

  Item 2$\implies $Item 1: Conversely, suppose that $R_{!}$ is injective, consider the diagram

  
  and suppose that $R\mathbin {\diamond }S=R\mathbin {\diamond }T$. Note that, since $R_{!}$ is injective, given a diagram of the form
  
  if $R_{!}(U)=R\mathbin {\diamond }U=R\mathbin {\diamond }V=R_{!}(V)$, then $U=V$. In particular, for each $x\in X$, we may consider the diagram
  
  where we have $R\mathbin {\diamond }S\mathbin {\diamond }[x]=R\mathbin {\diamond }T\mathbin {\diamond }[x]$, implying that we have
  \[ S(x)=S\mathbin {\diamond }[x]=T\mathbin {\diamond }[x]=T(x) \]

  for each $x\in X$. Thus $S=T$ and $R$ is a monomorphism.

• •

  Proposition 8.5.10.1.2$\implies $Proposition 8.5.10.1.3: Assume that $R$ is a monomorphism.

  • •

    We first notice that the functor $\mathrm{Rel}(\mathrm{pt},-)\colon \mathrm{Rel}\to \mathsf{Sets}$ maps $R$ to $R_{!}$ by Remark 8.7.1.1.3.

  • •

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

  • •

    Since $R$ is a monomorphism and $\mathrm{Rel}(\mathrm{pt},-)$ maps $R$ to $R_{!}$, it follows that $R_{!}$ is also a monomorphism.

  • •

    Since the monomorphisms in $\mathsf{Sets}$ are precisely the injections (, of ), it follows that $R_{!}$ is injective.

• •

  Proposition 8.5.10.1.3$\implies $Proposition 8.5.10.1.2: Assume that $R_{!}$ is injective.

  • •

    We first notice that the functor $\mathrm{Rel}(\mathrm{pt},-)\colon \mathrm{Rel}\to \mathsf{Sets}$ maps $R$ to $R_{!}$ by Remark 8.7.1.1.3.

  • •

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

  • •

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

  • •

    Since $R_{!}$ is a monomorphism and $\mathrm{Rel}(\mathrm{pt},-)$ maps $R$ to $R_{!}$, it follows that $R$ is also a monomorphism.

• •

  Item 2$\implies $Item 6: We proceed in a few steps:

  • •

    Let $U,V\in \mathcal{P}(A)$ such that $R_{!}(U)\subset R_{!}(V)$, assume $R_{!}$ to be injective, and consider the set $U\cup V$.

  • •

    Since $R_{!}(U)\subset R_{!}(V)$, we have

    \begin{align*} R_{!}(U\cup V) & = R_{!}(U)\cup R_{!}(V)\\ & = R_{!}(V), \end{align*}

    where we have used Item 13 of Proposition 8.7.1.1.4 for the first equality.

  • •

    Since $R_{!}$ is injective, this implies $U\cup V=V$.

  • •

    Thus $U\subset V$, as we wished to show.

• •

  Item 2$\implies $Item 6: We proceed in a few steps:

  • •

    Suppose Item 6 holds, and let $U,V\in \mathcal{P}(A)$ such that $R_{!}(U)=R_{!}(V)$.

  • •

    Since $R_{!}(U)=R_{!}(V)$, we have $R_{!}(U)\subset R_{!}(V)$ and $R_{!}(V)\subset R_{!}(U)$.

  • •

    By assumption, this implies $U\subset V$ and $V\subset U$.

  • •

    Thus $U=V$, showing $R_{!}$ to be injective.

• •

  Item 6$\implies $Item 12: Let $U,V\in \mathcal{P}(A)$ and consider the diagram

  
  By Remark 8.7.1.1.3, we have
  \begin{align*} R_{!}(U) & = R\mathbin {\diamond }U,\\ R_{!}(V) & = R\mathbin {\diamond }V. \end{align*}

  Now, if $R\mathbin {\diamond }U\subset R\mathbin {\diamond }V$, then $R_{!}(U)\subset R_{!}(V)$. By assumption, we then have $U\subset V$.

• •

  Item 12$\implies $Item 6: Consider the diagram

  
  and suppose that $R\mathbin {\diamond }S\subset R\mathbin {\diamond }T$. Note that, by assumption, given a diagram of the form
  
  if $R_{!}(U)=R\mathbin {\diamond }U\subset R\mathbin {\diamond }V=R_{!}(V)$, then $U\subset V$. In particular, for each $x\in X$, we may consider the diagram
  
  for which we have $R\mathbin {\diamond }S\mathbin {\diamond }[x]\subset R\mathbin {\diamond }T\mathbin {\diamond }[x]$, implying that we have
  \[ S(x)=S\mathbin {\diamond }[x]\subset T\mathbin {\diamond }[x]=T(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.

• •

  If $R$ is a monomorphism, then, by Item 2 of Proposition 8.5.10.1.2, the functor

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

  is full.

• •

  As a result, given $a\in A$ and $U\in \mathcal{P}(A)$ such that $R(a)\subset R(U)$, it follows that $\left\{ a\right\} \subset U$.

• •

  Thus, we have $a\in U$.

• •

  Let $a\in A$ and consider the subset $U=A\setminus \left\{ a\right\} $.

• •

  Since $a\not\in U$, we have $R(a)\centernot {\subset }R(U)$ by the contrapositve of Item 2.

• •

  As a result, there must exist some $b\in R(a)$ with $b\not\in R(U)$.

• •

  In particular, we have $a\in R^{-1}(b)$.

• •

  Moreover, the condition $b\not\in R(U)=R(A\setminus \left\{ a\right\} )$ means that, if $a'\in A\setminus \left\{ a\right\} $, then $a'\not\in R^{-1}(b)$.

• •

  Thus $R^{-1}(b)=\left\{ a\right\} $.

• •

  By the equivalence between Item 1 and Item 6 of Proposition 8.5.10.1.2, to show that $R$ is a monomorphism it suffices to prove that, for each $U,V\in \mathcal{P}(A)$, if $R(U)\subset R(V)$, then $U\subset V$.

• •

  So let $u\in U$ and assume $R(U)\subset R(V)$.

• •

  By assumption, there exists some $b\in B$ with $R^{-1}(b)=\left\{ u\right\} $.

• •

  In particular, $b\in R(U)$.

• •

  Since $R(U)\subset R(V)$, we also have $b\in R(V)$.

• •

  Thus, there exists some $v\in V$ with $b\in R(v)$.

• •

  However, $R^{-1}(b)=\left\{ u\right\} $, so we must in fact have $v=u$.

• •

  Therefore $u\in V$, showing that $U\subset V$.

This finishes the proof.

• •

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

• •

  Item 13$\implies $Item 3 of Proposition 8.5.10.1.3: Given $a\in A$, we may pick $b=f(a)$, in which case $R^{-1}(f(a))$ will be equal to $\left\{ a\right\} $ by assumption.

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

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

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

• •

  Let $a$ be an arbitrary element of $A$. By our assumption, the condition $R^{-1}(R_{*}(U))=U$ must hold for the singleton set $U=\left\{ a\right\} $.

• •

  From $R^{-1}(R_{*}(\left\{ a\right\} ))=\left\{ a\right\} $, it follows that $a\in R^{-1}(R_{*}(\left\{ a\right\} ))$.

• •

  This means there must exist some $b\in R(a)$ such that $R^{-1}(b)\subset \left\{ a\right\} $.

• •

  The condition $b\in R(a)$ implies that $a\in R^{-1}(b)$. Therefore, $R^{-1}(b)$ is a non-empty subset of $\left\{ a\right\} $.

• •

  The only non-empty subset of $\left\{ a\right\} $ is $\left\{ a\right\} $ itself.

• •

  Thus, we must have $R^{-1}(b)=\left\{ a\right\} $.

By Item 3 of Proposition 8.5.10.1.3, it then follows that $R$ is a monomorphism.

• •

  $R^{-1}(R_{*}(U))\subset U$: We proceed in a few steps:

  • •

    Let $a\in R^{-1}(R_{*}(U))$.

  • •

    By definition, there exists some $b\in R(a)$ such that $R^{-1}(b)\subset U$.

  • •

    Since $b\in R(a)$ implies $a\in R^{-1}(b)$, it follows immediately that $a\in U$.

  • •

    Thus, $R^{-1}(R_{*}(U))\subset U$.

• •

  $U\subset R^{-1}(R_{*}(U))$: Let $a\in U$. By assumption, there exists an element $b\in B$ such that $R^{-1}(b)=\left\{ a\right\} $. Thus $R^{-1}(b)\subset U$, so $a\in R^{-1}(R_{*}(U))$.

Combining both inclusions gives $R^{-1}(R_{*}(U))=U$.

We proceed by showing:

• •

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

• •

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

• •

  Step 3: Item 2$\implies $Item 4.

• •

  Step 4: Item 4$\implies $Item 2.

• •

  Step 5: Item 1$\implies $Item 3.

• •

  Step 6: Item 3$\implies $Item 1.

• •

  Step 7: $R$ is a monomorphism $\centernot {\implies }$Item 1.

• •

  Step 8: Item 1$\implies $ $R$ is a monomorphism.

• •

  Step 9: Proof of $(\star )$.

• •

  Step 10: Counterexample to the converse of $(\star )$.

• •

  Let $x\in R^{-1}(R(a))$. By definition, this means $R(x)\cap R(a)\neq \text{Ø}$.

• •

  Since the image sets are pairwise disjoint, this can only be true if $x=a$.

• •

  Therefore, $R^{-1}(R(a))\subset \left\{ a\right\} $.

• •

  Since $R$ is total, $R(a)$ is non-empty.

• •

  Thus $R(a)\cap R(a)\neq \text{Ø}$, which implies $a\in R^{-1}(R(a))$.

• •

  Therefore, $\left\{ a\right\} \subset R^{-1}(R(a))$.

Combining both inclusions, we have $R^{-1}(R(a))=\left\{ a\right\} $.

The condition $R^{-1}(R(a))=\left\{ a\right\} $ implies two facts:

• •

  Totality. The element $a$ must belong to the set $\left\{ x\in A \mid R(x)\cap R(a)\neq \text{Ø}\right\} $. For this to be true, the condition must hold for $x=a$, so $R(a)\cap R(a)\neq \text{Ø}$. This is equivalent to $R(a)\neq \text{Ø}$. Since this must hold for all $a\in A$, the relation $R$ is total.

• •

  Injectivity. Any element $x\in A$ such that $x\neq a$ must not belong to the set. This means that for any $x\neq a$, we must have $R(x)\cap R(a)=\text{Ø}$. This means the image sets of distinct elements of $A$ are pairwise disjoint.

Thus, $R$ is total and injective.

• •

  First, let $U=\left\{ a\right\} $. By assumption, we have

  \[ \left\{ a\right\} =\left\{ a'\in A\ \middle |\ R^{-1}(R(a'))\subset \left\{ a\right\} \right\} . \]

  Since $a$ is in the set on the left-hand side, it must also be in the set on the right-hand side. Thus $R^{-1}(R(a'))\subset \left\{ a\right\} $ must be true.

• •

  Next, consider the complement $U=A\setminus \left\{ a\right\} $. By assumption, we have

  \[ A\setminus \left\{ a\right\} =\left\{ a'\in A\ \middle |\ R^{-1}(R(a'))\subset A\setminus \left\{ a\right\} \right\} \]

  Since $a$ is not in the set on the left-hand side, it cannot be in the set on the right-hand side. Thus $R^{-1}(R(a))\centernot {\subset }A\setminus \left\{ a\right\} $.

• •

  The statement $R^{-1}(R(a))\centernot {\subset }A\setminus \left\{ a\right\} $ implies that there exists an element $x\in R^{-1}(R(a))$ such that $x\not\in A\setminus \left\{ a\right\} $. The only such element is $a$, so we must have $a\in R^{-1}(R(a))$.

• •

  Combining these two results, namely $R^{-1}(R(a))\subset \left\{ a\right\} $ and $a\in R^{-1}(R(a))$, we conclude that $R^{-1}(R(a))=\left\{ a\right\} $, as we wished to show.

• •

  $U\subset S(U)$: Let $u\in U$.

  • •

    Since $R$ is total, we have $R(u)\neq \text{Ø}$.

  • •

    By definition, $R(U)=\bigcup _{x\in U}R(x)$, so $R(u)\subset R(U)$.

  • •

    Therefore, $R(u)\cap R(U)=R(u)$.

  • •

    Since $R(u)\neq \text{Ø}$, we have $R(u)\cap R(U)\neq \text{Ø}$.

  • •

    By the definition of $S(U)$, it follows that $u\in S(U)$.

• •

  $S(U)\subset U$: Let $a\in S(U)$.

  • •

    By assumption, $R(a)\cap R(U)\neq \text{Ø}$.

  • •

    This means $R(a)\cap \bigcup _{u\in U}R(u)\neq \text{Ø}$.

  • •

    Using the distributivity of intersection over union (Chapter 4: Constructions With Sets, Item 8 of Proposition 4.3.6.1.2), this is equivalent to

    \[ \bigcup _{u\in U}(R(a)\cap R(u))\neq \text{Ø}. \]
  • •

    For this union of sets to be non-empty, at least one of the sets in the union must be non-empty. Thus, there must exist some $u\in U$ such that $R(a)\cap R(u)\neq \text{Ø}$.

  • •

    Since $R$ is injective, the images of distinct elements are disjoint. Thus, for the intersection $R(a)\cap R(u)$ to be non-empty, we must therefore have $a=u$.

  • •

    Since $u\in U$, it follows that $a\in U$.

As both inclusions hold, we conclude that $U=S(U)$.

• •

  Totality: Let $a\in A$. We must show that $R(a)\neq \text{Ø}$.

  • •

    Consider the singleton set $U=\left\{ a\right\} $.

  • •

    By assumption, $U=\left\{ x\in A\ \middle |\ R(x)\cap R(U)\neq \text{Ø}\right\} $.

  • •

    Since $a\in U$, we must have $R(a)\cap R(U)\neq \text{Ø}$.

  • •

    Substituting $U=\left\{ a\right\} $, we get $R(a)\cap R(\left\{ a\right\} )\neq \text{Ø}$.

  • •

    Since $R(\left\{ a\right\} )=R(a)$, this simplifies to $R(a)\cap R(a)=R(a)\neq \text{Ø}$.

  • •

    Thus $R(a)\neq \text{Ø}$ for all $a\in A$, showing $R$ to be total.

• •

  Injectivity: Let $a,a'\in A$ such that $a\neq a'$. We must show that $R(a)\cap R(a')=\text{Ø}$.

  • •

    Consider the singleton set $U=\left\{ a\right\} $.

  • •

    By assumption, $U=\left\{ x\in A\ \middle |\ R(x)\cap R(U)\neq \text{Ø}\right\} $.

  • •

    Since $a\neq a'$, we have $a'\not\in U$.

  • •

    Therefore, $a'$ cannot satisfy the membership condition for $U$. This means $R(a')\cap R(U)=\text{Ø}$.

  • •

    Substituting $U=\left\{ a\right\} $, we get $R(a')\cap R(\left\{ a\right\} )=\text{Ø}$, which simplifies to $R(a')\cap R(a)=\text{Ø}$.

  • •

    As this holds for any pair of distinct elements, the relation $R$ is injective.

This completes the proof.

• •

  Since $R$ is total and $a\in A$, there exists some $b\in B$ such that $a\sim _{R}b$.

• •

  In this case, we have $x\sim _{R\mathbin {\diamond }S}b$, and since $R\mathbin {\diamond }S=R\mathbin {\diamond }T$, we have also $x\sim _{R\mathbin {\diamond }T}b$.

• •

  Thus there must exist some $a'\in A$ such that $x\sim _{T}a'$ and $a'\sim _{R}b$.

• •

  However, since $a\sim _{R}b$ and $a'\sim _{R}b$, we must have $a=a'$ since $R$ is injective.

• •

  Thus $x\sim _{T}a$ as well.

• •

  A similar argument shows that if $x\sim _{T}a$, then $x\sim _{S}a$.

• •

  Thus $S=T$, showing $R$ to be a monomorphism.

This finishes the proof.

Since $R(a_{1})$, $R(a_{2})$, and $R(a_{3})$ are all distinct, $R$ satisfies the condition in $(\star )$.

Taking $U=\left\{ a_{1},a_{2}\right\} $ and $V=\left\{ a_{3}\right\} $, however, shows that $R(U)=R(V)$ holds while $U\neq V$, so $R$ can’t be a monomorphism.

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

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

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

However, since $\boldsymbol {\mathsf{Rel}}$ is locally posetal, the Hom-set $\operatorname {\mathrm{Hom}}_{\mathbf{Rel}(X,A)}(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.