Symmetric and Transitive Relation is not necessarily Reflexive/Proof 3

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $S$ be a set.

Let $\alpha \subseteq S \times S$ be a relation on $S$.

Let $\alpha$ be both symmetric and transitive.


Then it is not necessarily the case that $\alpha$ is also reflexive.


Proof

Proof by Counterexample:

Let $S = \set {1, 2}$ be a set.


Let $\RR$ be the relation on $S$ defined as:

$\forall x, y \in S: x \mathrel \RR y \iff x = y = 2$


\(\ds x\) \(\RR\) \(\ds y\)
\(\ds \leadsto \ \ \) \(\ds x\) \(=\) \(\ds y = 2\)
\(\ds \leadsto \ \ \) \(\ds y\) \(=\) \(\ds x = 2\)
\(\ds \leadsto \ \ \) \(\ds y\) \(\RR\) \(\ds x\)

Thus $\alpha$ is symmetric.


Now let $x \mathrel \RR y$ and $y \mathrel \RR z$

Then:

$x = y = 2, y = z = 2$

and so:

$x \mathrel \RR z$


Now let $x = 1$.

Then it is not the case that:

$x \mathrel \RR x$

and so $\RR$ is not reflexive.


Hence $\RR$ is both symmetric and transitive but not reflexive.

$\blacksquare$


Sources