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.

  • $\begingroup$ 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. $\endgroup$ – lulu May 10 '18 at 21:03
  • 1
    $\begingroup$ R isn't reflexive, but you should use (1,1) as an example. S is mod 11, that's an equivalent relation. $\endgroup$ – GNUSupporter 8964民主女神 地下教會 May 10 '18 at 21:04
  • $\begingroup$ @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)} $\endgroup$ – Mohamad Moustafa May 10 '18 at 21:11
  • $\begingroup$ 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. $\endgroup$ – lulu May 10 '18 at 21:12
  • $\begingroup$ You can read about Equivalence Relations here. $\endgroup$ – lulu May 10 '18 at 21:13

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 $[1]$ 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 $[1] \cap [2] = \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?

  • $\begingroup$ 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. $\endgroup$ – Mohamad Moustafa May 10 '18 at 21:09
  • $\begingroup$ 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. $\endgroup$ – Mohamad Moustafa May 10 '18 at 21:30
  • $\begingroup$ @MohamadMoustafa In one class there all numbers which difference is divisible by 11. Sometimes we write $[1]$, $[2]$, 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. $\endgroup$ – Przemysław Scherwentke May 10 '18 at 21:34
  • $\begingroup$ 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 $\endgroup$ – Mohamad Moustafa May 10 '18 at 21:38

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.