Symmetric Closure of Ordering may not be Transitive

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $\struct {S, \preceq}$ be an ordered set.

Let $\preceq^\leftrightarrow$ be the symmetric closure of $\preceq$.


Then it is not necessarily the case that $\preceq^\leftrightarrow$ is transitive.


Proof

Proof by Counterexample:

Let $S = \set {a, b, c}$ where $a$, $b$, and $c$ are distinct.

Let:

${\preceq} = \set {\tuple {a, a}, \tuple {b, b}, \tuple {c, c}, \tuple {a, c}, \tuple {b, c} }$:


Then $\preceq$ is an ordering, but $\preceq^\leftrightarrow$ is not transitive, as follows:


$\preceq$ is reflexive because it contains the diagonal relation on $S$.

That $\preceq$ is transitive and antisymmetric can be verified by inspecting all ordered pairs of its elements.

Thus $\preceq$ is an ordering.


Now consider $\preceq^\leftrightarrow$, the symmetric closure of $\preceq$:

${\preceq^\leftrightarrow} = {\preceq} \cup {\preceq}^{-1} = \set{\tuple {a, a}, \tuple {b, b}, \tuple {c, c}, \tuple {a, c}, \tuple {c, a}, \tuple {b, c}, \tuple {c, b} }$

by inspection.


Now $\tuple {a, c} \in {\preceq^\leftrightarrow}$ and $\tuple {c, b} \in {\preceq^\leftrightarrow}$, but $\tuple {a, b} \notin {\preceq^\leftrightarrow}$.

Thus $\preceq^\leftrightarrow$ is not transitive.

$\blacksquare$