Reflexive Closure of Transitive Antisymmetric Relation is Ordering

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $S$ be a set.

Let $\prec$ be a transitive, antisymmetric relation on $S$.

Let $\preceq$ be the reflexive closure of $\prec$.


Then $\preceq$ is an ordering on $S$.

Proof

Reflexive

Follows from Reflexive Closure is Reflexive.

$\Box$


Transitive

Follows from Reflexive Closure of Transitive Relation is Transitive.

$\Box$


Antisymmetric

Let $a, b \in S$.

Suppose that $a \ne b$.

Then by the definition of the diagonal relation,

$\left({(a,b)}\right) \notin \Delta_S$ and
$\left({(b,a)}\right) \notin \Delta_S$.

Since $\prec$ is antisymmetric, $\left({(a,b)}\right)$ and $\left({(b,a)}\right)$ are not both in $\prec$.

Thus $a \not\preceq b$ or $b \not\preceq a$.

$\blacksquare$