2
$\begingroup$

Looking for help on B) How many classes does the equivalence relation partition set X

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

$xRy \iff x + y$ is a multiple of $11$,

$xSy \iff x − y$ is a multiple of $11$.

A) One of $R$ and $S$ is an equivalence relation, the other is not. Determine which is which and justify your answers.

B) Into how many classes does the equivalence relation partition set $X$?

So far I've determined that S is the equivalence relation as R isn't reflexive or transitive. My only attempt at B is that there is 11-1=10 non-zero congruence classes, so does each one correspond to a non-zero equivalence class?

Any help is appreciated!

$\endgroup$
  • 4
    $\begingroup$ Where does this "non-zero" stuff come from? $\endgroup$ – ancientmathematician Apr 14 '18 at 16:53
  • 4
    $\begingroup$ What is a "non-zero" equivalence class? $\endgroup$ – Morgan Rodgers Apr 14 '18 at 16:54
  • 1
    $\begingroup$ @CyclotomicField: Sorry, but "a zero equivalence class" is a bit of a nonsense on a set that doesn't even contain zero, such that the given set $X$. $\endgroup$ – zipirovich Apr 14 '18 at 18:29
  • 1
    $\begingroup$ @CyclotomicField It's unambiguous, but it's also meaningless in the normal context of equivalence relations. And is a term that doesn't actually show up in the problem $\endgroup$ – Morgan Rodgers Apr 15 '18 at 17:11
  • 1
    $\begingroup$ What's wrong with a "zero equivalence class? Doe $11 -11=0$ make $11$ any less equivalent? Where did you get this weird idea that you aren't supposed to count the the equivalence class to zero? $\endgroup$ – fleablood Apr 15 '18 at 17:20
1
$\begingroup$

Just count them.

$1 R 12 R 23 R 34 R .... R 90$

$2 R 13 R 24 R 35 R .... R 91$

....

$10 R 21 R 32 R 43 R..... R 98$

$11 R 22 R 33 R 44 R ..... R 99$

That's 11.

It doesn't make any sense to subtract the "zero" equivalence class for 2 reasons.

1) The "zero" equivalence class is STILL an equivalence class so why they heck would you omit it? NOWHERE in the question does it say ANYTHING about how many non-zero equivalence classes; it ask how many equivalence classes. And $\{11,22,33,44,55,66,77,88,99\}$ is certainly an equivalence class, isn't it?

2) Since no method of "addition" has been defined or discussed, there is no meaning to defining any one of the equivalence classes as be a "zero" equivalence class. IF we were to define $\{x|x R c\} + \{x|x R d\} = \{x| x R (d+c\pm 11k \text{ for some integer } k)\}$ and define $[0]$ as the equivelence clas so that $[0] + \{x|x R c\} = \{x|x R c\}$ then, yes, $\{11,22,33,44,55,66,77,88,99\} = [0]$. But again, so what, it's still an equivalence class, isn't it?

$\endgroup$
0
$\begingroup$

To show $S$ is an equivalence relation you can either verify directly that it is reflexive, transitive, and symmetric or demonstrate that the relation partitions the set and use the fundamental theorem of equivalence relations. If you can demonstrate the existence of the congruence classes you have such a partition and that's sufficient to demonstrate that you have an equivalence relation. As you've deduced there are eleven such classes, and ten of them do not contain zero. I would also encourage you to consider the first method of directly verifying the three defining properties as it's both instructive and relatively easy.

$\endgroup$
  • $\begingroup$ So is the answer 10 for B) correct? $\endgroup$ – RealGib Apr 14 '18 at 18:23
  • 1
    $\begingroup$ @RealGib: No, it's not. $\endgroup$ – zipirovich Apr 14 '18 at 18:30
  • 1
    $\begingroup$ None of the equivalence classes on $X$ contain 0, since $X$ does not contain 0. $\endgroup$ – Morgan Rodgers Apr 15 '18 at 17:17
  • 1
    $\begingroup$ "Morgan Rodgers continued insistence on ignoring this obvious interpretation of the OPs comments". But it goes both ways. I agree that "$\{11,...99\}$ do not contain $0$ as so can't be 'zero' modulo class" is a bit too oblique and inaccurate and $11\equiv 0 \mod 11$ does indeed mean $\{11,...99\}$ is the zero element. But on another, and very important level A "zero" (additive identity) element can only be defined if addition on the classes (and NOT on the elements of the classes) is defined. So it is not unjustified. $\endgroup$ – fleablood Apr 16 '18 at 16:10
  • 1
    $\begingroup$ ... so I mostly agree with Morgan Rodgers although I believe saying "it isn't a zero module as it doesn't contain zero" evades the issue that it actually isn't a zero module because the means for which it is "zero" are not stated. Of more concern is... why leave out the zero modules. These seem to much of a "monkey see; monkey do" approach to math that is doomed to failure. You don't just do everything one way despite whether that is what a question asks. If was asked how many elments does $\{0,1,6,8\}$ you don't answer 3 because zero doesn't count and you don't answer "it goes to 8". $\endgroup$ – fleablood Apr 16 '18 at 16:15
0
$\begingroup$

The question is not asking you about "nonzero" equivalence classes, it is asking for the total number of equivalence classes. So the equivalence class that contains 0 counts the same as any other equivalence class (however you want to interpret this, your set $X$ does not contain 0 so the interpretation of which equivalence class is the "zero" involves concepts that go beyond the scope of what this problem is asking).

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