1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Equivalence relation

  1. May 15, 2009 #1
    let the relation [tex]\propto[/tex] on a set S have the properties
    (i) a [tex]\propto[/tex] a for every a [tex]\in[/tex] S
    (II) if a [tex]\propto[/tex] b and b [tex]\propto[/tex] c then c [tex]\propto[/tex] a

    show that [tex]\propto[/tex] is an equivalence relation on S.
    Does every equivalence relation on S satisfy (i) and (ii)

    I'm not sure where to start this i know
    (i) is the reflexive property and (ii) is the Transitive property.
    Im not sure where to go or how to tackle this,some pointers would be greatly appreciated
    Last edited: May 15, 2009
  2. jcsd
  3. May 15, 2009 #2


    User Avatar
    Science Advisor

    Presumably you know what an equivalence relation is! (If not, this is an extremely difficult question!:rofl:)

    A relation, R, is an equivalence relation on a set if and only if it satisfies:
    1) aRa for for all a in the set. (reflexive)
    2) if aRb and bRc then aRc. (transitive)
    3) if aRb then bRa. (symmetric)

    You are given that this relation, [tex]\propto[/tex], is reflexive and symmetric so all you need to do is show that if (1) and (2) are true then (3) is true. Frankly, I see a problem with that. That, as stated, is NOT true. It should be easy for you to write down a relation on {a, b, c} that is both reflexive and transitive but not symmetric.
  4. May 15, 2009 #3

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    Actually, you aren't given that it is transitive. The statement in the question is that

    aRb & bRc implies that cRa NOT that aRc.

    It is straight forward to show, with a propitious choice of c, that this implies symmetry which then implies...
  5. May 15, 2009 #4
    ah yes i see now, he threw that trick in and i didn't notice,thanks a million
  6. May 15, 2009 #5
    so we need to show it holds true for the 3 properties refexive,symmetric and Transitive. We are given that it is reflexive. a [tex]\propto[/tex] a it follows that b [tex]\propto[/tex] b therefore from (ii) a [tex]\propto[/tex] b and b[tex]\propto[/tex] c and b [tex]\propto[/tex] b we get a [tex]\propto[/tex] c which implies it is Transitive but also since a [tex]\propto[/tex] c and c [tex]\propto[/tex] a which implies it is symmetric


    every equivalence relation on S satisfies (i) and (ii) because in order for it to be an equivalence relation it has to satisfy the 3 properties of Reflexive,Symmetric and Transitive and if it holds true for these 3 properties it holds true for (i) and (ii)

    Last edited: May 15, 2009
  7. May 15, 2009 #6
    You're given it is reflexive.

    To show it's symmetric, you need to find a and b such that the given rules can be used to deduce that if a R b then b R a. *HINT*: a R a, and if a R b and b R c then c R a, so... what if b is a?

    To show it's transitive then, well, you have to show that if a R b and b R c then a R c... but you already know c R a is true, right? And it's reflexive?

    If you show reflexivity, symmetry, and transitivity, then you're done. Nothing else is required... except, perhaps, to show it's a binary relation, but I think that's extraneous to the discussion.
  8. May 15, 2009 #7
    Sorry, for this but is that not what im showing aRa it follow bRb...etc but then i show its transitive and from there also symmetric. Do i need to show its symmetric first? Sorry if this is silly question and thanks for the help
  9. May 15, 2009 #8
    No, you can show it in either order. I just happen to have seen it the other way around first. In theory, if you can show it one way and then the other, it doesn't matter which order you choose.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook