Induced Equivalence is Equivalence Relation

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$