Composition of Inverse Image Mappings of Mappings

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $A, B, C$ be non-empty sets.

Let $f: A \to B, g: B \to C$ be mappings.


Let:

$f^\gets: \powerset B \to \powerset A$

and

$g^\gets: \powerset C \to \powerset B$

be the inverse image mappings of $f$ and $g$.


Then:

$\paren {g \circ f}^\gets = f^\gets \circ g^\gets$


Proof

Let $T \subseteq C$.

We have:

\(\displaystyle \map {\paren {f \circ g}^\gets} T\) \(=\) \(\displaystyle \begin {cases} \set {x \in A: \map g {\map f x} \in T} & : \Img {g \circ f} \cap T \ne \O \\ \O & : \Img {g \circ f} \cap T = \O \end {cases}\)
and
\(\displaystyle \map {f^\gets \circ g^\gets} T\) \(=\) \(\displaystyle \begin {cases} \set {x \in A: \map f x \in \map {g^\gets} T} & : \Img f \cap \map {g^\gets} T \ne \O \\ \O & : \Img f \cap \map {g^\gets} T = \O \end {cases}\)
\(\displaystyle \) \(=\) \(\displaystyle \begin {cases} \set {x \in A: \map g {\map f x} \in T} & : \Img f \cap \map {g^\gets} T \ne \O \\ \O & : \Img f \cap \map {g^\gets} T = \O \end {cases}\)


It remains to be shown that:

$\Img f \cap \map {g^\gets} T = \O \iff \Img {g \circ f} \cap T = \O$

So:

\(\displaystyle \Img f \cap \map {g^\gets} T\) \(=\) \(\displaystyle \O\)
\(\displaystyle \leadstoandfrom \ \ \) \(\displaystyle \Img f\) \(\subseteq\) \(\displaystyle \relcomp B {\map {g^\gets} T}\) Empty Intersection iff Subset of Complement
\(\displaystyle \) \(=\) \(\displaystyle \map {g^\gets} {\relcomp C T}\) Complement of Preimage equals Preimage of Complement
\(\displaystyle \leadstoandfrom \ \ \) \(\displaystyle \Img {g \circ f}\) \(=\) \(\displaystyle \map {g^\gets} {\Img f}\) Intersection with Complement is Empty iff Subset
\(\displaystyle \) \(\subseteq\) \(\displaystyle \relcomp C T\) Subset of Preimage under Relation is Preimage of Subset: Corollary
\(\displaystyle \leadstoandfrom \ \ \) \(\displaystyle \Img {g \circ f} \cap T\) \(=\) \(\displaystyle \O\) Empty Intersection iff Subset of Complement

$\blacksquare$


Sources