Strict Weak Ordering Induces Partition

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $\struct {S, \prec}$ be a relational structure such that $\prec$ is a strict weak ordering on $S$.


Then $S$ can be partitioned into equivalence classes whose equivalence relation is "is non-comparable".


That is, each of the partitions $A$ of $S$ is a relational structure $\struct {\mathbb S, <}$ such that:

$\mathbb S$ is the set of these partitions of $S$;
$<$ is the strict total ordering on $\mathbb S$ induced by $\prec$.


Proof

From the definition of strict weak ordering, we define the symbol $\Bumpeq$ as:

$a \Bumpeq b := \neg a \prec b \land \neg b \prec a$

that is, $a \Bumpeq b$ means "$a$ and $b$ are non-comparable".

Checking in turn each of the criteria for equivalence:


Reflexive

As $\prec$ is antireflexive, by definition $\forall a \in S: \neg a \prec a$.

Hence by the Rule of Idempotence $\neg a \prec a \land \neg a \prec a$ and so $\forall a \in S: a \Bumpeq a$.


Symmetric

We have that $a \Bumpeq b$ is defined as being $\neg a \prec b \land \neg b \prec a$.

It follows from the Rule of Commutation that $\neg b \prec a \land \neg a \prec b$, and so $b \Bumpeq a$.


Transitive

The relation $a \Bumpeq b$ is defined as being transitive in a strict weak ordering.

$\blacksquare$