The Clowder Project

• •

  Preservation of Identities. Let $A$ be a set. Given $a,b\in A$, we have

  \[ a \sim _{\operatorname {\mathrm{Gr}}(\operatorname {\mathrm{id}}_{A})} b \iff \operatorname {\mathrm{id}}_{A}(a) = b \iff a = b \iff a \sim _{\Delta _{A}} b, \]

  so $\operatorname {\mathrm{Gr}}(\operatorname {\mathrm{id}}_{A}) = \Delta _{A}.$

• •

  Preservation of Composition. Let $A$, $B$, and $C$ be sets and let $f \colon A \to B$ and $g \colon B \to C$ be functions. For each $a\in A$ and each $c \in C$, we have

  \begin{align*} a \sim _{\operatorname {\mathrm{Gr}}(g \circ f)} c & \iff [g \circ f](a) = c\\ & \iff g(f(a)) = c\\ & \iff \text{there exists $b \in B$ such that $f(a) = b$ and $(b) = c$}\\ & \iff \text{there exists $b \in B$ such that $a \sim _{\operatorname {\mathrm{Gr}}(f)} b$ and $b \sim _{\operatorname {\mathrm{Gr}}(g)} c$} \\ & \iff a \sim _{\operatorname {\mathrm{Gr}}(g) \mathbin {\diamond }\operatorname {\mathrm{Gr}}(f)} c \end{align*}

  so $\operatorname {\mathrm{Gr}}(g \circ f) = \operatorname {\mathrm{Gr}}(g) \mathbin {\diamond }\operatorname {\mathrm{Gr}}(f)$.

These correspond respectively to the following conditions:

1. 1.

   For each $a\in A$, there exists some $b\in B$ such that $a\sim _{\operatorname {\mathrm{Gr}}(f)}b$ and $b\sim _{f^{-1}}a$.

2. 2.

   For each $a,b\in A$, if $a\sim _{\operatorname {\mathrm{Gr}}(f)}b$ and $b\sim _{f^{-1}}a$, then $a=b$.

In other words, the first condition states that the image of any $a\in A$ by $f$ is nonempty, whereas the second condition states that $f$ is not multivalued. As $f$ is a function, both of these statements are true, and we are done.

• •

  Item 6a$\iff $Item 6b. This is shown in the proof of Proposition 8.5.2.1.2.

• •

  Item 6b$\implies $Item 6c. If $R$ is total and functional, then, for each $a\in A$, the set $R(a)$ is a singleton. Since the conditions

  • •

    $R(a)\cap V\neq \text{Ø}$;

  • •

    $R(a)\subset V$;

  are equivalent when $R(a)$ is a singleton, it follows that the sets

  \begin{align*} R^{-1}(V) & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\left\{ a\in A \ \middle |\ R(a)\cap V\neq \text{Ø}\right\} ,\\ R_{-1}(V) & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\left\{ a\in A\ \middle |\ R(a)\subset V\right\} \end{align*}

  are equal for all $V\in \mathcal{P}(B)$.

• •

  Item 6c$\implies $Item 6b. We claim that $R$ is indeed total and functional:

  • •

    Totality. We proceed in a few steps:

    • •

      If we had $R(a)=\text{Ø}$ for some $a\in A$, then we would have $a\in R_{-1}(\text{Ø})$, so that $R_{-1}(\text{Ø})\neq \text{Ø}$.

    • •

      But since $R^{-1}(\text{Ø})=\text{Ø}$, this would imply $R_{-1}(\text{Ø})\neq R^{-1}(\text{Ø})$, a contradiction.

    • •

      Thus $R(a)\neq \text{Ø}$ for all $a\in A$ and $R$ is total.

  • •

    Functionality. If $R^{-1}=R_{-1}$, then we have

    \begin{align*} \left\{ a\right\} & = R^{-1}(\left\{ b\right\} )\\ & = R_{-1}(\left\{ b\right\} ) \end{align*}

    for each $b\in R(a)$ and each $a\in A$, and thus $R(a)\subset \left\{ b\right\} $. But since $R$ is total, we must have $R(a)=\left\{ b\right\} $, so $R$ is functional.

• •

  Item 6a$\iff $Item 6d. This follows from Chapter 8: Relations, Proposition 8.5.3.1.1.

This finishes the proof.