97
$\begingroup$

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

$\endgroup$
6
  • 8
    $\begingroup$ This is a good problem to pose in an introductory Discrete Math/Logic course. $\endgroup$
    – Srivatsan
    Commented Jul 31, 2011 at 16:23
  • $\begingroup$ @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. $\endgroup$
    – mrf
    Commented Feb 7, 2014 at 7:10
  • 17
    $\begingroup$ How do you know that $aRb$? maybe there is no such $b$. $\endgroup$
    – LeeNeverGup
    Commented Feb 7, 2014 at 7:20
  • $\begingroup$ I have created a canonical Q&A, which is meant to address this question, and others like it. $\endgroup$
    – Xander Henderson ♦
    Commented Aug 26, 2020 at 22:16
  • $\begingroup$ Does this answer your question? Examples and Counterexamples of Relations which Satisfy Certain Properties $\endgroup$
    – user279515
    Commented Aug 28, 2020 at 14:21

6 Answers 6

Reset to default
93
$\begingroup$

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.

$\endgroup$
3
  • 2
    $\begingroup$ Why is the following not a counter-example that even with seriality, and transitivity and symmetry, a relation can fail to be reflexive on some set: Consider $S = \{1, 4, 5, 6\}$ and the relation $R$ where $(x,y) \in R$ if $x + y > 3$. On $S$, this relation is transitive, symmetric, and seriality holds. So reflexivity should too. Yet 1 + 1 $\not > 3$. $\endgroup$
    – Muno
    Commented Apr 6, 2016 at 2:50
  • 4
    $\begingroup$ @Muno $R(1, x) \land R(x, 1) \implies R(1, 1)$ does not hold for $x \ne 1$ $\endgroup$
    – DanielV
    Commented Jun 11, 2016 at 5:25
  • 1
    $\begingroup$ @Muno I guess your relation is not transitive? $\endgroup$
    – High GPA
    Commented Dec 3, 2020 at 20:41
39
$\begingroup$

No.

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

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

$\endgroup$
4
  • 1
    $\begingroup$ I googled seriality, not much came up. You sure it's spelled right? $\endgroup$
    – Chao Xu
    Commented Jul 22, 2010 at 10:40
  • $\begingroup$ 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. $\endgroup$
    – bryn
    Commented Jul 22, 2010 at 10:42
  • 6
    $\begingroup$ @ChaoXu ProofWiki uses the name serial relation. $\endgroup$
    – Martin Sleziak
    Commented Jul 10, 2012 at 12:37
  • $\begingroup$ @ChaoXu, $R$ can also be called "total" or "entire". Note that $R$ doesn't have to be an endorelation for totality to make sense. $\endgroup$
    – goblin GONE
    Commented Apr 21, 2016 at 12:55
15
$\begingroup$

Consider the set $S =\{a,b,c\}$, with $a, b$, and $c$ distinct, and the relation $$R = \{(a,c),(c,a),(a,a),(c,c)\} \subset S \times S$$

It's symmetric and transitive but it's not reflexive.

Added 3/4/2021

The argument $aRb \implies bRa \implies aRa$ is compelling except for one thing. What if there is no $b$ such that $aRb$?

$\endgroup$
2
  • $\begingroup$ Shouldn't that say "What if there is no b such that aRb?" say "What if there is no a such that aRb?" Note: the 'a'. $\endgroup$
    – nickalh
    Commented Aug 13, 2022 at 7:55
  • 2
    $\begingroup$ No, $a$ is given and you want to prove $aRa$. He argued $aRb \implies bRa \implies aRa$. I asked what if there is no $b$ such that $aRb$? $\endgroup$
    – Steven Alexis Gregory
    Commented Aug 17, 2022 at 15:31
4
$\begingroup$

To answer Muno's question, $R$ on $S$ is not transitive: $x=z=1$ and $y=3$ is a counterexample (any $y$ other than $1$ will do). $x+y=y+z>3$ but $x+z<3$.

silvascientist: $R$ satisfies Drittengleichheit if the implication is true; it is vacuously true if $xRz$ and $yRz$ is false. This does not mean that $xRy$ is true (similarly $xRy$ and $xRy$ false does not mean $xRx$ is true, simply that it vacuously satisfies the property) for the empty relation on a non-empty set. The same applies if $x$ isn't related to anything, so in neither case is $R$ reflexive.

$\endgroup$
2
$\begingroup$

You can get kind of rid of reflexivity. Assume the $R$ is a symmetric relation which satisfies the property of "Drittengleichheit": $xRz\land yRz\Rightarrow xRy$. In this case $R$ is a equivalence relation; you can easily deduce transitivity and reflexibility of $R$.

Do you notice the difference between "Drittengleichheit" and transitivity?

$\endgroup$
1
  • 2
    $\begingroup$ How does this rule out the empty relation? More generally, how does this rule out relations for which some elements are not related to anything at all? $\endgroup$
    – silvascientist
    Commented Dec 29, 2015 at 22:53
1
$\begingroup$

Reflexivity always requires for the binary relation to include every element of the set, which it may not even if transitivity and symmetry are both valid for the relation. However, it may be redundant if every element of the set is said to have a relative or the relation is redefined to be only on the subset of current set leaving out the excluded members for whome the relation doesn't map to anywhere. Although sometimes the definition of the relation itself might restrict the reflexivity, for example: the pair (a,b) where 'a' is b's brother.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .