# Equivalence Relation/Examples/Even Sum

## Contents

## Example of Equivalence Relation

Let $\Z$ denote the set of integers.

Let $\mathcal R$ denote the relation on $\Z$ defined as:

- $\forall x, y \in \Z: x \mathrel {\mathcal R} y \iff x + y \text { is even}$

Then $\mathcal R$ is an equivalence relation.

The equivalence classes are:

- $\eqclass 0 {\mathcal R}$
- $\eqclass 1 {\mathcal R}$

## Proof

Checking in turn each of the criteria for equivalence:

### Reflexivity

Let $x \in \Z$.

Then:

- $x + x = 2 x$

and so $x + x$ is an even integer.

Thus:

- $\forall x \in \Z: x \mathrel {\mathcal R} x$

and $\mathcal R$ is seen to be reflexive.

$\Box$

### Symmetry

\(\displaystyle x\) | \(\mathcal R\) | \(\displaystyle y\) | |||||||||||

\(\displaystyle \leadsto \ \ \) | \(\displaystyle x + y\) | \(=\) | \(\displaystyle 2 n\) | for some $n \in \Z$ | |||||||||

\(\displaystyle \leadsto \ \ \) | \(\displaystyle y + x\) | \(=\) | \(\displaystyle 2 n\) | for some $n \in \Z$ | |||||||||

\(\displaystyle \leadsto \ \ \) | \(\displaystyle x\) | \(\mathcal R\) | \(\displaystyle y\) |

Thus $\mathcal R$ is seen to be symmetric.

$\Box$

### Transitivity

\(\displaystyle x\) | \(\mathcal R\) | \(\displaystyle y\) | |||||||||||

\(\displaystyle y\) | \(\mathcal R\) | \(\displaystyle z\) | |||||||||||

\(\displaystyle \leadsto \ \ \) | \(\displaystyle x + y\) | \(=\) | \(\displaystyle 2 n\) | for some $n \in \Z$ | |||||||||

\(\displaystyle y + z\) | \(=\) | \(\displaystyle 2 m\) | for some $m \in \Z$ | ||||||||||

\(\displaystyle \leadsto \ \ \) | \(\displaystyle \paren {x + y} + \paren {y + z}\) | \(=\) | \(\displaystyle 2 n + 2 m\) | for some $m, n \in \Z$ | |||||||||

\(\displaystyle \leadsto \ \ \) | \(\displaystyle \paren {x + 2 y + z} - 2 y\) | \(=\) | \(\displaystyle 2 n + 2 m - 2 y\) | for some $m, n \in \Z$ | |||||||||

\(\displaystyle \leadsto \ \ \) | \(\displaystyle \paren {x + z}\) | \(=\) | \(\displaystyle 2 \paren {n + m - y}\) | for some $m, n \in \Z$ | |||||||||

\(\displaystyle \leadsto \ \ \) | \(\displaystyle x\) | \(\mathcal R\) | \(\displaystyle z\) |

Thus $\mathcal R$ is seen to be transitive.

$\Box$

$\mathcal R$ has been shown to be reflexive, symmetric and transitive.

Hence by definition it is an equivalence relation.

$\Box$

We have that:

- $x \mathrel {\mathcal R} 0 \iff x \text { is even}$
- $x \mathrel {\mathcal R} 1 \iff x \text { is odd}$

and the equivalence classes of $\mathcal R$ are $\eqclass 0 {\mathcal R}$ and $\eqclass 1 {\mathcal R}$ from the Fundamental Theorem on Equivalence Relations.

$\blacksquare$

## Sources

- 1977: Gary Chartrand:
*Introductory Graph Theory*... (previous) ... (next): Appendix $\text{A}.3$: Equivalence Relations: Problem Set $\text{A}.3$: $19$ - 1996: John F. Humphreys:
*A Course in Group Theory*... (previous) ... (next): Chapter $2$: Maps and relations on sets: Exercise $4$