# Equivalence Relation/Examples/Even Sum

## 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$