Item 3 (00SG) — The Clowder Project

8.5.3 Weak Inverse Images

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

Definition 8.5.3.1.1 ▶ Weak Inverse Images

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

\[ R^{-1}\colon \mathcal{P}\webleft (B\webright )\to \mathcal{P}\webleft (A\webright ) \]

defined by²

\[ R^{-1}\webleft (V\webright ) \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\left\{ a\in A\ \middle |\ R\webleft (a\webright )\cap V\neq \text{Ø}\right\} \]

for each $V\in \mathcal{P}\webleft (B\webright )$.

¹Further Terminology: Also called simply the inverse image function associated to $R$.
²Further Terminology: The set $R^{-1}\webleft (V\webright )$ is called the weak inverse image of $V$ by $R$ or simply the inverse image of $V$ by $R$.

Remark 8.5.3.1.2 ▶ Unwinding Definition 8.5.3.1.1

Identifying subsets of $B$ with relations from $B$ to $\mathrm{pt}$ via Chapter 4: Constructions With Sets, of , we see that the weak inverse image function associated to $R$ is equivalently the function

\[ R^{-1}\colon \underbrace{\mathcal{P}\webleft (B\webright )}_{\cong \mathrm{Rel}\webleft (B,\mathrm{pt}\webright )}\to \underbrace{\mathcal{P}\webleft (A\webright )}_{\cong \mathrm{Rel}\webleft (A,\mathrm{pt}\webright )} \]

defined by

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

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

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

Explicitly, we have

\begin{align*} R^{-1}\webleft (V\webright ) & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}V\mathbin {\diamond }R\\ & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\int ^{b\in B}V^{-_{1}}_{b}\times R^{b}_{-_{2}}. \end{align*}

Proof of Remark 8.5.3.1.2.

We have

\begin{align*} V\mathbin {\diamond }R& \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}\int ^{b\in B}V^{-_{1}}_{b}\times R^{b}_{-_{2}}\\ & =\left\{ a\in A\ \middle |\ \int ^{b\in B}V^{\star }_{b}\times R^{b}_{a}=\mathsf{true}\right\} \\ & = \left\{ a\in A\ \middle |\ \begin{aligned} & \text{there exists $b\in B$ such that the}\\[-2.5pt]& \text{following conditions hold:}\\[7.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}$}\\[10pt]\end{aligned} \right\} \\ & = \left\{ a\in A\ \middle |\ \begin{aligned} & \text{there exists $b\in B$ such that the}\\[-2.5pt]& \text{following conditions hold:}\\[7.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\webleft (a\webright )$}\\[10pt]\end{aligned} \right\} \\ & = \left\{ a\in A\ \middle |\ \text{there exists $b\in V$ such that $b\in R\webleft (a\webright )$}\right\} \\ & = \left\{ a\in A\ \middle |\ R\webleft (a\webright )\cap V\neq \text{Ø}\right\} \\ & \mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}R^{-1}\webleft (V\webright )\end{align*}

This finishes the proof.

Proposition 8.5.3.1.3 ▶ Properties of Weak Inverse Image Functions

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

1.
Functoriality. The assignment $V\mapsto R^{-1}\webleft (V\webright )$ defines a functor

\[ R^{-1}\colon \webleft (\mathcal{P}\webleft (B\webright ),\subset \webright )\to \webleft (\mathcal{P}\webleft (A\webright ),\subset \webright ) \]

where
- •
  Action on Objects. For each $V\in \mathcal{P}\webleft (B\webright )$, we have
  
  \[ \webleft [R^{-1}\webright ]\webleft (V\webright )\mathrel {\smash {\overset {\mathclap {\scriptscriptstyle \text{def}}}=}}R^{-1}\webleft (V\webright ). \]
- •
  Action on Morphisms. For each $U,V\in \mathcal{P}\webleft (B\webright )$:
  - •
    If $U\subset V$, then $R^{-1}\webleft (U\webright )\subset R^{-1}\webleft (V\webright )$.
2.
Adjointness. We have an adjunction
witnessed by a bijections of sets

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

natural in $U\in \mathcal{P}\webleft (A\webright )$ and $V\in \mathcal{P}\webleft (B\webright )$, i.e. such that:
- (★)

3.
Preservation of Colimits. We have an equality of sets

\[ R^{-1}\webleft (\bigcup _{i\in I}U_{i}\webright )=\bigcup _{i\in I}R^{-1}\webleft (U_{i}\webright ), \]

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

\[ \begin{gathered} R^{-1}\webleft (U\webright )\cup R^{-1}\webleft (V\webright ) = R^{-1}\webleft (U\cup V\webright ),\\ R^{-1}\webleft (\text{Ø}\webright ) = \text{Ø}, \end{gathered} \]

natural in $U,V\in \mathcal{P}\webleft (B\webright )$.

Oplax Preservation of Limits. We have an inclusion of sets

\[ R^{-1}\webleft (\bigcap _{i\in I}U_{i}\webright )\subset \bigcap _{i\in I}R^{-1}\webleft (U_{i}\webright ), \]

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

\[ \begin{gathered} R^{-1}\webleft (U\cap V\webright ) \subset R^{-1}\webleft (U\webright )\cap R^{-1}\webleft (V\webright ),\\ R^{-1}\webleft (A\webright ) \subset B, \end{gathered} \]

natural in $U,V\in \mathcal{P}\webleft (B\webright )$.

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

\[ \webleft (R^{-1},R^{-1,\otimes },R^{-1,\otimes }_{\mathbb {1}}\webright ) \colon \webleft (\mathcal{P}\webleft (A\webright ),\cup ,\text{Ø}\webright ) \to \webleft (\mathcal{P}\webleft (B\webright ),\cup ,\text{Ø}\webright ), \]

being equipped with equalities

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

natural in $U,V\in \mathcal{P}\webleft (B\webright )$.

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

\[ \webleft (R^{-1},R^{-1,\otimes },R^{-1,\otimes }_{\mathbb {1}}\webright ) \colon \webleft (\mathcal{P}\webleft (A\webright ),\cap ,A\webright ) \to \webleft (\mathcal{P}\webleft (B\webright ),\cap ,B\webright ), \]

being equipped with inclusions

\[ \begin{gathered} R^{-1,\otimes }_{U,V} \colon R^{-1}\webleft (U\cap V\webright ) \subset R^{-1}\webleft (U\webright )\cap R^{-1}\webleft (V\webright ),\\ R^{-1,\otimes }_{\mathbb {1}} \colon R^{-1}\webleft (A\webright ) \subset B, \end{gathered} \]

natural in $U,V\in \mathcal{P}\webleft (B\webright )$.

Interaction With Strong Inverse Images I. We have

\[ R^{-1}\webleft (V\webright )=A\setminus R_{-1}\webleft (B\setminus V\webright ) \]

for each $V\in \mathcal{P}\webleft (B\webright )$.

Interaction With Strong Inverse Images II. Let $R\colon A\mathrel {\rightarrow \kern -9.5pt\mathrlap {|}\kern 6pt}B$ be a relation from $A$ to $B$.

(a)
If $R$ is a total relation, then we have an inclusion of sets

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

natural in $V\in \mathcal{P}\webleft (B\webright )$.
(b)
If $R$ is total and functional, then the above inclusion is in fact an equality.
(c)
Conversely, if we have $R_{-1}=R^{-1}$, then $R$ is total and functional.

Proof of Proposition 8.5.3.1.3.

Item 1: Functoriality

Clear.

Item 2: Adjointness

This follows from

Item 3: Preservation of Colimits

This follows from Item 2 and

Item 4: Oplax Preservation of Limits

Omitted.

Item 5: Symmetric Strict Monoidality With Respect to Unions

This follows from Item 3.

Item 6: Symmetric Oplax Monoidality With Respect to Intersections

This follows from Item 4.

Item 7: Interaction With Strong Inverse Images I

This follows from Item 7 of Proposition 8.5.2.1.3.

Item 8: Interaction With Strong Inverse Images II

This was proved in Item 8 of Proposition 8.5.2.1.3.

Proposition 8.5.3.1.4 ▶ Properties of the Weak Inverse Image Function Operation

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

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

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

\[ \webleft (-\webright )^{-1}\colon \mathrm{Rel}\webleft (A,B\webright ) \to \mathsf{Pos}\webleft (\webleft (\mathcal{P}\webleft (A\webright ),\subset \webright ),\webleft (\mathcal{P}\webleft (B\webright ),\subset \webright )\webright ). \]
3.
Interaction With Identities. For each $A\in \operatorname {\mathrm{Obj}}\webleft (\mathsf{Sets}\webright )$, we have¹

\[ \webleft (\chi _{A}\webright )^{-1}=\operatorname {\mathrm{id}}_{\mathcal{P}\webleft (A\webright )}. \]
4.
Interaction With Composition. For each pair of composable relations $R\colon A\mathrel {\rightarrow \kern -9.5pt\mathrlap {|}\kern 6pt}B$ and $S\colon B\mathrel {\rightarrow \kern -9.5pt\mathrlap {|}\kern 6pt}C$, we have²

¹That is, the postcomposition
\[ \webleft (\chi _{A}\webright )^{-1}\colon \mathrm{Rel}\webleft (\mathrm{pt},A\webright )\to \mathrm{Rel}\webleft (\mathrm{pt},A\webright ) \]
is equal to $\operatorname {\mathrm{id}}_{\mathrm{Rel}\webleft (\mathrm{pt},A\webright )}$.
²That is, we have