# Preordering induces Ordering

## Theorem

Let $\struct {S, \RR}$ be a relational structure such that $\RR$ is a preordering.

Let $\sim_\RR$ denote the equivalence on $S$ induced by $\RR$:

- $x \sim_\RR y$ if and only if $x \mathrel \RR y$ and $y \mathrel \RR x$

Let $\preccurlyeq_\RR$ be the relation defined on the quotient set $S / {\sim_\RR}$ by:

- $\eqclass x {\sim_\RR} \preccurlyeq_\RR \eqclass y {\sim_\RR} \iff x \mathrel \RR y$

where $\eqclass x {\sim_\RR}$ denotes the equivalence class of $x$ under $\sim_\RR$.

Then $\preccurlyeq_\RR$ is an **ordering**.

## Proof

First we note from Ordering Induced by Preordering is Well-Defined that $\preccurlyeq_\RR$ is a well-defined relation.

Checking in turn each of the criteria for an ordering:

### Reflexivity

Let $A \in S / {\sim_\RR}$.

By the definition of quotient set, $A$ is non-empty.

Thus there exists $a \in A$.

Since $\RR$ is a preordering, it is reflexive.

Hence:

- $a \mathrel \RR a$

So by definition of $\preccurlyeq_\RR$:

- $\eqclass a {\sim_\RR} \preccurlyeq_\RR \eqclass a {\sim_\RR}$

Thus $\preccurlyeq_\RR$ has been shown to be reflexive.

$\Box$

### Transitivity

Let $A, B, C \in S / {\sim_\RR}$ such that $A \preccurlyeq_\RR B$ and $B \preccurlyeq_\RR C$.

Then:

- $\exists a \in A, b_1 \in B: a \mathrel \RR b_1$

- $\exists b_2 \in B, c \in C: b_2 \mathrel \RR c$

By the definition of quotient set:

- $b_1 \sim_\RR b_2$

By definition, $\sim_\RR$ is the equivalence on $S$ induced by $\RR$.

Hence:

- $b_1 \mathrel \RR b_2$

We have:

- $a \mathrel \RR b_1$
- $b_1 \mathrel \RR b_2$
- $b_2 \mathrel \RR c$
- $\mathrel \RR$ is transitive

Hence from Transitive Chaining:

- $a \precsim c$

Thus by the definition of $\mathrel \RR$:

- $A \preccurlyeq_\RR C$

We have that $A$, $B$ and $C$ are arbitrary.

It follows that $\preccurlyeq_\RR $ is transitive.

$\Box$

### Antisymmetry

Let $A, B \in S / {\sim_\RR}$ such that $A \preccurlyeq_\RR B$ and $B \preccurlyeq_\RR A$.

Then:

- $\eqclass a {\sim_\RR} \preccurlyeq_\RR \eqclass b {\sim_\RR}$
- $\eqclass b {\sim_\RR} \preccurlyeq_\RR \eqclass a {\sim_\RR}$

That is:

By definition of $S / {\sim_\RR}$:

- $a \mathrel \RR b$
- $b \mathrel \RR a$

But by definition of $\sim_\RR$, that means:

- $a \sim_\RR b$

Hence:

- $a, b \in \eqclass a {\sim_\RR}$

and:

- $a, b \in \eqclass b {\sim_\RR}$

Hence by Fundamental Theorem on Equivalence Relations:

- $\eqclass a {\sim_\RR} = \eqclass b {\sim_\RR}$

So $\preccurlyeq_\RR$ has been shown to be antisymmetric.

$\Box$

$\preccurlyeq_\RR$ has been shown to be reflexive, transitive and antisymmetric.

Hence by definition it is an ordering.

$\blacksquare$

## Sources

- 1982: P.M. Cohn:
*Algebra Volume 1*(2nd ed.) ... (previous) ... (next): Chapter $1$: Sets and mappings: Further exercises: $5$ - 1996: Winfried Just and Martin Weese:
*Discovering Modern Set Theory. I: The Basics*... (previous) ... (next): Part $1$: Not Entirely Naive Set Theory: Chapter $2$: Partial Order Relations: Exercise $40 \ \text {(b)}$