\documentclass[11pt,letterpaper]{article}
\usepackage{amsmath,amsfonts}
\setlength{\oddsidemargin}{0in}
\setlength{\evensidemargin}{0in}
\setlength{\textwidth}{6.5in}
\setlength{\topmargin}{-0.7in}
\setlength{\textheight}{9.2in}
\setlength{\parskip}{0.2em}
\parindent0mm
\def\Q{\mathbb{Q}}
\def\R{\mathbb{R}}
\def\Z{\mathbb{Z}}
\def\C{\mathbb{C}}
\begin{document}
\begin{center}
{\bf \Large Math 112 Homework 4 Solutions}\medskip
\end{center}
\vskip-2mm

{\bf Problem 1.}

(a) Since $d(x,a)\ge 0$ $\forall a\in A$, we always have $d(x,A)\ge 0$.
If $d(x,A)=0$, then for any $r>0$ we know that $r$ is not a lower bound of
$\{d(x,a),\ a\in A\}$, i.e.\ $\exists a\in A$ such that $d(x,a)<r$. We
conclude that $x\in\bar{A}$. Conversely, if $x\in \bar{A}$, then for any
$r>0$ there exists $a\in A$ such that $d(x,a)<r$, so $d(x,A)\le d(x,a)<r$.
We conclude that $d(x,A)$ cannot be positive; so $d(x,A)=0$.

(b) For every positive integer $n$, since $d(x,A)=\inf\{d(x,a),\ a\in A\}$, 
we know that $d(x,A)+\frac{1}{n}$ is not a lower bound of 
$\{d(x,a),\ a\in A\}$. So there exists $a_n\in A$ such that
$r_n=d(x,a_n)<d(x,A)+\frac{1}{n}$. So $d(x,A)\le r_n<d(x,A)+\frac{1}{n}$.
This implies that $\{r_n\}$ converges to $d(x,A)$. (given $\epsilon>0$,
there exists $N$ such that $\frac{1}{N}<\epsilon$, and for every $n\ge N$
we have $|r_n-d(x,A)|<\frac{1}{n}<\epsilon$).

(c) Assume $A$ is compact: then by Theorem 3.6 we know that the sequence
$\{a_n\}$ constructed in (b) has a convergent subsequence $\{a_{n_i}\}$. 
Let $a\in A$ be the limit of this subsequence. Then we have $d(x,a)\le
d(x,a_{n_i})+d(a_{n_i},a)$. Since $d(x,a_{n_i})\to d(x,A)$ and
$d(a_{n_i},a)\to 0$, the right-hand side converges to $d(x,A)$, and so 
$d(x,a)\le d(x,A)$. However $d(x,a)\ge d(x,A)$ by definition of $d(x,A)$,
so $d(x,a)=d(x,A)$.
\medskip

{\bf Problem 2.}

(a) First we prove that $x_n>\sqrt{\alpha}$ for all $n$. Indeed,
$x_1>\sqrt{\alpha}$; and, assuming that $x_n>\sqrt{\alpha}$, we have
$x_{n+1}-\sqrt{\alpha}=\frac{1}{2}(x_n+\frac{\alpha}{x_n}-2\sqrt{\alpha})=
\frac{1}{2}(\sqrt{x_n}-\sqrt{\alpha/x_n})^2>0$, so $x_{n+1}>\sqrt{\alpha}$. 
So by induction $x_n>\sqrt{\alpha}$ for all $n$. As a consequence, for all 
$n$ we have $\frac{\alpha}{x_n}<\sqrt{\alpha}<x_n$, so
$x_{n+1}=\frac{1}{2}(x_n+\frac{\alpha}{x_n})<\frac{1}{2}(x_n+x_n)=x_n$.
So the sequence $\{x_n\}$ decreases monotonically.

Since the sequence $\{x_n\}$ decreases monotonically and admits the lower
bound $\sqrt{\alpha}$, by Theorem 3.14 it converges to a certain limit 
$x\ge\sqrt{\alpha}$. Since $x_n\to x$, we have 
$\frac{\alpha}{x_n}\to\frac{\alpha}{x}$,
so $x_{n+1}\to \frac{1}{2}(x+\frac{\alpha}{x})$. However $x_{n+1}\to x$, so
by uniqueness of the limit we have $x=\frac{1}{2}(x+\frac{\alpha}{x})$,
which implies that $x=\frac{\alpha}{x}$, i.e.\ $x=\sqrt{\alpha}$.
(This can also be shown directly by estimating $|x_{n+1}-\alpha|$).

(b) $\epsilon_{n+1}=x_{n+1}-\sqrt{\alpha}=\frac{1}{2}(x_n+\frac{\alpha}{x_n}-
2\sqrt{\alpha})=\frac{1}{2x_n}(x_n^2+\alpha-2x_n\sqrt{\alpha})=\frac{1}{2x_n}
(x_n-\sqrt{\alpha})^2=\epsilon_n^2/2x_n$. Since $x_n>\sqrt{\alpha}$, we
conclude that $\epsilon_{n+1}<\epsilon_n^2/2\sqrt{\alpha}$. 

Setting $\beta=2\sqrt{\alpha}$, we show by induction on $n$ that
$\epsilon_{n+1}<\beta(\epsilon_1/\beta)^{2^n}$. For $n=1$ we have
$\epsilon_2<\epsilon_1^2/\beta=\beta(\epsilon_1/\beta)^2$.
Assume that $\epsilon_n<\beta(\epsilon_1/\beta)^{2^n}$: then
$\epsilon_{n+1}<\epsilon_n^2/\beta<\beta(\epsilon_1/\beta)^{2^{n+1}}$.
So the inequality holds for all $n=1,2,3,\dots$.

(c) If $\alpha=3$ and $x_1=2$, then $\epsilon_1=2-\sqrt{3}\simeq 0.268<0.3$,
and $\beta=2\sqrt{3}\simeq 3.464>3$, so $\epsilon_1/\beta<\frac{0.3}{3}=
\frac{1}{10}$. Hence $\epsilon_{n+1}<\beta(\epsilon_1/\beta)^{2^n}<
\beta\,10^{-2^n}<4\cdot 10^{-2^n}$. So $\epsilon_5<4\cdot 10^{-16}$,
$\epsilon_6<4\cdot 10^{-32}$.
\medskip

{\bf Problem 3.}

We show first that $\{d(p_n,q_n)\}$ is a Cauchy sequence in $\R$. Indeed,
fix $\epsilon>0$: there exists $N$ such that if $m,n\ge N$ then
$d(p_n,p_m)<\frac{\epsilon}{2}$. Similarly there exists $N'$ such that
if $m,n\ge N'$ then $d(q_n,q_m)<\frac{\epsilon}{2}$. Let $m,n\ge
\max(N,N')$: then $d(p_n,q_n)\le d(p_n,p_m)+d(p_m,q_m)+d(q_m,q_n)<
\frac{\epsilon}{2}+d(p_m,q_m)+\frac{\epsilon}{2}=d(p_m,q_m)+\epsilon$,
and similarly (exchanging $m$ and $n$) $d(p_m,q_m)<d(p_n,q_n)+\epsilon$.
So $|d(p_n,q_n)-d(p_m,q_m)|<\epsilon$ for all $m,n\ge\max(N,N')$. Therefore
$\{d(p_n,q_n)\}$ is a Cauchy sequence in $\R$; since $\R$ is complete, it
converges.
\medskip

{\bf Problem 4.}

(a) Let $\{p_n\}$, $\{q_n\}$ and $\{r_n\}$ be Cauchy sequences. The first
two properties of an equivalence relation are clearly satisfied: first,
$d(p_n,p_n)=0$ $\forall n$, so $\lim d(p_n,p_n)=0$, and therefore $\{p_n\}
\sim\{p_n\}$. Moreover, if $\{p_n\}\sim\{q_n\}$ then by definition 
$\lim d(p_n,q_n)=0$, so $\lim d(q_n,p_n)=0$ and $\{q_n\}\sim \{p_n\}$.
Finally, if $\{p_n\}\sim \{q_n\}$ and $\{q_n\}\sim\{r_n\}$, observe that
$0\le d(p_n,r_n)\le d(p_n,q_n)+d(q_n,r_n)$; since by Problem 4 these
sequences all converge, $0\le \lim d(p_n,r_n)
\le \lim d(p_n,q_n)+\lim d(q_n,r_n)=0+0=0$. Therefore $d(p_n,r_n)\to 0$, and we
conclude that $\{p_n\}\sim \{r_n\}$. So $\sim$ is an equivalence relation.

(b) Let $P,Q\in X^*$; let $\{p_n\}$, $\{p'_n\}$ be equivalent sequences
representing $P$, and let $\{q_n\}$, $\{q'_n\}$ be equivalent sequences 
representing $Q$. Since $d(p'_n,q'_n)\le
d(p'_n,p_n)+d(p_n,q_n)+d(q_n,q'_n)$, we have 
$\lim d(p'_n,q'_n)\le \lim d(p'_n,p_n)+\lim d(p_n,q_n)+\lim d(q_n,q'_n)$;
since the first and third term converge to $0$, we get $\lim d(p'_n,q'_n)
\le \lim d(p_n,q_n)$. Reversing the roles of $p_n$ and $p'_n$ and of
$q_n$ and $q'_n$, we also have the converse inequality; so $\lim
d(p'_n,q'_n)=\lim d(p_n,q_n)$, and therefore $\Delta(P,Q)$ is well-defined.

Next, we prove that $\Delta$ is a distance: let $\{p_n\}$, $\{q_n\}$,
$\{r_n\}$ be Cauchy sequences in $X$, representing elements $P,Q,R\in X^*$.
First, since $d(p_n,q_n)\ge 0$ $\forall n$, we get that $\Delta(P,Q)=
\lim d(p_n,q_n)\ge 0$. Moreover $\Delta(P,Q)=0$ if and only if
$d(p_n,q_n)\to 0$, i.e.\ if and only if $\{p_n\}$ and $\{q_n\}$ are
equivalent, i.e.\ if and only if $P=Q$. Next, observe that $\Delta(P,Q)=
\lim d(p_n,q_n)=\lim d(q_n,p_n)=\Delta(Q,P)$. Finally we check the triangle
inequality: since $d(p_n,q_n)\le d(p_n,r_n)+d(r_n,q_n)$, we have
$\Delta(P,Q)=\lim d(p_n,q_n)\le \lim d(p_n,r_n)+\lim d(r_n,q_n)=\Delta(P,R)
+\Delta(R,Q)$. So $\Delta$ is a distance function.

(c) Let $\{P_n\}$ be a Cauchy sequence in $(X^*,\Delta)$, and choose a
representative $\{p_{nk}\}$ for each $P_n$. Since $\{p_{nk}\}$ is a Cauchy
sequence in $X$, there exists an integer $K_n$ such that if $k,l\ge K_n$
then $d(p_{nk},p_{nl})<\frac{1}{n}$. Let $q_n=p_{nK_n}$. 

We first show that
$\{q_n\}$ is a Cauchy sequence in $X$. For this purpose, observe that,
for every value of $k$, $d(q_n,q_m)\le d(q_n,p_{nk})+d(p_{nk},p_{mk})+
d(p_{mk},q_m)$; in particular, if $k\ge \max(K_n,K_m)$, $d(q_n,p_{nk})=
d(p_{nK_n},p_{nk})<\frac{1}{n}$, by definition of $K_n$, and similarly
$d(p_{mk},q_m)=d(p_{mk},p_{mK_m})<\frac{1}{m}$. So for $k\ge \max(K_n,K_m)$
we have $d(q_n,q_m)<\frac{1}{n}+d(p_{nk},p_{mk})+\frac{1}{m}$. When
$k\to\infty$ the right-hand side converges to $\frac{1}{n}+\Delta(P_n,P_m)+
\frac{1}{m}$ by definition of $\Delta(P_n,P_m)$; so we conclude that
$d(q_n,q_m)\le \frac{1}{n}+\Delta(P_n,P_m)+\frac{1}{m}$. Fix a constant
$\epsilon>0$: since $\{P_n\}$ is a Cauchy sequence in $(X^*,\Delta)$, 
there exists $N$ such that $\forall n,m\ge N$, $\Delta(P_n,P_m)<
\frac{\epsilon}{2}$. Increasing $N$ if necessary we can also assume that
$\frac{1}{N}<\frac{\epsilon}{4}$. We conclude that, if $n,m\ge N$, then
$d(q_n,q_m)<\frac{1}{N}+\frac{\epsilon}{2}+\frac{1}{N}<\epsilon$. So
$\{q_n\}$ is a Cauchy sequence in $(X,d)$, and we can define $Q\in X^*$ to
be its equivalence class.

We now show that $P_n\to Q$. Fix $\epsilon>0$, and let $N$ be such that
$d(q_n,q_m)<\epsilon$ $\forall n,m\ge N$ (such an $N$ exists because
$\{q_n\}$ is a Cauchy sequence). Let $n\ge N$ and $m\ge \max(N,K_n)$: then
$d(p_{nm},q_m)\le d(p_{nm},q_n)+d(q_n,q_m)$. Since $m\ge K_n$, the first
term is bounded by $\frac{1}{n}$ (recall $q_n=p_{nK_n}$). Since $m,n\ge N$ 
the second term is bounded by $\epsilon$. So $d(p_{nm},q_m)<
\frac{1}{n}+\epsilon$. If we keep $n$ fixed and let $m\to \infty$, the
left-hand side converges to $\lim_{m\to\infty} d(p_{nm},q_m)=\Delta(P_n,Q)$.
So we conclude that $\Delta(P_n,Q)\le \frac{1}{n}+\epsilon$ for all $n\ge N$.
Increasing $N$ if necessary we can assume that $\frac{1}{N}<\epsilon$;
the conclusion becomes: $\forall n\ge N$, $\Delta(P_n,Q)<2\epsilon$.
Since $2\epsilon$ can be chosen as small as desired, we conclude that
$P_n\to Q$ (if one insists on getting $\Delta(P_n,Q)<\epsilon$ one can also
replace $\epsilon$ by $\frac{\epsilon}{2}$ in the preceding sentences).

(d) Let $p,q\in X$, and let $P_p=\phi(p)$, $P_q=\phi(q)$. The constant
sequences defined by $p_n=p$ and $q_n=q$ represent $P_p$ and $P_q$
respectively, by definition. We have $d(p_n,q_n)=d(p,q)$, so
$\Delta(P_p,P_q)=\lim d(p_n,q_n)=d(p,q)$.

(e) Let $P\in X^*$, and let $\{p_n\}$ be a Cauchy sequence representing
$P$. Fix $\epsilon>0$: there exists $N$ such that $\forall m,n\ge N$,
$d(p_n,p_m)<\epsilon$. Consider the constant sequence $q_n=p_N$, which 
represents the element $P_{p_N}=\phi(p_N)$ in $X^*$. For all $n\ge N$ we
have $d(p_n,q_n)=d(p_n,p_N)<\epsilon$, so taking the limit as $n\to\infty$
we conclude that $\Delta(P,P_{p_N})=\lim d(p_n,q_n)\le\epsilon$. So we have
shown that there exist elements of $\phi(X)$ which lie at arbitrarily small
distance from $P$. In other words, every element $P\in X^*$ belongs to
$\overline{\phi(X)}$. We conclude that $\phi(X)$ is dense in $X^*$.

Assume that $X$ is complete: then let $P\in X^*$, and let $\{p_n\}$ be
a Cauchy sequence in $X$ representing $P$. Since $X$ is complete, the
sequence $\{p_n\}$ converges to some limit $q\in X$. Consider the constant
sequence $q_n=q$ representing $P_q=\phi(q)$: since $p_n\to q$, we have
$d(p_n,q_n)=d(p_n,q)\to 0$, so the sequences $\{p_n\}$ and $\{q_n\}$ are
equivalent (in the sense of part (a)). Therefore they represent the same
element in $X^*$: we have $P=\phi(q)$. So every element of $X^*$ belongs
to $\phi(X)$, and we conclude that $\phi(X)=X^*$.
\end{document}
