# Relation Induced by Mapping 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 \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$