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.