Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

An equivalence relation is defined by three properties: reflexivity, symmetry and transitivity.

Doesn't symmetry and transitivity implies reflexivity? Consider the following argument.

For any $a$ and $b$, $a R b$ implies $b R a$ by symmetry. Using transitivity, we have $a R a$.

Source: Exercise 8.46, P195 of Mathematical Proofs, 2nd (not 3rd) ed. by Chartrand et al

share|improve this question
2  
This is a good problem to pose in an introductory Discrete Math/Logic course. –  Srivatsan Jul 31 '11 at 16:23
    
@LePressentiment Why would you add a random source to a three and half year old question?? This is a standard exercise that you can find in many many books. –  mrf Feb 7 at 7:10
1  
How do you know that $aRb$? maybe there is no such $b$. –  LeeNeverGup Feb 7 at 7:20

3 Answers 3

up vote 34 down vote accepted

Actually, without the reflexivity condition, the empty relation would count as an equivalence relation, which is non-ideal.

Your argument used the hypothesis that for each $a$, there exists $b$ such that $aRb$ holds. If this is true, then symmetry and transitivity imply reflexivity, but this is not true in general.

share|improve this answer

It can be, if you use Euclideanity instead of transitivity: a R c and b R c implies a R b.

As an aside, Euclideanity plus seriality characterises the equivalence relations.

share|improve this answer
    
This seems to fail though because (as Akhil mentioned) the empty relation would satisfy this but it's not reflexive. –  bryn Jul 22 '10 at 10:15
    
@bryn: ouch: somehow my eyes saw "reflexivity" and my brain read "symmetry". Different concepts, I have heard... –  Charles Stewart Jul 22 '10 at 11:26
    
Not to sound as though I'm picking on you, but I think this revised claim is also false. My first clue was the fact that the wikipedia article you referenced said that Euclidean+Reflexive => Equivalence. Since being reflexive is a stronger requirement than being serial I sought a counterexample, the smallest of which I can find is on the set {1,2} and is defined as Rxy <-> y = 2. –  bryn Jul 22 '10 at 11:57
    
@bryn: Rx2 & Rx2 -> Rxx. –  Charles Stewart Jul 22 '10 at 12:14
    
@Charles: ouch: I typed it into a program that does a brute-force search for counterexamples, but I misrepresented the Euclideanity as 'Rxy & Rxz -> Ryz'. Perhaps I should have read the definition you gave! Sorry. –  bryn Jul 22 '10 at 12:25

No.

The missing condition is sometimes called 'seriality' -- for any x there must be a y such that x R y.

If you add seriality to the symmetry and transitivity you get a reflexive relation again.

share|improve this answer
1  
I googled seriality, not much came up. You sure it's spelled right? –  Chao Xu Jul 22 '10 at 10:40
    
Perhaps I made up the noun form. If you google 'serial binary relation' it will come up. Although if you google 'seriality of binary relations' it will come up there too. –  bryn Jul 22 '10 at 10:42
    
@ChaoXu ProofWiki uses the name serial relation. –  Martin Sleziak Jul 10 '12 at 12:37

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.