# Find the equivalence classes

Prove or disprove: There is an equivalence relation $\sim$ on $\mathbb{Z}$ defined by $x \sim y$ if $x − y$ is even. What are the equivalence classes?

I have proven that there is an equivalence relation by proving symmetry, transitivity, and reflexivity. How do I go about partitioning $\mathbb{Z}$ into the equivalence classes?

• What is the class of $0$? And of $1$? How many classes are there? – lhf May 29 '14 at 2:31
• I understand that it can be broken up into the classes of 0, all positive integers, and all negative integers, but is there a general methodology for partitioning the set? – baba May 29 '14 at 2:33
• We will say that the numbers $a$ ans $b$ belong to the same family if $a-b$ is even, that is, $0$, or $2$, or $-2$, or $4$, or $-4$, and so on. How many families are there? – André Nicolas May 29 '14 at 2:35
• Hint: the only way a sum (or subtraction) renders an even number is when both are even or both are odd. – Miguelgondu May 29 '14 at 2:37
• infinite families – baba May 29 '14 at 2:38

The equivalent classes are: $$, and $$.

$ = \{x: x \in \mathbb{Z}, \text{and is even}\}$

$ = \{x: x \in \mathbb{Z}, \text{and is odd}\}$.

And if you define your relation: $x \sim y \iff x \equiv y \pmod n$, then you have $n$ equivalent classes:

$, , ..., [n-1]$

• It could also be $, $ (Douglas Adams reference). – Miguelgondu May 29 '14 at 2:44
• or  and . I got it now, thank you guys so much! – baba May 29 '14 at 2:46

If $x$ is even and $x\sim y$, then $y$ is even. Conversely if $x$ and $y$ are even, $x\sim y$. So a class is the set of even numbers.
Same reasoning for odd numbers.