Item 5 (02XN) — The Clowder Project

8.7.1 Direct Images

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

The direct image function associated to $R$ is the function¹

\[ R_{!}\colon \mathcal{P}(X)\to \mathcal{P}(Y) \]

defined by²

\begin{align*} R_{!}(U) & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\left\{ b\in Y\ \middle |\ R^{-1}(b)\cap U\neq \text{Ø}\right\} \\ & = \left\{ b\in Y\ \middle |\ \begin{aligned} & \text{there exists some $a\in U$}\\ & \text{such that $b\in R(a)$} \end{aligned} \right\} \\ & = \bigcup _{a\in U}R(a) \end{align*}

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

¹Further Notation: Also written simply $R\colon \mathcal{P}(X)\to \mathcal{P}(Y)$.
²Further Terminology: The set $R(U)$ is called the direct image of $U$ by $R$.

ゴ

Warning 8.7.1.1.2 ▶ Notation for Direct Images Is Confusing

Notation for direct images between powersets is tricky; see Chapter 4: Constructions With Sets, Warning 4.6.1.1.3. Here we’ll try to align our notation for relations with that for functions.

ゴ

Remark 8.7.1.1.3 ▶ Unwinding Definition 8.7.1.1.1

Identifying $\mathcal{P}(X)$ with $\mathrm{Rel}(\mathrm{pt},X)$ via Chapter 4: Constructions With Sets, Item 3 of Proposition 4.4.1.1.4, we see that the direct image function associated to $R$ is equivalently the function

\[ R_{!}\colon \underbrace{\mathcal{P}(X)}_{\cong \mathrm{Rel}(\mathrm{pt},X)} \to \underbrace{\mathcal{P}(Y)}_{\cong \mathrm{Rel}(\mathrm{pt},Y)} \]

defined by

\[ R_{!}(U)\mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}R\mathbin {\diamond }U \]

for each $U\in \mathcal{P}(X)$, where $R\mathbin {\diamond }U$ is the composition

\[ \mathrm{pt}\mathbin {\overset {U}{\mathrel {\rightarrow \kern -9.5pt\mathrlap {|}\kern 6pt}}}X\mathbin {\overset {R}{\mathrel {\rightarrow \kern -9.5pt\mathrlap {|}\kern 6pt}}}Y. \]

Proposition 8.7.1.1.4 ▶ Properties of Direct Images I

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

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:
- (★)
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:
  1. (i)
    The following conditions are equivalent:
    
    (I)
    we have $R_{!}(U)\subset V$.
    
    (II)
    We have $U\subset R_{-1}(V)$.
3.
Interaction With Unions of Families of Subsets. The diagram
commutes, i.e. we have

\[ \bigcup _{U\in \mathcal{U}}R_{!}(U)=\bigcup _{V\in R_{!}(\mathcal{U})}V \]

for each $\mathcal{U}\in \mathcal{P}(X)$, where $R_{!}(\mathcal{U})\mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}(R_{!})_{!}(\mathcal{U})$.
4.
Interaction With Intersections of Families of Subsets. The diagram
commutes, i.e. we have

\[ \bigcap _{U\in \mathcal{U}}R_{!}(U)=\bigcap _{V\in R_{!}(\mathcal{U})}V \]

for each $\mathcal{U}\in \mathcal{P}(X)$, where $R_{!}(\mathcal{U})\mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}(R_{!})_{!}(\mathcal{U})$.
5.
Interaction With Binary Unions. The diagram
commutes, i.e. we have

\[ R_{!}(U\cup V)=R_{!}(U)\cup R_{!}(V) \]

for each $U,V\in \mathcal{P}(X)$.
6.
Interaction With Binary Intersections. We have a natural transformation
with components

\[ R_{!}(U\cap V)\subset R_{!}(U)\cap R_{!}(V) \]

indexed by $U,V\in \mathcal{P}(X)$.
7.
Interaction With Differences. We have a natural transformation
with components

\[ R_{!}(U)\setminus R_{!}(V)\subset R_{!}(U\setminus V) \]

indexed by $U,V\in \mathcal{P}(X)$.
8.
Interaction With Complements. The diagram
commutes, i.e. we have

\[ R_{!}(U^{\textsf{c}})=R_{*}(U)^{\textsf{c}} \]

for each $U\in \mathcal{P}(X)$.
9.
Interaction With Binary Symmetric Differences. We have a natural transformation
with components

\[ R_{!}(U)\mathbin {\triangle }R_{!}(V)\subset R_{!}(U\mathbin {\triangle }V) \]

indexed by $U,V\in \mathcal{P}(X)$.
10.
Interaction With Internal Homs of Powersets. The diagram
commutes, i.e. we have an equality of sets

\[ R_{!}([U,V]_{X})=[R_{*}(U),R_{!}(V)]_{Y}, \]

natural in $U,V\in \mathcal{P}(X)$.
11.
Preservation of Colimits. We have an equality of sets

\[ R_{!}\left(\bigcup _{i\in I}U_{i}\right)=\bigcup _{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)\cup R_{!}(V) = R_{!}(U\cup V),\\ R_{!}(\text{Ø}) = \text{Ø}, \end{gathered} \]

natural in $U,V\in \mathcal{P}(X)$.
12.
Oplax Preservation of Limits. We have an inclusion of sets

\[ R_{!}\left(\bigcap _{i\in I}U_{i}\right)\subset \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 inclusions

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

natural in $U,V\in \mathcal{P}(X)$.
13.
Symmetric Strict Monoidality With Respect to Unions. The direct image function of Item 1 has a symmetric strict monoidal structure

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

being equipped with equalities

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

natural in $U,V\in \mathcal{P}(X)$.
14.
Symmetric Oplax Monoidality With Respect to Intersections. The direct image function of Item 1 has a symmetric oplax monoidal structure

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

being equipped with inclusions

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

natural in $U,V\in \mathcal{P}(X)$.
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.
Interaction With Products. 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\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.
Relation to Codirect Images. We have

\[ R_{!}(U)=R_{*}(U^{\textsf{c}})^{\textsf{c}} \]

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

Proof of Proposition 8.7.1.1.4.

Item 1: Functoriality

Omitted.

Item 2: Adjointness

This follows from Remark 8.7.1.1.3, Remark 8.7.2.1.2 and

Item 3: Interaction With Unions of Families of Subsets

We have

\begin{align*} \bigcup _{V\in R_{!}(\mathcal{U})}V & = \bigcup _{V\in \left\{ R_{!}(U)\in \mathcal{P}(X)\ \middle |\ U\in \mathcal{U}\right\} }V\\ & = \bigcup _{U\in \mathcal{U}}R_{!}(U).\end{align*}

This finishes the proof.

Item 4: Interaction With Intersections of Families of Subsets

We have

\begin{align*} \bigcap _{V\in R_{!}(\mathcal{U})}V & = \bigcap _{V\in \left\{ R_{!}(U)\in \mathcal{P}(X)\ \middle |\ U\in \mathcal{U}\right\} }V\\ & = \bigcap _{U\in \mathcal{U}}R_{!}(U).\end{align*}

This finishes the proof.

Item 5: Interaction With Binary Unions

We have

\begin{align*} R_{!}(U\cup V) & = \bigcup _{a\in U\cup V}R(a)\\ & = \left(\bigcup _{a\in U}R(a)\right)\cup \left(\bigcup _{a\in V}R(a)\right)\\ & = R_{!}(U)\cup R_{!}(V). \end{align*}

This finishes the proof.

Item 6: Interaction With Binary Intersections

We have

\begin{align*} R_{!}(U\cap V) & = \bigcup _{a\in U\cap V}R(a)\\ & \subset \left(\bigcup _{a\in U}R(a)\right)\cap \left(\bigcup _{a\in V}R(a)\right)\\ & = R_{!}(U)\cap R_{!}(V), \end{align*}

where we have used Chapter 4: Constructions With Sets, Item 7 of Proposition 4.3.6.1.2 by taking

\begin{align*} \mathcal{U} & = \left\{ R(a)\in \mathcal{P}(Y)\ \middle |\ a\in U\right\} ,\\ \mathcal{V} & = \left\{ R(a)\in \mathcal{P}(Y)\ \middle |\ a\in V\right\} . \end{align*}

Since $\mathcal{P}(Y)$ is posetal, naturality is automatic (Chapter 11: Categories, Item 4 of Proposition 11.2.7.1.2).

Item 7: Interaction With Differences

See [[Unknown Reference: proof-wiki:image-of-set-difference-under-relation]].

Item 8: Interaction With Complements

Applying Item 17 to $X\setminus U$, we have

\begin{align*} R_{!}(U^{\textsf{c}}) & = R_{!}(X\setminus U)\\ & = Y\setminus R_{*}(X\setminus (X\setminus U))\\ & = Y\setminus R_{*}(U)\\ & = R_{*}(U)^{\textsf{c}}. \end{align*}

This finishes the proof.

Item 9: Interaction With Binary Symmetric Differences

We have

\begin{align*} R_{!}(U)\mathbin {\triangle }R_{!}(V) & = (R_{!}(U)\cup R_{!}(V))\setminus (R_{!}(U)\cap R_{!}(V))\\ & \subset (R_{!}(U)\cup R_{!}(V))\setminus (R_{!}(U\cap V))\\ & = (R_{!}(U\cup V))\setminus (R_{!}(U\cap V))\\ & \subset R_{!}((U\cup V)\setminus (U\cap V))\\ & = R_{!}(U\mathbin {\triangle }V), \end{align*}

where we have used:

•
Chapter 4: Constructions With Sets, Item 2 of Proposition 4.3.12.1.2 for the first equality.
•
Item 6 of this proposition together with Chapter 4: Constructions With Sets, Item 1 of Proposition 4.3.10.1.2 for the first inclusion.
•
Item 5 for the second equality.
•
Item 7 for the second inclusion.
•
Chapter 4: Constructions With Sets, Item 2 of Proposition 4.3.12.1.2 for the last equality.

Since $\mathcal{P}(Y)$ is posetal, naturality is automatic (Chapter 11: Categories, Item 4 of Proposition 11.2.7.1.2). This finishes the proof.

Item 10: Interaction With Internal Homs of Powersets

We have

\begin{align*} R_{!}([U,V]_{X}) & = R_{!}(U^{\textsf{c}}\cup V)\\ & = R_{!}(U^{\textsf{c}})\cup R_{!}(V)\\ & = R_{*}(U)^{\textsf{c}}\cup R_{!}(V)\\ & = [R_{*}(U),R_{!}(V)]_{Y},\end{align*}

where we have used:

•
Item 5 for the second equality.
•
Item 17 for the third equality.

Since $\mathcal{P}(Y)$ is posetal, naturality is automatic (Chapter 11: Categories, Item 4 of Proposition 11.2.7.1.2). This finishes the proof.

Item 11: Preservation of Colimits

This follows from Item 2 and

Item 12: Oplax Preservation of Limits

Omitted.

Item 13: Symmetric Strict Monoidality With Respect to Unions

This follows from Item 11.

Item 14: Symmetric Oplax Monoidality With Respect to Intersections

This follows from Item 12.

Item 15: Interaction With Coproducts

Omitted.

Item 16: Interaction With Products

Omitted.

Item 17: Relation to Codirect Images

The proof proceeds in the same way as in the case of functions (Chapter 4: Constructions With Sets, Item 17 of Proposition 4.6.1.1.5): applying Item 17 of Proposition 8.7.4.1.4 to $A\setminus U$, we have

\begin{align*} R_{*}(X\setminus U) & = Y\setminus R_{!}(X\setminus (X\setminus U))\\ & = Y\setminus R_{!}(U). \end{align*}

Taking complements, we then obtain

\begin{align*} R_{!}(U) & = Y\setminus (Y\setminus R_{!}(U)),\\ & = Y\setminus R_{*}(X\setminus U), \end{align*}

which finishes the proof.

Proposition 8.7.1.1.5 ▶ Properties of Direct Images II

Let $R\colon X\mathrel {\rightarrow \kern -9.5pt\mathrlap {|}\kern 6pt}Y$ and $S\colon Y\mathrel {\rightarrow \kern -9.5pt\mathrlap {|}\kern 6pt}Z$ be relations.

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

\[ (-)_{!}\colon \mathrm{Rel}(X,Y) \to \mathsf{Sets}(\mathcal{P}(X),\mathcal{P}(Y)). \]
2.
Functionality II. The assignment $R\mapsto R_{!}$ defines a function

\[ (-)_{!}\colon \mathrm{Rel}(X,Y) \to \mathsf{Pos}((\mathcal{P}(X),\subset ),(\mathcal{P}(Y),\subset )). \]
3.
Interaction With Identities. We have

\[ (\Delta _{X})_{!}=\operatorname {\mathrm{id}}_{\mathcal{P}(X)}. \]
4.
Interaction With Composition. We have

5.
Interaction With Converses. We have

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

Proof of Proposition 8.7.1.1.5.

Item 1: Functionality I

There is nothing to prove.

Item 2: Functionality II

This follows from Item 1 of Proposition 8.7.1.1.4.

Item 3: Interaction With Identities

Indeed, we have

\begin{align*} (\chi _{X})_{!}(U) & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\bigcup _{a\in U}\chi _{X}(a)\\ & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\bigcup _{a\in U}\left\{ a\right\} \\ & = U\\ & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\operatorname {\mathrm{id}}_{\mathcal{P}(X)}(U) \end{align*}

for each $U\in \mathcal{P}(X)$. Thus $(\chi _{X})_{!}=\operatorname {\mathrm{id}}_{\mathcal{P}(X)}$.

Item 4: Interaction With Composition

Indeed, we have

\begin{align*} (S\mathbin {\diamond }R)_{!}(U) & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\bigcup _{a\in U}[S\mathbin {\diamond }R](a)\\ & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\bigcup _{a\in U}S(R(a))\\ & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\bigcup _{a\in U}S_{!}(R(a))\\ & = S_{!}\left(\bigcup _{a\in U}R(a)\right)\\ & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}S_{!}(R_{!}(U))\\ & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}[S_{!}\circ R_{!}](U) \end{align*}

for each $U\in \mathcal{P}(X)$, where we used Item 11 of Proposition 8.7.1.1.4. Thus $(S\mathbin {\diamond }R)_{!}=S_{!}\circ R_{!}$.

Item 5: Interaction With Converses

Omitted.

Statistics Cite

Noticed something off, or have any comments? Feel free to reach out!

•Email
•Discord

You can also use the contact form below: