5.2 Completeness

5.21   Definition (Completeness axiom.) Let $F$ be an ordered field. We say that $F$ is complete if it satisfies the condition:

Every binary search sequence in $F$ converges to a unique point in $F$.

5.22   Example. The field $\mbox{{\bf Q}}$ is not complete, since in example 5.16 we found a binary search sequence in $\mbox{{\bf Q}}$ that does not converge.

5.23   Definition (Real field, $\mbox{{\bf R}}$.) A real field is a complete ordered field. We will use the name $\mbox{{\bf R}}$ to denote a real field.

5.24   Remark. It is not at all clear that any real fields exist. If real fields do exist, there is a question of uniqueness; i.e., is it the case that any two real fields are ``essentially the same"? I don't want to worry about what mathematical existence means, so let me formulate the questions: Are the axioms for a real field consistent; i.e., is it the case that no contradictions can be derived from them? Note that we are not entirely free to throw axioms together. If I were to make a definition that a 3-field is an ordered field in which $3=0$, I would immediately get a contradiction: $3=0$ and $3>0$. All I can say about consistency is that no contradictions have been found to follow from the real field axioms. There exist proofs that any two real fields are essentially the same, cf. [35, page 129]. (This source uses a different statement for the completeness axiom than we have used, but the axiom system is equivalent to ours.) There also exist constructions of pairs of very different real fields, cf. [41].

In what follows, I am going to assume that there is a real field $\mbox{{\bf R}}$ (which I'll call the real numbers). Any theorems proved will be valid in all real fields.

5.25   Theorem (Archimedean property 1.) Let $\mbox{{\bf R}}$ be a real field, and let $x\in\mbox{{\bf R}}$. Then there is an integer $n\in\mbox{{\bf N}}$ such that $n>x$.

Proof: Let $x\in\mbox{{\bf R}}$, and suppose (in order to get a contradiction) that there is no $n\in\mbox{{\bf N}}$ with $n>x$. Then $x\geq n$ for all $n$. Now $${ \left\{ \left[ 0,{x\over {2^n}}\right]\right\}}$$ is a binary search sequence in $\mbox{{\bf R}}$. Since $x\geq 2^n$, I have $${ 1\leq {x\over {2^n}}}$$ for all $n\in\mbox{{\bf N}}$. We see that $${ \left\{\left[ 0,{x\over {2^n}}\right]\right\}\to 1}$$, but clearly $${ \left\{\left[ 0,{x\over {2^n}}\right]\right\}\to 0}$$. Since completeness of $\mbox{{\bf R}}$ implies that a binary search sequence has a unique limit, this yields a contradiction, and proves the theorem. $\mbox{ $\mid\!\mid\!\mid$}$

5.26   Corollary (Archimedean property 2.) Let $x\in\mbox{{\bf R}}\backslash\{0\}$. Then there is some $n\in\mbox{{\bf Z}}_{\geq 1}$ such that $${ {1\over n}<\vert x\vert}$$.

Proof: By the theorem, there is some $n\in\mbox{{\bf Z}}_{\geq 1}$ with $${n>{1\over {\vert x\vert}}}$$. Then $${ {1\over n}<\vert x\vert}$$. $\mid\!\mid\!\mid$

5.27   Corollary (Archimedean property 3.) Let $x$ be a real number, and let $C$ be a positive real number. Suppose

$$\vert x\vert \leq {C\over n} \mbox{ for all }n \in \mbox{{\bf Z}}_{\geq 1}.$$ (5.28)

Then $x=0$.

Proof: Let $x\in\mbox{{\bf R}}$, and let $C \in \mbox{${\mbox{{\bf R}}}^{+}$}$ satisfy

$$\vert x\vert \leq {C\over n} \mbox{ for all }n \in \mbox{{\bf Z}}_{\geq 1}.$$ (5.29)

Suppose, in order to get a contradiction, that $x\neq 0$. Then by Archimedian property 2 there is some $n\in\mbox{{\bf Z}}_{\geq 1}$ such that ${1\over n} < {\vert x\vert \over C}$, i.e. ${C\over n} < \vert x\vert$. This contradicts (5.29). $\mid\!\mid\!\mid$

5.30   Theorem. If $t\in\mbox{{\bf R}}$, then there is an integer $n$ and a number $\varepsilon\in[0,1)$ such that $t=n+\varepsilon$.

In order to prove this theorem, I will use the following lemma.

5.31   Lemma. If $t\in\mbox{{\bf R}}$, then the interval $(t,t+1]$ contains an integer.

Proof:

Case 1.

$t\in[0,\infty)$: Suppose $t\in[0,\infty)$ and $(t,t+1]$ does not contain an integer. I will show that $t\geq n$ for all $n\in\mbox{{\bf N}}$. This contradicts the Archimedean property, so no such $t$ can exist. For each $n\in\mbox{{\bf N}}$, let $P(n)=``n\leq t$". Then $P(0)$ is true, since I assumed that $t\in[0,\infty)$. Let $n\in\mbox{{\bf N}}$ be a number such that $P(n)$ is true; i.e., $n\leq t$. If $n+1$ were $>t$, we'd have $t<n+1\leq t+1$, and this cannot happen, since $(t,t+1]$ contains no integers. Hence,

$$P(n)\mbox{$\hspace{1ex}\Longrightarrow\hspace{1ex}$}n+1\leq t\mbox{$\hspace{1ex}\Longrightarrow\hspace{1ex}$}P(n+1),$$

and by induction, $t\geq n$ for all $n\in\mbox{{\bf N}}$. This gives the desired contradiction.

Case 2.

$t\in\mbox{{\bf R}}^-$: If $t\in\mbox{{\bf R}}^-$, then by Case 1 there is an integer $n$ with

$$-t<n\leq -t+1.$$

Then

$$t\leq -n+1<t+1.$$

If $t<-n+1$, then $(t,t+1]$ contains $-n+1$. If $t=-n+1$, then $(t,t+1]=(-n+1,-n+2]$ contains $-n+2$. $\mid\!\mid\!\mid$

Proof of theorem 5.30. Let $t\in\mbox{{\bf R}}$. By the lemma, there is an integer $n$ with $t<n\leq t+1$. Then

$$0\leq t-n+1<1,$$

and $t=(n-1)+(t-n+1)$ gives the desired decomposition. $\mid\!\mid\!\mid$

5.32   Theorem. There is a number $x\in\mbox{{\bf R}}$ such that $x^2=2$.

Proof: Let $\{[a_n,b_n]\}$ be the binary search sequence constructed in example 5.16. We know there is a unique $x\in\mbox{{\bf R}}$ such that $0\leq a_n\leq x\leq b_n$ for all $n$. Then $0\leq a_n^2\leq x^2\leq b_n^2$, and by our construction $0\leq a_n^2\leq 2\leq b_n^2$ for all $n\in\mbox{{\bf N}}$, so

$$\vert 2-x^2\vert\leq b_n^2-a_n^2=(b_n-a_n)(b_n+a_n)\leq {1\over {2^n}}\cdot 4\leq {4\over n}$$ (5.33)

for all $n\in\mbox{{\bf Z}}_{\geq 1}$.

By Archimedean property 3, we conclude that $2-x^2=0$, i.e., $x^2=2$. $\mid\!\mid\!\mid$

5.34   Theorem. Let $x\in\mbox{{\bf R}}$. Then there is a binary search sequence $\{[a_n,b_n]\}$ in $\mbox{{\bf R}}$ such that $a_n\in\mbox{{\bf Q}}$ and $b_n\in\mbox{{\bf Q}}$ for all $n$, and such that $\{[a_n,b_n]\}\to x$.

Proof: I will suppose $x\geq 0$. The case where $x\leq 0$ is left to you. By the Archimedean property of $\mbox{{\bf R}}$, there is an integer $N$ such that $N>x$, so $x\in[0,N]$. Now build a binary search sequence $\{[a_n,b_n]\}$ as follows:

$$\begin{eqnarray*}[a_0,b_0]&=&[0,N] \cr [a_{n+1},b_{n+1}]&=&\cases{ \left[a_n, {{... ...over 2},b_n\right] &if $x>\left[ {{a_n+b_n}\over 2}\right]$.\cr} \end{eqnarray*}$$

From the construction, we have $a_n\leq a_{n+1}\leq b_{n+1}\leq b_n$ and $${b_n-a_n={{b_0-a_0}\over {2^n}}}$$. A simple induction argument shows that $a_n\in\mbox{{\bf Q}}$ and $b_n\in\mbox{{\bf Q}}$ for all $n\in\mbox{{\bf N}}$, and an induction proof similar to the one in example 5.16 shows that
$a_n\leq x\leq b_n$ for all $n\in\mbox{{\bf N}}$ so $\{[a_n,b_n]\}\to x$. $\mid\!\mid\!\mid$