Order-Extension Principle

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $S$ be a set.

Let $\preceq$ be an ordering on $S$.


Then there exists a total ordering $\le$ on $S$ such that:

$\forall a, b \in S: \left({a \preceq b \implies a \le b}\right)$


Strict Orderings

Let $S$ be a set.

Let $\prec$ be a strict ordering on $S$.


Then there exists a strict total ordering $<$ on $S$ such that:

$\forall a, b \in S: a \prec b \implies a < b$


Proof 1

Let $\preceq$ be an ordering on the set $S$.

If $\preceq$ is a total ordering, the result is complete.


Suppose, then, that $\preceq$ is not a total ordering.

Let $T$ be the set of orderings on $S$ that extend $\preceq$, ordered by inclusion.

Let $C$ be a chain in $T$.

By Union of Nest of Orderings is Ordering, $\bigcup C$ is an ordering.

Thus every chain in $T$ has an upper bound in $T$.

By Zorn's Lemma, $T$ has a maximal element, $\le$.


$\le$ is seen to be a total ordering, as follows:

Suppose that $a, b \in S$, $a \not \le b$, and $b \not \le a$.

Let $\le'$ be the relation defined as:

$\le' \mathop {:=} \le \cup \left\{{(a, b)}\right\}$

Let $\le'^-$ be the transitive closure of $\le'$.

Then by Ordering can be Expanded to compare Additional Pair, $\le'^-$ is an ordering.

But $\le'^- \mathop {\supsetneq} \le$, contradicting the maximality of $\le$.

Thus, $\le$ is a total ordering.

$\blacksquare$


Proof 2

Let $\prec$ be the reflexive reduction of $\preceq$.

By Reflexive Reduction of Ordering is Strict Ordering, $\prec$ is a strict ordering.

By the strict form of the Order-Extension Principle, there exists a strict total ordering $<$ on $S$ such that:

$\forall a, b \in S: \left({a \prec b \implies a < b}\right)$

Let $\le$ be the reflexive closure of $<$.

Let $a, b \in S$.

If $a \preceq b$, then by Law of Excluded Middle either $a \prec b$ or $a = b$.

If $a = b$, then by the definition of reflexive closure, $a \le b$.

If $a \prec b$, then by the choice of $<$, $a < b$ so $a \le b$.

Thus for all $a, b \in S$, $a \preceq b \implies a < b$.

By Reflexive Closure of Strict Total Ordering is Total Ordering, $\le$ is a total ordering.

$\blacksquare$


Remarks


As shown in Proof 2, the order-extension principle is weaker than the Boolean Prime Ideal Theorem (BPI).

It is known that it is in fact strictly weaker than BPI.

However, it cannot be proved in Zermel-Fraenkel set theory without the Axiom of Choice. In fact it is known to be strictly stronger than the Ordering Principle.