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$