Order-Extension Principle/Proof 1

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: \paren {a \preceq b \implies a \le b}$


Proof

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 $\TT$ be the set of orderings on $S$ that extend $\preceq$, ordered by inclusion.

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

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

Thus every chain in $\TT$ has an upper bound in $\TT$.

By Zorn's Lemma, $\TT$ has a maximal element, $\RR$.


$\RR$ is seen to be the total ordering whose existence is to be demonstrated, as follows:

Suppose that:

$\exists a, b \in S: \tuple {a, b} \notin \RR \land \tuple {b, a} \notin \RR$

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

$\RR' := \RR \cup \set {\tuple {a, b} }$

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

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

But $\RR'^- \supsetneq \RR$, contradicting the maximality of $\RR$.

Thus, $\RR$ is a total ordering.

$\blacksquare$


Axiom of Choice

This proof depends on the Axiom of Choice, by way of Zorn's Lemma.

Because of some of its bewilderingly paradoxical implications, the Axiom of Choice is considered in some mathematical circles to be controversial.

Most mathematicians are convinced of its truth and insist that it should nowadays be generally accepted.

However, others consider its implications so counter-intuitive and nonsensical that they adopt the philosophical position that it cannot be true.