How many equivalence classes does the following equivalence relation have?

Question

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!

Answer 1

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.

Answer 2

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

Answer 3

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.