0

In the set $\mathbb{Z}$ we describe the relation:

$a\mathrel{R}b \Leftrightarrow a\equiv b\pmod2 \text{ and } a\equiv b\pmod3$

Prove that $R$ is an equivalence relation. Describe $\overline{0}$ and how many different classes of equivalence relations exist?

I know that to prove that R is an equivalence relation we need to show that R has Reflexivity, symmetry and transitivity, but we have not done any examples in class and I am not very aware of how to prove it .

Just guidelines to help me understand are enough, no full solutions plese!

My solution on symmetry, tell me if it's correct:

$a\equiv bmodn$ : $\exists n \epsilon \mathbb{Z} : n \mid (a-b)$

$a\mathrel{R}b$ : $a\equiv bmod2$ and $a\equiv bmod3$

$b\mathrel{R}a$ : $b\equiv amod2$ and $b\equiv amod3$

$\exists 3 \epsilon Z : 3 \mid (a-b)$

$\exists 2 \epsilon Z : 2 \mid (a-b)$

$\exists 3 \epsilon Z : 3 \mid (b-a)$

$\exists 2 \epsilon Z : 2 \mid (b-a)$

let $a-b = k$

$b-a = -k$

$\exists (-1) (-1)(a-b) = (b-a)$

Community
  • 1
Rrjrjtlokrthjji
  • 506
  • 3
  • 19
  • 2
    I'm not sure what you mean when you use $\exists$. For symmetry you just need to prove that $a\equiv b\mod n$ is equivalent to $b\equiv a\mod n$. I think you got the idea right that $n|a-b$ if and only if $n|b-a$ but your notation is quite hard to decypher. – MichalisN Nov 05 '13 at 10:30

3 Answers3

2

Hint:

To prove that ${\bf R}$ is an equivalence relation, you must prove:

  • Reflexivity: for all $a$, we have $a{\bf R}a$
  • Symmetry: if $a{\bf R}b$, then $b{\bf R}a$
  • Transitivity: if $a{\bf R}b$ and $b{\bf R}c$, then $a{\bf R}c$

Work:

Given that you have not had any examples in class, I will do the case for reflexivity and leave you the others as exercise. Note that we will need a definition of the modulo operation: we write that $a \equiv b$ (mod n) iff $\exists n \in \mathbb{Z}$ s.t. $n|(a-b)$: $a$ is equivalent to $b$ mod $n$ if and only if $n$ divides their difference.

Reflexivity:
Take any $a \in \mathbb{Z}$. Then $a \equiv a$ (mod 2) and $a \equiv a$ (mod 3), because $(a-a)=0$ and $2|0$ and $3|0$. To prove that two and three both divide zero, we note that there exists $0$, an integer such that $n \cdot 0 = 0$.

Newb
  • 17,672
  • 13
  • 67
  • 114
1

You can also see this as follows: $x \equiv y \pmod{2}$ and $x \equiv y \pmod{3} $ if and only if $x \equiv y \pmod{6}$.

Jef
  • 3,821
1

The equivalence relation is the intersection of the equivalence relations $a\tilde{}b$ iff $a\equiv b \mod 2$ and $a\tilde{} b$ iff $a\equiv b \mod 3$. The intersection of two equivalence relations is again an equivalence relation. See this question

Community
  • 1
MichalisN
  • 5,402