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\}\) by definition of preimage of element
\(\displaystyle \) \(=\) \(\displaystyle \left\{ {s : \exists y: \left({ y = t \land \left({ s, y }\right) \in \mathcal R }\right)}\right\}\) by Equality implies Substitution
\(\displaystyle \) \(=\) \(\displaystyle \left\{ {s : \exists y \in \left\{ t \right\}: \left({ s, y }\right) \in \mathcal R}\right\}\) by definition of singleton
\(\displaystyle \) \(=\) \(\displaystyle \mathcal R^{-1} \left({ \left\{ {t}\right\} }\right)\) by definition of preimage of subset

$\blacksquare$


Sources