\magnification=\magstep1
\centerline{Mathematics 242 -- Principles of Analysis}
\centerline{Discussion 2 -- Solutions}
\centerline{October 7, 2004}
\bigskip
\noindent
{\it Discussion Questions}
\bigskip
\noindent
{A)}  The second defining property of the supremum $s = \sup(S)$
above says: if $s' < s$, then there exists $x \in S$
such that $x > s'$.  Show that this statement is equivalent 
to saying:  If $t$ is any upper bound for $S$, then $t \ge s$.  
(Note and Hint:  In fact, many analysis books {\it define} the
supremum using this alternate form, because it clearly shows
that $\sup(S)$ is the ``least upper bound'' for $S$.
The relation between these statements comes from
one of our basic logical equivalences!)
\bigskip
\noindent
{\it Solution:}  The form given in question A 
for saying $s = \sup(S)$ is the 
{\it contrapositive} of the book's definition:  Book:  If
$s' < s$, then $s'$ is not an upper bound for $S$ (that is,
there exists an $x \in S$ such that $x > s'$).  Contrapositive
of this is:  If $s'$ is an upper bound for $S$, then $s' \ge s$.
Replacing $s'$ by $t$ we get exactly what is here.
\bigskip
\noindent
{B)}  Let $S$ be a nonempty bounded subset of ${\bf R}$.  Show
that $s = \sup(S)$ is {\it unique}.  Method: Assume that two 
real numbers $s,s'$ both satisfy the definition, then deduce 
that $s$ must equal $s'$.
\bigskip
\noindent
{\it Solution:}  Using the form from problem A, let $s$ and $s'$
both satisfy the defining properties of $\sup(S)$.  Since 
$s$ is  $\sup(S)$, and $s'$ is an upper bound for $S$, we 
get from A, $s \le s'$.  Similarly, since $s'$ is $\sup(S)$
and $s$ is an upper bound for $S$, $s' \le s$.  These
two inequalities show $s = s'$.
\bigskip
\noindent
{C)}  Prove that if $x < y$ are any real numbers, then 
there exist {\it infinitely many} rational numbers $r$
with $x < r < y$.  Hint:  Last time we showed that there is one
such rational number.  Try to extend that proof.
\bigskip
\noindent
{\it Solution:}  In class we showed that given any reals 
$x < y$, there exists a rational number $r_1$ with $x < r_1 < y$.
Repeat the same argument, with $r_1$ playing the role of $y$.
There exists a rational number $r_2$ with $x < r_2 < r_1 < y$.
Continuing in the same way, we can find a sequence of rational
numbers $r_n$, $n \in {\bf N}$ such that 
$x < \cdots < r_n < \cdots < r_2 < r_1 < y$
for all $n$.  The $r_i$ are distinct by construction, 
so there are infinitely many rationals between $x$ and $y$ (a whole
denumerable set of them).
\bigskip
\noindent
{D)}  Let $a/b$ be a rational number written as a 
fraction in lowest terms with $0 < a/b < 1$.
\medskip
\item{1)}  Show using the Archimedean Property that
there exists an integer $n$ such that
$${1\over n+1} \le {a\over b} \le {1 \over n}.$$
\bigskip
\noindent
{\it Solution:}  Consider the number $b/a > 1$.  By the Archimedean
Property of ${\bf N}$, there exists a natural number $n$ such that
$n \le b/a \le n+1$.  Then inverting (and correspondingly 
reversing the inequalities), we have
$${1\over n+1} \le {a\over b} \le {1\over n}$$
as claimed.  Note:  We cannot have equality in both cases, so 
we could always write one of these as a strict inequality.
If $a/b$ happens to equal the reciprocal of a natural number we
could make $a = 1/(n+1)$, for instance.
\medskip
\item{2)} If $n$ is chosen as in part 1, show that
$a/b - 1/(n+1)$ is a fraction that when written in lowest terms 
has numerator is less than $a$.
\bigskip
\noindent
{\it Solution:}  We have 
$a/b - 1/(n+1) = (a(n+1) - b)/(b(n+1))$.  If this fraction
is not already in lowest terms, then canceling common 
factors can only make the numerator {\it smaller}.  Hence
to prove what we want here, it suffices to show that 
$$a(n+1) - b < a.$$
From the proof of part 1, $an < b \le a(n+1)$, so 
subtracting $a(n+1)$ everywhere, $-a < b - a(n+1) < 0$.
Reversing signs (and switching the inequalities correspondingly),
$a > a(n+1) - b$, which is what we wanted to show.
\bigskip
\item{3)}  Use the Principle of Strong Induction from
Problem Set 3 to show that every rational number $a/b$ as
above can be written as a sum:
$${a\over b} = {1\over n_1} + \cdots + {1\over n_k}$$
for some distinct natural numbers $n_i$.
(For instance $49/90 = 1/3 + 1/9 + 1/10$.)
\medskip
\noindent
{\it Solution:}  The result from part 2 says that if we
find the integer $n$ with $1/(n+1) \le a/b < 1/n$,
then the difference $a/b - 1/(n+1)$, written in lowest
terms, must have a smaller numerator than $a/b$.  This means
that we should try to set up an induction argument where the 
``induction variable'', so to speak, is the integer $a$ in the
numerator of the fraction.  

The base case for the induction is numbers of the form
$a/b = 1/b$ (where $a = 1$).  These are already written 
in unit fraction, or ``Egyptian'' form.  So the base case
requires no proof ( :) ).  Now consider any $0< a/b < 1$ in 
lowest terms.  By part 2, there exists an integer $n+1$
such that $a/b - 1/(n+1)$ has numerator $< a$ when written
in lowest terms.  By strong induction, this means that we can
write 
$${a\over b} - {1\over (n+1)} = {1\over n_1} + \cdots + {1\over n_k}$$
for some distinct integers $n_1, \ldots, n_k$.  But then
$${a\over b} = {1\over (n+1)} + {1\over n_1} + \cdots + {1\over n_k}$$
and the only thing left to prove is that 
$n+1, n_1, \ldots, n_k$ must all be {\it distinct}.  Since
$n_1,\ldots,n_k$ are distinct, this just means that we need 
to show $n + 1 \ne n_i$ for $i = 1, \ldots, k$.  Aiming for
a contradiction, suppose on the contrary that $n+1 = n_i$ for
some $i$, and for convenience, 
renumber so that $i = 1$.  Then $a/b - 2/(n+1) = 1/n_2 + \cdots + 1/n_k > 0$.
But for $n > 1$, we always have $2/(n+1) > 1/n$.  This implies
that $a/b - 1/n > a/b - 2/(n+1) > 0$.  But note that
$n$ was chosen to make $1/(n+1) \le a/b < 1/n$, so $a/b - 1/n < 0$. 
Hence, we have found a 
contradiction because $a/b - 1/n$ cannot be both positive and
negative.  Hence the denominators $n+1,n_1, n_2, \ldots,n_k$ 
are all distinct.
\bye  