• Support PF! Buy your school textbooks, materials and every day products Here!

Please help - Binary Relations driving me utterly insane

  • Thread starter Mathmos6
  • Start date
  • #1
81
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:

Answers and Replies

  • #2
81
0
Never mind, got it.
 

Related Threads for: Please help - Binary Relations driving me utterly insane

Replies
2
Views
3K
  • Last Post
Replies
11
Views
3K
  • Last Post
Replies
2
Views
1K
Replies
9
Views
2K
  • Last Post
Replies
0
Views
1K
  • Last Post
Replies
3
Views
3K
  • Last Post
Replies
0
Views
1K
  • Last Post
Replies
2
Views
3K
Top