- #1

- 81

- 0

## Homework Statement

If R and S are two equivalence relations on the same set A, we deﬁne 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: