Preimage of Singleton

From ProofWiki
Jump to: navigation, search

Theorem

Let $\mathcal R$ be a relation.

Let $\mathcal R^{-1} \left({t}\right)$ denote the preimage of $t$ under $\mathcal R$.

Let $\mathcal R^{-1} \left({ \left\{{t}\right\} }\right)$ denote the preimage of $\left\{{t}\right\}$ under $\mathcal R$.


Then:

$\mathcal R^{-1} \left({ \left\{{t}\right\} }\right) = \mathcal R^{-1} \left({t}\right)$


Proof

\(\displaystyle \mathcal R^{-1} \left({ t }\right)\) \(=\) \(\displaystyle \left\{ {s : \left({ s, t }\right) \in \mathcal R}\right\}\) $\quad$ by definition of preimage of element $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \left\{ {s : \exists y: \left({ y = t \land \left({ s, y }\right) \in \mathcal R }\right)}\right\}\) $\quad$ by Equality implies Substitution $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \left\{ {s : \exists y \in \left\{ t \right\}: \left({ s, y }\right) \in \mathcal R}\right\}\) $\quad$ by definition of singleton $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \mathcal R^{-1} \left({ \left\{ {t}\right\} }\right)\) $\quad$ by definition of preimage of subset $\quad$

$\blacksquare$


Sources