Image of Singleton under Relation

From ProofWiki
Jump to: navigation, search

Theorem

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

Then the image of an element of $S$ is equal to the image of a singleton containing that element, the singleton being a subset of $S$:

$\forall s \in S: \mathcal R \left({s}\right) = \mathcal R \left[{\left\{{s}\right\}}\right]$


Proof

We have the definitions:

\(\displaystyle \mathcal R \left({s}\right)\) \(=\) \(\displaystyle \left\{ {t \in T: \left({s, t}\right) \in \mathcal R}\right\}\) $\quad$ Definition of Image of Element under Relation $\quad$
\(\displaystyle \mathcal R \left[{\left\{ {s}\right\} }\right]\) \(=\) \(\displaystyle \left\{ {t \in T: \exists s \in \left\{ {s}\right\}: \left({s, t}\right) \in \mathcal R}\right\}\) $\quad$ Definition of Image of Subset under Relation $\quad$


\(\displaystyle t\) \(\in\) \(\displaystyle \mathcal R \left({s}\right)\) $\quad$ $\quad$
\(\displaystyle \implies \ \ \) \(\displaystyle \left({s, t}\right)\) \(\in\) \(\displaystyle \mathcal R\) $\quad$ $\quad$
\(\displaystyle \implies \ \ \) \(\, \displaystyle \exists s \in \left\{ {s}\right\}: \, \) \(\displaystyle \left({s, t}\right)\) \(\in\) \(\displaystyle \mathcal R\) $\quad$ since $s \in \left\{ {s}\right\}$ by definition of Singleton $\quad$
\(\displaystyle \implies \ \ \) \(\displaystyle t\) \(\in\) \(\displaystyle \mathcal R \left[{\left\{ {s}\right\} }\right]\) $\quad$ $\quad$
\(\displaystyle \implies \ \ \) \(\displaystyle R \left({s}\right)\) \(\subseteq\) \(\displaystyle \mathcal R \left[{\left\{ {s}\right\} }\right]\) $\quad$ Definition of Subset $\quad$


\(\displaystyle t\) \(\in\) \(\displaystyle \mathcal R \left[{\left\{ {s}\right\} }\right]\) $\quad$ $\quad$
\(\displaystyle \implies \ \ \) \(\, \displaystyle \exists s \in \left\{ {s}\right\}: \, \) \(\displaystyle \left({s, t}\right)\) \(\in\) \(\displaystyle \mathcal R\) $\quad$ $\quad$
\(\displaystyle \implies \ \ \) \(\displaystyle \left({s, t}\right)\) \(\in\) \(\displaystyle \mathcal R\) $\quad$ since $r \in \left\{ {s}\right\} \implies r = s$ by Singleton Equality $\quad$
\(\displaystyle \implies \ \ \) \(\displaystyle t\) \(\in\) \(\displaystyle \mathcal R \left({s}\right)\) $\quad$ $\quad$
\(\displaystyle \implies \ \ \) \(\displaystyle \mathcal R \left[{\left\{ {s}\right\} }\right]\) \(\subseteq\) \(\displaystyle R \left({s}\right)\) $\quad$ $\quad$


Finally:

$\mathcal R \left({s}\right) = \mathcal R \left[{\left\{{s}\right\}}\right]$

by definition of set equality.

$\blacksquare$