next up previous index
Next: 5.2 Completeness Up: 5. Real Numbers Previous: 5. Real Numbers   Index

5.1 Sequences and Search Sequences

5.1   Definition (Sequence.) Let $A$ be a set. A sequence in $A$ is a function $f\colon \mbox{{\bf N}}\to A$. I sometimes denote the sequence $f$ by $\{f(n)\}$ or $\{f(0),f(1),f(2),\cdots\}$. For example, if $f\colon\mbox{{\bf N}}\to\mbox{{\bf Q}}$ is defined by $\displaystyle {f(n)={1\over {n+1}}}$, I might write

\begin{displaymath}f=\left\{ {1\over {n+1}}\right\}=\left\{1,{1\over 2},{1\over 3},\cdots\right\}.\end{displaymath}

5.2   Warning. The notation $\{f(0),f(1),f(2),\cdots\}$ is always ambiguous. For example,

\begin{displaymath}\{1,2,4,8,16,\cdots\}\end{displaymath}

might denote $\{2^n\}$. It might also denote $\{\phi(n)\}$ where $\phi(n)$ is the number of regions into which a circle is divided when all the segments joining the vertices of an inscribed regular $(n+1)$-gon are drawn.

\psfig{file=not2n.ps,angle=-90,width=5.5in}

5.3   Entertainment. Show that $\phi(4)=2^4$, but that it is not true that $\phi(n)=2^n$ for all $n\in\mbox{{\bf N}}$.

5.4   Warning. The notation for a sequence and a set are the same, but a sequence is not a set. For example, as sets,

\begin{displaymath}\{1,2,3,4,5,6,\cdots\}=\{2,1,4,3,6,5,\cdots\}.\end{displaymath}

But as sequences,

\begin{displaymath}\{1,2,3,4,5,6,\cdots\}\neq\{2,1,4,3,6,5,\cdots\}.\end{displaymath}

5.5   Notation ( $\mbox{{\bf Z}}_{\geq k}$) Recall from section 3.65, that If $k\in\mbox{{\bf Z}}$, then

\begin{displaymath}\mbox{{\bf Z}}_{\geq k}=\{n\in\mbox{{\bf Z}}\colon n\geq k\}. \end{displaymath}

Thus, $\mbox{{\bf Z}}_{\geq 0}=\mbox{{\bf N}}$. Occasionally I will want to consider sequences whose domain is $\mbox{{\bf Z}}_{\geq k}$ where $k\neq 0$. I will denote such a sequence by

\begin{displaymath}\{f(n)\}_{n\geq k}.\end{displaymath}

Hence, if

\begin{displaymath}f=\{1,2,3,\cdots\},\end{displaymath}

then $f(n)=n+1$ for all $n\in\mbox{{\bf N}}$, and if

\begin{displaymath}g=\{1,2,3,\cdots\}_{n\geq 1},\end{displaymath}

then $g(n)=n$ for all $n\in\mbox{{\bf Z}}_{\geq 1}$.

5.6   Remark. Most of the results we prove for sequences $\{f(n)\}$ have obvious analogues for sequences $\{f(n)\}_{n\geq k}$, and I will assume these analogues without explanation.

5.7   Examples. $\qquad$ $\{i^n\}=\{1,i,-1,-i,1,i,\cdots\}$ is a sequence in $\mbox{{\bf C}}_{\mathbf{Q}}$.

\begin{displaymath}\left\{\left[ 0,{1\over n}\right]\right\}_{n\geq 1}=\left\{[0...
...ft[0,{1\over
2}\right],\left[0,{1\over 3}\right],\cdots\right\}\end{displaymath}

is a sequence of intervals in an ordered field $F$.

5.8   Definition (Open and closed intervals.) An interval $J$ in an ordered field is closed if it contains all of its endpoints. $J$ is open if it contains none of its endpoints. Thus,

\begin{displaymath}\emptyset,[a,b],(-\infty,a],[a,\infty),(-\infty,\infty) \mbox{ are closed intervals. }\end{displaymath}


\begin{displaymath}\emptyset,(a,b),(-\infty,a),(a,\infty),(-\infty,\infty) \mbox{ are open intervals. }\end{displaymath}


\begin{displaymath}(a,b],[a,b) \mbox{ where } a<b\mbox{ are neither open nor closed. }\end{displaymath}

5.9   Definition (Binary search sequence.) Let $F$ be an ordered field. A binary search sequence $\{[a_n,b_n]\}$ in $F$ is a sequence of closed intervals with end points $a_n,b_n$ in $F$ such that
1)
$[a_{n+1},b_{n+1}]\subset [a_n,b_n]$ for all $n\in\mbox{{\bf N}}$, and
2)
$\displaystyle {b_n-a_n={{b_0-a_0}\over {2^n}}}$ for all $n\in\mbox{{\bf N}}$.
Condition 1) is equivalent to

\begin{displaymath}a_n\leq a_{n+1}\leq b_{n+1}\leq b_n \mbox{ for all } n\in\mbox{{\bf N}}.\end{displaymath}

5.10   Warning. Note that the intervals in a binary search sequence are closed. This will be important later.

5.11   Definition (Convergence of search sequence.) Let $F$ be an ordered field, let $\{[a_n,b_n]\}$ be a binary search sequence in $F$, and let $x\in F$. We say $\{[a_n,b_n]\}$ converges to $x$ and write $\{[a_n,b_n]\}\to x$ if $x\in[a_n,b_n]$ for all $n\in\mbox{{\bf N}}$. We say $\{[a_n,b_n]\}$ converges, if there is some $x\in F$ such that $\{[a_n,b_n]\}\to x$. We say $\{[a_n,b_n]\}$ diverges if there is no such $x$.

5.12   Example. Let $F$ be an ordered field. Then $\displaystyle { \left\{\left[0,{1\over
{2^n}}\right]\right\}}$ is a binary search sequence and $\displaystyle {\left\{\left[0,{1\over
{2^n}}\right]\right\}\to 0}$.

5.13   Exercise. Let $F$ be an ordered field, let $a,b\in F$ with $a<b$. Let $\displaystyle {m={{a+b}\over 2}}$. Show that
1)
$a<m<b.$
2)
$\displaystyle { {{m-a}}={{b-m}}={1\over 2}(b-a)}.$
(Conditions 1) and 2) say that $m$ is the midpoint of $a$ and $b$.)

5.14   Exercise. Let $F$ be an ordered field and let $a,b\in F$ with $a\leq b$ and let $c,d$ be points in $[a,b]$. Show that

\begin{displaymath}\vert c-d\vert \leq b-a;\end{displaymath}

i.e., if two points lie in an interval then the distance between the points is less than or equal to the length of the interval.

5.15   Exercise. A Show that $2^n\geq n$ for all $n\in\mbox{{\bf N}}$.

5.16   Example (A divergent binary search sequence.) Define a binary search sequence $\{[a_n,b_n]\}$ in $\mbox{{\bf Q}}$ by the rules

\begin{eqnarray*}[a_0,b_0]&=& [1,2]. \cr
[a_{n+1},b_{n+1}] &=& \cases{ \left[ a_...
...er 2},b_n\right] &if $\left({{a_n+b_n}\over 2}\right)^2 <2$.\cr}
\end{eqnarray*}



Thus,

\begin{displaymath}{{a_0+b_0}\over 2}={{1+2}\over 2}={3\over 2}; \hspace{.2in}\l...
...>2, \mbox{ so }[a_1,b_1] = \left[ {2\over 2},{3\over 2}\right];\end{displaymath}


\begin{displaymath}{{a_1+b_1}\over 2}={{ {2\over 2}+{3\over 2}}\over 2} ={5\over...
...}<2, \mbox{ so } [a_2,b_2]=\left[ {5\over
4},{6\over 4}\right];\end{displaymath}


\begin{displaymath}{{a_2+b_2}\over 2}={{ {5\over 4}+{6\over 4}}\over 2}={{11}\ov...
...mbox{ so } [a_3,b_3]=\left[
{{11}\over 8},{{12}\over 8}\right].\end{displaymath}

Since $\displaystyle { {{a_n+b_n}\over 2}}$ is the midpoint of $[a_n,b_n]$, we have

\begin{displaymath}[a_{n+1},b_{n+1}]\subset [a_n,b_n]\end{displaymath}

and
\begin{displaymath}
b_{n+1}-a_{n+1}={1\over 2}(b_n-a_n)
\end{displaymath} (5.17)

It follows from (5.17) that

\begin{displaymath}b_n-a_n={1\over {2^n}}(b_0-a_0) \mbox{ for all } n\in\mbox{{\bf N}}.\end{displaymath}

Hence $\{[a_n,b_n]\}$ is a binary search sequence. For each $n\in\mbox{{\bf N}}$, let $P(n)$ be the proposition

\begin{displaymath}P(n)=``a_n^2<2\leq b_n^2.''\end{displaymath}

Then $P(0)$ says $1^2<2\leq 2^2$, so $P(0)$ is true. Let $n\in\mbox{{\bf N}}$. If $\displaystyle {\left( {{a_n+b_n}\over 2}\right)^2\geq 2}$, then

\begin{eqnarray*}
P(n)&\mbox{$\Longrightarrow$}& a_n^2<2\leq b_n^2\mbox{$\hspace...
..._{n+1}^2< 2\leq b_{n+1}^2 \\
&\mbox{$\Longrightarrow$}& P(n+1).
\end{eqnarray*}



If $\displaystyle {\left( {{a_n+b_n}\over 2}\right)^{\!\!2}<2}$, then

\begin{eqnarray*}
P(n)&\mbox{$\Longrightarrow$}& a_n^2<2\leq b_n^2\mbox{$\hspace...
..._{n+1}^2< 2\leq b_{n+1}^2 \\
&\mbox{$\Longrightarrow$}& P(n+1).
\end{eqnarray*}



Hence, in all cases, $P(n) \mbox{$\hspace{1ex}\Longrightarrow\hspace{1ex}$}P(n+1)$, and by induction, $a_n^2<2\leq b_n^2$ for all $n\subset\mbox{{\bf N}}$. Since $x^2\neq 2$ for all $x\in\mbox{{\bf Q}}$, we have
\begin{displaymath}
a_n^2<2<b_n^2 \mbox{ for all } n\in\mbox{{\bf N}}.
\end{displaymath} (5.18)

I now will show that $\{[a_n,b_n]\}$ diverges. Suppose, in order to get a contradiction, that for some $x\in\mbox{{\bf Q}}$, $\{[a_n,b_n]\}\to x$. Then

\begin{displaymath}0\leq a_n\leq x\leq b_n \mbox{ for all } n\in\mbox{{\bf N}},\end{displaymath}

so

\begin{displaymath}a_n^2\leq x^2\leq b_n^2.\end{displaymath}

Combining this with (5.18), we get
\begin{displaymath}
\vert x^2-2\vert\leq b_n^2-a_n^2=(b_n-a_n)(b_n+a_n)
\leq\left({b_0-a_0 \over 2^n}\right)(b_0+b_0)={4\over
{2^n}}
\end{displaymath} (5.19)

for all $n\in\mbox{{\bf N}}$. Since $2$ is not a square in $\mbox{{\bf Q}}$, $x^2-2\neq 0$. Write $\displaystyle {
\vert x^2-2\vert={p\over q}}$, where $p,q\in\mbox{{\bf Z}}_{\geq 1}$. Then

\begin{displaymath}\mbox{ for all }n \in \mbox{{\bf N}},\; {p\over q}\leq {4\over {2^n}},\end{displaymath}

so

\begin{displaymath}\mbox{ for all }n \in \mbox{{\bf N}},\; 2^n\leq {{4q}\over p}\leq 4q.\end{displaymath}

By exercise 5.15A, for all $n\in\mbox{{\bf N}}$,
\begin{displaymath}
n\leq 2^n\leq 4q.
\end{displaymath} (5.20)

Statement (5.20) is false when $n=4q+1$, and hence our assumption that $\{[a_n,b_n]\}\to x$ was false. $\mbox{ $\mid\!\mid\!\mid$}$


next up previous index
Next: 5.2 Completeness Up: 5. Real Numbers Previous: 5. Real Numbers   Index