\magnification=\magstep1
\centerline{MATH 242 -- Principles of Analysis}
\centerline{Selected Solutions -- Problem Set 3 B}
\centerline{February 18, 2011}
\bigskip
\noindent
{\it General Comment:}  The idea on problems 7, 8, 9 is to use the 
definition of the lub of a set of real numbers to prove the required
assertion.  So you need to show two things:  (1) the given number
is {\it an upper bound} for the set in question, and (2) no smaller
number is also an upper bound (or equivalently that if you have any 
upper bound for the set, then it is greater than or equal to the 
``candidate'' least upper bound.
\bigskip
\noindent 
\S 1.5/7 (a) Given that $A$ is a nonempty bounded set of real numbers, 
and $B = \{x + k\mid x \in A\}$.  Let $\alpha = {\rm lub}(A)$.  
\medskip
\item{(1)} We claim that $\alpha + k$ is an upper bound for $B$.
Since $\alpha$ is an upper bound for $A$, if $x \in A$ is any element
of $A$, then $x \le \alpha$.  Hence, by Axiom 8 (p. 13), 
$x + k \le \alpha + k$.  This shows that $\alpha + k$ is an upper
bound of $B$.  
\item{(2)}  Let $\beta$ be any upper bound for $B$.  Then 
$\beta \ge x + k$ for all $x \in A$ since the numbers $x + k$
for $x \in A$ are all the elements of $B$.  Hence if we subtract
$k$ from both sides of the last ineqality (Axiom 8 again),
$\beta - k \ge x$ for all $x \in A$.  This says that $\beta - k$
is an upper bound for $A$.  Hence, by the definition of the
least upper bound, $\beta - k \ge \alpha$.  Then, adding $k$
to both sides in the last inequality (Axiom 8, yet again!),
$\beta \ge \alpha + k$.  
\medskip
\noindent
Therefore, by the definition $\alpha + k = {\rm lub}(A) + k = {\rm lub}(B)$.
\bigskip
\noindent
Part (b) is almost the same, but least upper bounds are replaced by
greatest lower bounds, and all inequalities reverse.  
\bigskip
\noindent
8. (a)  First consider the case where $k = 0$.  Then $B = \{0\cdot x\mid x\in A\} = \{0\}$.
Hence ${\rm lub}(B) = 0 = 0\times {\rm lub}(A)$.  
Next, assume $k > 0$ and write $\alpha = {\rm lub}(A)$ (for convenience).  
\medskip
\item{(1)} We claim that $\alpha k$ is an upper bound for $B$.
Since $\alpha$ is an upper bound for $A$, if $x \in A$ is any element
of $A$, then $x \le \alpha$.  Hence, since $k > 0$, by Axiom 9 (p. 13), 
$k x \le k \alpha$.  This shows that $k \alpha$ is an upper
bound of $B$.  
\item{(2)}  Let $\beta$ be any upper bound for $B$.  Then 
$\beta \ge k x$ for all $x \in A$ since the numbers $k x$
for $x \in A$ are all the elements of $B$.  Since $k > 0$, $1/k$ exists
in ${\bf R}$ and $1/k > 0$ too.  We can
multiply through by
$1/k$ on both sides of the last ineqality (Axiom 9 again) to get
${\beta/k} \ge x$ for all $x \in A$.  This says that ${\beta/k}$
is an upper bound for $A$.  Hence, by the definition of the
least upper bound, ${\beta/k} \ge \alpha$.  Then, multiplying $k$
on both sides in the last inequality (Axiom 9, yet again!),
$\beta \ge k \alpha$.  
\medskip
\noindent
Therefore, by the definition $k \alpha = k\cdot {\rm lub}(A) = {\rm lub}(B)$.
\bigskip
\noindent
Part (b) is related to part (a) in the same way that problem 7 part (b) 
is related to problem 7 part (a).  
\bigskip
\noindent
(c)  If $k < 0$, then $k\cdot{\rm lub}(A) = {\rm glb}(B)$ and $k\cdot {\rm glb}(A) = {\rm lub}(B)$,
since multiplying by a negative number reverses inequalities (Theorem 1.3.1 part (i)).    
\bigskip
\noindent
9. A general comment first -- I did not get the feeling that {\it anyone} (even those
who had completely correct solutions) really understood
the subtlety of this problem.  The thing that makes it tricky is the condition you
are working with: 
\medskip 
\centerline{\it (*)  For each element $x \in A$, there exists some $y \in B$ such
that $y \ge x$.}  
\medskip
\noindent
Statements like this one, involving the {\it quantifiers} 
``for all'' and ``there exists'' (or ``for some'') are going to be our {\it constant
concern, our ``bread and butter''} from now on in this course, and you need to get 
a good feeling for what ``nested quantifiers'' like the ones here actually mean.  

\bigskip
\noindent
(a) The given condition {\it does not imply} that that each element of $B$ is 
greater than or equal to every element in $A$.  Example:  Let $A = \{0,1\}$ and
$B = \{0,1,2\}$.  Then for each $x \in A$ there is some element $y \in B$
such that $y \ge x$.  (For $x = 0$, take $y = $ any element in $B$.  For 
$x = 1$, take $y = 1$ or $y = 2$.)  On the other hand $0 \in B$ is not
greater than or equal to $1 \in A$.  

\bigskip
\noindent
This is a perfectly good counterexample for part (a).  It {\it does not} show all
of the possibilities for sets $A$ and $B$ satisfying this condition and the 
possible subtleties, 
though.  To get a better feeling for what the condition can say in more complicated
examples, consider the following sets:
$$A = \left\{1 - {1\over n} \mid n \in {\bf N}\right\}$$
and 
$$B = \left\{1 - {2n+1\over 2n(n+1)} \mid n \in {\bf N}\right\}.$$
Let's write $a_n = 1 - 1/n$, and $b_n = 1 - (2n+1)/(2n(n+1))$.  
It is easy to check that $a_n < a_{n+1}$ for all $n \ge 1$
and $b_n < b_{n+1}$ for all $n \ge 1$.  Some algebra shows that
$$b_n = {1\over 2}(a_n + a_{n+1})$$
for all $n \ge 1$.   So $b_n$ is the {\it midpoint of the interval} 
from $a_n$ to $a_{n+1}$.  As a result, 
the elements of $A$ and $B$ are completely ``interleaved'' like this:
$$a_1 < b_1 < a_2 < b_2 < a_3 < b_3 < \cdots $$
You should be able to see that both of these sequences are tending
to the limit $1$ as $n \to \infty$.  However, {\it all} of these 
are strict inequalities.  In particular:
\bigskip
\item{} Condition (*) holds, since for every $n \ge 1$, the elements 
$a_n \in A$ and $b_n \in B$ satisfy $b_n \ge a_n$.  
\bigskip
\noindent
On the other hand (unlike the first ``simple'' example, in which we had finite sets)
\bigskip
\item{} No single element of $B$ is an upper bound for $A$, since
for each $n\ge 1$, $a_{n+1} > b_n$.  
\bigskip
\noindent
Moreover,
\bigskip
\item{} Both $A$ and $B$ have least upper bound $= 1$, but that number
is not contained in either of the sets.
\bigskip
\noindent
This example shows that even in a ``complicated'' example, the inequality
from part (b) of the problem holds.  Here is a general proof of that part:
\bigskip
\noindent
\S 1.5/ 9 (b) Let $A$ and $B$ be sets satisfying condition (*) above. 
If $x \in A$ is any element of $A$, then there is some $y \in B$
(possibly depending on $x$) such that $x \le y$.  That $y$ satisfies
$y \le {\rm lub}(B)$.  Hence by Axiom 7 (p. 13), for all $x \in A$, 
$x \le {\rm lub}(B)$.  Therefore ${\rm lub}(B)$ is an upper bound
for the set $A$.  It follows from the definition that ${\rm lub}(A) \le {\rm lub}(B)$.//
\bigskip
\noindent
It is instructive to think how this works in the ``complicated''
example above(!)
\bigskip
\noindent
13 (a)  This is FALSE -- a counterexample is $A = \{-2,1\}$.
$\alpha = {\rm lub}(A) = 1$, but 
$${\rm lub}(\{|x| \mid x \in A\}) = {\rm lub}(\{1,2\}) = 2 \ne |\alpha|.$$
(The intuition is that if $x < 0$, then $|x| = -x$ and multiplying 
an inequality on elements of $A$ by $-1$ to get $|x| = -x$ in that
case will {\it reverse the inequality} as in Theorem 1.3.1 (i).)
\bigskip
\noindent
(b) This is TRUE -- a proof goes like this:  First if $x\in A$ and 
$y \in B$, then by Axiom 8 (twice):
$$x+y \le \alpha + y \le \alpha + \beta.$$
Then by Axiom 7, $x + y \le \alpha + \beta$, and $\alpha + \beta$
is an upper bound of $\{x + y \mid x\in A, y \in B\}$.  
For the rest of the proof, instead of showing that any other upper
bound of the set of sums $x + y$ is greater than or equal to 
$\alpha + \beta$, it will be somewhat more convenient to show
one of our equivalent forms of the definition.  We will show
that no number $< \alpha + \beta$ is an upper bound for the set
of sums $x + y$.  So let $\varepsilon > 0$.  Then there exist 
$x \in A$ satisfying $\alpha - \varepsilon/2 < x \le \alpha$
and similarly, there exist $y \in B$ satisfying 
$\beta - \varepsilon/2 < y \le \beta$.  If we add corresponding
terms here (using Axioms 8 and 7), 
$$(\alpha + \beta) - \varepsilon < x + y \le \alpha + \beta.$$
This shows that 
$$\alpha + \beta = {\rm lub}(\{x + y \mid x \in A, y\in B\}).$$
\bigskip
\noindent
(c) and (d) are FALSE for reasons similar to part (a).  (e) 
is TRUE by problem 8 from \S 1.3 (recall that $B$ consists
of positive numbers only). 
\bigskip
\noindent
23.  This is similar to the proof that $\sqrt{2}$ is irrational that
we did in class.  

Suppose that $\sqrt{p} = {m \over n}$ for some $m,n \in {\bf Z}$ with $n \ne 0$.
By unique factorization in ${\bf Z}$, we may assume the fraction ${m\over n}$ is
in {\it lowest terms} -- namely that $m, n$ have {\it no common factors}.  

The equation $\sqrt{p} = {m\over n}$ implies that $n^2 p = m^2$.  But that
says $p$ divides $m^2 = m\cdot m$.  Because of the algebraic fact given 
in the problem, we conclude that $p$ divides $m$.  So we can write $m = pk$
for some integer $k$.  Substituting in, this says $n^2 p = p^2 k^2$.
But then we can cancel $p$'s on each side to obtain $n^2 = p k^2$.  
Now the same argument shows that $p$ divides $n^2 = n\cdot n$, so $p$
divides $n$. Since $p$ divides $m$ and $n$, the fraction was not 
in lowest terms, and this is a contradiction.  Hence $\sqrt{p}$
is not rational.  
\bye
