Equivalence RelationsDate: 12/10/2001 at 16:01:15 From: Joelle Subject: Equivalence relations Let X = {1, 2, 3, 4, 5} , Y = {3, 4}. Define a relation R on the power set of X by A R B if A U Y = B U Y. a) Prove that R is an equivalence relation. b) What is the equivalence class of {1, 2}? c) How many equivalence classes are there? Date: 12/11/2001 at 09:03:15 From: Doctor Paul Subject: Re: Equivalence relations >a) Prove that R is an equivalence relation. Certainly this relation is reflexive: A ~ A means A u Y = A u Y and this is clearly true. To show ~ is symmetric, we need to show A ~ B -> B ~ A A ~ B means A u Y = B u Y. This implies B u Y = A u Y and this is equivalent to B ~ A. So ~ is symmetric. Finally, show ~ is transitive: A ~ B and B ~ C -> A ~ C Well, A~B means A u Y = B u Y and B~C means B u Y = C u Y Thus we have A u Y = B u Y = C u Y so A ~ C Thus ~ is an equivalence relation. >b) What is the equivalence class of {1, 2}? Two elements of the power set of X are going to be related if and only if they are in the same equivalence class - that's what an equivalence relation does - it partitions the elements of a set into classes where two elements are in the same equivalence class if and only if they are related by the given equivalence relation. So what elements are going to be in the same class as {1,2}? Those that are related to it by ~ So we want to pick an element A of the power set of X such that A u {3,4} = {1,2} u {3,4} = {1,2,3,4} So we have the following restrictions on the set A: It must contain both 1 and 2. It might or might not contain either 3 or 4. It cannot contain 5. It looks as if your possibilities are: {1,2} {1,2,3} {1,2,4} {1,2,3,4} >c) How many equivalence classes are there? I'll leave this for you. The idea is similar to part (b) - just pick an element of the power set of X and compute the elements that are in the same equivalence class. Recall that equivalence classes are distinct (their intersections are always empty) so you'll never use any of the four that we found above in any other class. Finally, recall that since X has 5 elements, P(X) will have 2^5 = 32 elements. It shouldn't take you too long to come up the classes to which the other 28 elements belong. I hope this helps. Please write back if you'd like to talk about this some more (especially if there is something you don't understand). - Doctor Paul, The Math Forum http://mathforum.org/dr.math/ Date: 12/11/2001 at 10:11:24 From: Joelle Subject: Equivalence relation Resp. Dr. Paul, Thank you for the solution. What I did not understand is ... to calculate the total number of equivalence classes, do I need to consider each of the 28 members separately, as you did for one member, or is there a general method? Is it possible to calculate the number of equivalence classes for a set with n elements? Date: 12/11/2001 at 10:36:32 From: Doctor Paul Subject: Re: Equivalence relation It is in general not possible to calculate the number of equivalence classes for a set with n elements because the number of equivalence classes will always depend on the associated equivalence relation (whenever we speak of equivalence classes, there had better be an assumed equivalence relation somewhere in the background). We had: A ~ B if A u Y = B u Y What if I came up with some other way of defining the relation ~ that retained the property of ~ being an equivalence relation? Consider: A ~ B if A = B Here, ~ is clearly an equivalence relation (verify this if it's not inherently obvious) and the equivalence classes are going to be the 32 elements of P(X). Certainly two distinct elements of P(X) won't be in the same equivalence class under this new definition of the relation ~ because this can only happen when the elements are related (i.e., they are equal) and we are assuming from the outset that these two elements are distinct. Thus we have 32 distinct, one element equivalence classes. > do I need to consider each of the 28 members separately Yes. Pick one (we picked {1,2} earlier) and then see what other elements are in the same equivalence class. This will eliminate some of your other possibilities (we eliminated three other choices). You won't need to pick the element {1,2,3} because we know that the intersection of two distinct equivalence classes is empty. For example, if you try to find what elements are in the same equivalence class as {1,2,3}, you'll just end up with {1,2}, {1,2,4}, and {1,2,3,4} again. So you won't have to actually compute this 28 different times - each time you pick one, it should eliminate several of the remaining possibilities. After you've compute the class associated with a particular element, just pick an element that doesn't belong to any of the classes that have already been determined. - Doctor Paul, 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/