Reflexive Reduction of Ordering is Strict Ordering
Contents
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)