Order-Extension Principle/Strict/Proof 1

Theorem

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

Let $\mathcal A$ be the set of relations $A$ on $S$ with the property that the transitive closure $A^+$ of $A$ is a strict ordering of $S$.

For each $\left({x, y}\right) \in S \times S$, let $\left({x, y}\right)' = \left({y, x}\right)$.

Let $A \in \mathcal A$.

Let $\left({x, y}\right) \in S \times S$.

Let $\left({x, y}\right) \in A^+$.

Then:

$\left({A \cup \left\{ {\left({x, y}\right)}\right\} }\right)^+ = A^+$

so:

$A \cup \left\{ {\left({x, y}\right)}\right\} \in \mathcal A$

Let $\left({y, x}\right) \in A^+$.

Then:

$\left({ A \cup \left\{ {\left({y, x}\right)}\right\} }\right)^+ = A^+$

so:

$A \cup \left\{ {\left({x, y}\right)'}\right\} = A \cup \left\{ {\left({y, x}\right)}\right\} \in \mathcal A$

Otherwise, $x$ and $y$ are non-comparable by $A^+$.

So by Strict Ordering can be Expanded to Compare Additional Pair:

$A \cup \left\{ {\left({x, y}\right)}\right\} \in \mathcal A$

Thus it has been shown that for each $A \in \mathcal A$ and each $\left({x, y}\right) \in S$, either:

$A \cup \left\{ {\left({x, y}\right)}\right\} \in \mathcal A$

or:

$A \cup \left\{ {\left({x, y}\right)'}\right\} \in \mathcal A$

$\Box$

Let $A \subseteq S \times S$.

Let $A \in \mathcal A$.

Let $F$ be a finite subset of $A$.

Since $A^+$ is a strict ordering, it is asymmetric.

Since Transitive Closure is Closure Operator, $F^+ \subseteq A^+$.

So $F^+$ is also asymmetric.

Since $F^+$ is also transitive, it is a strict ordering.

So $F \in \mathcal A$.

Suppose instead that each finite subset of $A$ is in $\mathcal A$.

We must show that $A^+$ is antireflexive.

Suppose for the sake of contradiction that for some $x \in S$, $\left({x, x}\right) \in A^+$.

Then by the definition of transitive closure, there are elements $y_0, \dots, y_n$ such that $x = y_0 = y_n$ and:

$\left({y_0, y_1}\right), \left({y_1, y_2}\right), \dotsc, \left({y_{n - 1}, y_n}\right) \in A$

Let $F = \left\{ {\left({y_0, y_1}\right), \left({y_1, y_2}\right), \dotsc, \left({y_{n - 1}, y_n}\right)}\right\}$.

Then $F$ is a finite subset of $A$.

But $\left({x, x}\right) \in F^+$, contradicting the fact that $F \in \mathcal A$.

Thus we see that $A^+$ is antireflexive, and thus a strict ordering of $S$.

Therefore, $\mathcal A$ has finite character.

$\Box$

Note that ${\prec} = {\prec^+}$, so ${\prec} \in \mathcal A$.

By the Restricted Tukey-Teichmüller Theorem (Strong Form), there exists an $R \in \mathcal A$ such that:

${\prec} \subseteq R$

For each $\left({m, n}\right) \in S \times S$, either $\left({m, n}\right) \in R$ or $\left({n, m}\right) = \left({m, n}\right)' \in R$.

Then:

$R^+$ is a strict total ordering of $S$.

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

$\blacksquare$

Boolean Prime Ideal Theorem

This proof depends on the Boolean Prime Ideal Theorem (BPI), by way of Restricted Tukey-Teichmüller Theorem.

Although not as strong as the Axiom of Choice, the BPI is similarly independent of the Zermelo-Fraenkel axioms.

As such, mathematicians are generally convinced of its truth and believe that it should be generally accepted.