1
$\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$
  • 1
    $\begingroup$ The second sentence of the second paragraph is wrong. You may not conclude $b \sim a$. $\endgroup$ – vadim123 Jan 20 '17 at 22:59
  • $\begingroup$ No. Review the definition of reflexivity and consider the subset relation, $\subset$. $\endgroup$ – avs Jan 20 '17 at 22:59
  • $\begingroup$ Sorrry, mixed up the terms. Fixed the post with what I meant to say. $\endgroup$ – Andrew Tawfeek Jan 20 '17 at 23:03
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$
  • $\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 '17 at 0:24
  • $\begingroup$ Hmmm.. So is that error what makes the empty relation a counterexample? $\endgroup$ – Andrew Tawfeek Jan 21 '17 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 '17 at 17:20
2
$\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$
  • $\begingroup$ Oh thank you very much. I did not think of that! I'll edit the answer $\endgroup$ – user194469 Jan 20 '17 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$ – Tim B. Jan 20 '17 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 '17 at 23:03
  • $\begingroup$ @vadim123 doesn't empty relation satisfy reflexivity (and all other things) vacuously? $\endgroup$ – user160738 Jan 20 '17 at 23:03
  • 2
    $\begingroup$ You can read a complete argument in here: math.stackexchange.com/q/1081333/194469 $\endgroup$ – user194469 Jan 20 '17 at 23:05

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