Strict Weak Ordering Induces Partition

From ProofWiki
Jump to: navigation, search

Theorem

Let $\left({S, \prec}\right)$ 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 $\left({\mathbb S, <}\right)$ such that:

  • $\mathbb S$ is the set of these partitions of $S$;


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$