# Why isn't reflexivity redundant in the definition of equivalence relation?

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

-
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
How do you know that $aRb$? maybe there is no such $b$. –  LeeNeverGup Feb 7 at 7:20

## 3 Answers

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.

-

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.

-
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

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.

-
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