Continuum Property implies Well-Ordering Principle

From ProofWiki
Jump to navigation Jump to search

Theorem

The Continuum Property of the positive real numbers $\R_{\ge 0}$ implies the Well-Ordering Principle of the natural numbers $\N$.


Proof

Suppose that the set of positive real numbers $\R_{\ge 0}$ has the Continuum Property.


Aiming for a contradiction, let $T \subseteq \N$ be a subset of $\N$ which has no smallest element.

Then:

$\forall t \in T: \exists u \in T: u < t$


Let $A \in \R_{\ge 0}$.

For every $t \in T$, let $a_t = \dfrac A {2^t}$.

We have that $t \in \N$, so $t \ge 0$.

Therefore $2^t \ge 1$.

This $a_t$ can never be greater than $A$.

Therefore $\left\{{a_t: t \in T}\right\}$ has an upper bound.

As $\R_{\ge 0}$ has the Continuum Property, it follows that $\left\{{a_t: t \in T}\right\}$ has a supremum $B$.

We have that $\dfrac {7 B} 8 < B$.

Thus $\dfrac {7 B} 8$ is not an upper bound of $\left\{{a_t: t \in T}\right\}$.

Therefore there exists $m \in T$ such that:

$a_m > \dfrac {7B} 8$

Then there is $n \in T$ such that $n < m$.

Let $n = m - p$.

Then:

\(\displaystyle a_n\) \(=\) \(\displaystyle \dfrac A {2^n}\)
\(\displaystyle \) \(=\) \(\displaystyle \dfrac A {2^{m - p} }\)
\(\displaystyle \) \(=\) \(\displaystyle \dfrac {A \cdot 2^p} {2^m}\)
\(\displaystyle \) \(\ge\) \(\displaystyle \dfrac {A \cdot 2} {2^m}\)
\(\displaystyle \) \(=\) \(\displaystyle 2 \cdot a_m\)
\(\displaystyle \) \(>\) \(\displaystyle 2 \cdot \dfrac {7B} 8\)
\(\displaystyle \) \(=\) \(\displaystyle \dfrac {7B} 4\)
\(\displaystyle \) \(>\) \(\displaystyle B\)

Therefore $a_n > B$.

This contradicts the supposition that $B$ is the supremum of $\left\{{a_t: t \in T}\right\}$

Thus our initial supposition that $T \subseteq \N$ has no smallest element was false.

As $T$ is arbitrary, it follows that each $T \subseteq \N$ has a smallest element.

Thus the Well-Ordering Principle holds for $\N$, as was to be proved.

$\blacksquare$


Also see