Relation is Connected and Reflexive iff Total
Jump to navigation
Jump to search
Theorem
Let $S$ be a set.
Let $\mathcal R$ be a relation on $S$.
Then:
- $\mathcal R$ is both a connected relation and a reflexive relation
- $\mathcal R$ is a total relation.
Proof
Necessary Condition
Let $\mathcal R$ be a relation on $S$ which is both connected and reflexive.
Let $\tuple {a, b} \in S \times S$.
Suppose $a = b$.
Then as $\mathcal R$ is reflexive, $\tuple {a, b} \in \mathcal R$.
Suppose $a \ne b$.
Then as $\mathcal R$ is connected, $\tuple {a, b} \in \mathcal R \lor \tuple {b, a} \in \mathcal R$.
That is:
- $\forall \tuple {a, b} \in S \times S: \tuple {a, b} \in \mathcal R \lor \tuple {b, a} \in \mathcal R$.
Thus $\mathcal R$ is a total relation.
$\Box$
Sufficient Condition
Let $\mathcal R$ be a total relation on $S$.
Then:
- $\forall \tuple {a, b} \in S \times S: \tuple {a, b} \in \mathcal R \lor \tuple {b, a} \in \mathcal R$
by definition.
Thus:
- $\forall \tuple {a, a} \in S \times S: \tuple {a, a} \in \mathcal R$
and so $\mathcal R$ is reflexive.
If $a \ne b$ the condition still holds, and so:
- $\forall \tuple {a, b} \in S \times S: a \ne b \implies \tuple {a, b} \in \mathcal R \lor \tuple {b, a} \in \mathcal R$
and so $\mathcal R$ is connected.
$\blacksquare$