The Clowder Project

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

1. 1.

   Functoriality. The assignment $U\mapsto R_{*}(U)$ defines a functor

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

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

   • •

     If $U\subset V$, then $R_{*}(U)\subset R_{*}(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}(Y)} \hookrightarrow R_{*}\circ R^{-1},\\ R^{-1}\circ R_{*} \hookrightarrow \operatorname {\mathrm{id}}_{\mathcal{P}(X)}. \end{align*}

      In particular:

      • •

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

      • •

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

   2. (b)

      A bijections of sets

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

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

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

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

      • •

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

3. 3.

   Interaction With Unions of Families of Subsets. The diagram

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

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

4. 4.

   Interaction With Intersections of Families of Subsets. The diagram

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

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

5. 5.

   Interaction With Binary Unions. We have a natural transformation

   
   with components
   \[ R_{*}(U)\cup R_{*}(V)\subset R_{*}(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_{*}(U\cap V)=R_{*}(U)\cap R_{*}(V) \]

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

7. 7.

   Interaction With Differences. We have a natural transformation

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

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

8. 8.

   Interaction With Complements. The diagram

   
   commutes, i.e. we have
   \[ R_{*}(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_{*}(U)\mathbin {\triangle }R_{*}(V)\neq R_{*}(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_{!}(U),R_{*}(V)]_{X}\subset R_{*}([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_{*}(U_{i})\subset R_{*}\left(\bigcup _{i\in I}U_{i}\right), \]

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

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

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

12. 12.

    Preservation of Limits. We have an equality of sets

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

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

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

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

13. 13.

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

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

    being equipped with inclusions

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

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

14. 14.

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

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

    being equipped with equalities

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

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

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)_{*}(U'\mathchoice {\mathbin {\textstyle \coprod }}{\mathbin {\textstyle \coprod }}{\mathbin {\scriptstyle \textstyle \coprod }}{\mathbin {\scriptscriptstyle \textstyle \coprod }}V')=R_{*}(U')\mathchoice {\mathbin {\textstyle \coprod }}{\mathbin {\textstyle \coprod }}{\mathbin {\scriptstyle \textstyle \coprod }}{\mathbin {\scriptscriptstyle \textstyle \coprod }}S_{*}(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)_{*}(U'\boxtimes _{X'\times Y'}V')=R_{*}(U')\boxtimes _{X\times Y}S_{*}(V') \]

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

17. 17.

    Relation to Direct Images. We have

    \[ R_{*}(U)=Y\setminus R_{!}(X\setminus U) \]

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

18. 18.

    Interaction With Injections. If $R$ is injective, then we have

    \begin{align*} R^{\mathrm{im}}_{*}(U) & = R_{!}(U),\\ R^{\mathrm{cp}}_{*}(U) & = Y\setminus \mathrm{Im}(R), \end{align*}

    so

    \begin{align*} R_{*}(U) & = R^{\mathrm{im}}_{*}(U)\cup R^{\mathrm{cp}}_{*}(U)\\ & = R_{!}(U)\cup (Y\setminus \mathrm{Im}(R)) \end{align*}

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

19. 19.

    Interaction With Surjections. If $R$ is surjective, then we have

    \begin{align*} R^{\mathrm{im}}_{*}(U) & \subset R_{!}(U),\\ R^{\mathrm{cp}}_{*}(U) & = \text{Ø},\\ \end{align*}

    so

    \[ R_{*}(U)\subset R_{!}(U) \]

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

20. 20.

    Interaction With Bijections I. If $R$ is bijective, then we have

    \begin{align*} R^{\mathrm{im}}_{*}(U) & = R_{!}(U),\\ R^{\mathrm{cp}}_{*}(U) & = \text{Ø}, \end{align*}

    so $R_{!}=R_{*}$.

21. 21.

    Interaction With Bijections II. If $R_{!}=R_{*}$, then $R$ is bijective.

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_{*}$ defines a function

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

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

   \[ (-)_{*}\colon \mathsf{Sets}(X,Y) \to \operatorname {\mathrm{Hom}}_{\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

   \[ (\operatorname {\mathrm{id}}_{X})_{*}=\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 }_{*}=R_{-1}. \]