# Relation Induced by Mapping is Equivalence Relation

Jump to navigation
Jump to search

## Theorem

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

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

- $\tuple {s_1, s_2} \in \RR_f \iff \map f {s_1} = \map f {s_2}$

Then $\RR_f$ is an equivalence relation.

## Proof

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

Checking in turn each of the criteria for equivalence:

### Reflexive

$\RR_f$ is reflexive:

- $\forall x \in S: \map f x = \map f x \implies x \mathrel {\RR_f} x$

$\Box$

### Symmetric

$\RR_f$ is symmetric:

\(\displaystyle x\) | \(\RR_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\) | \(\RR_f\) | \(\displaystyle x\) | Definition of $f$ |

$\Box$

### Transitive

$\RR_f$ is transitive:

\(\displaystyle x\) | \(\RR_f\) | \(\displaystyle y\) | |||||||||||

\(\, \displaystyle \land \, \) | \(\displaystyle y\) | \(\RR_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\) | \(\RR_f\) | \(\displaystyle z\) | Definition of $f$ |

$\Box$

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

$\blacksquare$

## Sources

- 1967: George McCarty:
*Topology: An Introduction with Application to Topological Groups*... (previous) ... (next): Chapter $\text{I}$: Sets and Functions: Factoring Functions: Theorem $10$ - 1975: T.S. Blyth:
*Set Theory and Abstract Algebra*... (previous) ... (next): $\S 6$. Indexed families; partitions; equivalence relations: Example $6.6$ - 1975: Bert Mendelson:
*Introduction to Topology*(3rd ed.) ... (previous) ... (next): Chapter $1$: Theory of Sets: $\S 7$: Relations: Exercise $2$ - 1978: Thomas A. Whitelaw:
*An Introduction to Abstract Algebra*... (previous) ... (next): Chapter $4$: Mappings: Exercise $10$ - 1982: P.M. Cohn:
*Algebra Volume 1*(2nd ed.) ... (previous) ... (next): Chapter $1$: Sets and mappings: $\S 1.4$: Equivalence relations - 2000: James R. Munkres:
*Topology*(2nd ed.) ... (previous) ... (next): $1$: Set Theory and Logic: $\S 3$: Relations: Exercise $3.4 \ \text{(a)}$