# Symmetric Transitive and Serial Relation is Reflexive

Jump to navigation
Jump to search

## Theorem

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

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

- 1965: E.J. Lemmon:
*Beginning Logic*... (previous) ... (next): $\S 4.5$: Properties of Relations: Exercise $2 \ \text{(c)}$ - 1965: Seth Warner:
*Modern Algebra*... (previous) ... (next): Exercise $10.5$