Symmetric and Transitive therefore Reflexive

From ProofWiki
Jump to navigation Jump to search

Fallacy

Let $\mathcal R \subseteq S \times S$ be a relation which is symmetric and transitive.

Then $\mathcal R$ is also always reflexive.


Consider $x, y \in S$.

Suppose $x \mathrel {\mathcal R} y$.

Then as $\mathcal R$ is symmetric, it follows that $y \mathrel {\mathcal R} x$.

As $\mathcal R$ is transitive, it follows that $x \mathrel {\mathcal R} x$.

Therefore $x \mathrel {\mathcal R} x$ and so $\mathcal R$ is reflexive.


Resolution

For $\mathcal R$ to be reflexive, it is necessary for $x \mathrel {\mathcal R} x$ for all $x \in S$.

Unless it is the case that $\forall x \in S: \exists y \in S: x \mathrel {\mathcal R} y$, it is not necessarily the case that also $y \mathrel {\mathcal R} x$, and so the reasoning does not follow.

Take the set $S = \set {0, 1}$ and the relation:

$\mathcal R \subseteq S \times S: x \mathrel {\mathcal R} y \iff x = y = 1$


It is seen that:

$\mathcal R$ is symmetric
$\mathcal R$ is transitive

but:

$\mathcal R$ is not reflexive, as $\neg \paren {0 \mathrel {\mathcal R} 0}$.

$\blacksquare$


Also see


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Symmetric_and_Transitive_therefore_Reflexive&oldid=418397"