Strictly Precedes is Strict Ordering
Work In Progress In particular: Needs a complete rewrite. Use (and partially merge with?) Reflexive Reduction of Transitive Antisymmetric Relation is Strict Ordering and Reflexive Reduction of Antisymmetric Relation is Asymmetric. This had an unsupported statement looking an awful lot like Extended Transitivity that really did not seem to belong, so I yanked it. If any sources need to be adjusted as a result, that should probably happen. You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by completing it. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{WIP}} from the code. |
Theorem
Let $\struct {S, \preceq}$ be an ordered set.
Let $\prec$ be the relation on $S$ defined as:
- $a \prec b \iff \paren {a \ne b} \land \paren {a \preceq b}$
That is, $a \prec b$ if and only if $a$ strictly precedes $b$.
Then:
- $a \preceq b \iff \paren {a = b} \lor \paren {a \prec b}$
and $\prec$ is a strict ordering on $S$.
Proof
We are given that $\struct {S, \preceq}$ is an ordered set.
Antireflexivity
Follows immediately:
- $\forall a \in S: a = a \implies a \nprec a$
This article, or a section of it, needs explaining.
You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by explaining it.
To discuss this page in more detail, feel free to use the talk page.
When this work has been completed, you may remove this instance of{{Explain}}
from the code.
Hence $\prec$ is antireflexive by definition.
$\Box$
Transitivity
Let $a, b, c \in S$ such that $a \preceq b, b \preceq c$.
$a \preceq b \land b \preceq c \implies a \preceq c$ from transitivity of $\preceq$.
Now suppose $a \preceq b, b \preceq c, a = c$.
Then:
- $a \preceq b$
but because of the antisymmetry of $\preceq$:
- $b \npreceq c$
So a condition for transitivity to be violated will not arise in this circumstance.
If either $a = b$ or $b = c$, then $a \nprec b$ and $b \nprec c$ by antireflexivity of $\prec$.
So $\prec$ is shown to be transitive.
$\Box$
Asymmetry
A direct application of Antireflexive and Transitive Relation is Asymmetric.
Hence $\prec$ is shown to be asymmetric.$\blacksquare$
Let $a \preceq b$.Either $a = b$ or $a \ne b$ by the Law of Excluded Middle.
If $a = b$ the proof is complete.
Suppose $a \ne b$. Then it follows that $a \prec b$.
Thus $a \preceq b \implies \paren {a = b} \lor \paren {a \prec b}$.
$\blacksquare$
Now let $\paren {a = b} \lor \paren {a \prec b}$.If $a = b$ then $a \preceq b$ by the reflexivity of $\preceq$.
If $a \prec b$ then $a \preceq b$ by definition.
$\blacksquare$
Sources
- 1967: Garrett Birkhoff: Lattice Theory (3rd ed.) ... (next): $\S \text I.1$: Lemma $1$