Equivalence Relation/Examples/Even Sum

From ProofWiki
Jump to navigation Jump to search

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