Symmetric Transitive and Serial Relation is Reflexive

From ProofWiki
Jump to: navigation, search

Theorem

Let $\mathcal R$ be a relation which is:

symmetric
transitive
serial.


Then $\mathcal R$ is reflexive.


Thus such a relation is an equivalence.


Proof

Let $S$ be a set on which $\mathcal R$ is a relation which is symmetric, transitive and serial.


As $\mathcal R$ is symmetric:

$x \mathcal R y \implies y \mathcal R x$

As $\mathcal R$ is transitive:

$x \mathcal R y \land y \mathcal R x \implies x \mathcal R x$

As $\mathcal R$ is serial:

$\forall x \in S: \exists y \in S: x \mathcal R y$


Let $x \in S$.

Then

\(\, \displaystyle \exists y \in S: \, \) \(\displaystyle \left({x, y}\right)\) \(\in\) \(\displaystyle \mathcal R\) as $\mathcal R$ is serial
\(\displaystyle \implies \ \ \) \(\displaystyle \left({y, x}\right)\) \(\in\) \(\displaystyle \mathcal R\) as $\mathcal R$ is symmetric
\(\displaystyle \implies \ \ \) \(\displaystyle \left({x, x}\right)\) \(\in\) \(\displaystyle \mathcal R\) as $\mathcal R$ is transitive

Thus:

$\forall x: x \mathcal R x$

and by definition $\mathcal R$ is reflexive.


It follows by definition that such a relation is an equivalence relation.

$\blacksquare$


Sources