# Equivalence classes with this relation equivalence

Given this relation: $R=\{(a,b) \in \mathbb{Z}\times\mathbb{Z} \quad aRb \iff \exists h\in \mathbb{Z}: \quad b+3a=4h\}$ proves:

1) $R$ is an equivalence relation. Proved.

2) show the partition set $\mathcal{Z}_R$ inducted by $R$.

For the second question, I have already a solution (not from me) but I'm not sure that is correct: $$\mathcal{Z}_R = \mathbb{Z}^2/R =\{[0]_R,[1]_R\}$$ where:

$$[0]_R=\{b \in \mathcal{Z}; \quad 0Rb\}= \{b \in \mathcal{Z}; \quad \exists h \in \mathcal{Z}: b=4h \}$$

and

$$[1]_R=\{b \in \mathcal{Z}; \quad 1Rb\}= \{b \in \mathcal{Z}; \quad \exists h \in \mathcal{Z}: b+3=4h \}$$

Essentially I don't understand why only these 2 classes are in $\mathcal{Z}_R$. Why is this correct(if it is)? If not can someone explain me how can find the equivalence classes of the partition set. thanks in advance

• What does $Z_R$ signify? – Siddharth Bhat Aug 30 '16 at 9:42
• Actually there are 4 classes. Are you familiar with modular arithmetic (integers $\mod{4}$)? – Crostul Aug 30 '16 at 9:53
• @SiddharthBhat the set of equivalence classes of $R$ . – Alfonse Aug 30 '16 at 10:00
• @Crostul yes I know basic stuff. – Alfonse Aug 30 '16 at 10:01
• Well, this equivalence is the same as $$aRb \Longleftrightarrow a \equiv b \pmod{4}$$ and so it is the usual equivalence of the integers $\mod{4}$, with the usual 4 equivalence classes and the quotient is nothing but $\Bbb{Z}/4\Bbb{Z}$. – Crostul Aug 30 '16 at 10:02

$$a+3a=4h\iff a+3b\equiv0\pmod4\iff a\equiv-3b\equiv b\pmod4$$

Hence $$aRb\iff a\equiv b\pmod4$$ Thus there are four equivalence classes.(there are not two!)

Hint: distinguish among even and odd values for $a$. Can you prove that:

1) If $a = 2m+1, m \in \mathbb{Z}$ then $a \in [1]_R$?

2) If $a = 2m, m \in \mathbb{Z}$ then $a \in [0]_R$?

• There are 4 equivalence classes. – Crostul Aug 30 '16 at 9:54
• Of course. If you prove that the above facts to be false, you obtain "only" the falsity of the answers provided by OP's source. I'all add up to the answer! Thanks. :-) – Filippo De Bortoli Aug 30 '16 at 10:02

It is obvious that $0$ and $1$ are not equivalent since $1$ is not a multiple of $4$, therefore the equivalence classes determined by them ($[0]$ and $[1]$) are disjoint. Now we consider four cases:

1. If $k$ is a multiple of $4$, then $k+3\times0$ is a multiple of $4$, so $k$ is related to $0$.

2. If $k=4n+1$ for some integer $n$, then $k+3\times1$ is a multiple of $4$, so $k$ is related to $1$.

3. If $k=4n+2$ for some integer $n$, then $k+3\times0$ and $k+3\times1$ are not multiples of $4$. This shows that there are more than two equivalence classes. In this case, $k$ is related to $2$ (check this), so the third equivalence class will be $[2]$.

4. If $k=4n+3$ for some integer $n$, then $k+3\times0$, $k+3\times1$, and $k+3\times2$ are not multiples of $4$, which means that $k$ is in none of the equivalence classes we have found, therefore, there is another equivalence class, which is $[3]$ (check that $k$ is related to $3$).

In conclusion, there are four equivalence classes: $[0]$, $[1]$, $[2]$, and $[3]$.