Reflexive Reduction of Ordering is Strict Ordering

Theorem

Let $\mathcal R$ be an ordering on a set $S$.

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

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

Proof 1

Antireflexivity

Follows from Reflexive Reduction is Antireflexive.

$\Box$

Transitivity

Suppose $\left({x, y}\right), \left({y, z}\right) \in \mathcal R^\ne$.

By antireflexivity $x \ne y$ and $y \ne z$.

We consider the two remaining cases.

Case 1: $x = z$

If $x = z$ then:

$\left({x, y}\right), \left({y, x}\right) \in \mathcal R^\ne$

and so:

$\left({x, y}\right), \left({y, x}\right) \in \mathcal R$

Then by the antisymmetry of $\mathcal R$:

$x = y$

and:

$\left({x, x}\right) \in \mathcal R^\ne$

which contradicts that $\mathcal R^\ne$ is antireflexive.

Case 2: $x \ne z$

By the transitivity of $\mathcal R$:

$\left({x, z}\right) \in \mathcal R$

and by $x$ and $z$ being distinct:

$\left({x, z}\right) \notin \Delta_S$

It follows by the definition of reflexive reduction:

$\left({x, z}\right) \in \mathcal R^\ne$

Hence $\mathcal R^\ne$ is transitive.

$\blacksquare$

Proof 2

By definition, an ordering is both reflexive and transitive.

The result then follows from Reflexive Reduction of Transitive Antisymmetric Relation is Strict Ordering.

$\blacksquare$

Sources

• 1965: Seth Warner: Modern Algebra ... (previous) ... (next): $\S 14$ (passim)