Getting the elements of an equivalence class, and total number of equivalence classes

40 Views Asked by At

$$\text{Let } A = \{1,2,3,4,...,271\}. \text{Define the relation $R$ on $A \times A$ by:}$$

$$ \text{for any $(a,b)$, $(c,d) \in A \times A$, $(a,b)R(c,d)$ iff $a + b = c+ d$.}$$

$\text{(a) List all the elements of $[(3,3)]$, the equivalence class of $(3,3)$.}$

$\text{(b) How many equivalence classes does $R$ have? Explain.}$

For part (a) I'm not sure how to get the elements of $[(3,3)]$ when there are two elements in the set. It wouldn't just be every set where 3 is the first element, right? i.e. $(3,1),(3,2),(3,3),...,(3,271)$

For part (b), $|A \times A| = 271 \times 271 = 73441$. So would the number of equivalence classes be $73441 + 1 = 73442$, considering the empty set?

1

There are 1 best solutions below

8
On BEST ANSWER

For (a), the equivalence class of $(3,3)$ is the set of pairs $(a,b)$ such that $(3,3) \mathbin{R} (a,b)$, namely $$\{ (a,b) \in A \times A : 3+3 = a+b \}$$ This is certainly not the set $\{ (3,1),(3,2),\dots,(3,271) \}$.

For (b), you need to consider what values $a+b$ can take for $(a,b) \in A \times A$. Each equivalence class of $R$ corresponds with a unique value of $a+b$, so the number of possible values that $a+b$ can take is equal to the number of equivalence classes of $R$.