Reflexive Relation is Serial
Jump to navigation
Jump to search
Theorem
Every reflexive relation is also a serial relation.
Proof
Let $\RR \subseteq S \times S$ be a relation in $S$.
We have that $\RR$ is serial if and only if:
- $\forall x \in S: \exists y \in S: \tuple {x, y} \in \RR$
That is, if and only if every element relates to at least one element.
We have that $\RR$ is reflexive if and only if:
- $\forall x \in S: \tuple {x, x} \in \RR$
Hence if $\RR$ is reflexive, every $x$ is related to itself, thereby fulfilling the criterion for $\RR$ to be serial.
$\blacksquare$