\documentclass{ymexam}

\usepackage{a4wide,times,amsmath,amssymb}

\newcommand{\N}{{\mathbb{N}}}
\newcommand{\R}{{\mathbb{R}}}
\DeclareMathOperator{\Int}{int}
\DeclareMathOperator{\ext}{ext}
\newcommand{\eps}{\varepsilon}

\begin{document}

\codenumber{0590313}
\year{2006}
\title{Metric Spaces}
\duration{$1\half$ hours}

\begin{rubric}
  Answer \underline{three} questions. \\
  Please write your answers in ink; pencil is acceptable for graphs and
  diagrams. Do not use red ink.\\
  Standard calculators will be provided.\\
  The marking scheme shown on each question is indicative only.
\end{rubric}

\maketitle

\begin{question}
  Suppose $X$ is a non-empty set and that $d:X\times X\to\R$. What
  properties must $d$ satisfy, in order for it to be a \emph{metric} on $X$?
  If $x_0\in X$ and $r>0$, define the \emph{open ball} $B(x_0,r)$. \marks{8}
  
  Show that the function defined by
  $$d_0(x,y)=\begin{cases}
              1 & \text{ if } x\neq y \\
              0 & \text{ if } x=y
             \end{cases}$$
  is a metric (the \emph{discrete metric}) on $X$.\marks{5}
  
  If $d$ is a metric on $X$ and $A\subseteq X$, define the interior $\Int(A)$, 
  the exterior $\ext(A)$ and the boundary $\partial A$ in the metric
  space $(X,d)$. Show that $A$ and its complement $A^c$ have the same boundary.
  \marks{8}
  
  Define the terms \emph{open} and \emph{closed}, as applied to the set $A$ 
  in $(X,d)$. Show that, under the discrete metric, all sets are both open and 
  closed, and have empty boundary.\marks{9}
\end{question}

\begin{question}
  Suppose $(X,d)$ is a metric space, $(x_n)_{n\in\N}$ is a sequence
  in $X$ and $x\in X$. What does it mean to say that $x_n$
  \emph{converges} to $x$ as $n\to\infty$? Show that if, as $n\to\infty$, 
  $x_n\to x$ and $x_n\to y$ then $x=y$.\marks{10}
  
  Suppose a sequence $(f_n)_{n\in\N}$ converges to a limit $f$ in the
  metric space $C[a,b]$ (continuous, real-valued functions on the 
  interval $[a,b]$), with the uniform metric 
  $$d_\infty(f,g)=\sup_{t\in[a,b]}|f(t)-g(t)|=\max_{t\in[a,b]}|f(t)-g(t)|.$$  
  Show that $f_n$ also converges pointwise to $f$; that is, that for
  each $t\in[a,b]$ we have $f_n(t)\to f(t)$ in $\R$.\marks{4}
  
  Consider the following sequences in $C[0,1]$:
  \begin{align*}
    g_n(t) &= \frac{\sin(nt)}{n}; \\
    h_n(t) &= \frac{nt}{1+(nt)^2}.
  \end{align*}
  Indicate briefly why both of these sequences converge pointwise to $0$, and 
  determine whether or not each one converges to $0$ in the uniform metric.
  \marks{16}
\end{question}

\begin{question}
  Suppose $(X,d)$ is a metric space and $f:X\to X$ is a function. What
  does it mean to say that a real number $k\geq 0$ is a 
  \emph{Lipschitz constant} for $f$? Show that if $f$ is a Lipschitz 
  function (that is, one for which a Lipschitz constant exists)
  then $f$ is continuous.\marks{10}
  
  If $X$ is the interval $[a,b]$ with the standard metric, $f$ is
  differentiable on $[a,b]$ and $f'$ is continuous on $[a,b]$, use the
  Mean Value Theorem to show that the smallest Lipschitz constant for $f$ is 
  $$\max_{t\in[a,b]}|f'(t)|.\marks{5}$$
  
  State without proof the \emph{Contraction Mapping Theorem} \marks{6}
  and use it to show that there is exactly one solution in the interval 
  $[0,1]$ to the equation $t=1-\cos(1-t)$.\marks{6}
  
  Starting from $t_0=0.25$, use a calculator to find the next three steps in 
  the iteration converging to this solution.\marks{3}
\end{question}

\begin{question}
  What is meant by a \emph{subsequence} of a sequence $(x_n)_{n\in\N}$ in a 
  metric space $(X,d)$? Show that if $x_n\to x\in X$ as $n\to\infty$
  then any subsequence of $(x_n)_{n\in\N}$ also converges to $x$.\marks{9}
  
  In $\R$ with the standard metric, give examples of:
  \begin{enumerate}
  \item a sequence with no convergent subsequence;
  \item a divergent sequence with a convergent subsequence
  \end{enumerate}
  (and indicate why your examples have these properties).\marks{8}
  
  What does it mean to say that a metric space $(X,d)$ is \emph{sequentially 
    compact?} Show that the following spaces are \emph{not} sequentially
  compact:

  \begin{enumerate}
  \item the open interval $(0,1)\subseteq\R$ with the standard metric;
  \item the set
    $$\{f:[0,1]\to\R:
      \text{ $f$ is continuous and $|f(t)|\leq 1$ for all $t\in[0,1]$}\}$$
    with the uniform metric $d_\infty$ (defined in Question~2).\marks{13}
  \end{enumerate}
  
\end{question}

\begin{solution}
  The three properties of a metric are:
  \begin{description}
  \item[M1] $d(x,y)\geq 0$ for all $x,y\in X$ and $d(x,y)=0$ if and only if $x=y$
    \marks{2}
  \item[M2] $d(x,y)=d(y,x)$ for all $x,y\in X$\marks{2}
  \item[M3] $d(x,y)\leq d(x,z)+d(z,y)$ for all $x,y,z\in X$.\marks{2}
  \end{description}
  The ball is defined by
  $$B(x_0,r)=\{x\in X:d(x_0,x)<r\}.\marks{2}$$
  M1 and M2 are clear from the definition. \marks{1}
  M3 is clear in the case $x=y$, since then the LHS is zero and the
  RHS is non-negative. In the case that $x=y$, so the LHS is $1$, 
  we must have either $x\neq z$ or $z\neq y$, so the RHS is either $1$
  or $2$, showing that M3 is true in this case too. \marks{4}

  The interior of $A$ is the set
  $$\Int(A)=\{x\in X:B(x,r)\subseteq A\text{ for some $r>0$}\}\marks{2}$$
  The exterior of $A$ is the set
  $$\ext(A)=\{x\in X:B(x,r)\subseteq A^c\text{ for some $r>0$}\}\marks{2}$$
  The boundary of $A$ is the set
  $$\partial A=\{x\in X:\text{ for all $r>0$, $B(x,r)$ intersects both
    $A$ and $A^c$}\}\marks{2}$$
  $A$ and $A^c$ have the same boundary because the definition of
  $\partial A$ is symmetric in $A$ and $A^c$. \marks{2}
  
  $A$ is open if it contains none of its boundary ($A\cap\partial A=\emptyset$),
  \marks{2} and closed if it contains all of its boundary ($\partial
  A\subseteq A$).\marks{2}

  In the discrete metric $d_0$, we have
  $$B(x_0,1)=\{x\in X:d_0(x_0,x)<1\}=\{x_0\}$$
  If $x\in A$ then $B(x,1)=\{x\}\subseteq A$ and if $x\in A^c$ then 
  $B(x,1)=\{x\}\subseteq A$. It follows that $\Int(A)=A$, that
  $\ext(A)=A^c$ and that $\partial A=\emptyset$. \marks{3}
  Since the boundary is empty, we have both $A\cap\partial A=\emptyset$ and 
  $\partial A\subseteq A$, so $A$ is both open and closed.\marks{2}

  \begin{remarks}
    All familiar stuff. The definition of open and closed is unusual, of
    course, but this is the way I did it in lectures. If someone uses
    the more conventional approach, then of course they'll get full credit.
  \end{remarks}
\end{solution}

\begin{solution}
  $x_n$ converges to $x$ as $n\to\infty$ if for any $\eps>0$ there
  exists $N\in\N$ such that if $n>N$ then $d(x_n,x)<\eps$.\marks{3}
  
  If both $x_n\to x$ and $x_n\to y$ then for any $\eps>0$ there exist
  $M,N\in\N$ such that if $n>M$ then $d(x_n,x)<\eps/2$ and if $n>N$ then
  $d(x_n,y)<\eps/2$. If $n>\max(M,N)$ then
  $$d(x,y)\leq d(x,x_n)+d(x_n,y)<\frac{\eps}{2}+\frac{\eps}{2}=\eps$$
  since this is true for all $\eps>0$, $d(x,y)\leq 0$. But $d(x,y)\geq 0$ by
  definition, so $d(x,y)=0$ and hence $x=y$.\marks{7}

  For any given $t\in[a,b]$, we have
  $$|f_n(t)-f(t)|\leq\sup_{t\in[a,b]}|f_n(t)-f(t)|=d_\infty(f_n,f)$$
  It follows that if $f_n\to f$ in the uniform metric, then $f_n(t)\to
  f(t)$ for each $t$.\marks{4}

  Since $|\sin(nt)|/n\leq1/n\to 0$, we have $g_n(t)\to 0$ for any $t$; also
  $$h_n(t)=\frac{1/(nt)}{1/(nt)^2+1}\to 0$$
  for any $t$.\marks{4}
  Calculate:
  \begin{align*}
    d_\infty(g_n,0) &=    \sup_{t\in[0,1]}|f_n(t)-0| \\
                    &=    \sup_{t\in[0,1]}\frac{|\sin(nt)|}{n} \\
                    &\leq \frac{1}{n} \\
                    &\to  0 \text{ as $n\to\infty$}
  \end{align*}
  which shows that $g_n\to 0$ in the metric $d_\infty$.\marks{5}
  
  Notice that $h_n(t)=h_1(nt)$, and choose $t_0\in(0,1)$, so $h_1(t_0)>0$.
  Since $h_n(t_0/n)=h_1(t_0)$, we have
  \begin{align*}
    d_\infty(h_n,0) &=    \sup_{t\in[0,1]}|h_n(t)-0| \\
                    &=    \sup_{t\in[0,1]}h_n(t) \\
                    &\geq h_n(t_0/n) \\
                    &=    h_1(t_0)
  \end{align*}
  This shows that $d_\infty(h_n,0)\nrightarrow 0$ as $n\to\infty$, so $h_n$
  does not converge to $0$ in the metric $d_\infty$.\marks{7}
  \begin{remarks}
    All familiar ideas; but of course these particular examples are unseen.
  \end{remarks}
\end{solution}

\begin{solution}
  A Lipschitz constant is a constant $k\geq 0$ with the property that
  $d(f(x),f(y))\leq kd(x,y)$ for all $x,y\in X$.\marks{3}
  
  If $f$ has a Lipschitz constant of $0$, then it is evidently
  constant, and hence continuous. If $f$ has a Lipschitz constant $k>0$,
  then for any $\eps>0$ we let $\delta=\eps/k$, so if $d(x,y)<\delta$
  then $d(f(x),f(y))\leq kd(x,y)<k\delta=\eps$, showing that $f$ is
  uniformly continuous on $X$.
  
  Let
  $$k=\max_{t\in[a,b]}|f'(t)|.$$
  If $s,t\in[a,b]$ and $s\neq t$ then, by the mean value theorem,
  $$|f(s)-f(t)|=|f'(\tau)||s-t|\leq k|s-t|$$
  where $\tau$ is some number between $s$ and $t$. If $s=t$ then
  $|f(s)-f(t)|=0=k|s-t|$, so $k$ is indeed a Lipschitz constant for $f$.
  \marks{7}
  To show that $k$ is the minimal Lipschitz constant, choose some $t_0$
  such that $|f'(t_0)|=k$. This means that
  $$\frac{|f(t)-f(t_0)|}{|t-t_0|}\to k$$
  as $t\to t_0$. In particular, for any $\eps>0$ we can choose $t$ such
  that 
  $$\frac{|f(t)-f(t_0)|}{|t-t_0|}>k-\eps$$
  This shows that $k-\eps$ is not a Lipschitz constant for $f$, so $k$
  is the minimal Lipschitz constant.\marks{5}
  
  The contraction mapping theorem states that if $(X,d)$ is a complete
  metric space and $F:X\to X$ has a Lipschitz constant $k<1$ then $F$
  has a unique fixed point in $X$. Moreover, for any $x_0\in X$ the
  iterates $(F^{(n)}(x_0))_{n\in\N}$ converge to the fixed point as
  $n\to\infty$.\marks{6}
  
  Let $f(t)=1-\cos(1-t)$. If $t\in[0,1]$ then $\cos(t)\in[0,1]$, so 
  $1-\cos(1-t)\in[0,1]$ also. This shows that $f$ leaves invariant the
  complete metric space $[0,1]$.
  
  We have $f'(t)=\sin(1-t)$. On the interval $[0,1]$, $\sin$ is non-negative 
  and increasing, so
  $$\max_{t\in[0,1]}|\sin(1-t)|=\sin(1)$$
  This shows that $f$ has Lipschitz constant $\sin(1)<1$, and hence by
  the contraction mapping theorem a unique fixed in point in $[0,1]$.\marks{6}

  Starting from $t_0=0.25$, we have $t_1=f(t_0)\approx 0.268$,
  $t_2=f(t_1)\approx 0.256$ and $t_3=f(t_2)\approx 0.264$. \marks{3}
  
  \begin{remarks}
    Again, all familiar but an unseen example of a contraction.
  \end{remarks}
\end{solution}

\begin{solution}
  If $(n_k)_{k\in\N}$ is a strictly increasing sequence of natural
  numbers, then the sequence $(x_{n_k})_{k\in\N}$ is a subsequence of 
  $(x_n)_{n\in\N}$.\marks{3}
  Suppose $x_n\to x$ as $n\to\infty$ and we have a subsequence
  $(x_{n_k})_{k\in\N}$. Then for any $\eps>0$ there exists $N\in\N$ such
  that if $n>N$ then $d(x_n,x)<\eps$. Since $(n_k)_{k\in\N}$ is strictly
  increasing in $\N$, we have $n_k\geq k$ for all $k$. If follows that
  if $k>N$ then $n_k>N$, so $d(x_{n_k},x)<\eps$, showing that
  $x_{n_k}\to x$ as $k\to\infty$\marks{6}
  \begin{enumerate}
  \item Let $x_n=n$. Then any subsequence $(x_{n_k})$ has
    $x_{n_k}>k$, so $x_{n_k}\to\infty$ as $k\to\infty$. This shows that
    there is no convergent subsequence.\marks{4}
  \item Let $x_n=(-1)^n$. Then $x_{2n}=1$ and $x_{2n+1}=-1$. These
    subsequences are trivially convergent, and the fact that they have
    different limits shows that $(x_n)_{n\in\N}$ itself is divergent.
    \marks{4}
  \end{enumerate}
  A metric space $(X,d)$ is called sequentially compact if every
  sequence in $X$ has a convergenbt subsequence.\marks{3}
  \begin{enumerate}
  \item Let $x_n=1/n$. Since $x_n\to 0$ as $n\to\infty$ in $\R$, every 
    subsequence of $(x_n)_{n\in\N}$ also converges to $0$ in $\R$. If a
    subsequence were to converge in $(0,1)$, then it would also
    converge in $\R$, and would thus have two distinct limits in $\R$,
    which is impossible; it follows that no subsequence can converge in
    $(0,1)$. \marks{5}
  \item Let $f_n(t)$ be a continuous function on $[0,1]$ which is zero outside
    the interval $I_n=[1/(n+1),1/n]$ and has a maximum value of $1$ over 
    $I_n$. Then, if $m\neq n$ $|f_m-f_n|=|f_n|$ on $I_n$, so
    $d_\infty(f_m,f_n)\geq 1$. This shows that $(f_n)_{n\in\N}$ has no
    Cauchy subsequence, and hence no convergent subsequence.\marks{5}
    
  \end{enumerate}
  \begin{remarks}
    Nothing at all new here, but the technical details are tricky.
  \end{remarks}

\end{solution}


\end{document}

