\magnification=\magstep1
\centerline{Mathematics 242 -- Principles of Analysis}
\centerline{Selected Solutions for Problem Set 5, ``B'' portion}
\centerline{March 18, 2011}
\bigskip
\noindent
\S 2.3/15.  The idea of this problem is to show that if we assume
that every bounded monotone sequence converges, then it follows
that every nonempty set $A$ that is bounded above has a least upper bound.
(In other words, we will show that the statement of the Completeness
Axiom follows from the Monotone Convergence Theorem.  We proved the
opposite implication in class, and 
both of these statements are also equivalent to the Nested
Interval Theorem(!))  So 
we start with a set $A \subset {\bf R}$ that is bounded above.
We construct two sequences ${x_n}$ and ${y_n}$ as described
in the problem.  We take $x_1 \in A$ an arbitrary element
and we let $y_1$ in ${\bf R}$ be any upper bound for $A$.  Then
assuming $x_n$ and $y_n$ have already been constructed, let
$z_n = {x_n + y_n\over 2}$ and consider two possible cases
for determining $x_{n+1}$ and $y_{n+1}$:
\bigskip
\item{$\bullet$}  Case 1:  If $z_n$ is an upper bound for $A$, then 
we let $x_{n+1} = x_n$ and $y_{n+1} = z_n$.  
\item{$\bullet$}  Case 2:  If, on the other hand $z_n$ is not
an upper bound for $A$, then there exists some $a' \in A$
with $a' > z_n$, so we let $x_{n+1} = a'$ and $y_{n+1} = y_n$.
\bigskip
\noindent
We note the following:
\bigskip
\item{$\bullet$}  By construction, $x_n \in A$ for all $n$
and $y_n$ is an upper bound of $A$ for all $n$.  
\item{$\bullet$}  The sequence $\{x_n\}$ is monotone increasing
and bounded above by $y_1$ since all $x_n \in A$.  
\item{$\bullet$}  The sequence $\{y_n\}$ is monotone decreasing
and bounded below by any $x_m$.  
\bigskip
\noindent
(a)  It follows now that $\{x_n\}$ and $\{y_n\}$ are both
convergent sequences, since our hypothesis is that every
bounded monotone sequence in ${\bf R}$ converges.  
\bigskip
\noindent
(b)  Since $z_n$ is the midpoint of the line segment from
$x_n$ to $y_n$ for each $n$, we note that for all $n\ge 1$,
$$ y_{n+1} - x_{n+1} \le {1\over 2}(y_n - x_n).$$
(We have equality in Case 1 and the strict inequality in
Case 2 as above.)  If we ``unwind'' this back to the 
beginning of the construction, we see
$$\eqalign{
y_{n+1} - x_{n+1} &\le {1\over 2}(y_n - x_n) \cr
                  &\le {1\over 2^2}(y_{n-1} - x_{n-1})\cr
                  &\ \vdots\cr
                  &\le {1\over 2^n}(y_1 - x_1).\cr}$$
Hence if we let $n \to \infty$, we see that 
$$\lim_{n\to\infty} (y_n - x_n) = 0,$$
since ${1\over 2^n} \to 0$ as $n\to \infty$.  
That implies
$$\lim_{n\to\infty} y_n = \lim_{n\to\infty} x_n$$
by part (a) and Theorem 2.2.5a.  
\bigskip
\noindent
(c)  Call the limit of $\{x_n\}$ and $\{y_n\}$ $\alpha \in {\bf R}$.
We want to show that $\alpha$ satisfies the properties of the least
upper bound of $A$.  First, since every $y_n$ is an upper bound
for $A$, we have $x \le y_n$ for all $x \in A$ and all $n$.  It
follows from Theorem 2.2.7 that $x \le \alpha$ for all $x \in A$.
Hence $\alpha$ is an upper bound for $A$.  On the other hand, if
$\varepsilon > 0$,  then since $x_n \to \alpha$, there exist 
$n_0 \in {\bf N}$ such that $\alpha - \varepsilon < x_n \le \alpha$
for all $n \ge n_0$.  Since the $x_n \in A$ for all $n$, this
implies that $\alpha - \varepsilon$ is not an upper bound
for $A$.  It follows that $\alpha = {\rm lub}(A)$.  
\bigskip
\noindent
\S 2.5/12.  Both parts of this are TRUE.  For part (a) suppose that we
have an sequence of positive numbers $\{x_n\}$ with $x_n \to 0$ as
$n\to\infty$.  Then we want to show how to produce a strictly decreasing
subsequence.  We can take $x_{n_1} = x_1$ to start.  Now suppose we
have found 
$$x_{n_1} > \cdots > x_{n_k}.$$
Letting $\varepsilon = x_{n_k}$ in the definition of convergence
we see that there exists some $N_0$ such that $|x_n - 0| = x_n < \varepsilon = x_{n_k}$
for all $n \ge N_0$.  Letting $n_{k+1}$ be any one such integer 
that is also $> n_k$ we get $x_{n_{k+1}}$ satisfying 
$$x_{n_1} > \cdots > x_{n_k} > x_{n_{k+1}}.$$
By induction, this shows there exists a strictly decreasing subsequence. 

Now for (b), if infinitely many $x_n > 0$, then we can apply the same 
reasoning as in (a) to get a strictly decreasing subsequence chosen
from the positive terms in the whole sequence.  If there are not infinitely
many $x_n > 0$, then there must be infinitely many $x_n < 0$ and we
can repeat essentially the same argument above {\it with the negative terms}.
We can let $n_1$ be any index such that $x_{n_1} < 0$.  Then assuming
we have found 
$$x_{n_1} < \cdots < x_{n_k},$$
let $\varepsilon = |x_{n_k}|$ in the definition of convergence.
we see that there exists some $N_0$ such that $|x_n - 0| = |x_n| < \varepsilon = |x_{n_k}|$
for all $n \ge N_0$.  Letting $n_{k+1}$ be any one such integer 
that is also $> n_k$ and such that $x_{n_{k+1}} < 0$, we get $x_{n_{k+1}}$ satisfying 
$|x_{n_{k+1}}| < |x_{n_k}|$, which implies $x_{n_{k+1}} > x_{n_k}$
(since both are negative).  Hence
$$x_{n_1} < \cdots < x_{n_k} < x_{n_{k+1}}.$$
By induction, this shows there exists a strictly increasing subsequence. 
\bigskip
\noindent
13.  We suppose that $\{x_n\}$ is a bounded sequence with the property that every
convergent subsequence converges to the same limit $a$.  Aiming for
a contradiction, suppose $x_n \not\to a$.  This is equivalent to saying
there exists some $\varepsilon_0 > 0$ such that for all $n_0 \in {\bf N}$, 
$|x_n - a|\ge \varepsilon_0$ for some $n \ge n_0$.

Let $\varepsilon_0 > 0$
be any fixed number for which it is true that 
\bigskip
\noindent
(*) {\it for all $n_0 \in {\bf N}$, 
$|x_n - a|\ge \varepsilon_0$ for some $n \ge n_0$.}
\bigskip 
We claim that there is a subsequence $\{x_{n_k}\}$ with the property that
$|x_{n_k} - a| \ge \varepsilon_0$ for all $k \in {\bf N}$.  To see this,
we apply (*) above with $n_0 = 1$, and we get a first term $x_{n_1}$ for 
$n_1 \ge 1$ satisfying $|x_{n_1} - a| \ge \varepsilon_0$.  Then assuming 
that $x_{n_1},\ldots,x_{n_k}$ have been constructed, apply the statement 
(*) above with $n_0 = n_k + 1$.  We
get $n_{k+1} \ge n_k + 1$ such that $|x_{n_{k+1}} - a| \ge \varepsilon_0$.
Continuing in the same way (i.e. by induction) 
this shows our claim.  

It is clear that the subsequence $\{x_n\}$ constructed here cannot
converge to $a$ since all the terms are uniformly bounded away from $a$.
Moreover, no subsequence of this subsequence can converge to $a$ either, 
for the same reason.

However, since the original sequence was bounded, this subsequence
is bounded too.  Hence the Bolzano-Weierstrass theorem applies
and shows that there must be a convergent subsequence of the $\{x_{n_k}\}$.
That convergent subsequence is also a subsequence of the original $\{x_n\}$.
Hence the assumption implies it must converge to $a$.  This contradicts
what we said in the last paragraph.  

Hence $x_n$ must converge to $a$.  (Wow!)
\bye
