Relations and Equivalence Classes

Date: 01/10/99 at 11:04:19
From: Emma Warren
Subject: Relations and Equivalence classes

Hi Dr. Math,

I'm hoping you can help me again. The question is:

  The following relations are defined on the set of integers

  1) a~b if and only if a^2-b^2 is divisible by 5
  2) a~b if and only if a+2b is divisible by 3

  Show that each of these is an equivalence relation, and determine 
  the equivalence classes under each relation.

I know that for the relation to be an equivalence relation it must be 
reflexive, symmetric, and transitive.
 
The second relation seems fairly easy and precise. Here's how I tried 
it:

Reflexive test:

   Is a~a for all a in the set of integers?
   a~a if and only if a+2a is divisible by 3
   Since a+2a = 3a is divisible by 3, the relationship is reflexive.

Symmetric test;

   If a~b, then a+2b is divisible by 3. So a+2b = 3N (where N is in 
   the set of integers). Thus a = 3N - 2b. So:

      b+2a = b+2(3N-2b)
           = b+6N-4b
           = 6N-3b
           = 3(2N-b)  - this is divisible by 3

   So, b+2a is divisible by 3. Thus b~a and the relation is symmetric.

Transitive test:

   If a~b and b~c, then:
 
      a+2b = 3N  (where N is in the set of integers)
      b+2c = 3M  (where M is in the set of integers)

   Adding the two together gives:

      a+3b+2c = 3N+3M
      a+2c = 3N+3M-3b
      a+2c = 3(N+m-b)  - this is divisible by 3
   So, a+2c is divisible by 3. Thus a~c and the relation is 
   transitive.

The relation has all three properties and so is an equivalence 
relation.

I'm having trouble with the second one though. I hope you can clear up 
the way in which I have to do these sorts of questions.

Thanks again,
Emma

Date: 01/11/99 at 14:25:53
From: Doctor Teeple
Subject: Re: Relations and Equivalence classes

Hi Emma,

Thanks for writing to Dr. Math. 

You did a fabulous job of proving the second equivalence relation! You 
have the right idea, and the first equivalence relation is very 
similar. I'll give you some hints about what will happen as you try to 
prove the three requirements. Bear with me if you've already gotten 
them:

Reflexivity: 
Is 0 divisible by 5? You can think of it this way - what do you get 
when you divide 0 by 5? Is there a remainder? No. So yes, 0 is 
divisible by 5. This may seem like cheating because you can replace the 
5 by any number in the previous questions, but all that says is that 0 
is divisible by any number.

Symmetry:
When you prove symmetry, you assume that a^2 - b^2 is divisible by 5. 
What do you get when you factor out a negative? If a number is 
divisible by 5, is its negative divisible by 5?

Transitivity: 
From your assumptions, you know that a^2 - b^2 and b^2 - c^2 are 
divisible by 5. When you add two numbers divisible by 5, is the sum 
divisible by 5? Try it with a few numbers if you're not sure.

To find the equivalence classes, you want to get an idea of which 
numbers are equivalent to each other. The best way to find this out is 
to just do some examples. I'll help with the first one. Keeping in mind 
that a~b if and only if a^2-b^2 is divisible by 5, try listing the 
squares and then subtracting. First, here are the squares of the first 
few digits:

   1   4   9   16   25   36   49   64   81   100   121   144 ...

If b = 1, and a = 2, 3, 4, 5, 6, . . ., here are a^2 - b^2:

      a    | 2   3    4    5    6    7    8    9   10    11    12
 a^2 - b^2 | 3   8   15   24   35   48   63   80   99   120   143 ...

By looking for those that are divisible by 5, we see that 1 is 
equivalent to 4, 6, 9, and 11. Thus, one equivalence class consists of 
at least 1, 4, 6, 9, and 11. There are more, and we'll look for the 
general pattern a little later on. 

If b = 2, and a = 3, 4, 5, 6, 7, ..., we get for a^2 - b^2:

   5   12   21   32   45   60   77   96   117   140 ...

From this we see that 2 is equivalent to 3, 7, 8, and 12. So another 
equivalence class contains 2, 3, 7, 8, 12, . . . . 

So far we have the following two equivalence classes:

   1, 4, 6, 9, 11, . . . 
   2, 3, 7, 8, 12, . . .

Which numbers are we missing? The multiples of 5. Does it make sense 
that the multiples of 5 will be in their own equivalence relation? Try 
squaring and subtracting them to see that you will get a multiple of 5. 
Among the three classes, we've accounted for all of the integers. 

Now, what is the pattern of the other two equivalence classes? To see 
it, try this method. Write down the integers from 1 to 16. Draw a box 
around the multiples of 5 and circle all those that are in the first 
equivalence class above (i.e.: all those equivalent to 1). Look how the 
circled ones and the non-circled ones relate to the multiples of 5. You 
should have something like: 

   circle plain plain circle box

and the pattern repeats. This may seem simplistic but it's a good way 
to see what's going on. 

More technically (which you can skip if you only need the above or 
haven't studied modular aritmetic), we're looking for integers whose 
squares are equivalent to mod 5. (I'll use = for equivalence). So:

   a^2 = b^2 (mod 5)

The circled ones are those where:

   a^2 = b^2 = 1 (mod 5)

that is, if you square them and divide by 5, you get a remainder of 1. 

The plain ones are those where:

   a^2 = b^2 = 4 (mod 5)

And the boxed ones are those where:

   a^2 = b^2 = 0 (mod 5)

So in each case, a^2 - b^2 = 0 (mod 5), which means a^2 - b^2 is a 
multiple of 5. 

Basically, the above is a complicated way of saying try a few numbers 
to see what will be equivalent. That's the most direct way of looking 
for the equivalence classes. Note that while I didn't address negative 
numbers, they should also be included.

If you didn't understand any of the above or need help on anything 
else, please write back. Good luck!

- Doctor Teeple, The Math Forum
  http://mathforum.org/dr.math/