\section{Limits}

\news[Definitions and abstract properties]
Let us work in a metric space $(M,d)$.  If $A\included M$, and $b\in
M$, we shall say that $b$ is an \defn{adherent point} of $A$ if $b\in
A$ or else $b$ is a cluster point of $A$.

Recall that a sequence $(a_n:n\in\N)$ is technically a function on
$\N$; the range of the function is the set $\{a_n:n\in\N\}$.  Say that
this range is included in $M$, and that it has an
adherent point $b$.  Then for every neighborhood $U$ of $b$, and for
every $N$ in $\N$, there is $m$ in $\N$ such that $m\geq N$ and
\begin{equation}\label{eqn:nbhd}
a_m\in U.
\end{equation}
Suppose that for every neighborhood $U$ of $b$ there is $N$ in $\N$
such that \pref{eqn:nbhd} holds whenever $m\geq N$.  Then $b$ is a
\defn{limit} of the sequence; one also says that the sequence
\defn{converges} to $b$, and one writes
$$\lim_{n\to\infty}a_n=b.$$
So limits of sequences are adherent points of their ranges; but the
converse need not be the case.

\begin{lemma*}
  If a sequence has a limit, then no other point is a limit of the
  sequence or a cluster
  point of the range of the sequence.
\end{lemma*}

\begin{proof}
  Suppose $(a_n:n\in\N)$ converges to $b$, and $c\neq b$.  Let
  $\epsilon=d(b,c)/2$, and let $N$ be such that $a_m\in B(b,\epsilon)$
  whenever $m\geq N$.  Then $a_m\notin B(c,\epsilon)$ when $m\geq N$.
  Therefore $c$ is not a limit of $(a_n:n\in\N)$.  Neither is $c$ a
  cluster point of $\{a_n:n\in\N\}$, since $B(c,\epsilon)$ contains
  only finitely many of its points. 
\end{proof}

\begin{example*}
  The sequence $((-1)^n+1/(n+1):n\in\N)$ has two
  cluster points, namely $\pm1$, and therefore has no limit.
\end{example*}

A cluster point is the limit of \emph{something}.   A sequence $(a_n)$
of real numbers is \defn{strictly increasing} if
$$m<n\implies a_m<a_n$$
for all $m$ and $n$ in $\N$.  In particular, the identity-sequence
$(n:n\in\N)$ is strictly increasing.  If $(a_n)$ is an arbitrary sequence, and
$f$ is a strictly increasing sequence of natural numbers, then the
composition $(a_{f(i)}:i\in\N)$ is a \defn{sub-sequence} of $(a_n)$.
In particular, a sequence is a sub-sequence of itself.

\begin{lemma*}
Suppose  $\{a_n:n\in\N\}$ is a subset of, and $b$ is a point of, a
metric space.  
\begin{itemize}
\item
If $b$ is a cluster point of $\{a_n:n\in\N\}$, then some subsequence
of $(a_n:n\in\N)$ converges to $b$.   
\item
If $b$ is a limit of $(a_n:n\in\N)$ then every subsequence of
$(a_n:n\in\N)$ converges to $b$. 
\end{itemize}
\end{lemma*}

\begin{proof}
  Suppose $b$ is a cluster point of $\{a_n:n\in\N\}$.  Define a strictly
  increasing function $f:\N\to\N$ recursively as follows.  Let
  $f(0)=0$.  If $f(n)$ has been defined, let $f(n+1)$ be a number $m$
  such that $m>f(n)$ and $a_m\in B(b;1/(n+1))$.  Then
  $(a_{f(n)}:n\in\N)$ converges to $b$.  Indeed, if $r\in\N$ and
  $r\geq 1/\epsilon$, then $a_{f(r)}\in B(b;1/r)\included
  B(b;\epsilon)$.

Suppose $b$ is a limit of  $(a_n:n\in\N)$, and $f:\N\to\N$ is a
strictly increasing function.  If $U$ is a neighborhood of $b$, then
there is $N$ in
$\N$ such that, whenever $m\geq N$, we have $a_m\in U$ and in
particular $a_{f(m)}\in U$ (since $f(m)\geq m$).  Thus $(a_{f(n)}:n\in\N)$
has limit $b$.
\end{proof}

An adherent point of $\{a_n:n\in\N\}$ need not be a limit of any
sub-sequence of $(a_n)$.  The limit of a sub-sequence need not be a
cluster point of the range of the original sequence.

\begin{examples*}
  Every element of $\{1/(n+1):n\in\N\}$ is an adherent point, but the
  sequence $(1/(n+1):n\in\N)$ converges to $0$, and therefore no sub-sequence
  converges to any other limit.  The sequence
  $((-1)^n+(1+(-1)^n)/(n+1):n\in\N)$, composed with $n\mapsto 2n+1$,
  yields the sub-sequence $(-1:n\in\N)$, which converges to $-1$; but
  $-1$ is not a cluster point of $\{(-1)^n+(1+(-1)^n)/(n+1):n\in\N\}$.
\end{examples*}

Say $f$ is a function from $M$ to $\R$, and $b\in M$, and $L\in\R$.
We say $L$ is the \defn{limit} of $f$ at $b$, and write
$$\lim_b f=\lim_{x\to b}f(x)=L,$$
if for every positive $\epsilon$ there is a neighborhood $U$ of $b$
such that
$$\abs{f(x)-L}<\epsilon$$
whenever $x\in U\setminus\{b\}$.

\begin{theorem*}
  The following are equivalent:
  \begin{itemize}
    \item $\lim _b f=L$.
\item
$\lim_{n\to\infty}f(a_n)=L$ whenever $(a_n)$ is a sequence in
  $M\setminus\{b\}$ that converges to $b$.
  \end{itemize}
\end{theorem*}

\begin{lemma*}
  Convergent sequences are bounded.
\end{lemma*}

\begin{proof}
  Suppose $\lim_{n\to\infty}a_n=a$.  For some $N$, if $n\geq N$, then
  $a_n\in B(a;1)$.  Let $r=\max\{d(a,a_i):i<N\}$.  Then $a_n\in
  B(a;r+1)$ for all $n$.
\end{proof}

\news[Convergence in Euclidean spaces]
Convergence in $\R^k$ can be referred to convergence in $\R$.  In this
context, we may understand an element $\tuple a$ of $\R^k$ to be
$(a^{(0)},\dots,a^{(k-1)})$.  

\begin{lemma*}
  Suppose $(\tuple a_n:n\in\N)$ is a sequence in $\R^k$, and
  $\tuple b\in \R^k$.  Then $(\tuple a_n:n\in\N)$ converges to $\tuple
  b$ if and only if each sequence $(a^{(i)}_n:n\in\N)$ converges to $b^{(i)}$.
\end{lemma*}

\begin{proof}
  Say $\tuple c\in\R^k$.  If $\norm{\tuple c}<\epsilon$, then
  $\abs{c^{(i)}}<\epsilon$.  
Conversely, if $\abs{c^{(i)}}<\epsilon/\radix k$ in each case, then
  $\norm{\tuple c}<\epsilon$. 
\end{proof}

\begin{theorem*}
  Suppose $(\tuple a_n)$ and $(\tuple b_n)$ are sequences in $\R^k$,
  and $(r_n)$ is a sequence in $\R$.  Assume that
$$\lim_{n\to\infty}\tuple a_n=\tuple a;\quad 
\lim_{n\to\infty}\tuple b_n=\tuple b;\quad
\lim_{n\to\infty}r_n=r.$$
Then:
\begin{enumerate}
  \item
$\lim_{n\to\infty}(\tuple a_n+\tuple b_n)$ exists, and is $\tuple
    a+\tuple b$;
\item
$\lim_{n\to\infty}r_n\tuple a_n$ exists, and is $r\tuple a$;
\item
if $r\neq0$, then $\lim_{n\to\infty}r_n\inv\tuple a_n$ exists, and is
    $r\inv\tuple a$.
\end{enumerate}
\end{theorem*}

\begin{proof}
  By the last lemma, we may assume $k=1$.  Let $\epsilon>0$.

If $n$ is large enough, then
$\abs{a-a_n}<\epsilon/2$ and $\abs{b=b_n}<\epsilon/2$, and therefore
$\abs{(a+b)-(a_n +b_n)}\leq\abs{a-a_n}+\abs{b-b_n}\leq\epsilon$.

For the second part, we have
\begin{align*}
\abs{ra-r_na_n}=&\abs{ra-r_na+r_na-r_na_n}\\
           \leq &\abs{ra-r_na} +\abs{r_na-r_na_n}\\
              = &\abs a\abs{r-r_n} +\abs{r_n}\abs{r_na-r_na_n}.
\end{align*}
Since $(r_n)$ is bounded, there is $s$ such that $\abs{r_n}\leq s$ for
all $n$.  Let $n$ be so large that $\abs{r-r_n}<\epsilon/2(1+\abs a)$
and $\abs{r_na-r_na_n}<\epsilon/2s$; then $\abs{ra-r_na_n}<\epsilon$.

For the last part, it is enough to show that
$\lim_{n\to\infty}r_n\inv=r\inv$, if $r\neq0$.  But if $r\neq0$, then
$$\abs{\frac 1r-\frac 1{r_n}} = \abs{\frac{r_n-r}{rr_n}} \leq
2\frac{\abs{r_n-r}}{\abs r^2},$$
provided $n$ is large enough that $\abs{r-r_n}\leq \abs r/2$ and
consequently $\abs r/2<\abs{r_n}$.  Now require $n$ also to be large
enough that ${\abs{r_n-r}}<{\abs r^2}\epsilon/2$.
\end{proof}

\begin{exercise}
  In each of the following cases, determine whether the sequence
$$\left(\frac{\sum_{i=0}^ka_in^i}{\sum_{j=0}^{\ell}b_jn^j}:n\in\N\right)$$
has a limit; find the limit if it exists.  Here the $a_i$ and $b_j$
are real numbers, and $a_k$ and $b_{\ell}$ are not zero.
  \begin{enumerate}
    \item
$k<\ell$.
\item
$k=\ell$.
\item
$k>\ell$.
  \end{enumerate}
\end{exercise}

\news[Monotone sequences]

A sequence $(a_n)$ of real numbers is \defn{increasing} if $a_n\leq
a_{n+1}$ for all $n$.

\begin{exercise}
  Prove that, if $(a_n)$ is increasing, then $a_m\leq a_n$ whenever
  $m\leq n$.
\end{exercise}

A \defn{decreasing} sequence has the obvious definition.  A sequence
is \defn{monotone} if it is either increasing or decreasing.

\begin{examples*}
 The sequences $(2n)$ and $(-3n^2)$ are monotone, the first
  increasing, the second decreasing.  The sequence $(n+(-1)^n)$ is
  not monotone.  
\end{examples*}

\begin{theorem*}[Monotone Convergence]
  A bounded increasing sequence converges to the supremum of its range.
\end{theorem*}

\begin{proof}
  Suppose $\sup\{a_n:n\in\N\}=b$.  Then for all positive $\epsilon$,
  $b-\epsilon$ is not an upper bound for the set, so $b-\epsilon<a_N$
  for some $N$.  If $(a_n)$ is increasing, then $b-\epsilon<a_n$, and
  therefore $0<b-a_n<\epsilon$, whenever $n\geq N$.
\end{proof}

\begin{example*}
Say $0<a<2b$.  Define $(a_n)$ recursively by $a_0=a$ and
$a_{n+1}=a_n/2+b$.  Then, by induction, $a_n<2b$ and $a_n<a_{n+1}$ for
all $n$.  So $\lim_{n\to\infty}a_n$ exists; say it is $c$.  This is
also the limit of $a_n/2+b$, so $c=c/2+b$, whence $c=2b$.
\end{example*}

\news[Completeness]

In a space with metric $d$, a sequence $(a_n)$ is called \defn{Cauchy}
if for all positive $\epsilon$ there is $N$ such that
$$d(a_m,a_n)<\epsilon$$
whenever $m,n>N$.

\begin{lemma*}
  Every convergent sequence is a Cauchy sequence.
\end{lemma*}

\begin{proof}
  Suppose $\lim_{n\to\infty}a_n=b$.  If $\epsilon>0$, let $N$ be such that
$$m\geq N\implies d(a_m,b)<\frac{\epsilon}2.$$
Then
\begin{align*}
  m,n\geq N&\implies d(a_m,b),d(a_n,b)<\frac{\epsilon}2\\
&\implies d(a_m,a_n)\leq  d(a_m,b)+d(a_n,b)<{\epsilon},
\end{align*}
so $(a_n)$ is Cauchy.
\end{proof}

\begin{example*}
  The sequence $(1/n)$ is a sequence in $(0,1)$ with the usual metric;
  it converges in $\R$ to $0$, so it is Cauchy---but not
  convergent---in $(0,1)$. 
\end{example*}

\begin{lemma*}
  Every Cauchy sequence is bounded, and if some subsequence converges,
  then the whole sequence converges to the same limit.
\end{lemma*}

\begin{proof}
  Say $(a_n)$ is Cauchy.  Let $N$ be such that
$$m,n\geq N\implies d(a_m,a_n)<1.$$
Let $r=\max\{d(a_m,a_N):m<N\}$.  Then $a_m\in B(a_N;r+1)$ for all $m$,
so $(a_n)$ is bounded.  Also, suppose $f:\N\to\N$ is strictly increasing,
and $\lim_{n\to\infty}a_{f(n)}=b$.  If $\epsilon>0$, let $M$ and $M'$
be such that
\begin{align*}
  m\geq M &\implies d(a_m,b)<\frac{\epsilon}2,\\
m,n\geq M' &\implies d(a_n,a_m)<\frac{\epsilon}2.
\end{align*}
Now let $m=f(\max\{M,M'\})$.  Then $m\geq M$ and $m\geq M'$ (why?).
Therefore
$$n\geq M'\implies d(a_n,b)\leq d(a_n,a_m)+d(a_m,b)<\epsilon.$$
Therefore $(a_n)$ converges to $b$.
\end{proof}

\begin{exercise}
  If $f:\N\to\N$ is strictly increasing, prove by induction that
  $f(n)\geq n$ for all $n$ in $\N$.
\end{exercise}

A metric space is \defn{complete} if every Cauchy sequence in the
space converges.

\begin{theorem*}
  $\R^k$ is complete.
\end{theorem*}

\begin{proof}
Let $(a_n)$ be a Cauchy sequence in $\R^k$.  Then $\{a_n\}$ is
  bounded.  If this set is finite, then it converges (why?).  If this
  set is infinite, then it has a cluster point by 
  the Bolzano--Weierstra\ss\ Theorem.  In this case, $(a_n)$ has a
  convergent subsequence, by an earlier lemma, so the sequence itself
  converges, by the preceding lemma.
\end{proof}

\begin{exercise}
  Supply the missing detail in the proof.
\end{exercise}

So $\R$ is complete in two senses: as an ordered field, and as a
metric space.

\begin{exercise}
  Let $K$ be a subfield of $\R$; so $K$ is an ordered field, and $K$
  inherits a metric from $\R$.  Prove that $K$ is complete as an
  ordered field $\iff$ it is complete as a metric space.  
\end{exercise}

With the usual metric, $\Q$ is not complete.  Are other metrics on
$\Q$ possible?  Besides the trivial metric, there is a metric for each
prime $p$.  Indeed, every non-zero rational number can be written as
$$\frac ab p^n$$
for some integers $a$, $b$ and $n$, where $p$ does not divide $a$ or
$b$, and $n$ is unique.  Then we define a new absolute value on $\Q$
by
$$\abs{\frac ab p^n}_p=\frac 1{p^n}$$
and $\abs0_p=0$.  Finally, define a metric $d_p$ by
$$d_p(x,y)=\abs{x-y}_p.$$
\begin{exercise}
  Prove that $d_p$ is in fact a metric.
\end{exercise}
Here, $d_p$ is the \tech{$p$-adic metric}.  With this metric, $\Q$ is
a subfield and a subspace of a field called $\Q_p$, which is complete
as a metric space; the
study of this field is \tech{$p$-adic analysis}.  We shall not pursue
it here.

\begin{theorem*}
  Every compact metric space is complete.
\end{theorem*}

\begin{proof}
    The proof that $\R^k$ is complete is really a proof that a metric
    space is complete, provided that every bounded infinite subset has
    a cluster point.  This is a property of compact metric spaces, by
    an earlier theorem.
\end{proof}