Relation Induced by Mapping is Equivalence Relation

From ProofWiki
Jump to navigation Jump to 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 \map f {s_1} = \map f {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: \map f x = \map f x \implies x \mathrel {\mathcal R_f} x$

$\Box$


Symmetric

$\mathcal R_f$ is symmetric:

\(\displaystyle x\) \(\mathcal R_f\) \(\displaystyle y\) by definition
\(\displaystyle \leadsto \ \ \) \(\displaystyle \map f x\) \(=\) \(\displaystyle \map f y\) Definition of $f$
\(\displaystyle \leadsto \ \ \) \(\displaystyle \map f x\) \(=\) \(\displaystyle \map f y\) Equals is Equivalence Relation, and so Symmetric
\(\displaystyle \leadsto \ \ \) \(\displaystyle y\) \(\mathcal R_f\) \(\displaystyle x\) Definition of $f$

$\Box$


Transitive

$\mathcal R_f$ is transitive:

\(\displaystyle x\) \(\mathcal R_f\) \(\displaystyle y\)
\(\, \displaystyle \land \, \) \(\displaystyle y\) \(\mathcal R_f\) \(\displaystyle z\)
\(\displaystyle \leadsto \ \ \) \(\displaystyle \map f x\) \(=\) \(\displaystyle \map f y\) Definition of $f$
\(\, \displaystyle \land \, \) \(\displaystyle \map f y\) \(=\) \(\displaystyle \map f z\) Definition of $f$
\(\displaystyle \leadsto \ \ \) \(\displaystyle \map f x\) \(=\) \(\displaystyle \map f z\) Equals is Equivalence Relation, and so Transitive
\(\displaystyle \leadsto \ \ \) \(\displaystyle x\) \(\mathcal R_f\) \(\displaystyle z\) Definition of $f$

$\Box$


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

$\blacksquare$


Sources