Subsection 7.4.3 (00SA): Weak Inverse Images

Style	Class	Font	Theorem Environments
Style 1	`book`	Alegreya Sans	`tcbthm`
Style 2	`book`	Alegreya Sans	`amsthm`
Style 3	`book`	Arno*	`amsthm`
Style 4	`book`	Computer Modern	`amsthm`

7.4.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 7.4.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}}}=}}\webleft\{ a\in A\ \middle |\ R\webleft (a\webright )\cap V\neq \text{Ø}\webright\} \]

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 7.4.3.1.2 ▶ Unwinding Definition 7.4.3.1.1

Identifying subsets of $B$ with relations from $B$ to $\text{pt}$ via Chapter 2: 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,\text{pt}\webright )}\to \underbrace{\mathcal{P}\webleft (A\webright )}_{\cong \mathrm{Rel}\webleft (A,\text{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}}}\text{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 ^{x\in B}V^{-_{1}}_{x}\times R^{x}_{-_{2}}. \end{align*}

Proof of Remark 7.4.3.1.2.

We have

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

This finishes the proof.

Proposition 7.4.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.

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 )$.
Adjointness. We have an adjunction
witnessed by a bijections of sets
\[ \textup{Hom}_{\mathcal{P}\webleft (A\webright )}\webleft (R^{-1}\webleft (U\webright ),V\webright )\cong \textup{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:
- The following conditions are equivalent:
  - We have $R^{-1}\webleft (U\webright )\subset V$;
  - We have $U\subset R_{!}\webleft (V\webright )$.
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 $\webleft\{ U_{i}\webright\} _{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 $\webleft\{ U_{i}\webright\} _{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$.
1. 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 )$.
2. If $R$ is total and functional, then the above inclusion is in fact an equality.
3. Conversely, if we have $R_{-1}=R^{-1}$, then $R$ is total and functional.

Proof of Proposition 7.4.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 7.4.2.1.3.

Item 8: Interaction With Strong Inverse Images II

This was proved in Item 8 of Proposition 7.4.2.1.3.

Proposition 7.4.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.

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 ). \]
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 ). \]
Interaction With Identities. For each $A\in \text{Obj}\webleft (\mathsf{Sets}\webright )$, we have¹
\[ \webleft (\chi _{A}\webright )^{-1}=\text{id}_{\mathcal{P}\webleft (A\webright )}; \]
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²