Transitive Relation whose Symmetric Closure is not Transitive
Jump to navigation
Jump to search
Theorem
Let $S = \set {p, q}$, where $p$ and $q$ are distinct elements.
Let $\RR = \set {\tuple {p, q} }$.
Then $\RR$ is transitive but its symmetric closure is not.
Proof
$\RR$ is vacuously transitive because there are no elements $a, b, c \in S$ such that $a \mathrel \RR b$ and $b \mathrel \RR c$.
Let $\RR^\leftrightarrow$ be the symmetric closure of $\RR$.
Then $\RR^\leftrightarrow = \RR \cup \RR^{-1} = \set {\tuple {p, q}, \tuple {q, p} }$.
Then:
- $p \mathrel {\RR^\leftrightarrow} q$ and $q \mathrel {\RR^\leftrightarrow} p$
but:
- $p \not \mathrel {\RR^\leftrightarrow} p$
Therefore $\RR^\leftrightarrow$ is not transitive.
$\blacksquare$