Equivalence RelationsDate: 05/06/2003 at 17:32:13 From: Kerri Subject: Equivalence Relations I have a question about Equivalence relations. Determine with proof which of the three equivalence relation properties hold for the following relation. (a) Let R be the relation on the set A={1,2,3,4} defined by R = {(1,1),(1,2),(1,3),(1,4),(2,1),(2,2),(3,1),(3,3),(4,1)} (b) Let R be the relation on the natural numbers defined by nRm if and only if n divides into m with zero remainder. How would you prove the equivalence relation with ordered pairs such as in (a)? Thanks. Kerri Date: 05/06/2003 at 23:57:16 From: Doctor Samus Subject: Re: Equivalence Relations Hi Kerri, To start, we should list the three different properties of an equivalence relation R on a set A: I) Reflexivity: xRx for all x in A II) Symmetry: If xRy then yRx for x and y in A III) Transitivity: If xRy and yRz then xRz for x, y and z in A To determine which properties hold, we must look at the elements in the relation and see which properties they satisfy. Let's look at a) and see which properties hold: I) Doesn't hold, since 4 is in A, but (4,4) is not in R II) Holds, since for every (x,y) in R, (y,x) is also in R III) Doesn't hold, since (2,1) and (1,3) are in R, but (2,3) is not So for (a), only property II (symmetry) holds. To do b, simply investigate the same three properties for the relation in the problem. Note that to show a property doesn't hold, we need only find a single example showing that the property doesn't hold. To show that a property does hold, we have to show that it's true for all elements in the relation to which the property applies. I hope this helps. Please feel free to write back if you neeed more help. - Doctor Samus, The Math Forum http://mathforum.org/dr.math/ Date: 05/07/2003 at 00:16:26 From: Kerri Subject: Thank you (Equivalence Relations) Thank you Doctor Samus, so much! I had no idea how to work this and now I understand it completely. (b) wasn't a problem after your explanation of (a). Thanks again! Kerri |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/