How many equivalence classes are there

380 Views Asked by At

$E={1,2,3,4,5,6,7,8}$ Defines the product set E × E the relation R: $(p, q) R (p_0, q_0) $if $ p-p_0$ even and $q-q_0 $divisible by 3

Question :How many equivalence classes are there

My attempt :

$p-p_0$is even $\Rightarrow$$p-p_0=2k$$\Rightarrow$$p=p_0[2]$ So for that exist two equivalent classes 0 and 1

$q-q_0$is divisible by 3 $\Rightarrow$$q-q_0=3k$$\Rightarrow$$q=q_0[3]$ So for that exist three equivalent classes 0 and 1 and 2

So finally :

exist 6 equivalent classes :(1, 0),(1,1),(1,2),(0,0)(0,1)(0,2)$

Is that correct?

1

There are 1 best solutions below

5
On

As JMoravitz commented, $0$ is not an element of your set.
So you seem to change notation between the question and your tentative of answering it.
To keep it tidy, I'll reformulate the question.

We have a set $E = \{ 1, 2, 3, 4, 5, 6, 7, 8\}$ and a binary relation $R$ defined on $E\times E$ by $$(p,q) R (r,s) \quad\text{ iff }\quad 2|p-r \;\text{ and }\; 3|q-s.$$ Apparently, you already concluded that $R$ is an equivalence relation on $E\times E$, and just want to know what are the equivalence classes.
These are the following $6$: $$(1,1)/R, (1,2)/R, (1,3)/R, (2,1)/R, (2,2)/R, (2,3)/R.$$ (Here, I'm using the notation in which, for an equivalence relation $\sim$ on a set $X$, we denote by $x/{\sim}$ the equivalence class of $x \in X$; another common notation would be $[x]_{\sim}$, but I'll use the previous one.)

To show that those are exactly the equivalence classes, let us start by describe the class of the element $(1,1)$, that is, to list the elements which are $R$-related with $(1,1)$.
Given the definition, these are the elements whose first coordinate is odd (so that the difference with $1$ is even) and the second coordinate is $1$, $4$ or $7$ (so that subtracting $1$ we get a multiple of $3$).
Hence $$(1,1)/R = \{ (1,1), (1,4), (1,7), (3,1), (3,4), (3,7), (5,1), (5,4), (5,7), (7,1), (7,4), (7,7) \}.$$ Analogously you can conclude that \begin{align} (1,2)/R &= \{ (1,2), (1,5), (1,8), (3,2), (3,5), (3,8), (5,2), (5,5), (5,8), (7,2), (7,5), (7,8) \},\\ (1,3)/R &= \{ (1,3), (1,6), (3,3), (3,6), (5,3), (5,6), (7,3), (7,6) \},\\ (2,1)/R &= \{ (2,1), (2,4), (2,7), (4,1), (4,4), (4,7), (6,1), (6,4), (6,7), (8,1), (8,4), (8,7) \},\\ (2,2)/R &= \{ (2,2), (2,5), (2,8), (4,2), (4,5), (4,8), (6,2), (6,5), (6,8), (8,2), (8,5), (8,8) \},\\ (2,3)/R &= \{ (2,3), (2,6), (4,3), (4,6), (6,3), (6,6), (8,3), (8,6) \}. \end{align} Now, just to confirm, you can count that there are $64$ elements listed in those classes (without repetitions), and since that is the same number of elements in $E \times E$, we know that we didn't forget any one.

(These means that you are right, if we increment by one each coordinate of each pair in your list of equivalence classes. Notice, however, that even so, there would be a problem in your answer: for example $(1,1)$ is not an equivalence class; what is correct is that $(1,1)/R$ is an equivalence class.)