Induced Equivalence is Equivalence Relation

From ProofWiki
Jump to: navigation, search

Theorem

Let $f: S \to T$ be a mapping.

Let $\mathcal R_f \subseteq S \times S$ be the relation induced by $f$:

$\tuple {s_1, s_2} \in \mathcal R_f \iff f \paren {s_1} = f \paren {s_2}$


Then $\mathcal R_f$ is an equivalence relation.


Proof

We need to show that $\mathcal R_f$ is an equivalence relation.


Checking in turn each of the criteria for equivalence:


Reflexive

$\mathcal R_f$ is reflexive:

$\forall x \in S: f \paren x = f \paren x \implies x \mathrel {\mathcal R_f} x$

$\Box$


Symmetric

$\mathcal R_f$ is symmetric:

\(\displaystyle x \mathrel {\mathcal R_f} y\) \(\implies\) \(\displaystyle f \paren x = f \paren y\) $\quad$ by definition $\quad$
\(\displaystyle \) \(\implies\) \(\displaystyle f \paren y = f \paren x\) $\quad$ Symmetry of Equals $\quad$
\(\displaystyle \) \(\implies\) \(\displaystyle y \mathrel {\mathcal R_f} x\) $\quad$ by definition $\quad$

$\Box$


Transitive

$\mathcal R_f$ is transitive:

\(\displaystyle x \mathrel {\mathcal R_f} y \land y \mathrel {\mathcal R_f} z\) \(\implies\) \(\displaystyle f \paren x = f \paren y \land f \paren y = f \paren z\) $\quad$ by definition $\quad$
\(\displaystyle \) \(\implies\) \(\displaystyle f \paren x = f \paren z\) $\quad$ Transitivity of Equals $\quad$
\(\displaystyle \) \(\implies\) \(\displaystyle x \mathrel {\mathcal R_f} z\) $\quad$ by definition $\quad$

$\Box$


Thus $\mathcal R_f$ is reflexive, symmetric and transitive, and is therefore an equivalence relation.

$\blacksquare$


Sources