0
$\begingroup$

I am going through some practice questions and am having trouble to finding distinct equivalence classes and this is my understanding so far.

Let S be a nonempty subset of Z, and let R be a relation defined on $S$ by $xRy$ if $3 | (x + 2y)$.

Find the distinct equivalence classes for $S=\{−7, −6, −2, 0, 1, 4, 5, 7\}$

Now, I understand that for $3 | (x + 2y) \equiv$ $$x\equiv -2y(mod 3)$$

So that means, I would have to find combinations of elements from the set S such that $-2y$ must have a remainder $x$ when divided by 3? However for one of the solutions given, $$[5] = \{5,-7\}$$

If I am not mistaken, for $-2(5) = - 10; -2(-7) = 14$ and $$-10(mod3)=2$$ $$14(mod3)=2$$.

So, then $[2] = \{5,-7\}$ right? Or am I missing something that I don't understand. Also, from further observation, anything divided by 3 can only have remainder of 0,1 and 2. Then [5] = ... doesn't make sense. If anyone could clarify, that would be helpful! Thanks.

$\endgroup$
1
$\begingroup$

So that means, I would have to find combinations of elements from the set S such that $−2y$ must have a remainder $x$ when divided by $3$?

No; this means that $x$ and $-2y$ must have the same remainder when divided by $3$. For example, both $5$ and $-2(-7)$ have the remainder $2$ when divided by $3$, so $5$ and $-7$ are in the same class.

So, then $[2] = \{5,-7\}$ right?

$2$ doesn't belong to $S$, so technically the "class of $2$", which you denoted $[2]$, is meaningless in this context.

Then $[5]$ doesn't make sense

By definition, $[5]$ means "the equivalence class that contains $5$." Hopefully the above remarks make it clearer that this does makes sense.

$\endgroup$
  • $\begingroup$ $[5]={x∈S: xR5}={x∈S: x≡-10(mod3)} = {x ∈ S : 3 | (x +10)} = \{5,-7\}$ Is that correct? $\endgroup$ – misheekoh Dec 15 '15 at 20:03
  • 1
    $\begingroup$ @misheekoh You want to replace all your instances of $Z$ with $S$ since here $S$ is the set on which the equivalence relation is defined. So by definition $[5] = \{ x \in S : xR5 \} = \{ x \in S : 3 |(x+10) \} = \{5, -7 \}$. But you have the right idea. $\endgroup$ – Alex Provost Dec 15 '15 at 20:05
  • $\begingroup$ So the idea is that for [5], the remainder of the elements in that class will have a remainder of 2 then right? $\endgroup$ – misheekoh Dec 15 '15 at 20:12
  • $\begingroup$ @misheekoh Yes, because $x \equiv -10 \mod 3 \iff x \equiv 2 \mod 3$. $\endgroup$ – Alex Provost Dec 15 '15 at 21:10
1
$\begingroup$

It's easier if you convert $3 \mid x+2y$ to $x + 2y \equiv 0 \pmod 3$. We then "solve" for $y$ in terms of $x$. $y \equiv x \pmod 3$. In other words, $$xRy \iff x \equiv y \pmod 3$$

It helps to make a table of $s \pmod 3$ for all $s \in S$.

\begin{array}{|c|rrrrrrrr|} \hline s & −7 & −6 & −2 & 0 & 1 & 4 & 5 & 7 \\ s \pmod 3 & 2 & 0 & 1 & 0 & 1 & 1 & 2 & 1 \\ \hline \end{array}

The partition of $S$ is therefore $\big\{\{-6,0\}, \{-2,1,4,7 \}, \{-7,5\} \big\}$

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