\magnification=\magstep1
\centerline{MATH 242 -- Principles of Analysis}
\centerline{Solutions for Problem Set 3 -- due:  Feb. 14}
\baselineskip=17pt
\bigskip
\noindent
{\it `A` Section}
\bigskip
\item{1.}  A set $B$ is said to be {\it finite} if there is some $n \in {\bf N}$ (the number of
elements in $B$), and a one-to-one and onto mapping $f : \{1,2,\ldots, n\} \to B$.  (Intuitively, we
think that $f(1) = b_1, f(2) = b_2, \ldots$ ``counts through'' all the elements of $B$ one at 
a time without repetitions and without missing any elements in $B$.)
For each of the following sets, either show $B$ is finite by determining the $n$ and constructing a mapping
$f$ as above, or say why no such mapping exists.
\itemitem{a.} $B = \{r = p/q \in {\bf Q} \mid 1 \le q \le 4\ {\rm and}\ 0 < r < 1\}$
\itemitem{} {\it Solution:}  This is a finite set containing exactly 5 elements:
$$B = \{1/2, 1/3, 2/3, 1/4, 3/4\}$$
We can construct a 1-1 onto mapping from $\{1,2,3,4,5\}$ to this $B$ from the order they
are listed here:  $f(1) = 1/2$, $f(2) = 1/3$, $f(3) = 2/3$, $f(4) = 1/4$, $f(5) = 3/4$.  
\itemitem{b.} $B = \{r = p/q \in {\bf Q} \mid 0 < r < 1\}$
\itemitem{} {\it Solution:} $B$ is {\it not} a finite set because, for instance, it contains all of the 
${1\over n}$ for $n \in {\bf N}$.  
\itemitem{c.} $B = \{n \in {\bf Z} \mid |n| \le 10^{14}\}$
\itemitem{} {\it Solution:}  $B$ is finite with $n = 2 \times 10^{14} + 1$ elements.
$f(k) = -2 \times 10^4 - 1 + k$ defines a 1-1 and onto mapping from $\{1,2,\ldots,n\}$ to $B$.
\item{2.}  Which of the following sequences converge to 0?  Explain your answers, but you do not
need to provide complete formal proofs of your assertions.
\itemitem{a.}  $\{x_n\}$, where
$$x_n = \cases{2^n & if $n \le 1000$\cr
               2^{-n} & if $n > 1000$\cr}$$
\itemitem{} {\it Solution:}  Intuitively, this sequence should converge to $0$ since 
although the first part of it, for $n \le 1000$ grows very rapidly and reaches a huge
value $2^{1000} \doteq 10^{300}$, once $n > 1000$, the terms rapidly decrease to 0.
\itemitem{b.}  $\{y_n\}$, where
$$y_n = \cases{1 & if $n$ is evenly divisible by $100$ \cr
               {1\over n} & if $n$ is not evenly divisible by $100$\cr}$$
\itemitem{} {\it Solution:}  There are arbitrarily large $n$ that are evenly divisible
by $100$.  So there are $y_n$ for $n$ arbitarily large such that $y_n = 1$.  (Formally, 
there exists $\varepsilon > 0$, like $\varepsilon = 1/2$, such that for all $n_0$, $|y_n - 0| > 1/2$
for some $n \ge n_0$.)
\itemitem{c.}  $\{z_n\}$, where
$$z_n = \cases{n & if $n$ is a Mersenne prime number \cr
               {(-1)^n\over n^2} & if $n$ is not a Mersenne prime number\cr}$$
(look these up on Wikipedia and read about them)
\itemitem{} {\it Solution:}  The question of whether there are infinitely many Mersenne prime
numbers (i.e. primes of the form $M = 2^p - 1$ where $p$ is a prime), is a famous unsolved
problem.  It is not currently known whether there are infinitely many such primes or not.  (As of
January 2014, there
are 48 of them known.)  Hence {\it we don't know whether this sequence converges or not}!
If there are infinitely many Mersenne primes, the situation is like that in b.  If not, that is, if there 
are only finitely many Mersenne primes, then the sequence does converge to 0.    
\bigskip
\item{3.}  Let $f(x) = [x]$ be the greatest integer function, defined as $[x] = $ the greatest integer $\le x$.
\itemitem{a.}  If $x_n \to a$, does it follow that $[x_n] \to [a]$?  Prove or give a counterexample.
\itemitem{} {\it Solution:}  This is false because, for instance if $x_n = 1 - 1/n$, then $0 \le x_n < 1$
for all $n\ge 1$, so $[x_n] = 0$ for all $n$.  But $x_n \to a = 1$, and $[a] = [1] = 1$.  
\itemitem{b.}  If $[x_n] \to [a]$, does it follow that $x_n \to a$?  Prove or give a counterexample.
\itemitem{} {\it Solution:}  This is also false.  Here's a counterexample:  Let $x_n = {1\over 2}$
for all $n$ (a constant sequence).  Then $[x_n] = 0$ for all $n$ and $[x_n] \to [0]$.  But
$x_n \to 1/2 \ne 0$.  
\bigskip
\noindent
{\it `B` Section}
\bigskip
\item{1.}
\itemitem{a.}  Prove that $\sqrt{3}$ is an irrational number.
\itemitem{} {\it Solution:}  Suppose on the contrary that $\sqrt{3} = {m \over n}$ where $m,n$
are integers.  We may assume $m,n$ have no common factors (by cancelling any common
factors between the numerator and denominator of the fraction).  Squaring both sides and
clearing denominators, we
get $3n^2 = m^2$.  Since $3$ divides $m^2$ evenly, $3$ must also divide $m$ (this follows
because $3$ is a prime number).  In other words
$m = 3k$ for some integer $k$.  But then $3n^2 = 9k^2$ so $n^2 = 3k^2$.  Now, we repeat
the same reasoning to claim that $3$ must divide $n$ as well.  Since we assumed $m,n$
had no common factors, we have reached a contradiction.  There can be no integers
$m,n$ that satisfy the original equation $\sqrt{3} = {m\over n}$.  Therefore $\sqrt{3}$
is irrational.  
\bigskip
\itemitem{} {\it Alternate method:}  The equation $3n^2 = m^2$ also implies that 
both $n$ and $m$ must be odd (since they must have the same parity and they 
cannot both be even since then the fraction $m/n$ would not be in lowest terms).  
If $n = 2\ell + 1$ and $m = 2k + 1$, we get $3(4\ell^2 + 4\ell + 1) = 4k^2 + 4k + 1$, 
so $6\ell^2 + 6\ell + 1 = 2k^2 + 2k$.  But notice this also gives a contradiction
since the left side of the last equation must be odd, and the right side must be even.
\itemitem{b.}  If $r \ne 0$ and $s$ are rational numbers, show that $r\sqrt{3} + s$ is also
an irrational number.  (Hint:  Suppose not and derive a contradiction.)
\itemitem{} {\it Solution:}  Suppose $r \sqrt{3} + s = x$, where $x$ is rational.  Then
$\sqrt{3} = {x - s \over r}$ must also be rational (${\bf Q}$ is closed under sums and
quotients).  But that contradicts part a.  So $r \sqrt{3} + s$ is also irrational.
\itemitem{c.} If $x = r\sqrt{3} + s$ and $x' = r'\sqrt{3} + s'$ are two numbers as in part b, what
can be said about $x + x'$ and $xx'$?  Are they necessarily irrational too?  
\itemitem{} {\it Solution:}  No, the sum and product are not necessarily 
irrational.  For instance if $x = \sqrt{3}$ and $x' = -\sqrt{3}$, then $x + x' = 0$
and $xx' = -3$.  Both of those {\it are rational}.
\item{2.}  Let $A$ and $B$ be two nonempty sets of real numbers. 
\itemitem{a.} Assume that $x \le y$ for all $x \in A$
and $y\in B$. Show that ${\rm lub}\ A$ and ${\rm glb}\ B$ must exist.
\itemitem{} {\it Solution:}  Let $y \in B$ (which exists because we 
assume $B$ is nonempty.  By the given information, $x \ge y$ for every $x \in A$.  
Therefore, $y$ is an upper bound for $A$. By the LUB axiom for ${\bf R}$, $A$ has
a least upper bound in ${\bf R}$.  Similarly every element of $A$ is a lower bound
for $B$, so ${\rm glb}(B)$ exists by the result of Corollary 1.5.11 in our text.   
\itemitem{b.}  Under the same assumptions as part a, show that ${\rm lub}\ A \le {\rm glb}\ B$.
\itemitem{} {\it Solution:} Suppose on the contrary that ${\rm lub} A > {\rm glb} B$.  Then 
${\rm glb} B$ is not an upper bound for $A$, so there exists $x \in A$ with 
${\rm glb} B < x \le {\rm lub} A$.  But then since $x$ is not a lower bound 
for $B$, we also have $y \in B$ such that ${\rm glb} B \le y < x$.  This contradicts
the assumption that $x \le y$ for all $x$ in $A$ and all $y$ in $B$.  
\itemitem{c.}  Now assume that $A$ and $B$ are bounded.  
Is it true that ${\rm lub}\ A \le {\rm glb}\ B$ implies that $x \le y$ for all $x \in A$
and $y\in B$?  Prove or give a counterexample.
\itemitem{} {\it Solution:}  This is true.  Every $x \in A$ satisfies $x \le {\rm lub}(A)$
and every $y \in B$ satisfies ${\rm glb}(B) \le y$.  But then under this assumption,
$x \le {\rm lub}(A) \le {\rm glb}(B) \le y$.  So $x \le y$ for all $x\in A$ and $y \in B$.  
\item{3.}  Let $A$ be a bounded set of real numbers and let $B = \{k x\mid x \in A\}$, where
$k < 0$ is a strictly negative number.  Show that $B$ is also bounded.  Then, determine formulas
for computing  ${\rm lub}\ B$
and ${\rm glb}\ B$ in terms of ${\rm lub}\ A$ and ${\rm glb}\ A$, and prove your assertions.
\item{} {\it Solution:}  Since $A$ is bounded (i.e. bounded above and below), there exist real
numbers $\ell, u$ such that $\ell \le x \le u$ for all $x \in A$.  Since $k$ is negative, this
implies $k\ell \ge kx \ge ku$.  But then $B$ is bounded too, since $ku$ is a lower bound and
$k\ell$ is an upper bound for $B$.  Noting the reversal of the inequalities that occurred here, we claim
that 
\medskip
\item{(a)} ${\rm lub}(B) = k {\rm glb}(A)$, and 
\item{(b)} ${\rm glb}(B) = k {\rm lub}(A)$.  
\medskip
\item{}  To prove (a), write $m = {\rm glb}(A)$.  By the definition, this means first that $x \ge m$
for all $x \in A$.  But then $kx \le km$, and hence $km$ is an upper bound for $B$.  Next we assume that 
$u$ is any other upper bound for $B$, so $kx \le u$ for all $x \in A$.  But this implies $x \ge {u\over k}$
for all $x \in A$.  So since $m$ is the greatest lower bound for $A$, we have 
$m \ge {u\over k}$.  But that implies $km \le u$.  Therefore, $km = {\rm lub}(B)$.  The proof of (b) 
is similar:   write $M = {\rm lub}(A)$.  By the definition, this means first that $x \le M$
for all $x \in A$.  But then $kx \ge kM$, and hence $kM$ is a lower bound for $B$.  Next we assume that 
$\ell$ is any other lower bound for $B$, so $kx \ge \ell$ for all $x \in A$.  But this implies 
$x \le {\ell\over k}$ for all $x \in A$.  So since $M$ is the least upper bound for $A$, we have 
$M \le {\ell\over k}$.  But that implies $kM \ge \ell$.  Therefore, $kM = {\rm glb}(B)$.
   
\item{4.}  Determine whether each of the following sequences converge and prove your assertions using 
the $\varepsilon, n_0$ definition of convergence.
\itemitem{a.}  $x_n = {3n^2\over n^2 + 5}$
\itemitem{}  {\it Solution:}  This sequence converges to $a = 3$.  Proof:  Let $\varepsilon > 0$.  
Since ${\bf N}$ is not bounded in ${\bf R}$, no matter how big $\sqrt{15\over \varepsilon}$ is, there
exist $n_0 > \sqrt{15\over \varepsilon}$ in ${\bf N}$, and 
for any such $n_0$, $n_0^2 > {15\over \varepsilon}$ (since
the squaring function is increasing for positive inputs), and hence ${15 \over n_0^2} < \varepsilon$.  
Then for all $n \ge n_0$, we have 
$$|x_n - 3| = \left|{-15\over n^2 + 5}\right| < {15\over n^2} \le {15 \over n_0^2} < \varepsilon.$$
This shows $x_n \to 3$ as $n\to \infty$ by the definition. 
\itemitem{b.}  $x_n = {1\over \ln(n)}$
\itemitem{} {\it Solution:}  This sequence converges to $a = 0$.  Proof:  Let $\varepsilon > 0$.  
Since ${\bf N}$ is not bounded in ${\bf R}$, no matter how big $e^{1\over \varepsilon}$ is, there
exist $n_0 > e^{1\over \varepsilon}$ in ${\bf N}$, and for any such $n_0$, $\ln(n_0) > {1 \over \varepsilon}$ (since
$\ln$ is increasing), and hence ${1\over \ln(n_0)} < \varepsilon$.  Then for
all $n \ge n_0$, we have
$$|x_n - 0| = \left|{1\over \ln(n)}\right| = {1\over \ln(n)} \le {1 \over \ln(n_0)} < \varepsilon.$$
This shows $x_n \to 0$ as $n\to \infty$ by the definition. 
\itemitem{c.}  $x_n = \cos(n\pi)$.  
\itemitem{} {\it Solution:}  We have $\cos(n\pi) = 1$ if $n$ is even and $\cos(n\pi) = -1$ if 
$n$ is odd.  Therefore $x_n = \cos(n\pi)$ does not converge to any $a \in {\bf R}$.  To prove this, 
let us show that no matter what $a$ is, there exist $\varepsilon >0$ such that 
for all $n \in {\bf N}$, there always exist $n \in {\bf N}$ such that 
$|x_n - a| \ge \varepsilon$.  In fact, say $\varepsilon = 1/2$.  For the even $n$ we have 
$|x_n - a| = |1 - a|$, while for odd $n$, $|x_n - a| = |-1 - a| = |1 + a|$.  For  

\end 
