Strictly Precedes is Strict Ordering

From ProofWiki
Jump to navigation Jump to search



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$

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