0
$\begingroup$

Consider a relation R: A → A which is both symmetric and transitive.

The following proof shows that the relation is also reflexive: Take a ∈ A. If a ∼ b then b ∼ a by symmetry, and hence a ∼ a by transitivity. Therefore, the relation is reflexive."

Is the proof correct or not?

I think it is incorrect. I think it should be "For every a ∈ A, there exists b ∈ A that a ~ b and b ~ a.", not just "Take a ∈ A". After that we can use symmetry and transitivity to prove it is reflexive. That is what I think.

Am I right? Or what is the correct answer and the reason? THANKS!

$\endgroup$
  • $\begingroup$ There may not be just one $b$ technically, unless the relation is a function . Just a technicality. $\endgroup$ – user645636 Nov 16 '19 at 22:13
2
$\begingroup$

The proof is wrong and you are wrong. After all, there are relations which are both symmetric and transitive which are not reflexive. Take the empty relation for instance (that is, we never have $a\mathrel Rb$).

However, if you add the hypothesis that for each $a\in A$, there is some $b\in A$ such that $a\mathrel Bb$, then the first proof that you described works.

$\endgroup$
1
$\begingroup$

If $\sim$ is symmetric and transitive, then $a\sim b$ and $b\sim a$ implies $a\sim a$. However, as you say, this presumes the existence of some such $b$. In general, symmetric and transitive do not imply reflexive.

You can make a sort of silly counterexample by just defining $\sim$ on a set. Take the set $\{x,y\}$ and the relation containing only $x\sim x$. This is not reflexive since $y\not\sim y$.

$\endgroup$
1
$\begingroup$

There is no reason why given an $a$ there should be any $b$ which relates to it.

If such a $b$ exists for every $a$ then you are done. But the empty relation on a singleton set (set with one element) is (trivially - there are no cases) symmetric and transitive, but not reflexive.

$\endgroup$

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