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

Equivalence relation

  • #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:

Answers and Replies

  • #2
HallsofIvy
Science Advisor
Homework Helper
41,794
925
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.
 
  • #3
matt grime
Science Advisor
Homework Helper
9,395
3
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...
 
  • #4
ah yes i see now, he threw that trick in and i didn't notice,thanks a million
 
  • #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:
  • #6
492
0
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.
 
  • #7
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
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
 
  • #8
492
0
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.
 

Related Threads for: Equivalence relation

  • Last Post
Replies
13
Views
1K
  • Last Post
Replies
5
Views
989
  • Last Post
Replies
5
Views
2K
  • Last Post
Replies
4
Views
1K
  • Last Post
Replies
9
Views
2K
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
3
Views
2K
Top