2
$\begingroup$

I've been wondering recently the following:

Let $\sim $ be a symmetric and transitive relation defined on $S $. Let $a \sim b $, which implies $b \sim a $ by symmetry, and by transitivity, $a \sim a $. Hence, $\sim $ is reflexive.

I can't think of any counterexamples, although any are welcome. Also, if there is some counterexample, where could be the flaw in my reasoning be?

$\endgroup$
3
  • 1
    $\begingroup$ The second sentence of the second paragraph is wrong. You may not conclude $b \sim a$. $\endgroup$
    – vadim123
    Jan 20, 2017 at 22:59
  • $\begingroup$ No. Review the definition of reflexivity and consider the subset relation, $\subset$. $\endgroup$
    – avs
    Jan 20, 2017 at 22:59
  • $\begingroup$ Sorrry, mixed up the terms. Fixed the post with what I meant to say. $\endgroup$
    – Andrew Tawfeek
    Jan 20, 2017 at 23:03

2 Answers 2

Reset to default
5
$\begingroup$

You're assuming that there exists a $b$ such that $a\sim b$ in your argument. If you don't know the relation is reflexive, that $b$ may not exist. Put differently, reflexivity in the presence of symmetry and transitivity is equivalent to each element being equivalent to some other one

$\endgroup$
3
  • $\begingroup$ Ohhhh I think I understand, if $\sim $ is not reflexive, then the equivalence class $[a]_\sim $ may as well be empty because there's no guaranteed element in that set? $\endgroup$
    – Andrew Tawfeek
    Jan 21, 2017 at 0:24
  • $\begingroup$ Hmmm.. So is that error what makes the empty relation a counterexample? $\endgroup$
    – Andrew Tawfeek
    Jan 21, 2017 at 0:25
  • $\begingroup$ The empty relation is a little confusion to think about. Here's a clearer counterexample: just take any set and define an equivalence relation on a strict subset. E.g. on the set of all people, let two people (the set) be equivalent if they have the same age and also are both blond (the strict subset). Then that's symmetric and transitive, but not reflexive because brown haired people are not in relation to anything.. $\endgroup$
    – Louis
    Jan 23, 2017 at 17:20
3
$\begingroup$

Reflexivity is a~a. You are using symmetry as reflexivity. As vadim123, noted, symmetry and transitivity do not imply reflexivity. The empty relation is a counterexample.

$\endgroup$
7
  • $\begingroup$ Oh thank you very much. I did not think of that! I'll edit the answer $\endgroup$
    – user194469
    Jan 20, 2017 at 23:01
  • $\begingroup$ If you included a "for all $a\in S$" in the first sentence, it would make it easier to upvote. $\endgroup$
    – Lukas Betz
    Jan 20, 2017 at 23:01
  • $\begingroup$ I actually had just finished editting my post, accidentally mixed up the terms, but yes, that's what I meant. And is that above a sufficent "proof" then? $\endgroup$
    – Andrew Tawfeek
    Jan 20, 2017 at 23:03
  • $\begingroup$ @vadim123 doesn't empty relation satisfy reflexivity (and all other things) vacuously? $\endgroup$
    – user160738
    Jan 20, 2017 at 23:03
  • 2
    $\begingroup$ You can read a complete argument in here: math.stackexchange.com/q/1081333/194469 $\endgroup$
    – user194469
    Jan 20, 2017 at 23:05

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