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 \}$$


$$[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

  • $\begingroup$ What does $Z_R$ signify? $\endgroup$ – Siddharth Bhat Aug 30 '16 at 9:42
  • $\begingroup$ Actually there are 4 classes. Are you familiar with modular arithmetic (integers $\mod{4}$)? $\endgroup$ – Crostul Aug 30 '16 at 9:53
  • $\begingroup$ @SiddharthBhat the set of equivalence classes of $R$ . $\endgroup$ – Alfonse Aug 30 '16 at 10:00
  • $\begingroup$ @Crostul yes I know basic stuff. $\endgroup$ – Alfonse Aug 30 '16 at 10:01
  • $\begingroup$ 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}$. $\endgroup$ – 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$?

  • $\begingroup$ There are 4 equivalence classes. $\endgroup$ – Crostul Aug 30 '16 at 9:54
  • $\begingroup$ 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. :-) $\endgroup$ – user124708 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]$.


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.