# Number of classes an equivalence relation partitions a set X

I am struggling a bit with regards to sets and relations and would appreciate any help.

The question goes as follows:

Consider the relations R and S, defined on the set X = {1, 2, . . . , 99} as follows.

xRy ⇐⇒ x + y is a multiple of 11,
xSy ⇐⇒ x − y is a multiple of 11.

Determine which of those two is an equivalence relation , and find out into
how many classes does it partition the set X?


I know the definition of equivalence relation ,but it seems to me that both those relations are not reflexive. For R there can be (1,10) and for S there can be (99,88).

As for the second part, I have no idea whatsoever what classes and partitions mean as the given definition is quite vague.

• A relation $\sim$ is "reflexive" if $a\sim a$ for every $a$ in the set in question. Not sure how your examples show that either $R$ or $S$ is non-reflexive. – lulu May 10 '18 at 21:03
• R isn't reflexive, but you should use (1,1) as an example. S is mod 11, that's an equivalent relation. – GNUSupporter 8964民主女神 地下教會 May 10 '18 at 21:04
• @lulu so the set {(a,a),(a,b),(b,a),(b,b)} is reflexive? The way I understand it is that it's only reflexive if it is in this form {(a,a),(b,b),(c,c)} – Mohamad Moustafa May 10 '18 at 21:11
• Yes, your example is reflexive (assuming you only have the two elements). It is certainly not true that the only reflexive relations are the ones you mention. – lulu May 10 '18 at 21:12
• You can read about Equivalence Relations here. – lulu May 10 '18 at 21:13

## 2 Answers

For equivalence relation, we need to check three criteria: Reflexivity, symmetry, and transitivity.

For reflexivity, you are verifying that $xRx$ and $xSx$ for all $x \in X$. As GNU Supporter suggested, $1R1$ will fail because $1+1=2$ is not a multiple of 11. We do not need to check symmetry or transitivity for $R$ because if it is not reflexive, it is not an equivalence relation.

To see that $xSx$ is true, $x-x=0=0\cdot 11$ is clearly a multiple of 11 for any $x$.

For symmetry, you need $xSy$ implies $ySx$. Hint, if $xSy$, then there exists an integer $k$ such that $x-y = 11k$. If $k$ is an integer, then $-k$ is as well. Use that to show that $S$ is symmetric.

For transitivity, assume $xSy$ and $ySz$ for some $x,y,z \in X$. This means there exists integers $k,m$ such that $x-y = 11k$ and $y-z = 11m$. Add the two equations and on the LHS, you get $x-z$. What do you get on the RHS? Can you show this implies transitivity?

Przemyslaw already explained what the equivalence classes are. A partition of the set means that every element will belong to some equivalence class, and no element will be in multiple classes. The notation for the equivalence class of a certain number is adding brackets around it. So $$ is the equivalence class of $1$. You can write it as $[n] = \{x \in X|nSx\}$. Since the equivalence relation partitions the set, the fact that $1S2$ is false (since $1-2=-1$ is not divisible by 11), then $ \cap  = \emptyset$. This is how you can partition the set.

HINT: Is $x+x$ divisible by 11 for integer $x$? And what about $x-x$? (The division in your question is in integers, not naturals).

The classes are $\{1,1+11,1+22,1+33,\ldots,1+88\}$, $\{2,2+11,2+22,\ldots,2+88\}$, $\ldots$

Can you finish this?

• Regarding the second part, I need an explanation not an answer as the notes we have dont mention classes and talk about partitions in a really vague way. I dont know what "how many classes does it partition the set X" means. – Mohamad Moustafa May 10 '18 at 21:09
• Will this go on till {11,11+11,11+22,..} Thus having a total of 11 classes? And I still dont understand how did you reach the conclusion to divide them into those classes.What is the rule?I looked over the wikipedia article but that wasnt too helpful. – Mohamad Moustafa May 10 '18 at 21:30
• @MohamadMoustafa In one class there all numbers which difference is divisible by 11. Sometimes we write $$, $$, and so on, to show a generator of the class.. I took 1, all elements generated by 1, then 2, all elements generated by 2, until there was anything to take, i.e. until 11. So there are 11 of them, indeed. – Przemysław Scherwentke May 10 '18 at 21:34
• oh so since the multiples of 11 are 0,11,22,.. the class are {1+0,1+11,1+22,...},{2+0,2+11,2+22,...},... Now it makes sense.Thx alot – Mohamad Moustafa May 10 '18 at 21:38