# Symmetric Transitive and Serial Relation is Reflexive

Jump to navigation
Jump to search

## Theorem

Let $\RR$ be a relation which is:

Then $\RR$ is reflexive.

Thus such a relation is an equivalence.

## Proof

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

As $\RR$ is symmetric:

- $x \mathrel \RR y \implies y \mathrel \RR x$

As $\RR$ is transitive:

- $x \mathrel \RR y \land y \mathrel \RR x \implies x \mathrel \RR x$

As $\RR$ is serial:

- $\forall x \in S: \exists y \in S: x \mathrel \RR y$

Let $x \in S$.

Then

\(\ds \exists y \in S: \, \) | \(\ds \tuple {x, y}\) | \(\in\) | \(\ds \RR\) | as $\RR$ is serial | ||||||||||

\(\ds \leadsto \ \ \) | \(\ds \tuple {y, x}\) | \(\in\) | \(\ds \RR\) | as $\RR$ is symmetric | ||||||||||

\(\ds \leadsto \ \ \) | \(\ds \tuple {x, x}\) | \(\in\) | \(\ds \RR\) | as $\RR$ is transitive |

Thus:

- $\forall x: x \mathrel \RR x$

and by definition $\RR$ is reflexive.

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

$\blacksquare$

## Sources

- 1965: E.J. Lemmon:
*Beginning Logic*... (previous) ... (next): Chapter $4$: The Predicate Calculus $2$: $5$ Properties of Relations: Exercise $2 \ \text{(c)}$ - 1965: Seth Warner:
*Modern Algebra*... (previous) ... (next): Chapter $\text {II}$: New Structures from Old: $\S 10$: Equivalence Relations: Exercise $10.5$