Reflexive Reduction of Transitive Antisymmetric Relation is Strict Ordering

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $S$ be a set.

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

Let $\mathcal R^\ne$ denote the reflexive reduction of $\mathcal R$.


Then $\mathcal R^\ne$ is a strict ordering.


Proof

To show that $\mathcal R^\ne$ is a strict ordering, it is sufficient to show that $\mathcal R^\ne$ is antireflexive and transitive.


Antireflexive

Follows from Reflexive Reduction is Antireflexive.

$\Box$


Transitive

Let $a, b, c \in S$.

Let $a \mathrel{\mathcal R^\ne} b$ and $b \mathrel{\mathcal R^\ne} c$.

By the definition of reflexive reduction:

$a \ne b$ and $a \mathrel{\mathcal R} b$
$b \ne c$ and $b \mathrel{\mathcal R} c$

Since $\mathrel{\mathcal R}$ is transitive:

$a \mathrel{\mathcal R} c$


Suppose, with a view to deriving a contradiction, that $a = c$.

Since $a \mathrel{\mathcal R} b$ it follows that $c \mathrel{\mathcal R} b$.

Since $c \mathrel{\mathcal R} b$, $b \mathrel{\mathcal R} c$, and $\mathrel{\mathcal R}$ is antisymmetric, $b = c$.

But this contradicts $b \ne c$.

The conclusion is that $a \ne c$.


Recall that $a \mathrel{\mathcal R} c$.

By the definition of reflexive reduction:

$a \mathrel{\mathcal R^\ne} c$

$\blacksquare$