Inverse of Induced Mapping does not necessarily equal Mapping Induced by Inverse

From ProofWiki
Jump to: navigation, search


Let $S$ and $T$ be sets.

Let $\mathcal R \subseteq S \times T$ be a relation.

Let $\mathrel R^\to$ be the mapping induced on the power set $\mathcal P \left({S}\right)$ of $S$ by $\mathcal R$.

Let $\mathrel R^\gets$ be the mapping induced on the power set $\mathcal P \left({T}\right)$ of $T$ by the inverse relation $\mathcal R^{-1}$.

Then it is not necessarily the case that:

$\left({\mathrel R^\to}\right)^{-1} = \mathcal R^\gets$

That is, the inverse of the mapping induced by $\mathcal R$ does not always equal the mapping induced by the inverse $\mathcal R$.


Proof by Counterexample:

Let $S = T = \left\{{0, 1}\right\}$.

Let $\mathcal R = \left\{{\left({0, 0}\right), \left({0, 1}\right)}\right\}$.

We have that:

$\mathcal R^{-1} = \left\{{\left({0, 0}\right), \left({1, 0}\right)}\right\}$
$\mathcal P \left({S}\right) = \mathcal P \left({T}\right) = \left\{ {\varnothing, \left\{ {0}\right\}, \left\{ {1}\right\} , \left\{{0, 1}\right\} }\right\}$

Thus, by inspection:

\(\displaystyle \mathrel R^\to \left({\varnothing}\right)\) \(=\) \(\displaystyle \varnothing\) $\quad$ $\quad$
\(\displaystyle \mathrel R^\to \left({\left\{ {0}\right\} }\right)\) \(=\) \(\displaystyle \left\{ {0, 1}\right\}\) $\quad$ $\quad$
\(\displaystyle \mathrel R^\to \left({\left\{ {1}\right\} }\right)\) \(=\) \(\displaystyle \varnothing\) $\quad$ $\quad$
\(\displaystyle \mathrel R^\to \left({\left\{ {0, 1}\right\} }\right)\) \(=\) \(\displaystyle \left\{ {0, 1}\right\}\) $\quad$ $\quad$

Note that $\left({\mathrel R^\to}\right)^{-1}$ is the inverse of a mapping which is neither an injection nor a surjection, and so is itself not a mapping from $\mathcal P \left({T}\right)$ to $\mathcal P \left({S}\right)$.

\(\displaystyle \left({\mathrel R^\to}\right)^{-1} \left({\varnothing}\right)\) \(=\) \(\displaystyle \left\{ {\varnothing, \left\{ {1}\right\} }\right\}\) $\quad$ $\quad$
\(\displaystyle \left({\mathrel R^\to}\right)^{-1} \left({\left\{ {0}\right\} }\right)\) \(=\) \(\displaystyle \varnothing\) $\quad$ $\quad$
\(\displaystyle \left({\mathrel R^\to}\right)^{-1} \left({\left\{ {1}\right\} }\right)\) \(=\) \(\displaystyle \varnothing\) $\quad$ $\quad$
\(\displaystyle \left({\mathrel R^\to}\right)^{-1} \left({\left\{ {0, 1}\right\} }\right)\) \(=\) \(\displaystyle \left\{ {\left\{ {0}\right\}, \left\{ {0, 1}\right\} }\right\}\) $\quad$ $\quad$

This can be seen to be completely different from $\mathrel R^\gets$, which can be determined by inspection to be:

\(\displaystyle \mathrel R^\gets \left({\varnothing}\right)\) \(=\) \(\displaystyle \varnothing\) $\quad$ $\quad$
\(\displaystyle \mathrel R^\gets \left({\left\{ {0}\right\} }\right)\) \(=\) \(\displaystyle \left\{ {0}\right\}\) $\quad$ $\quad$
\(\displaystyle \mathrel R^\gets \left({\left\{ {1}\right\} }\right)\) \(=\) \(\displaystyle \left\{ {0}\right\}\) $\quad$ $\quad$
\(\displaystyle \mathrel R^\gets \left({\left\{ {0, 1}\right\} }\right)\) \(=\) \(\displaystyle \left\{ {0}\right\}\) $\quad$ $\quad$