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!

Please help - Binary Relations driving me utterly insane

  1. May 12, 2009 #1
    1. The problem statement, all variables and given/known data

    If R and S are two equivalence relations on the same set A, we define R ◦ S =
    {(x, z ) ∈ A × A : there exists y ∈ A such that (x, y) ∈ R and (y, z ) ∈ S }.

    Show that the following conditions are equivalent:
    (i) R ◦ S is a symmetric relation on A ;
    (ii) R ◦ S is a transitive relation on A ;
    (iii) S ◦ R ⊆ R ◦ S ;
    (iv) R ◦ S is the unique smallest equivalence relation on A containing both R and S .

    3. The attempt at a solution

    I've spent literally hours trying to solve this and my brain is leaking out my ears now :( I've managed to prove (i -think-) that (i)=>(ii), and that (i)<=>(iii), but I can't see any way whatsoever to show (ii)=>(i), and I've managed to show that R ◦ S contains both R and S for (iv) but I don't know how to show that if it's the smallest such relation (iv)<=>(i) or (ii) or (iii).

    Please help! I'm quite a way out of my depth - (ii)=>(i) is the most frustrating bit, because I'm sure it's probably really obvious but I just can't seem to get it out! :(
    Last edited: May 12, 2009
  2. jcsd
  3. May 12, 2009 #2
    Never mind, got it.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook