Relations and Equivalence ClassesDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/