0
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ What is the class of $0$? And of $1$? How many classes are there? $\endgroup$ – lhf May 29 '14 at 2:31
  • 1
    $\begingroup$ 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? $\endgroup$ – baba May 29 '14 at 2:33
  • $\begingroup$ 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? $\endgroup$ – André Nicolas May 29 '14 at 2:35
  • $\begingroup$ Hint: the only way a sum (or subtraction) renders an even number is when both are even or both are odd. $\endgroup$ – Miguelgondu May 29 '14 at 2:37
  • $\begingroup$ infinite families $\endgroup$ – baba May 29 '14 at 2:38
4
$\begingroup$

The equivalent classes are: $[0]$, and $[1]$.

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

$[1] = \{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:

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

$\endgroup$
  • $\begingroup$ It could also be $[42], [1]$ (Douglas Adams reference). $\endgroup$ – Miguelgondu May 29 '14 at 2:44
  • $\begingroup$ or [12] and [3]. I got it now, thank you guys so much! $\endgroup$ – baba May 29 '14 at 2:46
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.