Equivalence ClassesDate: 02/19/99 at 03:41:21 From: Wayne Chow Subject: Discrete Mathematics Is there an equivalence class containing exactly 271 elements? Date: 02/19/99 at 19:22:14 From: Doctor Kate Subject: Re: Discrete Mathematics To define an equivalence class, one needs to define an equivalence relation. There are all sorts of equivalence relations one could use, and to answer your question, it would help to know if you had a particular equivalence relation in mind. I will assume you do not. Let's define an equivalence relation. Let a and b be numbers. To say a is equivalent to b, I will write a ~ b. An equivalence relation is any relation that satisfies these rules: 1) a ~ a always (this rule is called reflexivity) 2) if a ~ b, then b ~ a (this is called symmetry) 3) if a ~ b and b ~ c, then a ~ c (called transitivity) So there are all sorts of equivalences: Example 1: Equals (=) is an equivalence relation because: 1) a = a all the time 2) if a = b, b = a 3) if a = b and b = c, a = c Example 2: Let us define a ~ b if a and b have the same sign (let's pretend 0 has positive sign for the purpose of this example). For example, 3 ~ 5, 7 ~ 2, -5 ~ -18, but -6 is NOT equivalent to 3. 1) a has the same sign as a, so a ~ a 2) if a has the same sign as b, b has the same sign as a 3) if a has the same sign as b, and b has the same sign as c, a and c must have the same sign! Example 3: We will say a ~ b if a and b have the same remainder when you divide by three. (Notice that I've just changed what ~ (equivalent) means - it's different now than in the last example. I can define it in lots of ways, as long as I follow the three rules for equivalence relations.) For example, 3 ~ 6, because both have remainder 0 when you divide by three. Further, 1 ~ 16, because both have remainder 1 when you divide by three, but 2 is NOT equivalent to 7 because 2 has remainder 2, but 7 has remainder 1. For fun, try to check the three rules yourself. Here's the first one: 1) a ~ a because you always get the same remainder when you divide a by three (yes, it's really easy). Back to your question: An equivalence class is a set of things that are equivalent to each other. So for '=', every equivalence class is size 1, since the only thing equivalent (equal) to a is a itself. For the second example, the equivalence classes are infinitely big, because there are infinitely many things with positive sign, and infinitely many things with negative sign. Now in the third example, what possibilities do we have? We can have a remainder of 0, 1 or 2, so there are really three equivalence classes: 1) the things with remainder 0 when you divide by three (multiples of 3) 2) the things with remainder 1 when you divide by three (like 1, 4, 7, 10...) 3) the things with remainder 2 when you divide by three (like 2, 5, 8, 11...) But how big are they? They're infinite again. These are pretty normal examples of equivalence classes, but if you want to find one with an equivalence class of size 271, what could you do? Well, we could be silly, for a moment, and define an equivalence class like this: Let's talk about the integers. Let a and b be integers. If a and b are both between 1 and 271, a ~ b. If a and b are both outside the interval 1 to 271, a ~ b. If one of a and b is between 1 and 271 and the other is not, a is NOT equivalent to b. I know it is silly! But it's a perfectly good equivalence relation. I will let you check the three rules yourself. Now, what equivalence classes do we have here? Clearly, we have two: 1) 1, 2, 3, .... 271 2) everything else And what size does the first one have? You guessed it. I can imagine you asking whether there is a less silly example. Dodging the question of what "silly" means exactly, I will say that there is not really (well, maybe slightly better, but nothing as nice as my examples above), if you want to work with integers. However, you can define equivalence relations on all sorts of sets. You can define equivalence relations on your socks: all socks of the same colour are equivalent. So you may have three equivalence classes: grey, blue, and pink. These equivalence classes probably won't have size 271, but you never know. They're your socks, not mine. So the answer to your question is yes. - Doctor Kate, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2015 The Math Forum
http://mathforum.org/dr.math/