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\}\) Definition of Image of Element under Relation
\(\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\}\) Definition of Image of Subset under Relation


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


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


Finally:

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

by definition of set equality.

$\blacksquare$