Transitive Relation whose Symmetric Closure is not Transitive

From ProofWiki
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$