Strictly Precedes is Strict Ordering

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $\left({S, \preceq}\right)$ be an ordered set.

Let $\prec$ be the relation on $S$ defined as:

$a \prec b \iff (a \ne b) \land (a \preceq b)$

That is, $a \prec b$ if and only if $a$ strictly precedes $b$.


Then:

$a \preceq b \iff (a = b) \lor (a \prec b)$

and $\prec$ is a strict ordering on $S$.


Proof

We are given that $\left({S, \preceq}\right)$ is an ordered set.

Antireflexive

Follows immediately:

$\forall a \in S: a = a \implies a \not \prec a$


$\Box$

Transitive

Suppose $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$, it is not then possible for $b \preceq c$. So a condition for transitivity to be violated will not arise in this circumstance.

If either $a = b$ or $b = c$, then $a \not \prec b$ and $b \not \prec c$ by antireflexivity of $\prec$.

So $\prec$ is shown to be transitive.

$\Box$

Asymmetric

A direct application of Antireflexive and Transitive Relation is Asymmetric.


Hence the result.

$\blacksquare$

Let $a \preceq b$.

Either $a = b$ or $a \ne b$ by the Law of Excluded Middle.

If $a = b$ we are done.

Suppose $a \ne b$. Then it follows that $a \prec b$.

Thus $a \preceq b \implies (a = b) \lor (a \prec b)$.

$\blacksquare$


Now let $(a = b) \lor (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