analysis--oxford-A2-I-metric-spaces.tex

\documentclass[12pt]{article}
\usepackage{enumerate}
\usepackage{mathematics}

\DeclareMathOperator{\diam}{\mathrm{diam}}


\title{Oxford A2 - I - Metric Spaces
  \footnotetext{\url{https://courses.maths.ox.ac.uk/node/5378}}} \author{Dan Davison}
\author{}
\date{}

\begin{document}

\maketitle
\tableofcontents

\section{Sheet 1}

\subsection{}
\begin{mdframed}
\includegraphics[width=400pt]{img/oxford-a2-1-1.png}
\end{mdframed}

\begin{remark*}
  $d$ is the Hamming distance.
\end{remark*}

For $d$ to be a metric on $X$ we require
\begin{enumerate}
\item \textbf{$d$ is a function $d:X \times X \to $ (a set of non-negative numbers).}\\
  Yes, this is true.
\item \textbf{Positivity}:\\
  Yes, cardinality is never negative and it is clear that $d(a,b) = 0 \iff a = b$.
\item \textbf{Symmetry}:\\
  Yes, follows from the fact that $a_i \neq b_i \iff b_i \neq a_i$.
\item \textbf{Triangle inequality}:\\
  % Want: $d(a, b) \leq d(a, c) + d(c, b)$ for all $a, b, c \in X$.
  Note that $d(a, b) = \sum_{i=1}^n \epsilon_{a_i,b_i}$, where $\epsilon_{ij} :=
  \begin{cases}
    0, ~~~ i = j\\
    1, ~~~ i \neq j
  \end{cases}
$ (the ``negation'' of the Kronecker delta).

  Fix $i \in \{1, 2, \ldots, n\}$. Suppose that $\epsilon_{a_i,b_i} = 0$. Then
  $\epsilon_{a_i,b_i} \leq \epsilon_{a_i,c_i} + \epsilon_{c_i,b_i}$. Alternatively suppose that
  $\epsilon_{a_i,b_i} = 1$. Then we have either $\epsilon_{a_i,c_i} = 0$, in which case
  $\epsilon_{c_i,b_i} = \epsilon_{a_i,b_i} = 1$, or we have $\epsilon_{a_i,c_i} = 1$.

  Therefore $\epsilon_{a_i,b_i} \leq \epsilon_{a_i,c_i} + \epsilon_{c_i,b_i}$, and therefore
  $\sumin \epsilon_{a_i,b_i} \leq \sumin \epsilon_{a_i,c_i} + \sumin \epsilon_{c_i,b_i}$, as required.
\end{enumerate}

Recall that $d_1:\R^n\times\R^n\to\R_{\geq 0}$ is given by $d_1(a, b) := \sum_{i=1}^n|a_i - b_i|$.

Let $\Omega = \{0, 1\} \subseteq \R$ and let $a, b \in \Omega^n \subseteq \R^n$.

Note that $|a_i - b_i| = \epsilon_{a_ib_i}$.

Therefore $d_1(a, b) = \sum_{i=1}^n\epsilon_{a_ib_i} = d(a, b)$, as required.

\newpage
\subsection{}
\begin{mdframed}
\includegraphics[width=400pt]{img/oxford-a2-1-2.png}
\end{mdframed}

\begin{claim*}
  $A \cup B$ is bounded and $\diam(A \cup B) \leq \diam(A) + \diam(B)$.
\end{claim*}

\begin{proof}
  Let $c_1, c_2 \in A \cup B$.

  Note that $c_1, c_2 \in A \implies d(c_1, c_2) \leq \diam(A)$ and
  $c_1, c_2 \in B \implies d(c_1, c_2) \leq \diam(B)$.

  Suppose, without loss of generality, that $c_1 \in A$ and $c_2 \in B$. Let $c_3 \in A \cap
  B$. Then by the triangle inequality we have
  $d(c_1, c_2) \leq d(c_1, c_3) + d(c_3, c_2) \leq \diam(A) + \diam(B)$.

  Therefore $A \cup B$ is bounded and $\diam(A \cup B) \leq \diam(A) + \diam(B)$.
\end{proof}


\begin{claim*}
  If $A \subseteq B$ then $\diam(A) \leq \diam(B)$.
\end{claim*}

\begin{proof}
  Let $A \subseteq B$, and suppose for a contradiction that $\diam(A) > \diam(B)$. Then there exist
  $a_1, a_2 \in A$ such that $d(a_1, a_2) > \diam(B)$. But since $A \subseteq B$ we have
  $a_1, a_2 \in B$. This contradicts the definition of $\diam(B)$ as the supremum over distances
  between pairs of elements of $B$. Therefore $\diam(A) \leq \diam(B)$.
\end{proof}


\newpage
\subsection{}
\begin{mdframed}
\includegraphics[width=400pt]{img/oxford-a2-1-3.png}
\end{mdframed}

\begin{lemma*}
  Let $f:V \to W$ be a linear map between normed vector spaces. Then $f$ is continuous if and only
  if $\{\norm{f(x)} : \norm{x} \leq 1\}$ is bounded.
\end{lemma*}

\begin{proof}
  See $\epsilon-\delta$ argument in lecture notes.
\end{proof}

% \begin{claim*}
%   The Euclidean norm is independent of basis.
% \end{claim*}

% \begin{proof}~\\
%   Let $B$ and $B'$ be bases of $\R^n$ and let $P$ be a matrix with the elements of $B'$ as its
%   columns.

%   I.e. if $v$ contains the coordinates of a vector with respect to basis $B$, Then $Pv$...

%   With respect to $B$, we have $\norm{v} = \sqrt{\sumin v_i^2}$.

%   With respect to $B'$, we have $\norm{v} = \sqrt{\sumin (Pv_i)^2}$.
% \end{proof}

\begin{claim*}
  $\{\norm{\alpha(x)} : \norm{x} \leq 1\}$ is bounded. \Intuition{the image of the unit sphere is
    bounded in norm}
\end{claim*}

\begin{proof}
  Note that $\norm{\alpha(x)}^2 := \sum_{i=1}^n \alpha(x)_i^2$, where $\alpha(x)_i$ is the $i$-th
  coordinate of $\alpha(x)$ with respect to the standard basis.

Therefore it is sufficient to show that $\{|\alpha(x)_i| : \norm{x} \leq 1\}$ is bounded for all
$1 \leq i \leq n$.

Let $a_i$ be the $i$-th row of the $m \times n$ matrix of $\alpha$.

Then $|\alpha(x)_i| = |\langle a_i, x \rangle| \leq \norm{a_i}\norm{x}$.
\end{proof}

% \begin{intuition*}
%   The proof of the (linear, continuous) $\iff$ (linear, image bounded in norm) lemma uses
%   $\epsilon-\delta$ arguments. Then we use Cauchy-Schwarz to show that the image of the unit
%   sphere is bounded in norm as prescribed.
% \end{intuition*}

\newpage
\subsection{}
\begin{mdframed}
\includegraphics[width=400pt]{img/oxford-a2-1-4.png}
\end{mdframed}

\begin{proof}~\\
  Let $B(x, r)$ be an open ball of radius $r$ centered at $x$.

  Note that for every $\delta > 0$ there exists $N \in \N$ such that $d(x_n, \ell) < \delta$ for all
  $n > N$.

  Let $y \neq \ell$ and let $N = \min\{n ~|~ d(x_n, \ell) < d(y, \ell)\}$.

  Let $M = \argmin_{n \in \{1, \ldots, N\}} D(n)$, where $D:\N \to \R$ is defined by
  $D(n) :=
  \begin{cases}
    d(x_n, y), &x_n \neq y\\
    \infty, &x_n = y
  \end{cases}$.

  Informally, $x_M$ is the element of $S$ that is closest but not equal to $y$.

  Note that $\Big(B(\ell, \frac{x_M - y}{2})\setminus\{\ell\}\Big) \cap S = \emptyset$.

  Therefore $y \neq \ell \implies y \notin S'$, or equivalently, $S' \seq \{\ell\}$.

  Now suppose that $S$ is such that there exists $N \in \N$ such that $x_n = \ell$ for all $n > N$.

  Let $M = \max\{n ~|~ x_n \neq \ell\}$.

  Note that $\Big(B(\ell, \frac{x_M - \ell}{2})\setminus\{\ell\}\Big) \cap S = \emptyset$.

  Therefore it is possible that $\ell \notin S'$, or equivalently, $S' = \emptyset$.
\end{proof}

\newpage
\begin{mdframed}
\includegraphics[width=400pt]{img/oxford-a2-1-5-1.png}
\end{mdframed}

\begin{lemma*}
  Let $X$ and $Y$ be metric spaces. $h:X \to Y$ is continuous iff for every open set $U \in Y$, the
  preimage $h^\1(U)$ is an open set in $X$.
\end{lemma*}

\begin{claim*}
  $(g \circ f):R \to T$ is continuous.
\end{claim*}

\begin{proof}
Let $U_T$ be an open set of $T$.

Note that $(g \circ f)^\1(t) = f^\1(g^\1(t))$.

By the lemma, since $f$ and $g$ are continuous, $f^\1(g^\1(U_T))$ is an open set in $R$.
\end{proof}

\begin{mdframed}
\includegraphics[width=400pt]{img/oxford-a2-1-5-2.png}
\end{mdframed}

Where does it fail?

\begin{enumerate}
\item Positivity?
\item Symmetry?
\item Triangle inequality?
\end{enumerate}

\begin{mdframed}
\includegraphics[width=400pt]{img/oxford-a2-1-5-3.png}
\end{mdframed}

\begin{definition*}
  A subset $X \seq M$ is open if at every point $x \in X$ there exists a $\delta$ such that
  $B(x, \delta) \seq X$.
\end{definition*}

\begin{proof}~\\
  If $M$ is empty it is vacuously true, so suppose $M$ is not empty.

  $M$ itself is open since there are no points outside $M$, so any ball centred on a point of $M$
  must be a subset of $M$.

  Suppose that $X \subset (M, d)$ is not open.

  Then there exists $x \in X$ with the following property: there does not exist $\delta > 0$ such
  that $B(x, \delta) \seq X$.

  However, $M$ is finite. Therefore we may pick the element of $M$ that is closest to $x$, and set
  $\delta$ to be half this distance.

  This contradiction shows that no such non-open $X$ exists.
\end{proof}

\begin{mdframed}
\includegraphics[width=400pt]{img/oxford-a2-1-6-1.png}
\end{mdframed}

\begin{enumerate}
\item $(-5, 1) \cup (0, \infty) = (-5, \infty)$ open, not closed
\item $(-\infty, 2]$ not open, closed
\item $\{0\}$ not open, closed
\item $(0, 2]$ not open, not closed
\item $\R$ open, closed
\item $\Q$ not open, not closed (any interval $I \seq \R$ contains both rationals and irrationals)
\item $\Z$ not open, closed
\item $\emptyset$ open, closed
\end{enumerate}

\begin{mdframed}
\includegraphics[width=400pt]{img/oxford-a2-1-6-2.png}
\end{mdframed}

\begin{enumerate}
\item $[0, 1] \times \{0\}$ not open, closed\\
  \begin{tiny}
    A ball at any point will contain points outside, so not open.\\
    Complement is open, so closed.
    \par
  \end{tiny}
\item $(0, 1) \times \{0\}$ not open, not closed\\
  \begin{tiny}
    A ball at any point will contain points outside (by poking out in the y direction), so not open.\\
    Complement is not open (e.g. contains origin)
    \par
  \end{tiny}
\item $\{(x,y) ~|~ 1 < 4x^2 + y^2 < 4\}$ open, not closed\\
  {\tiny
    Region sandwiched between inner and outer ellipse.\\
    Clearly open, complement not open.
    \par}
\item $\{(x,y) ~|~ xy = 1\}$ not open, closed\\
  {\tiny
    clearly not open, e.g. ball at $(1,1)$ leaves the set\\
    complement is open
    \par}
\item $\Z \times \R$ not open, closed\\
  {\tiny
    Collection of horizontal lines.\\
    Not open, any ball will poke up/down in the y-direction, leaving the set.\\
    Complement is $\R^2$ with a collection of horizontal lines deleted.\\
    So complement is open.
    \par}
\item $\{(x,y) ~|~ x \in \Z \text{~and~} y > 0\}$ not open, not closed\\
  {\tiny
    Vertical lines, starting just above the y=0 line.\\
    Clearly not open.\\
    Complement not open, since it includes the y=0 line.
    \par}
\item $\{(x,y) ~|~ \exp(x^2 + y^2) = 1 + (y^3 - x^3)(x^7 + y^7)\}$ not open, closed\\
  \begin{tiny}
    One equation in 2D ambient space $\implies$ no solutions or a line of solutions.\\
    0 is a solution $\implies$ line of solutions $\implies$ not open, closed.\\
    \par
  \end{tiny}
\end{enumerate}

\newpage
\begin{mdframed}
\includegraphics[width=400pt]{img/oxford-a2-1-7.png}
\end{mdframed}

% \begin{remark*}
%   Since on a closed interval every continuous function is bounded and attains its bounds, the
%   supremum metric here is just a max metric.
% \end{remark*}

\begin{mdframed}
\begin{lemma*}
  Let $f:V \to W$ be a linear map between normed vector spaces. Then $f$ is continuous if and only
  if $\{\norm{f(v)} : \norm{v} \leq 1 \}$ is bounded.
\end{lemma*}

\begin{proof}
  See question 3.
\end{proof}
\end{mdframed}

% \url{https://math.stackexchange.com/questions/975759/are-differentiation-and-integration-continuous-functions}

\begin{enumerate}[label=\roman*)]
\item \textbf{Is $C^1[a,b]$ a closed subset of $C[a,b]$?}
  \red{TODO}

  $C^1[a,b] \seq C[a, b]$ is closed iff its complement is open.

  To answer this question we can either show that its complement is not open (could be done by
  counter-example), or open (requires positive proof).

  The complement of $C^1[a,b] \seq C[a, b]$ is the set of continuous functions that are not
  continuously differentiable. An example is $x \mapsto |x|$.

  Counter-example approach: if we could exhibit a pair of functions $f \in (C^1[a,b])^C$ and
  $g \in C^1[a,b]$, such that the distance between $f$ and $g$ can be made arbitrarily small, then
  this would prove that $(C^1[a,b])^C$ is not open and hence that $C^1[a,b]$ is not a closed subset
  of $C[a,b]$.

% \item Let $f,g \in C^1[a,b]$, let $h = f - g$ and fix $\epsilon > 0$.

%   For continuity at $f$ we seek $\delta > 0$ such that
%   \begin{align*}
%     & \sup_{x \in [a,b]} |f(x) - g(x)| < \delta \implies \sup_{x \in [a,b]} |f'(x) - g'(x)| < \epsilon\\
%     \iff & \sup_{x \in [a,b]} |(f - g)(x)| < \delta \implies \sup_{x \in [a,b]} |(f - g)'(x)| < \epsilon\\
%     \iff & \sup_{x \in [a,b]} |h(x)| < \delta \implies \sup_{x \in [a,b]} |h'(x)| < \epsilon.
%   \end{align*}
%   Suppose that such a $\delta$ exists.

\newpage
\item \textbf{Is differentiation continuous?}\\

  \begin{proof} (I)~\\
    Let $C[a,b]$ be the metric space of continuous functions on $[a,b]$ equipped with the supremum
    metric.

    Let $C^1[a,b]$ be the metric space of continuously differentiable functions on $[a,b]$ also
    equipped with the supremum metric.

    Note that the differentiation operator $D:C^1[a,b] \to C[a,b]$ is a linear map between vector
    spaces.

    Define a norm on $C[a,b]$ by $\norm{f} := \sup_{x\in [a,b]}|f(x)|$.

    Then, according to the lemma, $D$ is continuous if and only if
    $\{\norm{D(f)} : \norm{f} \leq 1 \}$ is bounded.

    Suppose for a contradiction that $M$ is such a bound.

    But consider the logistic function $f:[a,b] \to (0, 1)$ given by
    $f(x) := (1 + e^{-4(M+1)(x-a)})^{-1}$.

    Clearly $\norm{f} < 1$.

    Its derivative is $f'(x) = 4(M+1)f(x-a)(1-f(x-a))$ which (I assert) is continuous.

    So we have $f \in C^1[a,b]$ and $\norm{f} < 1$ and yet $f'(a) = M+1$.

    Therefore no such bound $M$ exists. Therefore the differentiation operator is not continuous.
  \end{proof}

  \begin{proof} (II Alex Coward)~\\
    Define $D:C^1[a,b] \to C[a,b]$ to be differentiation.

    We construct a sequence of functions that tend to the zero function, but whose derivatives
    always have image $[0, 1]$.

    Define $f_n(x) := \frac{1}{n}\sin\(\frac{nb}{2\pi}(x - a)\)$.

    Note that $(D f_n)(x) = \frac{b}{2\pi}\cos\(\frac{nb}{2\pi}(x - a)\)$.

    Note also that $\limn f_n = 0$.

    Suppose for a contradiction that $D$ is continuous.

    Then $\limn D(f_n) = D(\limn f_n) = D(0) = 0$.


  \end{proof}

\newpage
\item \textbf{Is integration continuous?}\\
  Let $C[a,b]$ be the metric space of continuous functions on $[a,b]$ equipped with the supremum
  metric.

  Let $C^1[a,b]$ be the metric space of continuously differentiable functions on $[a,b]$ also
  equipped with the supremum metric.

  Note that the integration operator defined by $F(f) := \int_a^x f$ is a linear map between vector
  spaces.

  Define a norm on $C[a,b]$ as $\norm{f} := \sup_{x\in [a,b]}|f(x)|$.

  Then, according to the lemma, $F$ is continuous if and only if
  $\{\norm{F(f)} : \norm{f} \leq 1 \}$ is bounded.

  Note that on a closed interval every continuous function is bounded.

  Let $f \in C[a,b]$ and let $L$ and $M$ be the lower and upper bounds of $f$ respectively.

  Then $(F(f))(x) \leq (M-L)x$, for all $x \in [a,b]$.

  Therefore $F$ is continuous.

\end{enumerate}

\newpage
\begin{mdframed}
\includegraphics[width=400pt]{img/oxford-a2-1-8-1.png}
\end{mdframed}

\begin{table}[h!]
  \begin{tabular}{c|c|l}
    $S$         &$S'$         &                \\
    \hline
    $(0, 1)$    & $[0, 1]$    &                \\
    $\{0\}$     & $\emptyset$ & 0 is an isolated point \\
    $\R$        & $\R$        &                \\
    $\Q$        & $\Q$        & Any ball placed on a rational contains both other rationals and irrationals.\\
    $\Z$        & $\emptyset$ & All integers are isolated points.               \\
    $\emptyset$ & $\emptyset$ &
  \end{tabular}
\end{table}

\begin{mdframed}
\includegraphics[width=400pt]{img/oxford-a2-1-8-2.png}
\end{mdframed}

% \begin{proof}~\\
%   Let $S \subset \R$.

%   Let $u \in (S')'$.

%   Then $\Big(B(u, \epsilon) \setminus \{u\}\Big) \cap S' \neq \emptyset$ for all $\epsilon > 0$.

%   Therefore there exists $t \in (S')'$ such that $t \in S'$.

%   If $t \in S$

%   Want: $\Big(B(u, \epsilon) \setminus \{u\}\Big) \cap S \neq \emptyset$ for all $\epsilon > 0$.
% \end{proof}

\begin{mdframed}
\includegraphics[width=400pt]{img/oxford-a2-1-8-3.png}
\end{mdframed}

\begin{table}[h!]
  \begin{tabular}{l|c|l|l}
    $S$                                 &  open          &   closed      &    \\
    $\{(x, y) \in S ~|~ x \geq 1\}$     &  open          &   closed      &    \\
    $\{(x, y) \in S ~|~ x > 0\}$        &  not open      &   open        &    \\
    $\{(1 + 1/n, 1) ~|~ n \in \N\}$     &  not open      &   not closed  & complement contains $(1,1)$   \\
    $\{(1/n, 1) ~|~ n \in \N\}$         &  not open      &   closed      & unlike previous, complement excludes $(0, 0)$\\
  \end{tabular}
\end{table}


% \newpage

\begin{mdframed}
\includegraphics[width=400pt]{img/oxford-a2-1-9.png}
\end{mdframed}

\begin{proof}~\\
  \textbf{Well-defined:}

  \textbf{Positivity}: By Cauchy-Schwartz, for non-zero $v, w$, we have
  \begin{align*}
    0 < ~&\frac{\langle v, w \rangle}{\norm{v}\norm{w}} \leq 1\\
    0 \leq~ &1 - \(\frac{\langle v,w\rangle}{\norm{v}\norm{w}}\)^2 < 1\\
    0 \leq~ &d(L_1, L_2) < 1
  \end{align*}
  (since we take the positive square root).

  \textbf{Symmetry}:

\end{proof}


\section{Sheet 2}


\subsection{}
\begin{mdframed}
\includegraphics[width=400pt]{img/oxford-a2-2-1.png}
\end{mdframed}

Let $(M, d)$ be a metric space and let $A, B \subseteq M$.

\red{Incomplete}

\begin{claim*}
  $\bar{A \cup B} = \bar A \cup \bar B$.
\end{claim*}
\begin{proof}~\\
  {\bf Forward inclusion}\\
  Let $x \in \bar{A \cup B}$. Then either $x \in A \cup B$ or $x$ is a limit point, but not a
  member, of $A \cup B$.

  If $x \in A \cup B$ then either $x \in A$ (in which case $x \in \bar A$) or $x \in B$ (in which
  case $x \in \bar B$): in both cases we have $x \in \bar A \cup \bar B$.

  Alternatively, suppose $x \in (A \cup B)'$ and $x \notin A \cup B$. Then for all $\epsilon > 0$
  we have that either $B(x, \epsilon) \cap A \neq \emptyset$ or
  $B(x, \epsilon) \cap B \neq \emptyset$. Therefore $x$ is a limit point of either $A$ or $B$. (To
  see this, WLOG suppose there exists $\phi > 0$ such that for all $0 < \epsilon < \phi$ we have
  $B(x, \epsilon) \cap A = \emptyset$. Then for all $0 < \epsilon < \phi$ we have
  $B(x, \epsilon) \cap B \neq \emptyset$ and $x$ is a limit point of $B$. Alternatively, $x$ is a
  limit point of both $A$ and $B$.) Therefore either $x \in \bar A$ or $x \in \bar B$ as required.

  {\bf Reverse inclusion}\\
  Let $x \in \bar A \cup \bar B$. WLOG let $x \in \bar A$. Then either $x \in A$ or $x$ is a limit
  point, but not a member, of $A$.

  If $x \in A$ then $x \in \bar A \subseteq \bar{A \cup B}$, and so $x \in \bar{A \cup B}$ as
  required.

  Alternatively, suppose $x$ is a limit point, but not a member, of $A$. Then $x$ is a limit point
  of $A \cup B$ and so $x \in \bar{A \cup B}$ as required.
\end{proof}

\begin{claim*}
  $\bar{A \cap B} \neq \bar A \cap \bar B$.
\end{claim*}
\begin{proof}
  \red{TODO}
\end{proof}

\newpage
\subsection{}



\begin{mdframed}
\includegraphics[width=400pt]{img/oxford-a2-2-2.png}
\end{mdframed}

\begin{mdframed}
\begin{intuition*}
  This claim is saying that $f$ is continuous iff for all subsets $A \subseteq M$, the external
  limit points of $A$ remain close to points of $A$ when forming the image under $f$.

  So the forward implication is unsurprising: continuity keeps them close.

  Regarding the reverse implication, if they remain close for all subsets $A$ then this ``remaining
  close'' is occurring across the whole of $M$, so it is plausible that this means $f$ is
  continuous.
\end{intuition*}
\end{mdframed}

\begin{claim*}
  Let $f:M \to N$ be a map between metric spaces. Then $f$ is continuous if and only if for every
  $A \subseteq M$ we have $f(\bar A) \subseteq \bar{f(A)}$.
\end{claim*}

\begin{proof}
  Let $f:M \to N$ be a map between metric spaces.

  $\implies$\\
  Suppose $f$ is continuous and let $A \subseteq M$. Note that $f^\1(\bar{f(A)})$ is closed (by
  continuity of $f$) and contains $A$. Therefore\footnote{Let $X, Y$ be subsets of a metric
    space. If $Y$ is closed and $X \subseteq Y$ then $\bar X \subseteq Y$.}
  $\bar A \in f^\1(\bar{f(A)})$. Therefore $f(\bar A) \in \bar{f(A)}$.

  $\impliedby$\\
  Suppose that for every $A \subseteq M$ we have $f(\bar A) \subseteq \bar{f(A)}$.

  We will show that for every closed $B \subseteq N$ we have that $f^\1(B)$ is closed.

  So let $B \subseteq N$ be closed and let $A = f^\1(B)$.

  Then $f(A) \subseteq B$ and since $B$ is closed, $\bar{f(A)} \subseteq B$ and therefore
  $f(\bar A) \subseteq \bar{f(A)} \subseteq B$.

  So we have $f(\bar A) \subseteq B$ or equivalently $\bar A \subseteq f^\1(B) = A$.

  Therefore $\bar A = A$ and so $A$ is closed.
\end{proof}

\newpage
\blue{Alternative proof of forward implication using convergent sequences (can reverse implication
  be done in a related way?)}

{\bf Notation.} $A'$ denotes the set of limit points of $A$.

\begin{lemma}\label{external-limit-points-suffice}
  Let $f:M \to N$ be a map between metric spaces and let $A \subseteq M$. Then
  \begin{align*}
    f(\bar A) \subseteq \bar{f(A)} \iff f(A' \setminus A) \subseteq \bar{f(A)}.
  \end{align*}
\end{lemma}
\begin{proof}~\\
  Note that $\bar A = A \cup (A' \setminus A)$, therefore
  $f(\bar A) = f(A \cup (A' \setminus A)) = f(A) \cup f(A' \setminus A)$.

  Therefore
  $f(\bar A) \subseteq \bar{f(A)} \iff f(A) \subseteq \bar{f(A)} ~\land~ f(A' \setminus A)
  \subseteq \bar{f(A)}$.

  But $f(A) \subseteq \bar{f(A)}$ is true by definition of closure.
\end{proof}

\begin{claim*}
  Let $f:M \to N$ be a map between metric spaces. Then $f$ is continuous if and only if for every
  $A \subseteq M$ we have $f(\bar A) \subseteq \bar{f(A)}$.
\end{claim*}

\begin{proof}
  Let $f:M \to N$ be a map between metric spaces.

  $\implies$\\
  Suppose $f$ is continuous.

  Let $A \subseteq M$. Note that by (\ref{external-limit-points-suffice}) it suffices to show that
  $f(m) \in \bar{f(A)}$ for all $m \in A' \setminus A$.

  So let $m \in A' \setminus A$ and let $(x_n)$ be a sequence in $A$ that converges to $m$. Since
  $f$ is continuous, $(f(x_n))$ is a sequence in $f(A)$ that converges to $f(m)$. Therefore $f(m)$
  is a limit point of $f(A)$, and so $f(m) \in \bar{f(A)}$ as required.

  $\impliedby$\\

  \red{(Incomplete)}

  Suppose that for every $A \subseteq M$ we have $f(\bar A) \subseteq \bar{f(A)}$.

  % By (\ref{external-limit-points-suffice}) this is equivalent to the hypothesis that for every
  % $A \subseteq M$ we have $f(A' \setminus A) \subseteq \bar{f(A)}$.

  We need to show that $f$ is continuous.

  % We will show this using the convergent sequences definition of continuity.

  Let $m \in M$ and let $(x_n)$ be a sequence in $M$ that converges to $m$.

  We need to show that the sequence $(f(x_n))$ converges to $f(m)$.

  By hypothesis, we know that $f(m) \in \bar{f(A)}$.

  % We will show this by showing that, for every $m \in M$ and for every sequence in $M$ that
  % converges to $m$,

  % We need to show that the closure of $A$ is mapped into the closure of the image of $A$, i.e. that
  % $f(\bar A) \subseteq \bar{f(A)}$.

  % Let $a \in A$.

  % We know:
  % \begin{enumerate}
  % \item For any ball in $N$ there exists a ball in $M$ which is mapped into it.
  % \item The preimage of every open set is open.
  % \item For every sequence $(x_n)$ in $M$ that converges to $a$ we have $f(x_n) \to f(a)$.
  % \end{enumerate}

\end{proof}



\newpage
\subsection{}
\let\T\undefined
\newcommand{\T}{\mathcal T}

\begin{mdframed}
\includegraphics[width=400pt]{img/oxford-a2-2-3.png}
\end{mdframed}

\begin{proof}
  Let $X = \{0, 1\}$ and $\T = \{\emptyset, \{0\}, \{0, 1\}\}$.
  \begin{enumerate}
  \item $\emptyset \in \T$ and $X \in \T$ \checkmark
  \item {\bf Finite intersections}: \checkmark
    \begin{align*}
      \emptyset \cap \{0\}    &= \emptyset \in \T \\
      \emptyset \cap \{0, 1\} &= \emptyset \in \T \\
      \{0\}     \cap \{0, 1\} &= \{0\} \in \T
    \end{align*}
    Yes, it is closed under pairwise intersections so it must be closed under higher-order
    intersections. \red{hang on...why not just demand closure
      under pairwise intersections then?}
  \item {\bf Arbitrary unions}: \checkmark
    \begin{align*}
      \emptyset \cup \{0\}    &= \{0\}    \in \T \\
      \emptyset \cup \{0, 1\} &= \{0, 1\} \in \T \\
      \{0\}     \cup \{0, 1\} &= \{0, 1\} \in \T
    \end{align*}
    Yes, it is closed under pairwise unions so it must be closed under higher-order
    unions.
  \end{enumerate}
\end{proof}

\begin{proof}
  Suppose for a contradiction that $d$ is a metric on $X$ whose open sets are equal to $\T$.

  Then $\{0\} \in X$ is an open set under $d$.

  Therefore there exists $\epsilon > 0$ such that $B_d(0, \epsilon) = \{0\}$. Therefore
  $d(0, 1) = d(1, 0) > 0$.

  But then $\{1\}$ is an open set, since using the same $\epsilon$ we have
  $B_d(1, \epsilon) = \{1\}$. This contradicts the definition of $\T$.
\end{proof}

\red{So a singleton set containing an isolated point embedded in a metric space is open?}


\newpage
\subsection{}

\begin{mdframed}
\includegraphics[width=400pt]{img/oxford-a2-2-4.png}
\end{mdframed}

\let\C\undefined
\newcommand{\C}{\mathcal{C}}

\begin{enumerate}[label=(\roman*)]
\item
  \begin{claim*}
    $\delta$ is a metric.
  \end{claim*}
  \begin{proof}~\\
    \begin{enumerate}
    \item {\bf Symmetry} \checkmark\\
      $d_Y$ is symmetric since it is a metric and therefore
      \begin{align*}
        \delta(f, g)
        = \sup_{x \in X} d_Y(f(x), g(x))
        = \sup_{x \in X} d_Y(g(x), f(x))
        = \delta(g, f).
      \end{align*}
    \item {\bf Positivity} \checkmark\\
      The codomain of $d_Y$ is $R_{\geq 0}$ since it is a metric and therefore
      $\sup_{a \in A} d_Y(a) \geq 0$ for all $A \subseteq Y^2$.
    \newpage
    \item {\bf Triangle inequality}
      \begin{claim*}
        Let $(X, d_X)$ and $(Y, d_Y)$ be metric spaces and let $(\C(X, Y), \delta)$ be the metric
        space of continuous bounded functions $X \to Y$ with metric $\delta$ defined by
        $$\delta(f, g) = \sup_{x \in X} d_Y\(f(x), g(x)\).$$ Then
        $\delta(f, g) + \delta(g, h) \geq \delta(f, h)$ for all $f, g, h \in \C(X, Y)$.
      \end{claim*}

      \begin{proof}~\\
        Let $f, g, h \in \C(X, Y)$ Then there exists a sequence $(x_n)_{n \geq 1}$ in $X$ such that
        $$\(d_Y\(f(x_n), h(x_n)\)\) \to \delta(f, h).$$

        Note that since $d_Y$ is a metric, we have for all $x \in X$
        \begin{align*}
          d_Y\(f(x), g(x)\) + d_Y\(g(x), h(x)\) \geq d_Y\(f(x), h(x)\).
        \end{align*}
        Therefore
        \begin{align*}
          \limn \Big(d_Y\(f(x_n), g(x_n)\) + d_Y\(g(x_n), h(x_n)\)\Big) \geq \delta(f, h).
        \end{align*}
        But
        \begin{align*}
          & \limn \Big(d_Y\(f(x_n), g(x_n)\) + d_Y\(g(x_n), h(x_n)\)\Big) \\
          =& \limn d_Y\(f(x_n), g(x_n)\) + \limn  d_Y\(g(x_n), h(x_n)\) \\
          \leq& \sup_{x\in X} d_Y\(f(x), g(x)\) + \sup_{x\in X} d_Y\(g(x), h(x)\) \\
          =& ~\delta(f, g) + \delta(g, h).
        \end{align*}
        Therefore $\delta(f, g) + \delta(g, h) \geq \delta(f, h)$.
      \end{proof}
    \end{enumerate}
    \newpage
    \item {\bf Triangle inequality}
      \begin{claim*}
        Let $(X, d_X)$ and $(Y, d_Y)$ be metric spaces and let $(\C(X, Y), \delta)$ be the metric
        space of continuous bounded functions $X \to Y$ with metric $\delta$ defined by
        $$\delta(f, g) = \sup_{x \in X} d_Y\(f(x), g(x)\).$$ Then
        $\delta(f, g) + \delta(g, h) \geq \delta(f, h)$ for all $f, g, h \in \C(X, Y)$.
      \end{claim*}

      \begin{proof}~\\
        Let $f, g, h \in \C(X, Y)$.

        Note that since $d_Y$ is a metric, we have for all $x \in X$
        \begin{align*}
          d_Y\(f(x), g(x)\) + d_Y\(g(x), h(x)\) \geq d_Y\(f(x), h(x)\).
        \end{align*}
        Therefore the suprema satisfy the inequality
        \begin{align*}
          \sup_{x\in X} \Big(d_Y\(f(x), g(x)\) + d_Y\(g(x), h(x)\)\Big) \geq \delta(f, h).
        \end{align*}
        Therefore we have
        \begin{align}
          \delta(f, g) + \delta(g, h)
          &= \sup_{x\in X} d_Y\(f(x), g(x)\) + \sup_{x\in X} d_Y\(g(x), h(x)\) \\
          &\geq \sup_{x\in X} \Big(d_Y\(f(x), g(x)\) + d_Y\(g(x), h(x)\)\Big) \\
          &\geq \delta(f, h).
        \end{align}
        \red{TODO: proof of triangle inequality for $\sup$ used to arrive at (2).}
      \end{proof}
  \end{proof}
\newpage
\item
  \begin{claim*}
    Let $(X, d_X)$ and $(Y, d_Y)$ be metric spaces and let $(\C(X, Y), \delta)$ be the metric
    space of continuous bounded functions $X \to Y$ with metric $\delta$ defined by
    $$\delta(f, g) = \sup_{x \in X} d_Y\(f(x), g(x)\).$$

    If $Y$ is complete then $\C(X, Y)$ is complete.
  \end{claim*}
  \begin{proof}~\\
    First, note that for all $f, g$ in $\C(X, Y)$ and for all $x \in X$ we have
    \begin{align*}
      d_Y(f(x), g(x)) \leq \delta(f, g).
    \end{align*}

    Suppose $Y$ is complete and let $(f_n)$ be a Cauchy sequence in $\C(X, Y)$.

    We want to show that $(f_n)$ converges in $\C(X, Y)$, and therefore that $\C(X, Y)$ is
    complete. The outline of our argument will be:
    \begin{enumerate}
    \item for all $x \in X$ the sequence $(f_n(x))$ in $Y$ is Cauchy;
    \item therefore such sequences converge in $Y$, since $Y$ is complete;
    \item therefore $(f_n)$ converges in $\C(X, Y)$, proving that $\C(X, Y)$ is complete.
    \end{enumerate}

    For part (a), since $(f_n)$ is Cauchy in $\C(X, Y)$, we have for all $x \in X$
    \begin{align*}
      d_Y\(f_m(x), f_n(x)\) \leq \delta(f_m, f_n) \to 0 ~\text{as}~ m, n \to \infty.
    \end{align*}
    Therefore $(f_n(x))$ in $Y$ is Cauchy for all $x \in X$.

    For part (c), we need to show that there exists $f \in \C(X, Y)$ such that $f_n \to f$. We
    claim that $f(x) = \limn f_n(x)$ is such a function.

    Fix $\epsilon > 0$ and let $N$ be such that
    $d_Y\(f_m(x), f_n(x)\) \leq \delta(f_m, f_n) < \epsilon$ for all $x \in X$ and all $m, n > N$.

    To prove that $(f_n) \to f$, fix $\epsilon > 0$ and for all $x \in X$ define $M(x) \in \N$ to
    be the smallest natural number such that $d_Y(f_n(x), f(x)) < \epsilon$ for all $n > M(x)$.

    Set $N = \sup_{x \in X} M(x)$. Note that for all $n > N$ we have that
    \begin{align*}
      \delta(f_n, f) = \sup_{x\in X} d_Y(f_n(x), f(x)) < \epsilon,
    \end{align*}
    proving that $(f_n) \to f$.

    Finally we must show $f$ is continuous and bounded.

    {\bf Continuity}:\\
    Note that the sequence $(f_n)$ (considered pointwise) converges uniformly to $f$ since for all
    $\epsilon > 0$ there exists $N$ such that for all $n > N$ we have
    $d_Y\(f_n(x), f(x)\) \leq \delta(f_n, f) < \epsilon$ for all $x \in X$. Therefore since the
    $f_n$ are continuous, we have that their limit $f$ is continuous.

    {\bf Boundedness}:\\
    To show\footnote{The bounded functions $X \to Y$ are not a vector space; we have no addition in
      $Y$. So unlike the proof that the normed vector space of bounded real-valued functions is
      complete, we cannot argue that $f_n$ is bounded, therefore $f = f_n + (f - f_n)$ is bounded.}
    that $f$ is bounded we must show that there exists $K \in \R$ such that for all
    $x_1, x_2 \in X$ we have $d_Y\(f(x_1), f(x_2)\) < K$.

    \red{TODO this isn't quite right yet, it shouldn't depend on $\epsilon$, indeed $\epsilon$ can
      be made arbitrarily small.}

    Fix $x_1, x_2 \in X$, $\epsilon \in \R$, let $n \in \N$ be such that for all $x \in X$ we have
    $d_Y\(f_n(x), f(x)\) < \epsilon$ and let $J \in \R$ be such that for all $u_1, u_2 \in X$ we
    have $d_Y\(f_n(u_1), f_n(u_2)\) < K$. Then
    \begin{align*}
      d_Y\(f(x_1), f(x_2)\)
      &\leq
        d_Y\(f(x_1),   f_n(x_1)\) +
        d_Y\(f_n(x_1), f_n(x_2)\) +
        d_Y\(f_n(x_2), f(x_2)\) \\
      &\leq
        2\epsilon + J.
    \end{align*}
    Therefore $f$ is bounded.

    Therefore if $(f_n)$ is Cauchy then it converges in $\C(X, Y)$, proving that $\C(X, Y)$ is
    complete.
  \end{proof}
  \newpage
\item
  \begin{problem*}
    Consider the map $R: \C\([0, 1], \R\) \to \C\((0, 1), \R\)$ which takes a continuous (bounded?)
    function on $[0, 1]$ to its restriction to $(0, 1)$. Is the image of $R$ closed?
  \end{problem*}
  \begin{proof}
    By definition, the image of $R$ is $R\big(\C\([0, 1], \R\)\big) \subseteq \C((0, 1),
    \R)$.

    Note that $\R$ is complete, so by (ii) we have that $\C((0, 1), \R)$ is complete.


    We would like to show that $R\big(\C\([0, 1], \R\)\big)$ is complete, since then it would be
    closed.

    I.e. we would like to show that if $(f_n)$ is a convergent sequence in
    $R\big(\C\([0, 1], \R\)\big)$ then it converges to a limit in $R\big(\C\([0, 1], \R\)\big)$.
  \end{proof}
\end{enumerate}




\subsection{}

\newpage


\begin{mdframed}
\includegraphics[width=400pt]{img/oxford-a2-2-5.png}
\end{mdframed}

\begin{remark*}
  We have a population $M$ of infinite binary sequences. The distance between any two sequences is
  obtained by XORing them and interpreting the result $(x_n)_{n\geq0}$ as a binary decimal
  $x_0 + \frac{x_1}{2} + \frac{x_2}{4} + \ldots \in [0, 2]$.

  $M$ is (claim) homeomorphic to the metric space $[0, 2) \subset \R$, since we have
  $f:M \to [0, 2)$ defined by
  \begin{align*}
    f\((x_n)\) = \sum_{n=0}^\infty \frac{x_n}{2^n},
  \end{align*}
  which (claim) is bijective and continuous (part (iv) of this exercise). Its inverse $g = f^\1$
  maps the real number to its binary expansion (e.g. via a division and remainder algorithm) and
  (claim) is also continuous.

  On might think that one could prove that $M$ is disconnected (part (ii)) and complete (part
  (iii)) by establishing this homeomorphism with $[0, 2)$ and appealing to the properties of
  $[0, 2)$. This would work for connectedness, since that property of a metric space {\it is}
  preserved by homeomorphism. However, completeness is {\it not} in general preserved by
  homeomorphism (e.g. $(0, 1)$ is not complete yet homeomorphic to $\R$).
\end{remark*}

\begin{question*}
  Let $X$ be a set and let $d:X^2 \to \R$ be a function not necessarily satisying the definition of
  a metric. Let $M$ be a metric space and let $(X, d)$ be homeomorphic to $M$. Does it follow that
  $d$ satisfies the definition of a metric?
\end{question*}

\begin{enumerate}[label=(\roman*)]
\item
  \begin{enumerate}
  \item {\bf Symmetry}: \checkmark This follows from the fact that $|x_n - y_n| = |y_n - x_n|$, or
    equivalently from the fact that XOR is commutative.
  \item {\bf Positivite definiteness}: \checkmark If $(x_n) \neq (y_n)$ then there exists $n$ such that
    $x_n \neq y_n$, contributing a non-zero term to the sum. Conversely if the distance is non-zero
    then such an $n$ must exist and we have $x_n \neq y_n$.
  \item {\bf Triangle inequality}: \checkmark\\
    We want to show $d\((x_n, y_n)\) + d\((y_n, z_n)\) \geq d\((x_n, z_n)\)$.

    Let $(x_n), (y_n), (z_n) \in M$. Define the following partition of $\N$:
    \begin{align*}
      A &= \{n \in \N ~|~ x_n = z_n\}\\
      B &= \{n \in \N ~|~ x_n \neq z_n\},
    \end{align*}
    and for every $(v_n), (w_n) \in M$ write
    $d_\chi\((v_n), (w_n)\) = \sum_{n \in \chi}\frac{|v_n - w_n|}{2^n}$ for $\chi \in \{A, B\}$, so
    that $d = d_A + d_B$. Then
    \begin{align}
      d\((x_n), (y_n)\) + d\((y_n), (z_n)\)
      &\geq d_B\((x_n), (y_n)\) + d_B\((y_n), (z_n)\) \nonumber\\
      &= d_B\((x_n), (z_n)\) \label{eq-2-5-1}\\
      &= d\((x_n), (z_n)\) \nonumber,
    \end{align}
    where \eqref{eq-2-5-1} is true because for every $n \in B$ we have that exactly one of
    $x_n \neq y_n$ or $y_n \neq z_n$ is true.
  \end{enumerate}
\newpage
\begin{mdframed}
\includegraphics[width=400pt]{img/oxford-a2-2-5.png}
\end{mdframed}
\item
  \begin{claim*}
    Let $U_0 = \{(x_n) \in M ~|~ x_0 = 0\}$. Then $U_0$ is open, and $M$ is disconnected.
  \end{claim*}

  \begin{proof}~\\
    Let $U_\chi = \{(x_n) \in M ~|~ x_0 = \chi\}$ for $\chi \in \{0, 1\}$.

    Let $u \in U_0$. Note that if $x \notin U_0$ then $x_0 = 1 \neq u_0$ and therefore
    $d(u, x) \geq 1$. Let $v \in U_0$ be such that $u_0 = v_0$ and $u_1 = v_1$. Then
    $d(u, v) \leq \frac{1}{2}$. Therefore the open ball $B(u, 1)$ of radius $1$ centered at $u$
    contains a point $v \neq u$, with $v \in U_0$. Therefore $U_0$ is open.

    By symmetry, $U_1$ is open also. So $M$ is the union of two disjoint non-empty open sets and is
    therefore disconnected.
  \end{proof}

  \begin{remark*}
    So $f: M \to [0, 2)$ is not a homeomorphism, since $[0, 2)$ is connected yet $M$ is not.
  \end{remark*}

\newpage
\begin{mdframed}
\includegraphics[width=400pt]{img/oxford-a2-2-5.png}
\end{mdframed}
\item
  \begin{claim*}
    $M$ is complete.
  \end{claim*}
  \begin{proof}
    Let $(\phi_i)_{i\geq 0}$ be a Cauchy sequence in $M$, where
    $\phi_i = (x_{i,n})_{n\geq 0} \in M$.


    Fix $\epsilon > 0$. Since $(\phi_i)$ is Cauchy, there exists $I$ such that for all $i, j > I$
    we have $d(\phi_i, \phi_j) < \epsilon$.

    Note that if $n \leq \floor{\log_2 \epsilon^{-1}}$ then $2^{-n} \geq \epsilon^{-1}$.

    Therefore for all $i, j > I$ we have that $x_{i,n} = x_{j,n}$ for
    $n \in 0, \ldots, \floor{\log_2 \epsilon^{-1}}$.

    Therefore $(\phi_i)$ is Cauchy and converges in $M$

  \end{proof}

  \begin{proof}
    Let $((x_n))_m \in M$ be the following sequence of sequences:
    \begin{align*}
      (1, 0, 0, \ldots), (1, 1, 0, 0, \ldots), (1, 1, 1, 0, 0, \ldots), \ldots.
    \end{align*}
    We claim that this is Cauchy and yet does not converge in $M$.

    To see that it is Cauchy, fix $\epsilon > 0$.  \todo{Exhibit an $N$ beyond which all sequences
      are within $\epsilon$, I think probably similar to the $\log_2 \epsilon^\1$ argument above.}

    To see that this does not converge within $M$, suppose for a contradiction that it converges to
    $L \in M$. Then for all $\epsilon > 0$ there exists $N$ such that $d(x, L) < \epsilon$ for all
    $n > N$. But

    \todo{Confused. Feels like it is not complete since in some sense that sequence converges to $2 \notin M$?}
  \end{proof}

\newpage
\begin{mdframed}
\includegraphics[width=400pt]{img/oxford-a2-2-5.png}
\end{mdframed}
\item
  \begin{claim*}
    Let $f:M \to \R$ be defined by $f\((x_n)\) = \sum_{n=0}^\infty \frac{x_n}{2^n}$. Then $f$ is
    continuous.
  \end{claim*}

  % \begin{remark*}
  %   Note that $U_0 = f^\1\([0, 1)\)$. Hence if $f$ is continuous then $U_0$ is the preimage of an
  %   open set under a continuous map and therefore $U_0$ is open.
  % \end{remark*}

  \begin{proof}
    Let $x = (x_n) \in M$ and fix $\epsilon > 0$.

    We want to show that there exists $\delta > 0$ such that if $d(x, y) < \delta$ then
    $|f(x) - f(y)| < \epsilon$.

    First, note that
    \begin{align*}
      |f(x) - f(y)|
      =    \Big|\sum_{n \geq 0} \frac{x_n - y_n}{2^n}\Big|
      \leq \sum_{n \geq 0} \frac{|x_n - y_n|}{2^n}
      = d(x, y).
    \end{align*}

    \begin{mdframed}
      \includegraphics[width=300pt]{img/oxford-a2-2-5-diagram.png}
    \end{mdframed}


    Let $N = \ceil{\log_2 \epsilon^{-1}}$ and let
    $B = \{(y_n) \in M ~|~ y_n = x_n ~ \forall n \leq N\}$ be a set of sequences that are initially
    identical to $x$.

    Note that $y \in B \implies d(x, y) \leq \epsilon$, since
    $
      \max_{y \in B} d(x, y)
      = \sum_{i=N+1}^\infty \frac{1}{2^i}
      = \frac{1}{2^N}
      \leq \epsilon.
    $

    \todo{The $\leq$ is worrrying, but worse than that we can have $y \notin B$ differing from $x$
      at position $N$ only, which will yield $d(x, y) \leq \epsilon$.}

    \blue{Note that $f$ gives the distance from the zero sequence.}

    % Note that $y \in B \implies d(x, y) < \epsilon$, since
    % \begin{align*}
    %   \max_{y \in B} d(x, y)
    %   = \sum_{i=N+1}^\infty \frac{1}{2^i}
    %   = \frac{1}{2^N}
    %   \leq \frac{1}{2 \cdot \frac{1}{\epsilon}}
    %   = \frac{\epsilon}{2}.
    % \end{align*}

    % Also if $y \notin B$ then there is a term in $d(x, y)$ at least as big as
    % $\frac{1}{2^{\ceil{\log_2 \epsilon^{-1}}}}$.

    % $d(x, y) > \epsilon$ since  Therefore $y \in B \implies d(x, y) < \epsilon$
    % Note that $\sum_{i=n+1}^m \frac{1}{2^i} < \frac{1}{2^n}$ for all $m \geq n$.
  \end{proof}
\end{enumerate}


\newpage
\subsection{}



\begin{mdframed}
  \includegraphics[width=400pt]{img/oxford-a2-2-6.png}
\end{mdframed}

% \begin{remark*}
%   Informally, $\|.\|$ assigns a value to a matrix $A$ as follows: consider the image under $A$ of
%   the unit circle centred at the origin. $\|A\|$ is the furthest distance from the origin of any
%   of the vectors in that image set.
% \end{remark*}


\begin{lemma}\label{a2-2-6-lemma-0a}
  Let $X \subseteq R$ and $c \geq 0$. Then $\sup cX = c\sup X$.
\end{lemma}

Continuous image of a compact set is compact. The sup here is a sup of a compact set so ... there's
a topological argument for this supremum being a maximum.

\begin{proof}
  Let $M = \sup cX$ and $c \geq 0$. Note that for all $x \in X$ we have $cx \leq M$ or equivalently
  $x \leq M/c$.  Therefore $M$ is an upper bound for $cX$ if and only if $M/c$ is an upper bound
  for $X$. Suppose for a contradiction that $K < M/c$ is also an upper bound for $X$. Then $cK < M$
  is an upper bound for $cX$, contradicting $M = \sup cX$. Therefore $\sup X = M/c$.
\end{proof}

\begin{lemma}\label{a2-2-6-lemma-0b}
  Let $U$ be a set and let $f:U \to \R$ and $g:U\to \R$. Then
  \begin{align*}
    \sup_{u\in U} \(f(u) + g(u)\) \leq \sup_{u\in U} f(u) + \sup_{u\in U} g(u).
  \end{align*}
\end{lemma}

\begin{proof}
  Let $F = \sup_{u\in U} f(u)$ and $G = \sup_{u\in U} g(u)$. Then for all $u \in U$ we have
  $f(u) \leq F$ and $g(u) \leq G$, therefore for all $u \in U$ we have $f(u) + g(u) \leq F +
  G$. Therefore $\sup_{u\in U} \(f(u) + g(u)\) \leq F + G$ as required.
\end{proof}


\newpage
\begin{mdframed}
  \includegraphics[width=400pt]{img/oxford-a2-2-6.png}
\end{mdframed}
\begin{enumerate}[label=(\roman*)]
\item
  \begin{claim*}
    Let $M$ be the space of real $n \times n$ matrices, let $S = \{x \in \R^n : \|x\| = 1\}$ and
    let $\|A\| = \sup_{v \in S} \|A(v)\|$. Then $\|.\|$ is a norm on $M$.
  \end{claim*}

  \begin{proof}
    Let $S = \{x \in \R^n : \|x\| = 1\}$ be the unit sphere in $\R^n$.
    \begin{enumerate}
    \item {\bf Positive definiteness}:\\
      First, note that $\|A\| = \sup_{v \in S} \|A(v)\| \geq 0$ since $\|v\| \geq 0$ for all
      $v \in \R^n$. We claim that $\|A\| = 0$ if and only if $A = 0$. Indeed, suppose $A = 0$. Then
      certainly $\|A\| = 0$. Conversely, suppose $\|A\| = 0$. Then for all $v \in S$ we have
      $Av = 0$, since otherwise $0$ would not be the supremum, and also $v \neq 0$. Therefore
      $A = 0$.

      \red{WRONG! $A$ might have non-empty nullspace. So instead consider whether $A$ has a non-zero entry.}

    \item {\bf Preservation of scalar multiplication}:\\
      Let $\lambda \in \R$. Then
      \begin{align*}
      \|\lambda A\|
        &= \sup_{v \in S} \|(\lambda A)(v)\| \\
        &= \sup_{v \in S} \|\lambda (A(v))\| \\
        &= \lambda  \sup_{v \in S} \|A(v)\| ~~~~~~~ \text{(by lemma (\ref{a2-2-6-lemma-0a}))} \\
        &= \lambda \|A\|.
      \end{align*}
      % Informally, we want to show that the greatest distance that the matrix $\lambda A$ takes a
      % vector in the unit circle differs from that distance for $A$ by a factor of $\lambda$.
    \item {\bf Triangle inequality}:\\
      Let $A, B \in M$ be real $n \times n$ matrices. We have
      \begin{align*}
        &\|A + B\| \\
        =& \sup_{v \in S} \|(A + B)v\| \\
        =& \sup_{v \in S} \|Av + Bv\|                     &\text{(by linearity of matrix multiplication)}\\
        \leq& \sup_{v \in S} \(\|Av\| + \|Bv\|\)          &\text{(by triangle inequality and preservation of weak inequalities)}\\
        \leq& \sup_{v \in S} \|Av\| + \sup_{v \in S} \|Bv\| &\text{(by lemma (\ref{a2-2-6-lemma-0b}))}\\
        =& \|A\| + \|B\|.
      \end{align*}
      % Well, what is the geometrical meaning of $A + B$? It's a matrix which does the same thing to
      % a vector as transforming it by $A$, and also transforming it by $B$, and then adding the two
      % resulting vectors. In other words it's the map $x \mapsto Ax + Bx$.

      % So yeah, the triangle inequality has to hold. On the left the {\it same} vector is
      % transformed by $A$ and $B$, and we take the sup over all possible choices of that vector. On
      % the right we get to choose different vectors for the $A$ and $B$ transformation, so we can't
      % possibly do worse.
    \end{enumerate}
  \end{proof}


  \newpage
  \begin{mdframed}
    \includegraphics[width=400pt]{img/oxford-a2-2-6.png}
  \end{mdframed}

  \begin{lemma}\label{a2-2-6-lemma-1}
    Let $X$ be a normed vector space, let $f:X \to X$ be a linear transformation. The following
    statements are equivalent:
    \begin{enumerate}[label=(\roman*)]
    \item $f$ is a contraction.
    \item There exists $0 < \sigma < 1$ such that $\|f(x) - f(y)\| < \sigma \|x - y\|$ for all
      $x, y \in X$.
    \item There exists $0 < \sigma < 1$ such that $\|f(x)\| < \sigma \|x\|$ for all $x \in X$.
    \end{enumerate}
  \end{lemma}

  \begin{proof}\hspace{0pt}\\
    \begin{tabular}{ll}
      $(i) \iff (ii)$: &This is the definition of a contraction on a normed vector space.\\
      \\
      $(ii) \implies (iii)$: &Suppose that (ii) is true. Then (iii) follows on taking $y = 0$, since
                               $f(0) = 0$.\\
      \\
      $(iii) \implies (ii)$: &Suppose that (iii) is true. Then we have\\
                       & $\|f(x) - f(y)\| = \|f(x - y)\| < \sigma \|x - y\|.$
    \end{tabular}
  \end{proof}

  \begin{lemma}\label{a2-2-6-lemma-2}
    For any $v \in \R^n$ we have $\|Av\| \leq \|A\| \cdot \|v\|$.
  \end{lemma}

  \begin{proof}
    It's obviously true for $v = 0$, so let $v \in \R^n$, $v \neq 0$. Then
    \begin{align*}
      \|Av\|
      =    \Bigg|\Bigg|A \frac{v}{\|v\|} \|v\| \Bigg|\Bigg|
      =    \Bigg|\Bigg|A \frac{v}{\|v\|} \Bigg|\Bigg| \cdot \|v\|
      ~\leq~ \|A\| \cdot \|v\|,
    \end{align*}
    since $\|\frac{v}{\|v\|}\| = 1$ and by definition $\|A\| = \sup_{u: \|u\| = 1} \|Au\|$.

  \end{proof}

\newpage
\begin{mdframed}
  \includegraphics[width=400pt]{img/oxford-a2-2-6.png}
\end{mdframed}

\item
  \begin{claim*}
    Suppose that $A \in M$ has $\|A\| < 1$. Show that the map $B \mapsto AB$ is a
    contraction.
  \end{claim*}

  \begin{proof}
    Let $A, B \in M$ and suppose that $\|A\| = \rho < 1$. Let
    $\rho < \sigma = \frac{\rho + 1}{2} < 1$. Then
    \begin{align*}
      \|AB\|
      &=    \sup_{v: \|v\| = 1} \|(AB)v\| \\
      &=    \sup_{v: \|v\| = 1} \|A(Bv)\| \\
      &\leq \sup_{v: \|v\| = 1} \|A\| \|Bv\| ~~~~~~~~\text{by lemma (\ref{a2-2-6-lemma-2})}\\
      &< \sigma \sup_{v: \|v\| = 1} \|Bv\| \\
      &= \sigma \|B\|.
    \end{align*}
    Therefore the map $B \mapsto AB$ is a contraction, by lemma (\ref{a2-2-6-lemma-1}).

    \red{Not sure we need $\sigma$ in this proof.}
  \end{proof}

  \begin{claim*}
    $I - A$ is invertible.
  \end{claim*}

  \begin{intuition*}
    $I - A$ is invertible if and only if $0$ is the only fixed point under transformation by $A$.
  \end{intuition*}

  \begin{proof}
    Suppose for a contradiction that $I - A$ is non-invertible. Then there exists $v \neq 0$ such
    that $(I - A)v = 0$. Therefore $Av = v$, therefore $\|Av\| = \|v\|$. However, by hypothesis
    $\|A\| < 1$, therefore from lemma (\ref{a2-2-6-lemma-2}) we have
    $\|Av\| \leq \|A\| \cdot \|v\| < \|v\|$, a contradiction.

    \todo{This proof depends on the hypothesis that $\|A\| < 1$, but it doesn't use the result that
      $B \mapsto AB$ is a contraction; was it supposed to?}
  \end{proof}

  \begin{remark*}
    The following statements are equivalent:
    \begin{enumerate}
    \item $I - A$ is invertible.
    \item $(I - A)v = 0 \implies v = 0$.
    \item $0$ is the only fixed point of the map $v \mapsto Av$.
    \item $1$ is not an eigenvalue of $A$.
    \end{enumerate}
    These equivalences lead to a few different proof variants. In particular (c) and (d) are true
    since $A$ is a contraction.
  \end{remark*}

  % \begin{proof} {\bf Alternative proof I}\\
  %   Suppose for a contradiction that $I - A$ is non-invertible. Then there exists $v \neq 0$ such
  %   that $(I - A)v = 0$, or equivalently $Av = v$. However, the linear map $v \mapsto Av$ is a
  %   contraction. Therefore $0$ is the only fixed point, a contradiction.
  % \end{proof}

  % \begin{proof} {\bf Alternative proof II}\\
  %   Note that $I - A$ is invertible if and only if $I - A$ is bijective. Suppose for a
  %   contradiction that there exists $v' \neq v$ such that $(I - A)v' = (I - A)v$, or equivalantly
  %   $A(v - v)' = v - v'$. Then $v - v'$ is a fixed point under the linear map $x \to Ax$. But this
  %   map is a contraction, so the only fixed point is $0$ and we have $v = v'$, a contradiction.
  % \end{proof}

  % \begin{proof} {\bf Alternative proof III}\\
  %   Note that $I - A$ is the linear map $B \mapsto B - AB$. So $I - A$ maps $B$ to the vector
  %   pointing from $AB$ to $B$. $I - A$ invertible if and only if this map is injective: i.e. there
  %   does not exist $B' \neq B$ such that $AB' + (B - AB) = B'$. I.e. the displacement of $B$ caused
  %   by the transformation $A$ is unique to $B$; no other matrix $B' \neq B$ is displaced in the
  %   same manner.
  % \end{proof}

  \todo{My main remaining question is this: we have the following two maps:
    \begin{enumerate}
    \item $f: \R^n \to \R^n$ given by $v \mapsto (I - A)v$
    \item $f: \R^{n\times n} \to \R^{n\times n}$ given by $B \mapsto (I - A)B$
    \end{enumerate}
    When proving that $I - A$ is invertible, I am free to base my argument on either of them,
    right?
    However, both maps are contractions under their respective metrics, so the arguments end up
    being very similar.
  }
  % \begin{proof}
  %   Let $X$ be a vector space, let $u, v \in X$, and let $f: X \to X$ be a linear map.

  %   Suppose $f(u) - u = f(v) - v$. Then
  %   \begin{align*}
  %     f(u) - f(v) &= u - v \\
  %     f(u - v)    &= u - v,
  %   \end{align*}
  %   so $u - v$ is a fixed point of $f$.
  % \end{proof}

  % \begin{example*}
  %   Let $M$ be 1-dimensional. Let $A = \frac{3}{4}$. Then $I - A = \frac{1}{4}$ is the map
  %   $B \mapsto \frac{B}{4}$. It is invertible (the vector that points from $AB$ to $B$ is unique
  %   for every $B$).
  % \end{example*}

  % \begin{example*}
  %   Let $M$ be n-dimensional. Let $A = \diag(\frac{3}{4})$. Then $I - A = \diag(\frac{1}{4})$ is the
  %   map $B \mapsto \frac{B}{4}$. It is invertible (the vector that points from $AB$ to $B$ is
  %   unique for every $B$).
  % \end{example*}

\end{enumerate}


\subsection{}


\newpage
\begin{mdframed}
\includegraphics[width=400pt]{img/oxford-a2-2-7.png}
\end{mdframed}

\begin{definition*}
  A metric space $M$ is \defn{connected} if and only if it cannot be written as the union of two
  non-empty disjoint open sets.
\end{definition*}


\begin{enumerate}[label=(\roman*)]
\item
  \begin{claim*}
    A metric space $M$ is \defn{connected} if and only if every integer-valued continuous function
    on $M$ is constant.
  \end{claim*}
  \begin{remark*}
    Suppose $M$ is connected and empty. Then every integer-valued continuous function on $M$ is
    constant and the claim is false. So we will suppose $M$ to be non-empty.
  \end{remark*}
  \begin{proof}
    % \begin{mdframed}
    %   {\bf Intuition}: The only way you can have a jump in values in the codomain without violating
    %   continuity would be if, in the domain, one set ended and another set started at that point,
    %   with the two sets not ``touching''. But if $M$ is connected, then no such partition into open
    %   sets exists. Conversely, if there exists a non-constant integer-valued continuous function,
    %   then $M$ must be disconnected.
    % \end{mdframed}

    We will prove the contrapositive in both directions. I.e. that $M$ is disconnected if and only
    if there exists a non-constant continuous map $f:M \to \Z$

    $\implies$

    Suppose $M$ is disconnected. Let $A$ and $B$ be two disjoint, non-empty open sets such that
    $A \cup B = M$. Let $f:M \to Z$ be defined by $f(m) =
    \begin{cases}
      0, & m \in A\\
      1, & m \in B.
    \end{cases}$ Then clearly \red{use the fact that preimages are open?} $f$ is continuous on $M$,
    since $f$ is constant on $A$ and constant on $B$, and there are no other points in $M$.

    $\impliedby$

    Suppose $f:M \to \Z$ is continuous and non-constant. We shall show that $M$ can be partitioned
    into two disjoint non-empty open sets.

    Fix $k \in f(M)$, an arbitrary integer in the image of $M$, and let $J = f(M) \setminus
    \{k\}$. Note that $J$ is non-empty, since $f$ is non-constant, and note that $\{k\}$ and $J$
    are open in $\Z$.

    But then the preimages $f^\1(\{k\})$ and $f^\1(J)$ partition $M$ and are non-empty, disjoint,
    and open, since $f$ is continuous. Therefore $M$ is disconnected.
  \end{proof}
\newpage
\begin{mdframed}
\includegraphics[width=400pt]{img/oxford-a2-2-7.png}
\end{mdframed}
\item
  \begin{claim*}
    $H = \{(x, y) \in \R^2 ~|~ x > 0\}$ is connected.
  \end{claim*}

  \begin{proof}
    Let $H = \{(x, y) \in \R^2 ~|~ x > 0\}$. Let $u, v \in H$. Note that there exists a continuous
    map $\gamma:[0, 1] \to H$ such that $\gamma(0) = u$ and $\gamma(1) = v$. (For example, we can
    use the straight line $\gamma(t) = u + t(v - u)$. Therefore $H$ is path-connected, and
    therefore connected.
  \end{proof}

  % \begin{proof}
  %   Let $H = \{(x, y) \in \R^2 ~|~ x > 0\}$ and suppose for a contradiction that there exists a
  %   continuous non-constant map $f:H \to \Z$.

  %   Let $u, v \in H$ be such that $f(u) \neq f(v)$. Let
  %   $L = \{u + \rho(v - u) ~|~ \rho \in (0, 1)\}$ be the straight line between $u$ and $v$. But $L$
  %   is connected, since $L$ is homeomorphic to $\R$.

  %   \todo{But this doesn't yield a contradiction because we could have $f$ constant on
  %     $\rho \in (0, 1)$, with different values at the endpoints $u$ and $v$.}

  %   Let $<$ be a total ordering relation on $L$ defined by $l_1 < l_2 \iff |v - l_2| < |v -
  %   l_1|$. Let $S = \{l \in L ~|~ f(l) = f(u)\}$, let $T = \{l \in L ~|~ [u, l] \subseteq S\}$ and
  %   let $c = \sup T$.

  %   We claim that $f$ is not continuous at $c$.

  %   Indeed, suppose $c \in T$ so that $f(c) = f(u)$. Let $\epsilon = \frac{1}{2}$ and suppose there
  %   exists $\delta > 0$ such that $|l - \delta|$ is such that

  %   By the Approximation Property of the supremum, $c \notin T$. \todo{This requires that $T$ is
  %     open.}

  %   Specifically, let $\rho:L \to [0, 1]$ be defined by $l = u + \rho(l)(v - u)$.
  % \end{proof}

  \begin{claim*}
    There are precisely two continuous functions $f:H \to \R$ satisfying $f(x, y)^2 = x^2$ for all
    $(x, y) \in H$.
  \end{claim*}

  \begin{proof}
    \todo{}
    % Examples are
    % \begin{align*}
    %   f(x, y) &= x\\
    %   f(x, y) &= -x.
    % \end{align*}
  \end{proof}

\item
  \begin{problem*}
    How many continuous functions $g:\R^2 \to \R$ are there satisfying $g(x, y)^2 = x^2$ for all
    $(x, y) \in \R^2$?
  \end{problem*}
  \begin{proof}
    \todo{}
  \end{proof}
\end{enumerate}

\subsection{}


\begin{mdframed}
\includegraphics[width=400pt]{img/oxford-a2-2-8.png}
\end{mdframed}
\begin{enumerate}[label=(\roman*)]
\item
  \begin{claim*}
    Let $U$ be an open subset of $\R$ and $c \in U$. Then $U \setminus \{c\}$ is disconnected.
  \end{claim*}
  \begin{proof}
    Let $U$ be an open subset of $\R$ and $c \in U$. Let $V = (-\infty, c) \cap U$ and
    $W = (c, \infty) \cap U$. Note that there exist $b < c$ and $d > c$ with $b, d \in U$, since
    $U$ is open. Therefore $V$ and $W$ are non-empty, open, disjoint, and we have $V \cup W =
    U$. Therefore $U$ is disconnected.
  \end{proof}
\item

  \begin{claim*}
    Let $a \in \R^2$. Then $\R^2 \setminus \{a\}$ is connected.
  \end{claim*}
  \begin{proof}
    Let $u, v \in \R^2 \setminus \{a\}$. Note that there exists a continuous map
    $\gamma:[0, 1] \to \R^2$ such that $\gamma(0) = u$ and $\gamma(1) = v$. (For example, we can
    use the straight line $\gamma(t) = u + t(v - u)$). Therefore $\R^2 \setminus \{a\}$ is
    path-connected, and therefore connected.
  \end{proof}
  % {\bf Fragments}\\
  % \begin{mdframed}
  %   Let $U, V \subseteq \R^2$ be disjoint open sets that partition $\R^2 \setminus \{a\}$. We shall
  %   show that one of them must be empty.

  %   Suppose for a contradiction that neither $U$ nor $V$ is empty. Let $u \in U$ and $v \in V$. Let
  %   $\gamma:[0, 1] \to \R^2$ be given by $\gamma(t) = u + t(v - u)$.


  %   and
  %   let $L = \{u + \rho(v - u) ~|~ \rho \in [0, 1]\}$ be the straight line between $u$ and
  %   $v$. Note that, since they are open, neither $U$ nor $V$ are singleton sets. Therefore we may
  %   specify that $a \notin L$ (the line ``misses'' $a$).

  %   Let $<$ be a total ordering relation on $L$ defined by $l_1 < l_2 \iff |v - l_2| < |v -
  %   l_1|$. Let $T = \{l \in L ~|~ [u, l] \subseteq U\}$ and let $c = \sup T$.

  %   Suppose $c \in T$. Then $c \in U$. But $U$ is open so we must have $c < d \in U$. \red{and I
  %     think it follows that $d \in T$}, contradicting $c$ as $\sup T$.

  %   Alternatively suppose $c \notin T$. Then $c \in V$. But $V$ is open, so similarly we must have
  %   $c > b \in V$. But then $b \in U$ and $b \in V$ contradicting their disjointness.

  %   These contradictions imply that either $U$ or $V$ is empty and therefore that
  %   $\R^2 \setminus \{a\}$ is connected.
  % \end{mdframed}
\newpage
\item
  \begin{claim*}
    There is no invertible function $f:[0, 1) \to (0, 1)$.
  \end{claim*}
  \begin{proof}
    \todo{}
  \end{proof}

  \red{Hint from Alex: $R^2$ and $R^1$ are not homeomorphic because iof the above difference in how
    they respond to removal of a point. But why are $R^2$ and $R^3$ not homeomorphic? In general
    this requires algebraic topology.}


\end{enumerate}


\subsection{}
\begin{mdframed}
\includegraphics[width=400pt]{img/oxford-a2-2-9.png}
\end{mdframed}


\end{document}