Complement of Preimage equals Preimage of Complement

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $f: S \to T$ be a mapping.

Let $T_1$ be a subset of $T$.


Then:

$\relcomp S {f^{-1} \sqbrk {T_1} } = f^{-1} \sqbrk {\relcomp T {T_1} }$

where:

$\complement_S$ (in this context) denotes relative complement
$f^{-1} \sqbrk {T_1}$ denotes preimage.


That is:

$S \setminus f^{-1} \sqbrk {T_1} = f^{-1} \sqbrk {T \setminus T_1}$


This can be expressed in the language and notation of inverse image mappings as:

$\forall T_1 \in \powerset T: \relcomp S {\map {f^\gets} {T_1} } = \map {f^\gets} {\relcomp T {T_1} }$


Proof

From One-to-Many Image of Set Difference: Corollary 2 we have:

$\relcomp {\Img \RR} {\RR \sqbrk {S_1} } = \RR \sqbrk {\relcomp S {S_1} }$

where:

$S_1 \subseteq S$
$\RR \subseteq T \times S$ is a one-to-many relation on $T \times S$.


Hence as $f^{-1}: T \to S$ is a one-to-many relation:

$\relcomp {\Preimg f} {f^{-1} \sqbrk {T_1} } = f^{-1} \sqbrk {\relcomp T {T_1} }$


But from Preimage of Mapping equals Domain, we have that:

$\Preimg f = S$

Hence:

$\relcomp S {f^{-1} \sqbrk {T_1} } = f^{-1} \sqbrk {\relcomp T {T_1} }$

$\blacksquare$


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Complement_of_Preimage_equals_Preimage_of_Complement&oldid=563825"