2
$\begingroup$

Let $S \subseteq \mathbb{Z}$, and define a relation $R$ on $S \times S$ by

$$(m, n)R(s, t) \quad \text{ if and only if } \quad m + n = s + t$$

Consider the set $S = \{1, 2, 3, 4, 5, 6\}$. How many equivalence classes does $R$ have? Describe the equivalence classes of $R$ without explicitly listing the partition of $S × S$.

My try: I have proved that the relation is an equivalence relation, $R$ is reflexive, symmetric, and transitive. For the set $S$ there are $2^6$ subsets. Any help starting this problem would be appreciated!

$\endgroup$
  • 1
    $\begingroup$ Anyone who’s played a game with dice (e.g. Monopoly) for some time, knows that every roll from $2$ to $12$ can be made with a pair of dice... $\endgroup$ – Erick Wong Jul 25 at 18:15
3
$\begingroup$

Two elements $(a,b)$ and $(c,d)$ in $S \times S$ are related if $a+b=c+d$. For example, if we take the element $(1,5) \in S \times S$, then $(1,5) \sim (1,5)$ because $1+5=1+5=6$.

So for finding the equivalence class of $(1,5)$ we ask ourselves: what are all other elements $(c,d) \in S \times S$ such that $(1,5) \sim (c,d)$?

For that, we want $c+d=6$. So look for all the pairs that satisfy this condition. $$[(1,5)]=\{(1,5), (5,1), (3,3), (2,4), (4,2)\}.$$ Likewise $$[(1,1)]=\{(1,1)\} \qquad \text{and} \qquad [(5,6)]=\{(5,6), (6,5)\}.$$

Hopefully you can proceed from here to get the remaining equivalence classes.

Note: If you just want the number of equivalence classes (without describing them), then note that each equivalence class can be associated with the sum of the pairs in that, e.g. the class $[(1,5)]$ can be associated to the sum $6$ and class $[(1,1)]$ can be associated with the sum $2$ and so on. So the number of distinct classes is the number of distinct sums.

$\endgroup$
  • $\begingroup$ So for example [(1,5)] and [(5,1)] will have the same elements, so overall I have the sum of 2,3,4,...,11 , hence 10 equivalence classes ? $\endgroup$ – HHH Jul 25 at 18:18
  • 1
    $\begingroup$ @HHH You remembered to include $(1,1)$ but you forgot about $(6,6)$. $\endgroup$ – Erick Wong Jul 25 at 18:31
2
$\begingroup$

Hint:

In general if $f:X\to Y$ is some function then the relation $\sim$ on $X$ defined by $a\sim b\iff f(a)=f(b)$ is an equivalence relation.

The equivalence class represented by $x\in X$ is the set $\{a\in X\mid f(a)=f(x)\}$ and there is a one-to-one relation between equivalence classes and elements of the image of $f$.

So the number of equivalence classes equals the cardinality of the image of $f$.


You can apply that here.

Note that $(m,n)R(s,t)\iff f(m,n)=f(s,t)$ where function $f:S\times S\to\mathbb Z$ is prescribed by $(m,n)\to m+n$.

You only have to find the cardinality of the set $\{m+n\mid m,n\in S\}$.

$\endgroup$
0
$\begingroup$

Let's describe the equivalence classes.
Every class has a feature that every pair in this class has the same sum. The minimum sum is 2 (from (1,1)), ant the max is 12 (from (6,6)).
It's easy to see, the we will also have all the numbers in a range [2,12].
That means, that you have 11 classes.

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