The Clowder Project

Let $R\colon X\mathrel {\rightarrow \kern -9.5pt\mathrlap {|}\kern 6pt}Y$ be a relation.

1. 1.

   Functoriality. The assignment $V\mapsto R_{-1}(V)$ defines a functor

   \[ R_{-1}\colon (\mathcal{P}(Y),\subset )\to (\mathcal{P}(X),\subset ). \]

   In particular, for each $U,V\in \mathcal{P}(Y)$, the following condition is satisfied:

   • (★)
   If $U\subset V$, then $R_{-1}(U)\subset R_{-1}(V)$.
2. 2.

   Adjointness. We have an adjunction

   
   witnessed by:
   1. (a)

      Units and counits of the form

      \begin{align*} \operatorname {\mathrm{id}}_{\mathcal{P}(X)} \hookrightarrow R_{-1}\circ R_{!},\\ R_{!}\circ R_{-1} \hookrightarrow \operatorname {\mathrm{id}}_{\mathcal{P}(Y)}. \end{align*}

      In particular:

      • •

        For each $U\in \mathcal{P}(X)$, we have $U\subset R_{-1}(R_{!}(U))$.

      • •

        For each $V\in \mathcal{P}(Y)$, we have $R_{!}(R_{-1}(V))\subset V$.

   2. (b)

      A bijections of sets

      \[ \operatorname {\mathrm{Hom}}_{\mathcal{P}(X)}(R_{!}(U),V)\cong \operatorname {\mathrm{Hom}}_{\mathcal{P}(X)}(U,R_{-1}(V)), \]

      natural in $U\in \mathcal{P}(X)$ and $V\in \mathcal{P}(Y)$. In particular:

      • (★)
      The following conditions are equivalent:
      • •

        We have $R_{!}(U)\subset V$.

      • •

        We have $U\subset R_{-1}(V)$.

3. 3.

   Interaction With Unions of Families of Subsets. The diagram

   
   commutes, i.e. we have
   \[ \bigcup _{V\in \mathcal{V}}R_{-1}(V)=\bigcup _{U\in R_{-1}(\mathcal{U})}U \]

   for each $\mathcal{V}\in \mathcal{P}(Y)$, where $R_{-1}(\mathcal{V})\mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}(R_{-1})_{!}(\mathcal{V})$.

4. 4.

   Interaction With Intersections of Families of Subsets. The diagram

   
   commutes, i.e. we have
   \[ \bigcap _{V\in \mathcal{V}}R_{-1}(V)=\bigcap _{U\in R_{-1}(\mathcal{U})}U \]

   for each $\mathcal{V}\in \mathcal{P}(Y)$, where $R_{-1}(\mathcal{V})\mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}(R_{-1})_{!}(\mathcal{V})$.

5. 5.

   Interaction With Binary Unions. We have a natural transformation

   
   with components
   \[ R_{-1}(U)\cup R_{-1}(V)\subset R_{-1}(U\cup V) \]

   indexed by $U,V\in \mathcal{P}(Y)$.

6. 6.

   Interaction With Binary Intersections. The diagram

   
   commutes, i.e. we have
   \[ R_{-1}(U\cap V)=R_{-1}(U)\cap R_{-1}(V) \]

   for each $U,V\in \mathcal{P}(Y)$.

7. 7.

   Interaction With Differences. We have a natural transformation

   
   with components
   \[ R_{-1}(U\setminus V)\subset R_{-1}(U)\setminus R_{-1}(V) \]

   indexed by $U,V\in \mathcal{P}(Y)$.

8. 8.

   Interaction With Complements. The diagram

   
   commutes, i.e. we have
   \[ R_{-1}(U^{\textsf{c}})=R^{-1}(U)^{\textsf{c}} \]

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

9. 9.

   Interaction With Symmetric Differences. The diagram

   
   does not commute in general, i.e. we may have
   \[ R_{-1}(U)\mathbin {\triangle }R_{-1}(V)\neq R_{-1}(U\mathbin {\triangle }V) \]

   in general, where $U,V\in \mathcal{P}(Y)$.

10. 10.

    Interaction With Internal Homs of Powersets. We have a natural transformation

    
    with components
    \[ [R^{-1}(U),R_{-1}(V)]_{X}\subset R_{-1}([U,V]_{Y}), \]

    indexed by $U,V\in \mathcal{P}(Y)$.

11. 11.

    Lax Preservation of Colimits. We have an inclusion of sets

    \[ \bigcup _{i\in I}R_{-1}(U_{i})\subset R_{-1}\left(\bigcup _{i\in I}U_{i}\right), \]

    natural in $\left\{ U_{i}\right\} _{i\in I}\in \mathcal{P}(Y)^{\times I}$. In particular, we have inclusions

    \[ \begin{gathered} R_{-1}(U)\cup R_{-1}(V) \subset R_{-1}(U\cup V),\\ \text{Ø}\subset R_{-1}(\text{Ø}), \end{gathered} \]

    natural in $U,V\in \mathcal{P}(Y)$.

12. 12.

    Preservation of Limits. We have an equality of sets

    \[ R_{-1}\left(\bigcap _{i\in I}U_{i}\right)=\bigcap _{i\in I}R_{-1}(U_{i}), \]

    natural in $\left\{ U_{i}\right\} _{i\in I}\in \mathcal{P}(Y)^{\times I}$. In particular, we have equalities

    \[ \begin{gathered} R_{-1}(U\cap V) = R_{-1}(U)\cap R_{-1}(V),\\ R_{-1}(Y) = Y, \end{gathered} \]

    natural in $U,V\in \mathcal{P}(Y)$.

13. 13.

    Symmetric Lax Monoidality With Respect to Unions. The codirect image function of Item 1 has a symmetric lax monoidal structure

    \[ (R_{-1},R^{\otimes }_{-1},R^{\otimes }_{-1|\mathbb {1}}) \colon (\mathcal{P}(X),\cup ,\text{Ø}) \to (\mathcal{P}(Y),\cup ,\text{Ø}), \]

    being equipped with inclusions

    \[ \begin{gathered} R^{\otimes }_{-1|U,V} \colon R_{-1}(U)\cup R_{-1}(V) \subset R_{-1}(U\cup V),\\ R^{\otimes }_{-1|\mathbb {1}} \colon \text{Ø}\subset R_{-1}(\text{Ø}), \end{gathered} \]

    natural in $U,V\in \mathcal{P}(Y)$.

14. 14.

    Symmetric Strict Monoidality With Respect to Intersections. The direct image function of Item 1 has a symmetric strict monoidal structure

    \[ (R_{-1},R^{\otimes }_{-1},R^{\otimes }_{-1|\mathbb {1}}) \colon (\mathcal{P}(X),\cap ,X) \to (\mathcal{P}(Y),\cap ,Y), \]

    being equipped with equalities

    \[ \begin{gathered} R^{\otimes }_{-1|U,V} \colon R_{-1}(U\cap V) \mathbin {\overset {=}{\rightarrow }}R_{-1}(U)\cap R_{-1}(V),\\ R^{\otimes }_{-1|\mathbb {1}} \colon R_{-1}(X) \mathbin {\overset {=}{\rightarrow }}Y, \end{gathered} \]

    natural in $U,V\in \mathcal{P}(Y)$.

15. 15.

    Interaction With Coproducts. Let $R\colon X\mathrel {\rightarrow \kern -9.5pt\mathrlap {|}\kern 6pt}X'$ and $S\colon Y\mathrel {\rightarrow \kern -9.5pt\mathrlap {|}\kern 6pt}Y'$ be relations. The diagram

    
    commutes, i.e. we have
    \[ (R\mathchoice {\mathbin {\textstyle \coprod }}{\mathbin {\textstyle \coprod }}{\mathbin {\scriptstyle \textstyle \coprod }}{\mathbin {\scriptscriptstyle \textstyle \coprod }}S)_{-1}(U'\mathchoice {\mathbin {\textstyle \coprod }}{\mathbin {\textstyle \coprod }}{\mathbin {\scriptstyle \textstyle \coprod }}{\mathbin {\scriptscriptstyle \textstyle \coprod }}V')=R_{-1}(U')\mathchoice {\mathbin {\textstyle \coprod }}{\mathbin {\textstyle \coprod }}{\mathbin {\scriptstyle \textstyle \coprod }}{\mathbin {\scriptscriptstyle \textstyle \coprod }}S_{-1}(V') \]

    for each $U'\in \mathcal{P}(X')$ and each $V'\in \mathcal{P}(Y')$.

16. 16.

    Interaction With Products. Let $f\colon X\mathrel {\rightarrow \kern -9.5pt\mathrlap {|}\kern 6pt}X'$ and $g\colon Y\mathrel {\rightarrow \kern -9.5pt\mathrlap {|}\kern 6pt}Y'$ be relations. The diagram

    
    commutes, i.e. we have
    \[ (R\boxtimes _{X'\times Y'}S)_{-1}(U'\boxtimes _{X'\times Y'}V')=R_{-1}(U')\boxtimes _{X\times Y}S_{-1}(V') \]

    for each $U'\in \mathcal{P}(X')$ and each $V'\in \mathcal{P}(Y')$.

17. 17.

    Relation to Inverse Images. We have

    \[ R_{-1}(V)=X\setminus R^{-1}(Y\setminus V) \]

    for each $V\in \mathcal{P}(Y)$.

18. 18.

    Interaction With Functional Relations. If $R$ is functional, then we have

    \begin{align*} R^{\mathrm{dom}}_{-1}(V) & = R^{-1}(V),\\ R^{\mathrm{cp}}_{-1}(V) & = X\setminus \operatorname {Dom}(R),\end{align*}

    so

    \begin{align*} R_{-1}(V) & = R^{\mathrm{dom}}_{-1}(V)\cup R^{\mathrm{cp}}_{-1}(V)\\ & = R^{-1}(V)\cup (X\setminus \operatorname {Dom}(R))\end{align*}

    for each $V\in \mathcal{P}(Y)$.

19. 19.

    Interaction With Total Relations. If $R$ is total, then we have

    \begin{align*} R^{\mathrm{dom}}_{-1}(V) & \subset R^{-1}(V),\\ R^{\mathrm{cp}}_{-1}(V) & = \text{Ø},\end{align*}

    so

    \[ R_{-1}(V)\subset R^{-1}(V) \]

    for each $V\in \mathcal{P}(Y)$.

20. 20.

    Interaction With Functions I. If $R$ is a function, then we have

    \begin{align*} R^{\mathrm{dom}}_{-1}(V) & = R^{-1}(V),\\ R^{\mathrm{cp}}_{-1}(V) & = \text{Ø},\end{align*}

    so $R_{-1}=R^{-1}$.

21. 21.

    Interaction With Functions II. If $R_{-1}=R^{-1}$, then $R$ is a function.

Let $R\colon X\mathrel {\rightarrow \kern -9.5pt\mathrlap {|}\kern 6pt}Y$ be a relation.

1. 1.

   Functionality I. The assignment $R\mapsto R_{-1}$ defines a function

   \[ (-)_{-1}\colon \mathsf{Sets}(X,Y) \to \mathsf{Sets}(\mathcal{P}(X),\mathcal{P}(Y)). \]
2. 2.

   Functionality II. The assignment $R\mapsto R_{-1}$ defines a function

   \[ (-)_{-1}\colon \mathsf{Sets}(X,Y) \to \mathsf{Pos}((\mathcal{P}(X),\subset ),(\mathcal{P}(Y),\subset )). \]
3. 3.

   Interaction With Identities. For each $X\in \operatorname {\mathrm{Obj}}(\mathsf{Sets})$, we have

   \[ (\Delta _{X})_{-1}=\operatorname {\mathrm{id}}_{\mathcal{P}(X)}. \]
4. 4.

   Interaction With Composition. For each pair of composable relations $R\colon X\mathrel {\rightarrow \kern -9.5pt\mathrlap {|}\kern 6pt}Y$ and $S\colon Y\mathrel {\rightarrow \kern -9.5pt\mathrlap {|}\kern 6pt}C$, we have

   

5. 5.

   Interaction With Converses. We have

   \[ R^{\dagger }_{-1}=R_{*}. \]