Item 4 (02U4) — The Clowder Project

8.7.3 Inverse Images

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

The inverse image function associated to $R$ is the function

\[ R^{-1}\colon \mathcal{P}(Y)\to \mathcal{P}(X) \]

defined by¹

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

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

¹Further Terminology: The set $R^{-1}(V)$ is called the inverse image of $V$ by $R$ or simply the inverse image of $V$ by $R$.

Remark 8.7.3.1.2 ▶ Unwinding Definition 8.7.3.1.1

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

\[ R^{-1}\colon \underbrace{\mathcal{P}(Y)}_{\cong \mathrm{Rel}(Y,\mathrm{pt})}\to \underbrace{\mathcal{P}(X)}_{\cong \mathrm{Rel}(X,\mathrm{pt})} \]

defined by

\[ R^{-1}(V)\mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}V\mathbin {\diamond }R \]

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

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

Proof of Remark 8.7.3.1.2.

We have

\begin{align*} V\mathbin {\diamond }R& \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\int ^{b\in Y}V^{-_{1}}_{b}\times R^{b}_{-_{2}}\\ & =\left\{ a\in X\ \middle |\ \int ^{b\in Y}V^{\star }_{b}\times R^{b}_{a}=\mathsf{true}\right\} \\ & = \left\{ a\in X\ \middle |\ \begin{aligned} & \text{There exists $b\in Y$ such that the}\\ & \text{following conditions hold:}\\[2.5pt]& \mspace {25mu}\rlap {\text{1.}}\mspace {22.5mu}\text{We have $V^{\star }_{b}=\mathsf{true}$.}\\ & \mspace {25mu}\rlap {\text{2.}}\mspace {22.5mu}\text{We have $R^{b}_{a}=\mathsf{true}$.}\\ \end{aligned} \right\} \\ & = \left\{ a\in X\ \middle |\ \begin{aligned} & \text{There exists $b\in Y$ such that the}\\ & \text{following conditions hold:}\\[2.5pt]& \mspace {25mu}\rlap {\text{1.}}\mspace {22.5mu}\text{We have $b\in V$.}\\ & \mspace {25mu}\rlap {\text{2.}}\mspace {22.5mu}\text{We have $b\in R(a)$.}\\ \end{aligned} \right\} \\ & = \left\{ a\in X\ \middle |\ \text{there exists $b\in V$ such that $b\in R(a)$}\right\} \\ & = \left\{ a\in X\ \middle |\ R(a)\cap V\neq \text{Ø}\right\} \\ & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}R^{-1}(V)\end{align*}

This finishes the proof.

Proposition 8.7.3.1.3 ▶ Properties of Inverse Images I

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

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:
- (★)
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:
  - (★)
3.
Interaction With Unions of Families of Subsets. The diagram
commutes, i.e. we have

\[ \bigcup _{U\in \mathcal{U}}R^{-1}(U)=\bigcup _{V\in R^{-1}(\mathcal{U})}V \]

for each $\mathcal{U}\in \mathcal{P}(X)$, where $R^{-1}(\mathcal{U})\mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}(R^{-1})_{!}(\mathcal{U})$.

4.
Interaction With Intersections of Families of Subsets. The diagram
commutes, i.e. we have

\[ \bigcap _{U\in \mathcal{U}}R^{-1}(U)=\bigcap _{V\in R^{-1}(\mathcal{U})}V \]

for each $\mathcal{U}\in \mathcal{P}(X)$, where $R^{-1}(\mathcal{U})\mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}(R^{-1})_{!}(\mathcal{U})$.

Interaction With Binary Unions. The diagram

commutes, i.e. we have

\[ R^{-1}(U\cup V)=R^{-1}(U)\cup R^{-1}(V) \]

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

Interaction With Binary Intersections. We have a natural transformation

with components

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

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

Interaction With Differences. We have a natural transformation

with components

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

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

Interaction With Complements. The diagram

commutes, i.e. we have

\[ R^{-1}(U^{\textsf{c}})=R_{*}(U)^{\textsf{c}} \]

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

Interaction With Symmetric Differences. We have a natural transformation

with components

\[ R^{-1}(U)\mathbin {\triangle }R^{-1}(V)\subset R^{-1}(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^{-1}([U,V]_{X})=[R_{-1}(U),R^{-1}(V)]_{Y}, \]

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

11.

Preservation of Colimits. We have an equality of sets

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

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

12.

Oplax Preservation of Limits. We have an inclusion of sets

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

\[ \begin{gathered} R^{-1}(U\cap V) \subset R^{-1}(U)\cap R^{-1}(V),\\ R^{-1}(X) \subset Y, \end{gathered} \]

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

13.

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

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

being equipped with equalities

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

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

14.

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

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

being equipped with inclusions

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

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

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.

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)^{-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.

Relation to Coinverse Images. We have

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

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

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*}

\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.

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*}

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

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

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.

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

Proof of Proposition 8.7.3.1.3.

Item 1: Functoriality

Omitted.

Item 2: Adjointness

This follows from

Item 3: Interaction With Unions of Families of Subsets

We have

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

This finishes the proof.

Item 4: Interaction With Intersections of Families of Subsets

We have

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

This finishes the proof.

Item 5: Interaction With Binary Unions

We have

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

where we have used Chapter 4: Constructions With Sets, Item 8 of Proposition 4.3.9.1.2 for the fourth equality.

Item 6: Interaction With Binary Intersections

We have

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

This finishes the proof.

Item 7: Interaction With Differences

We have

\begin{align*} R^{-1}(U)\setminus R^{-1}(V) & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\left\{ a\in X\ \middle |\ R(a)\cap U\neq \text{Ø}\right\} \setminus \left\{ a\in X\ \middle |\ R(a)\cap V\neq \text{Ø}\right\} \\ & = \left\{ a\in X\ \middle |\ \text{$R(a)\cap U\neq \text{Ø}$ and not $R(a)\cap V\neq \text{Ø}$}\right\} \\ & = \left\{ a\in X\ \middle |\ \text{$R(a)\cap U\neq \text{Ø}$ and $R(a)\cap V=\text{Ø}$}\right\} \\ & \subset \left\{ a\in X\ \middle |\ R(a)\cap (U\setminus V)\neq \text{Ø}\right\} \\ & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}R^{-1}(U\setminus V) \end{align*}

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

Item 8: Interaction With Complements

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

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

This finishes the proof.

Item 9: Interaction With Symmetric Differences

We have

\begin{align*} R^{-1}(U)\mathbin {\triangle }R^{-1}(V) & = (R^{-1}(U)\cup R^{-1}(V))\setminus (R^{-1}(U)\cap R^{-1}(V))\\ & \subset (R^{-1}(U)\cup R^{-1}(V))\setminus R^{-1}(U\cap V)\\ & = R^{-1}(U\cup V)\setminus R^{-1}(U\cap V)\\ & \subset R^{-1}((U\cup V)\setminus (U\cap V))\\ & = R^{-1}(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}(X)$ 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^{-1}([U,V]_{Y}) & = R^{-1}(U^{\textsf{c}}\cup V)\\ & = R^{-1}(U^{\textsf{c}})\cup R^{-1}(V)\\ & = R_{-1}(U)^{\textsf{c}}\cup R^{-1}(V)\\ & = [R_{-1}(U),R^{-1}(V)]_{X},\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 Coinverse Images

This follows from Item 17 of Proposition 8.7.2.1.4.

Item 18: Interaction With Functional Relations

This is a repetition of Item 18 of Proposition 8.7.2.1.4 and is proved there.

Item 19: Interaction With Total Relations

This is a repetition of Item 19 of Proposition 8.7.2.1.4 and is proved there.

Item 20: Interaction With Functions I

This is a repetition of Item 20 of Proposition 8.7.2.1.4 and is proved there.

Item 21: Interaction With Functions II

This is a repetition of Item 21 of Proposition 8.7.2.1.4 and is proved there.

Proposition 8.7.3.1.4 ▶ Properties of Inverse Images II

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

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

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

\[ (-)^{-1}\colon \mathrm{Rel}(X,Y) \to \mathsf{Pos}((\mathcal{P}(X),\subset ),(\mathcal{P}(Y),\subset )). \]
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.
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.
Interaction With Converses. We have

\[ (R^{\dagger })^{-1}=R_{!}. \]