- #1
Mathmos6
- 76
- 0
Homework Statement
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 .
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: