Ian Charlesworth

1. Uniform convergence and boundedness

   Suppose that $X$ is a set and $(f_n)_n$ is a sequence of functions $X \to \R$, so that each $f_n$ is bounded. Suppose further that $(f_n)_n$ converges uniformly to some $f : X \to \R$. Show that $(f_n)_n$ is uniformly bounded: that is, there is some $T \in \R$ so that for all $x \in X$ and all $n \in \N$, \[\abs{f_n(x)} \leq T.\]

2. Uniform convergence and sums

   In this problem, we will make the assumption that sequences are indexed beginning at $0$ rather than at $1$.

   1. Suppose that $(a_k)_k$ is a sequence in $\R$. For each $n \in \N$, set \[s_n = \sum_{k=0}^n a_k.\] If $(s_n)_n$ converges, we write $\sum_{k=0}^\infty a_k = \lim_{n\to\infty}s_n.$ Show that the sequence $(s_n)_n$ converges if and only if for every $\epsilon \gt 0$ there is some $N \in \N$ so that for any $n, m \in \N$ with $N \lt n \lt m$, \[\abs{\sum_{k=n}^m a_k} \lt \epsilon.\]
   2. Suppose now that $X$ is a set, and $(f_k)_k$ is a sequence of function $X \to \R$. For each $n \in \N$, set \[g_n = \sum_{k=0}^n f_k.\] Show that the sequence $(g_n)_n$ converges uniformly if and only if for every $\epsilon \gt 0$ there is some $N \in \N$ so that for any $n, m \in \N$ with $N \lt n \lt m$, \[\sup_{x \in X}\abs{\sum_{k=n}^m f_k(x)} \lt \epsilon.\] In this case, we say that $\sum_{k=0}^\infty f_k$ converges uniformly, and use this to denote the limit of $(g_n)_n$.
   3. Suppose that $(B_k)_k$ is a sequence in $\R_{\geq 0}$ so that \[\sum_{k=0}^\infty B_k\] converges, and $(f_k)_k$ is a sequence of functions $X \to \R$ so that $f_k$ is bounded by $B_k$: that is, $\abs{f_k(x)} \leq B_k$ for all $x \in X$. Use parts A and B to show that \[\sum_{k=0}^\infty f_k\] converges uniformly.
   4. Show that if $\abs{r} \lt 1$, then \[\sum_{k=0}^\infty r^k = \frac1{1-r}.\] (Hint: first notice that $(1-r)(1+r+r^2+\cdots+r^n) = 1-r^{n+1}$.)
   5. Suppose that $(a_k)_k$ is a sequence in $\R$ so that $\limsup_{k\to\infty} \abs{a_k}^{1/k} \lt 1$. Prove that \[\sum_{k=0}^\infty a_k x^k\] converges uniformly on $[-1, 1]$. (Here, "$a_kx^k$" is being used to mean the function $x \mapsto a_kx^k$.)

   A function of the form above is called a power series. Since a power series is the uniform limit of polynomials—which are continuous—it is continuous.

3. A poorly-behaved function

   Let $C : \R \to [-1, 1]$ be a continuous function with the properties that $C(2k) = 1$ and $C(2k+1) = -1$ for every $k \in \Z$, and that $\abs{C(x)-C(y)} \leq 4\abs{x-y}$ for all $x, y \in \R$.

   1. Prove that \[\sum_{{\color{red}j}=0}^\infty \paren{\frac34}^j C(9^j x)\] converges uniformly to some function $W : \R \to \R$.
   2. Let $n \in \N$ and $a \in \Z$. Show that \[\abs{W\paren{\frac{a+1}{9^n}} - W\paren{\frac{a}{9^n}}} \gt \paren{\frac34}^n.\] (Hint: the analysis here requires getting your hands dirty, and you'll probably need to make use of both 2D and its hint. Break the sum up into two pieces, and show that the tail is large enough to overcome the first piece.)
   3. Conclude that $W$ is continuous, but not differentiable at any point in $\R$.
   

Here are some further problems to think about out of interest. You do not need to attempt them, nor should you submit them with the assignment. They are coloured by approximate difficulty: easy/medium/hard.

• Uniform convergence and derivatives

  For each $n \in \N$, let \begin{align*} f_n : \R &\longrightarrow \R \\ x &\longmapsto \frac{x}{1+nx^2}. \end{align*} Show that the sequence $(f_n)_n$ converges uniformly (on $\R$) to some function $f$, and that $(f_n')_n$ converges to $f'$ pointwise on $\R\setminus\set0$, but not at $0$.

• Pointwise convergence versus metric space convergence

  Suppose $S$ is a set, and consider the set of functions from $S$ to $\R$, $\R^S = \set{f : S \to \R}$. Let us say that a metric $d$ on $\R^S$ gives rise to the topology of pointwise convergence if whenever $(f_n)_n$ is a sequence of functions in $\R^S$ we have that $(f_n)_n$ converges to a function $f$ with respect to $d$ if and only if $(f_n)_n$ converges pointwise to $f$.

  Show that there is a metric on $\R^S$ giving rise to the topology of pointwise convergence if and only if there is a one-to-one function $\varphi : S \to \N$.

• Uniform convergence versus metric space convergence

  1. Suppose that $S$ is a set and $(M, d_M)$ is a bounded metric space. Define a metric $d_\infty$ on $M^S = \set{f : S \to M}$ by \[d_\infty(f, g) = \sup_{s \in S} d_M(f(s), f(g)).\] Show that a sequence of functions $(f_n)_n$ in $M^S$ converges uniformly to $f : S \to M$ if and only if $(f_n)_n$ converges to $f$ with respect to the metric $d_\infty$.
  2. Let $(M, d_M)$ be a metric space. Define $d_M' : M \times M \to \R_{\geq 0}$ by $d_M'(x, y) = \min(1, d_M(x, y))$. Show that $d_M'$ is a metric equivalent to $d_M$ (i.e., $d_M'$ is a metric such that sets are open with respect to $d_M$ if and only if they are open with respect to $d_M'$). Notice that $(M, d_M')$ is bounded.
  3. Suppose that $X$ is a set, and $d, d'$ are equivalent metrics on $X$. Show that sequences converge with respect to $d$ if and only if they converge with respect to $d'$.
  4. Suppose that $S$ is a set and $(M, d_M)$ is an arbitrary metric space. Show that there is a metric on $M^S$ so that sequences in $M^S$ converge with respect to the metric if and only if they converge uniformly. (We say "the topology of uniform convergence is metrizable".)

• Monotone convergence of functions (Dini's Theorem)

  Suppose that $K$ is a compact metric space, and $(f_n)_n$ is a sequence of continuous functions $K \to \R$, so that $f_1 \leq f_2 \leq f_3 \leq \cdots$. Suppose further that $(f_n)_n$ converges pointwise to some continuous function $f$: that is, for every $x \in K$, \[\limni f_n(x) = f(x).\] Prove that $(f_n)_n$ converges to $f$ uniformly.

• A norm on integrable functions

  Let $R$ be the set of integrable functions on the interval $[a, b]$. Given $f \in R$, define \[\norm{f}_2 = \paren{\int_a^b\abs{f(t)}^2\,dt}^{\frac12}.\]

  1. Show that $\norm\cdot_2$ satisfies the triangle inequality in the following sense: for all $f, g, h \in R$, \[\norm{f-h}_2 \leq \norm{f-g}_2 + \norm{g-h}_2.\]
  2. Suppose $f \in R$. Show that for any $\epsilon \gt 0$, there is a continuous function $g \in R$ with \[\norm{f-g}_2 \lt \epsilon.\] (Hint: choose a suitable partition $P = \set{x_0, \ldots, x_n}$, and take a piece-wise linear function $g$ so that $g(x_i) = f(x_i)$.)
  3. Suppose $f \in R$. Show that for any $\epsilon \gt 0$ there is a polynomial $p \in R$ so that \[\norm{f-p}_2 \lt \epsilon.\] (Hint: for this one you need Stone's Theorem, which we hopefully will cover next week.)

  The function $d_2(f, g) = \norm{f-g}_2$ on $R\times R$ is a pseudo-metric on $R$: it satisfies the triangle inequality, $d_2(f,f) = 0$, and $d_2(f, g) = d_2(g, f)$, but $d_2(f, g)=0$ does not imply $f = g$. If we define $\sim$ by $f\sim g$ whenever $d_2(f, g) = 0$, then $R/\sim$ becomes a metric space; what we have done is show that (equivalence classes of) polynomials are dense in $R/\sim$.

• Monotony

  State precisely what is meant by:

  • a monotone sequence of functions;
  • a sequence of monotone functions; and
  • a monotone sequence of monotone functions.

  Provide examples to show that these three concepts are different.

• Uniform closures of algebras need not be algebras

  Recall that for $x \in \R$, $\floor{x}$ (the floor of $x$) is the greatest integer $k \in \Z$ with $k \leq x$. For $n \in \N$, define \begin{align*} \varphi_n: \R &\longmapsto \R\\ t & \longmapsto 2^{-n}\floor{2^nt}. \end{align*} Finally, let $\mathscr{A}$ be the algebra of functions generated by $(\varphi_n)_n$. That is, $\mathscr{A}$ consists of all functions which are finite sums of scalar multiples of finite products of $\varphi_n$'s.

  Let $\overline{\mathscr{A}}$ be the uniform closure $\mathscr{A}$. Show that $\overline{\mathscr{A}}$ is not an algebra. (Hint: $x\mapsto x$ is in $\overline{\mathscr{A}}$, but $x \mapsto x^2$ is not.)

  Reflect on what this example says about trying to plot quadratic or linear functions on a pixelated display.

• More on power series

  Prove that a power series is differntiable, and its derivative is given by differentiating the sum term-by-term. (This is not immediate and does take work, as in general, uniform limits of differentiable functions need not be differentiable, or may have derivatives unrelated to the derivatives of their approximants.) Conclude that a power series is infinitely differentiable.

• Functions orthogonal to polynomials are zero

  Let $f : [0, 1] \to \R$ be continuous.

  1. Show that $f \equiv 0$ if \[\int_0^1 f(t)^2\,dt = 0.\]
  2. Suppose that for every $n \in \N\cup\set0$, \[\int_0^1 f(t)t^n\,dt = 0.\] Show that $f \equiv 0$. (Hint: by the end of the week, we will have proved the following theorem which you may find useful: if $K \subseteq \R$ is compact and $g : K \to \R$ is continuous, there is a sequence of polynomials $(p_n)_n$ which converges uniformly to $g$ on $K$. Use this to show that $\int_0^1 f(t)^2\,dt=0$.)

• Another weird pathology

  Show by example that there exists a function $f : \R \to \R$ such that $f$ takes on every real value on every non-empty open set. That is, for any $U \subseteq \R$ open and any $y \in \R$, there is some $x \in U$ with $f(x) = y$. (This isn't really related to this week's material in particular, it's just an interesting problem.)

1. A pathological function

   Let $f : [0,1] \to \R$ be defined as follows: \[ f(x) = \begin{cases} 0 & \text{ if } x \notin \Q \\ 1 & \text{ if } x = 0 \\ \frac1q & \text{ if } x = \frac{p}{q} \text{ with } p \in \Z, q \in \N, \text{ and } p, q \text{ have no common factor}.\end{cases}\] (For example, $f(0) = f(1) = 1$, $f(1/2) = 1/2$, $f(1/4) = f(3/4) = 1/4$.)

   Prove that $f$ is integrable, and find its integral.

2. Integrals are insensitive to individual points

   1. This week, we will see that continuous functions are integrable. Use this to prove that if $f : [a, b] \to \R$ is bounded and continuous except at finitely many points, then $f$ is integrable.
   2. Suppose that $f : [a, b] \to \R$ is integrable, and $g : [a, b] \to \R$ is such that $f(x) = g(x)$ for all but finitely many $x \in [a, b]$. Show that $g$ is integrable, and \[\int_a^b f(x)\,dx = \int_a^b g(x)\,dx.\]

3. Properties of integrals

   1. Let $f : [0, 1] \to \R_{\geq 0}$ be continuous. Show that $f = 0$ (that is, $f$ is the constant function $0$) if and only if \[\int_0^1 f(t)\,dt = 0.\]
   2. Show that if the assumption of continuity is dropped in Part A, it is no longer true.
   3. Suppose that $f, g : [a, b] \to \R$ are such that $f(t) \leq g(t)$ for all $t \in \R$. Show that $U(f) \leq U(g)$. (Note that, as a consequence, if $f$ and $g$ are integrable then $\int_a^b f(t)\,dt \leq \int_a^b g(t)\,dt$.)
   4. Suppose that $f : [a, b] \to \R$ is monotonically increasing, i.e., if $a \leq t \lt s \leq b$ then $f(t) \leq f(s)$. Prove that $f$ is integrable.

4. An integral of integrals

   Suppose that $f : [0, 1] \times [0, 1] \to \R$ is continuous. Notice that for each $y_0 \in [0, 1]$, we have a function \begin{align*} [0, 1] &\longrightarrow \R \\ x &\longmapsto f(x, y_0). \end{align*} Each of these functions is continuous, and so integrable; this can be checked directly from the definition, or by using the sequential characterisation of continuity.

   1. Prove that for any $\epsilon \gt 0$ there is a $\delta \gt 0$ so that if $\abs{y - z} \lt \delta$, we have \[ \sup_{x \in [0, 1]} \abs{f(x, y) - f(x, z)} \lt \epsilon. \]
   2. Show that the function \begin{align*} I: [0, 1] &\longrightarrow \R \\ y &\longmapsto \int_0^1 f(x, y) \,dx \end{align*} is continuous, and therefore integrable.

Here are some further problems to think about out of interest. You do not need to attempt them, nor should you submit them with the assignment.

• Not definitions

  1. We say a function $f : X \to Y$ is funtinuous at $p \in X$ if for every $\epsilon \gt 0$ there is some $\delta \gt 0$ so that for every $x, y \in X$ with $d_X(x, y) \lt \delta$ we have $d_Y(f(x), f(y)) \lt \epsilon$.
     1. Are all functions funtinuous?
     2. Are all continuous functions funtinuous?
     3. Are all funtinuous functions continuous?
     4. Does a funtinuous function exist?
  2. We say a function $f : X \to Y$ is protinuous if for every $x_0 \in X$, $\forall\delta \gt 0$, for all $x \in X$ with $d_X(x, x_0) \lt \delta$ there exists $\epsilon \gt 0$ so that $d_Y(f(x), f(x_0)) \lt \epsilon$.
     1. Are all functions protinuous?
     2. Are all continuous functions protinuous?
     3. Are all protinuous functions continuous?
     4. Does a protinuous function exist?
  3. We say a function $f : X \to Y$ is antitinuous at a point $p \in X$ if for every $\epsilon \gt 0$ and all $x \in X$, there exists $\delta \gt 0$ so that $d_X(x, p) \lt \delta$ implies $d_Y(f(x), f(p)) \lt \epsilon$.
     1. Are all functions antitinuous?
     2. Are all continuous functions antitinuous?
     3. Are all antitinuous functions continuous?
     4. Does a antitinuous function exist?
  4. We say a function $f : X \to Y$ is continually uniformous if for all $x, y \in X$ and all $\epsilon \gt 0$ there is a $\delta \gt 0$ so that $d_X(x, y) \lt \delta$ implies $d_Y(f(x), f(y)) \lt \epsilon$.
     1. Are all functions continually uniformous?
     2. Are all uniformly continuous functions continually uniformous?
     3. Are all continually uniformous functions uniformly continuous?
     4. Does a continually uniformous function exist?
  5. We say a function $f : X \to Y$ is continuously uniform if for every $\epsilon \gt 0$ there is a $\delta \gt 0$ so that for all $x, y \in X$, $d_Y(f(x), f(y)) \lt \epsilon$ implies $d_X(x, y) \lt \delta$.
     1. Are all functions continuously uniform?
     2. Are all uniformly continuous functions continuously uniform?
     3. Are all continuously uniform functions uniformly continuous?
     4. Does a continuously uniform function exist?

• Integrals of integrals

  Let $f : [0, 1]\times[0, 1] \to \R$.

  1. Suppose rather than assuming that $f$ is continuous, we merely assume that for each $y \in [0, 1]$, the function $x \mapsto f(x, y)$ is integrable. Is \[ y \mapsto \int_0^1 f(x, y)\,dx \] continuous? Integrable?
  2. Suppose $f$ is continuous. Problem 4 allows us to define the integral \[\int_0^1 \int_0^1 f(x, y)\,dx\,dy,\] and a similar argument shows that \[\int_0^1 \int_0^1 f(x, y)\,dy\,dx\] exists as well. Must these two quantities be equal?
  3. Suppose rather than assuming that $f$ is continuous, we merely assume that for each $y \in [0, 1]$, the functions \[ x \mapsto f(x, y) \hspace{2cm}\text{and}\hspace{2cm} x \mapsto f(y, x) \] are both integrable. Must \[ y \mapsto \int_0^1 f(x, y)\,dx \hspace{2cm}\text{and}\hspace{2cm} y \mapsto \int_0^1 f(y, x)\,dx\] be integrable?
  4. Suppose now that $f$ is such that \[ x \mapsto f(x, y) \hspace{2cm}\text{and}\hspace{2cm} x \mapsto f(y, x) \] are integrable for each $y \in [0, 1]$, and that \[ y \mapsto \int_0^1 f(x, y)\,dx \hspace{2cm}\text{and}\hspace{2cm} y \mapsto \int_0^1 f(y, x)\,dx\] are integrable. Must \[ \int_0^1 \int_0^1 f(x, y)\,dx\,dy = \int_0^1 \int_0^1 f(x, y)\,dy\,dx\text{?} \]

1. A criterion for differentiability

   Suppose $f : (a, b) \to \R$ and $x \in (a, b)$. Show that $f$ is differentiable at $x$ if and only if there is a function $E : (a, b) \to \R$ continuous at $x$ and a constant $C \in \R$ so that $E(x) = 0$ and for all $t \in (a, b)$, \[f(t) = f(x) + C(t-x) + E(t)(t-x).\] Moreover, show that in this case $C = f'(x)$.

2. Some counterexamples of converses

   Give an example of continuous functions $f, g : \R \to \R$ so that:

   1. $f+g$ is differentiable but $f$ is not.
   2. $fg$ is differentiable, $f$ is not, and $g(x) \gt 0$ for all $x \in \R$.

3. More derivatives

   Let $S, C : \R \to [-1, 1]$ be differentiable functions with the following properties:

   • for all $x \in \R$, $S(x+\pi) = -S(x)$ and $C(x+\pi) = -C(x)$;
   • for all $x \in \R$, $S'(x) = C(x)$ and $C'(x) = -S(x)$; and
   • $C(0) = 1 = S\paren{\frac\pi2}$ while $C\paren{\frac\pi2} = 0 = S(0)$.

   Let \begin{align*} f : \R &\longrightarrow \R \\ t &\longmapsto \begin{cases} 0 & \text{ if } t = 0 \\ t^2S\paren{\frac1t} & \text{ if } t \neq 0.\end{cases} \end{align*}

   1. Show that $f$ is differentiable on $\R$, and find its derivative (in terms of $C$ and $S$).
   2. Show that $f'$ is discontinuous at $0$.

4. Inverses

   Suppose that $f : (a, b) \to \R$ is differentiable with $f'(x) \gt 0$ for all $x \in (a, b)$.

   1. Prove that $f$ is strictly monotonically increasing, i.e., if $a \lt x \lt y \lt b$ then $f(x) \lt f(y)$.
   2. Note that $f$ is one-to-one, and so has an inverse function $g : f((a, b)) \to (a, b)$. Show that $g$ is continuous.
   3. Show that for all $x \in (a, b)$, then we have $f(x) \in f((a, b))^\circ$ (the interior of $f((a,b))$). (Fixed grammar.)
   4. We saw that if $g$ is differentiable at $f(x)$, it must be the case that \[g'(f(x)) = \frac1{f'(x)}.\] Verify that $g$ is differentiable at $f(x)$.

5. Positive derivative at a point

   Suppose that $f : \R \to \R$ is differentiable, and $f'(0) \gt 0$.

   1. Show that if $f'$ is continuous at $0$, then there is some $\delta\gt0$ so that $f$ is monotonically increasing on $(-\delta, \delta)$.
   2. Show by example that this need not be the case if $f'$ is not continuous at $0$.

Here are some further problems to think about out of interest. You do not need to attempt them, nor should you submit them with the assignment.

• Differentiability and monotony

  1. Does there exist a differentiable function $f : \R\to\R$ which is not strictly monotonic on any open interval?
  2. Does there exist a differentiable function $f : \R\to\R$ which is not monotonic on any open interval? (Recall that monotonic differs from strictly monotonic in that the strict inequalities $\lt$, $\gt$ in its definition are replaced by weak inequalities $\leq$, $\geq$.)
  3. Does there exist a differentiable function $f : \R \to \R$ so that $f'(0) = 0$ but $f$ is strictly monotonic?

• Constants

  1. Prove that if $f : \R \to \R$ satisfies $f'(x) = 0$ for all $x \in \R$, then $f$ is constant. (There is actually something to check here.)
  2. Conclude that if $f' = g'$ then $f = g + C$ for some $C \in \R$.

• Growth

  Suppose that $f, g : \R \to \R$ are such that $f(0) = g(0)$ and $f'(x) \lt g'(x)$ for all $x \in \R$. Prove that $\abs{f(x)} \leq \abs{g(x)}$ for all $x \in \R$, with equality only when $x = 0$.

• Difference quotients

  Suppose $f : \R \to \R$. Define a function \begin{align*} F : \R^2 \setminus \set{(x, x) \mid x \in \R} &\longrightarrow \R \\ (x, y) &\longmapsto \frac{f(x) - f(y)}{x-y}. \end{align*} Under what conditions does $F$ extend continuously to $\R^2$, in the sense of Assignment 8 Question 4?

  (While this certainly seems to have something to do with differentiability, it is a little subtle. Notice, for example, that taking a derivative corresponds to holding one variable fixed and letting the other tend to it, or approaching the missing diagonal horizontally or vertically only; meanwhile continuity requires everything in an open ball to be close to the correct value, not just along the two axes. (It just now occurs to me how "axis" and "axe" both have the plural "axes".))

1. Connected sets

   Let $M$ be a metric space.

   1. Let $x \in M$. Prove that $\set{x}$ is connected.
   2. Suppose that $A, B \subseteq M$ are connected and $A \cap B \neq \emptyset$. Prove that $A \cup B$ is connected.

   Let us define a relation $\sim$ on $M$ as follows: given $x, y \in M$, $x \sim y$ if and only if there is a connected set $A \subseteq M$ with $x, y \in A$. Let us also write \[ [x]_\sim = \set{y \in M \mid x \sim y}.\]

   3. Prove that $\sim$ has the following three properties:
      1. for any $x \in M$, $x \sim x$;
      2. for any $x, y \in M$, if $x \sim y$ then $y \sim x$; and
      3. for any $x, y, z \in M$, if $x\sim y$ and $y \sim z$ then $x \sim z$.
      (This means that $\sim$ is an equivalence relation.)
   4. Suppose that $H \subseteq M$ is connected, and $x \in H$. Show that $H \subseteq [x]_\sim$.
   5. Suppose $x \in M$. Show that $[x]_\sim$ is connected.

   The equivalence classes $[x]_\sim \subseteq M$ are called the connected components of $M$; they are in a loose sense the "largest connected pieces" of $M$. Notice that \[M = \bigcup_{x \in M} [x]_\sim,\] that is, $M$ is the union of its connected components. Also, since $[x]_\sim = [y]_\sim$ whenever $x \sim y$, the connected components of $M$ are disjoint. Since every point of $M$ is in some connected component, it follows that a non-empty space $M$ is connected if and only if it has precisely one connected component.

   To give a few examples, the connected components of $\Z$ are the sets $\set{k}$ for each $k \in \Z$, and the connected components of $\Q$ are the sets $\set{q}$ for each $q \in \Q$. The connected components of $[0, 1) \cup \set{4} \cup (6, 9)$ are $[0, 1)$, $\set4$, and $(6,9)$. The circle $\set{(x, y) \in \R^2 \mid x^2 + y^2 = 1}$ has one connected component, itself; the same is true of any connected set. The empty set has no connected components (since in our definition, the empty set is not connected; we defined it this way so that we could unambiguously list the connected components of a set).

2. Path connected sets

   Suppose $M$ is a metric space. If $x, y \in M$, a path (in $M$) from $x$ to $y$ is a continuous function $\gamma : [0, 1] \to M$ with $\gamma(0) = x$ and $\gamma(1) = y$.

   Define a relation $\sim_p$ on $M$ by $x \sim_p y$ if and only if there is a path from $x$ to $y$ in $M$. As before, set \[ [x]_{\sim_p} = \set{y \in M | x \sim_p y}.\]

   1. Show that $\sim_p$ is an equivalence relation: that is,
      1. for any $x \in M$, $x \sim_p x$;
      2. for any $x, y \in M$, if $x \sim_p y$ then $y \sim_p x$; and
      3. for any $x, y, z \in M$, if $x\sim_p y$ and $y \sim_p z$ then $x \sim_p z$.

   The equivalence classes $[x]_{\sim_p} \subseteq M$ are called path components of $M$. If $M$ has exactly one path component, it is called path connected. (Note that $\emptyset$ is not path connected: it has zero path components, not one.)

   2. Show that if $M$ is path connected, then it is connected.

   3. Suppose that $E \subseteq \R^n$ is open. Show that the path components of $E$ are open (in $\R^n$).

      (If you find it useful, you may use without proof the fact that functions of the form \begin{align*}f : \R &\longrightarrow \R^n \\ t &\longmapsto \vec{a} + t\vec{b}\end{align*} are continuous, where $\vec{a}, \vec{b} \in \R^n$.)

   4. Prove that if $E \subseteq \R^n$ is open and connected, then $E$ is path connected.

   It is not true that connected sets are path connected in general. For example, the set \[T = \set{(0, y) \mid -1 \leq y \leq 1} \cup \set{\paren{x, \sin\paren{\frac1x}} \mid x \gt 0} \subseteq \R^2\] can be shown to be connected but not path connected; it's path components are the two separate pieces in the presentation above.

3. The Squeeze Theorem for functions

   Suppose that $E \subseteq M$ and $p$ is a limit point of $E$. Suppose further that $f, g, h : E \to \R$ are functions, and that for some $\delta \gt 0$ and all $x \in E$ with $0 \lt d(x, p) \lt \delta$ we have \[f(x) \leq g(x) \leq h(x).\] Finally, suppose that \[\lim_{x\to p} f(x) = L = \lim_{y \to p} h(y).\] Prove that \[\lim_{t\to p} g(t) = L.\]

4. A derivative

   Let \begin{align*}f : \R &\longrightarrow \R \\ x &\longmapsto \begin{cases}0 & \text{ if } x \in \Q \\ x^2 & \text{ otherwise}.\end{cases}\end{align*} Show that $f$ is differentiable at $0$, and find its derivative there. (Notice that $f$ is discontinuous everywhere except at $0$! (That is an exclaimation point, not a factorial; $f$ is discontinuous at $1$.))

Here are some further problems to think about out of interest. You do not need to attempt them, nor should you submit them with the assignment. They are coloured by approximate difficulty: easy/medium/hard.

• More on connected components

  1. Prove that if $E \subseteq M$ is connected, then so is $\overline E$.
  2. Prove that if $C \subseteq M$ is a connected component of $M$, then $C$ is closed.
  3. Prove that if $M$ has a finite number of connected components, then each component is clopen.
  4. Show that if $M$ has an infinite number of connected components. Which of the following are possible? Provide examples of those that are, and proofs that the rest are impossible.
     1. All the connected components of $M$ are open.
     2. All but finitely many connected components of $M$ are open.
     3. Infinitely many connected components of $M$ are open, and infinitely many are not.
     4. Finitely many connected components of $M$ are open, and the rest are not.
     5. None of the connected components of $M$ are open.

• Equivalent definitions of connectedness

  Let $M$ be a metric space and $E \subseteq M$. Show that the following are equivalent:

  • $E$ is non-empty, and there do not exist $U_1, U_2 \subseteq M$ disjoint open sets so that $U_1 \cap E$, $U_2 \cap E$ are non-empty with $E \subseteq U_1\cup U_2$;
  • every open cover of $E$ by disjoint sets has a subcover containing a single open set.

• Temperatures

  Show that there are two points on opposite sides of the equator with the same temperature as each other.

  What assumptions are needed to make this true? Are they physically reasonable?

• Mountains

  Suppose that you climb a mountain one day, and descend it the next. Show that there must be some time when your elevation was the same on both days.

• More on derivatives

  Suppose that $E \subseteq \R$ has the property and $p \in E' \cap (E^c)'$. Suppose further that $f, g : \R \to \R$. Define \begin{align*} \varphi : \R &\longrightarrow \R \\ t &\longmapsto \begin{cases} f(t) &\text{ if } t \in E \\ g(t) &\text{ if } t \in E^c.\end{cases} \end{align*} Prove that $\varphi$ is differentiable at $p$ if and only if $f$ and $g$ both are, $f'(p) = g'(p)$, and $f(p) = g(p)$.

1. A pathological function

   Let $f : [0,1] \to \R$ be defined as follows: \[ f(x) = \begin{cases} 0 & \text{ if } x \notin \Q \\ 1 & \text{ if } x = 0 \\ \frac1q & \text{ if } x = \frac{p}{q} \text{ with } p \in \Z, q \in \N, \text{ and } p, q \text{ have no common factor}.\end{cases}\] (For example, $f(0) = f(1) = 1$, $f(1/2) = 1/2$, $f(1/4) = f(3/4) = 1/4$.)

   Prove that $f$ is continuous at every irrational number, but discontinuous at every rational number.

2. Composition of functions continuous at a point

   Suppose that $X, Y, Z$ are metric spaces, that $f : X \to Y$ and $g : Y\to Z$, that $x_0 \in X$, and that $f$ is continuous at $x_0$ while $g$ is continuous at $f(x_0)$. Verify that $g\circ f$ is continuous at $x_0$.

   (You should not assume that $f$ or $g$ are continuous anywhere else. If you use the open set chracterisation mentioned in extra problems below, you should prove it, although I don't think that is the easiest way forward for this problem.)

3. Continuous functions on dense sets

   Suppose that $f, g : X \to Y$ are continuous, and $E \subseteq X$ is dense; recall that by definition this means $\overline E = X$.

   (This time you may use the additional characterisations of density given below, but if you do you should convince yourself that you can prove them.)

   1. Prove that $f(E)$ is dense in $f(X)$.
   2. Prove that if $f(x) = g(x)$ for all $x \in E$, then $f(x) = g(x)$ for all $x \in X$. (Thus the value of a continuous function is determined by its values on a dense set.)

4. Uniformly continuous functions have extensions

   Again, suppose that $E \subseteq X$ is dense, and suppose that $f : E \to Y$ is uniformly continuous on $E$. Suppose also that $Y$ is complete.

   1. Show that if $(x_n)_n$ is a Cauchy sequence in $E$, then $(f(x_n))_n$ is Cauchy in $Y$.
   2. Show that if $(x_n)_n$ and $(a_n)_n$ are sequences in $E$ converging to $x \in X$, then $(f(x_n))_n$ and $(f(a_k))_k$ converge in $Y$ to the same limit.
   3. Prove that there is a uniformly continuous function $\tilde f : X \to Y$ so that $\tilde f(x) = f(x)$ for all $x \in E$. (This function is called a continuous extension of $f$; by the previous problem, we know it is unique.)
   4. Show that if $f$ is merely assumed to be continuous, it may not have a continuous extension.

5. Distances and compact sets

   Suppose that $(M, d)$ is a metric space.

   1. Let $d_2$ be the metric on $M \times M$ given by \[d_2( (x_1, x_2), (y_1, y_2) )^2 = d(x_1, y_1)^2 + d(x_2, y_2)^2.\] Prove that \[d : M\times M \to \R_{\geq0}\] is continuous with respect to $d_2$.
   2. Suppose that $J, K \subseteq M$ are compact and non-empty. Prove that there are $x \in J$, $y \in K$ so that \[d(x, y) = \inf\set{d(s, t) \mid s \in J, t \in K}.\] (Any two compact sets have a pair of points which are as close as possible.)

6. Meditations on a theme of discontinuity

   1. Let $S : \R \to \R$ be a continuous function with the property that for any $T \in \R$ there are $x, y \gt T$ and $a, b \lt T$ so that \[S(x) = 1 = S(a) \hspace{2cm}\text{and}\hspace{2cm} S(y) = -1 = S(b).\] Let $f : \R \to \R$ satisfy $f(x) = S\paren{\frac1x}$ for $x \neq 0$, and $f(0) = 0$. Determine where $f$ is continuous.
   2. Let $f$ be the function from Part A. Find an open set $U \subseteq \R$ so that $f^{-1}(U)$ is not open.
   3. Let $g : \R \to \R$ be given by \[g(x) = \begin{cases} 0 & \text{ if } x \lt 0 \\ 1 & \text{ otherwise}.\end{cases}\] Determine which open subsets of $\R$ have open preimages under $g$.
   

Here are some further problems to think about out of interest. You do not need to attempt them, nor should you submit them with the assignment.

• A characterisation of density

  Suppose that $(M, d)$ is a metric space and $X \subseteq M$. Prove that the following are equivalent:

  1. $X$ is dense in $M$, i.e., $M = \overline{X}$ (the closure of $X$);
  2. for every $a \in M$ and every $\epsilon \gt 0$ there is some $x \in X \cap B_\epsilon(a)$; and
  3. for every $a \in M$ there is some sequence in $X$ converging to $a$.
  (Warning: this is not the same as saying that every $a \in M$ is a limit point of $X$; convince yourself that these are different.)

• Closures and limits

  I'm not sure if I proved these useful facts in lecture or not. Prove them now, without looking things up in the notes or the text.

  Suppose that $(M, d)$ is a metric space.

  1. Suppose that $F \subseteq M$ is closed, and $(x_n)_n$ is a sequence in $F$. Then if $(x_{n_k})_k$ is a convergent subsequence of $(x_n)_n$, its limit is in $F$.
  2. Suppose that $E \subseteq M$. Then $x \in \overline{E}$ if and only if there is a sequence in $E$ which converges to $x$.

• An open set characterisation of continuity at a point

  Suppose that $X, Y$ are metric spaces, $f : X \to Y$, and $x_0 \in X$. Show that $f$ is continuous at $x_0$ if and only if whenever $U \subseteq Y$ is open with $f(x_0) \in Y$, there is an open set $V \subseteq X$ with $x \in V \subseteq f^{-1}(U)$.

  This is unfortunately not as nice as the case for functions that are continuous on all of $X$.

• Distances, closed sets, and compact sets

  Suppose that $K \subseteq M$ is compact and $F \subseteq M$ is closed and bounded. Prove that there are $x \in K, y \in F$ so that \[d(x, y) = \inf\set{d(s, t) \mid s \in J, t \in K},\] or show by example that this may not be the case.

• Continuity and relatively open sets

  Let $(M, d)$ be a metric space, and $X \subseteq M$. Define $\iota$ to be the inclusion $\iota : X \hookrightarrow M$ defined by $x \mapsto x$. Ponder the relation between Assignment 4, Problem 3 and the continuity of $\iota$.

I recommend thinking about the "Not definitions" problem below.

1. Limits and order properties

   1. Suppose that $(a_n)_n$ is a convergent sequence in $\R$, and there are $N \in \N$ and $b \in \R$ such that $a_n \leq b$ for all $n \gt N$. Prove that \[\lim_{n\to\infty} a_n \leq b.\]
   2. Suppose that $(a_n)_n$ and $(b_n)_n$ are convergent sequences in $\R$ such that for some $N \in \N$ and every $n \gt N$, $a_n \leq b_n$. Prove that \[\lim_{n\to\infty} a_n \leq \lim_{n \to \infty} b_n.\] (Hint: use Part A.)
   3. Suppose that $(a_n)_n$ and $(b_n)_n$ are convergent sequences in $\R$ such that for some $N \in \N$ and every $n \gt N$, $a_n \leq b_n$, and so that \[\lim_{n\to\infty}a_n = \lim_{n\to\infty}b_n.\] Suppose further that $(c_n)_n$ is another sequence so that $a_n \leq c_n \leq b_n$ for $n \gt N$. Prove that $(c_n)_n$ converges to the same limit as $(a_n)_n$ and $(b_n)_n$.
   4. Show by example that if $(a_n)_n$ is a convergent sequence in $\R$ and $b \in \R$ is such that $a_n \lt b$ for all $n$, it may not be the case that \[\lim_{n\to\infty} a_n \lt b.\]
   5. Show that if $(a_n)_n$ is Cauchy in some metric space $(M, d)$, then \[\lim_{n\to\infty}\paren{\lim_{k\to\infty} d(a_n, a_k)} = 0.\]

2. Properties of limits superior and inferior

   Recall that the limit superior of a sequence of real numbers $(x_n)_n$ is defined to be \[ \limsup_{n\to\infty} x_n = \begin{cases} \infty & \text{ if } (x_n)_n \text{ is not bounded above}\\ -\infty & \text{ if } (x_n)_n \text{ is bounded above but } \paren{ \sup\set{x_k \mid k \gt n} }_n \text{ is not bounded below}\\ \displaystyle\lim_{n\to\infty} \sup\set{x_k \mid k \gt n} & \text{ otherwise}. \end{cases} \]

   1. Verify that if $(x_n)_n$ is bounded above, then the sequence $\paren{ \sup\set{x_k \mid k \gt n} }_n$ is monotonic.
   2. Prove that for every $y \in \R$ with $y \gt \limsup_{n\to\infty} x_n$, there are only finitely many $n \in \N$ for which $x_n \gt y$.
   3. Prove that for every $y \in \R$ with $y \lt \limsup_{n\to\infty} x_n$, there are infinitely many $n \in \N$ for which $x_n \gt y$.
   4. Prove that if $(x_n)_n$ and $(y_n)_n$ are sequences in $\R$, then \[\limsup_{n\to\infty} x_n + \limsup_{n\to\infty} y_n \geq \limsup_{n\to\infty} x_n + y_n,\] provided that all the limits superior involved are finite.
   5. Show by example that the above inequality is not always an equality.

   Be sure to consider the possibilities that $\limsup_{n\to\infty} x_n$ is $\pm\infty$ in B and C. Notice also that B and C together give another characterization of the limit superior: it is the unique element of $\R \cup \set{\infty, -\infty}$ with both properties.

3. Limits of functions

   1. Suppose $(M, d)$ is a metric space, $E \subseteq M$, $f, g : E \to \R$, and $p$ is a limit point of $E$. Suppose further that for some $r \gt 0$, the set $f(E\cap B_r(p)) = \set{f(x) \mid x \in E\cap B_r(p)} \subseteq \R$ is bounded, and that \[\lim_{x\to p}g(x) = 0.\] Show that \[\lim_{x\to p} f(x)g(x) = 0.\] (Note: you should not assume that $f$ has a limit at $p$, unless you prove it from these hypotheses.)

   Suppose that $(M, d)$ and $(X, d_X)$ are metric spaces, $E \subseteq M$, $f : E \to X$, and $p$ is a limit point of $E$.

   2. Show that if $f$ has a limit at $p$, then for every $\epsilon \gt 0$ there is some $r \gt 0$ so that whenever $x, y \in B_r(p) \cap E \setminus \set{p}$, $d_X(f(x), f(y)) \lt \epsilon$.
   3. Suppose that for every $\epsilon \gt 0$ there is some $r \gt 0$ so that whenever $x, y \in B_r(p) \cap E$, $d_X(f(x), f(y)) \lt \epsilon$. Show that if $X$ is complete, then $f$ has a limit at $p$.
   4. Show that part (C) may fail if $X$ is not assumed to be complete.

Here are some further problems to think about out of interest. You do not need to attempt them, nor should you submit them with the assignment. They are coloured by approximate difficulty: easy/medium/hard.

• Not definitions

  1. We say a sequence $(a_n)_n$ in a metric space $(M, d)$ is glomvergent if for every $\epsilon \gt 0$ there is $L \in M$ and $N \in \N$ so that for every $n \gt N$, $d(a_n, L) \lt \epsilon$.
     1. Are all sequences glomvergent?
     2. Are all convergent sequences glomvergent?
     3. Are all glomvergent sequences convergent?
     4. Does a glomvergent sequence exist?
  2. We say a sequence $(a_n)_n$ in a metric space $(M, d)$ is revergent if there is some $L \in M$ so that for every $N \in \N$ and every $n \gt N$, we have $d(a_n, L) \lt d(a_N, L)$.
     1. Are all sequences revergent?
     2. Are all convergent sequences revergent?
     3. Are all revergent sequences convergent?
     4. Does a revergent sequence exist?
  3. We say a sequence $(a_n)_n$ in a metric space $(M, d)$ is trivergent if there is some $L \in M$ and $N \in \N$ so that for every $n \gt N$, for every $\epsilon \gt 0$, we have $d(a_n, L) \lt \epsilon$.
     1. Are all sequences trivergent?
     2. Are all convergent sequences trivergent?
     3. Are all trivergent sequences convergent?
     4. Does a trivergent sequence exist?
  4. We say a sequence $(a_n)_n$ in a metric space $(M, d)$ is provergent if there is some $L \in M$ so that for every $\epsilon \gt 0$ and $N \in \N$, $n \gt N$ implies $d(a_n, L) \lt \epsilon$.
     1. Are all sequences provergent?
     2. Are all convergent sequences provergent?
     3. Are all provergent sequences convergent?
     4. Does a provergent sequence exist?
  5. We say a subset of a metric space is splopen if it contains all of its interior points.
     1. Are all subsets of metric spaces splopen?
     2. Are all open sets splopen?
     3. Are all splopen sets open?
     4. Does a splopen set exist?
  6. We say a subset of a metric space is fhtagn if it contains none of its limit points.
     1. Are all subsets of metric spaces fhtagn?
     2. Are all open sets fhtagn?
     3. Are all fhtagn sets open?
     4. Does a fhtagn set exist?
  7. We say a subset $U$ of a metric space $(M, d)$ is tropen if for every $x \in M$ and every $r \gt 0$, $B_r(x) \subseteq U$.
     1. Are all subsets of metric spaces tropen?
     2. Are all open sets tropen?
     3. Are all tropen sets open?
     4. Does a tropen set exist?
  8. We say a subset $U$ of a metric space $(M, d)$ is hopen if for every $x \in U$ and every $r \gt 0$, $B_r(x) \subseteq U$.
     1. Are all subsets of metric spaces hopen?
     2. Are all open sets hopen?
     3. Are all hopen sets open?
     4. Does a hopen set exist?
  9. We say a subset of a metric space is posed if it is not open.
     1. Are all subsets of metric spaces posed?
     2. Are all closed sets posed?
     3. Are all posed sets closed?
     4. Does a posed set exist?
  10. We say a subset of a metric space is clopen if it is both closed and open.
      1. Are all subsets of metric spaces clopen?
      2. Are all open sets clopen?
      3. Are all closed sets clopen?
      4. Does a clopen set exist?

• More on limits superior and inferior

  1. Repeat problem 2 for limits inferior, adjusting inequalities as appropriate.
  2. Determine what can be said about 2.D. when some of the limits involved are not finite. Find all cases involving infinite limits where the inequality can still be established.
  3. Given $E$ a subset of a metric space $M$ with a limit point $p$ and $f : E \to \R$, propose a definition of \[\limsup_{x \to p} f(x),\] and prove that your definition has several nice properties.
  4. Suppose that $(x_n)_n$ is a sequence in $\R$. Show that $(x_n)_n$ converges if and only if \[\limsup_{n\to\infty} x_n = \liminf_{x\to\infty} x_n\] and both are finite.

• Rudin's definitions of limits superior and inferior

  The goal of this problem is to show that our definition of $\limsup$ and $\liminf$ agrees with Rudin's.

  Suppose that $(x_n)_n$ is a sequence in $\R$. We say that $(x_n)_n$ diverges to infinity and write \[\limni x_n = \infty\] if for every $M \in \R$ there is some $N \in \N$ so that for all $n \gt N$, $x_n \gt M$. Similarly, we say that $(x_n)_n$ diverges to negative infinity and write \[\limni x_n = -\infty\] if for every $M \in \R$ there is some $N \in \N$ so that for all $n \gt N$, $x_n \lt M$.

  Once again, suppose $(x_n)_n$ is a sequence in $\R$. Let $E$ be the set of all subsequential limits of $(x_n)_n$, including (potentially) $\infty$ and $-\infty$. Define \[\rls_{n\to\infty} x_n = \sup(E) \hspace{1in}\text{and}\hspace{1in} \rli_{n\to\infty} x_n = \inf(E),\] where the $\sup$ of any set containing $\infty$ is understood to be $\infty$, and the $\inf$ of any set containing $-\infty$ is likewise understood to be $-\infty$, and $\sup\set{-\infty} = -\infty$, $\inf\set\infty = \infty$.

  1. Let $(x_n)_n$ and $E$ be as above. Prove that if the set of (real) subsequential limits of $(x_n)_n$ is not bounded above, then $\infty \in E$. (To rephrase: if $E\cap \R$ is not bounded above, then $\infty \in E$.)
  2. Prove that $E$ is non-empty.
  3. Show that $\rls_{n\to\infty} x_n = \infty$ if and only if $\limsup_{n\to\infty} x_n = \infty$.
  4. Show that $\rls_{n\to\infty} x_n = L \in \R$ if and only if $\limsup_{n\to\infty} x_n = L$.
  5. Show that $\rls_{n\to\infty} x_n = -\infty$ if and only if $\limsup_{n\to\infty} x_n = -\infty$.

• Pseudometrics

  (The hardest part of this problem is understanding the definitions.)

  A pseudometric on a set $M$ is a function $p : M\times M \to \R_{\geq0}$ such that:

  • for every $x \in M$, $p(x, x) = 0$;
  • for every $x, y \in M$, $p(x, y) = p(y, x)$; and
  • for every $x, y, z \in M$, $p(x, z) \leq p(x, y) + p(y, z)$.
  Note that we have not insisted that $p(x, y) = 0$ only if $y = x$.

  An equivalence relation on a set $X$ is a relation which is reflexive, symmetric, and transitive. That is, a relation $\sim$ such that:

  • for every $x \in X$, $x \sim x$;
  • for every $x, y \in X$, if $x \sim y$ then $y \sim x$; and
  • for every $x, y, z \in X$, if $x \sim y$ and $y \sim z$ then $x \sim z$.
  Given $x \in X$, the equivalence class of $x$ is the set $[x]_\sim = \set{y \in X \mid x \sim y}$. Notice that if $x \sim y$ then $[x]_\sim = [y]_\sim$. The set of equivalence classes is denoted \[{X/\!\sim} = \set{[x]_\sim \mid x \in X}.\]

  As an example, fix $k \in \N$ and define a relation $\sim$ on $\Z$ by $n \sim m$ if and only if $k$ divides $n - m$. Then, for example, $k \sim 15k \sim -2k$, and \[{\Z/\!\sim} = \set{[0]_\sim, [1]_\sim, \ldots, [k-1]_\sim}\] contains precisely $k$ distinct equivalence classes. It is possible to do arithmetic on these classes: we can define $[n]_\sim + [m]_\sim = [n+m]_\sim$ and $[n]_\sim[m]_\sim = [nm]_\sim$, and the definition does not depend on the choice of representatives $n \in [n]_\sim$, $m \in [m]_\sim$. This is the beginning of modular arithmetic.

  1. Prove that if $p$ is a pseudometric on $M$, then the relation $\sim$ defined by $x \sim y$ iff $p(x, y) = 0$ is an equivalence relation.
  2. Given $a, b \in M{/\!\sim}$ equivalence classes, let $x \in a$ and $y \in b$ and define $d(a, b) = p(x, y)$. Prove that $d$ does not depend on the choice of $x$ or $y$ here.
  3. Prove that $d$ is a metric on $M{/\!\sim}$.
  4. Let $p : \R^2\times\R^2 \to \R_{\geq 0}$ be defined by $p(x, y) = |x_1 + x_2 - y_1 - y_2|$. Show that $p$ is a pseudometric. Describe $\R^2{/\!\sim}$.
  5. Let $p : \R \times \R \to \R_{\geq 0}$ be defined by $p(x, y) = \inf\set{|x-y-k| \mid k \in \Z}$. Show that $p$ is a pseudometric. Describe $\R{/\!\sim}$.

• Families of pseudometrics

  Recall that in a metric space $(M, d)$, a sequence $(a_n)_n$ converges to a point $a$ if and only if for every open set $U \subseteq M$ with $a \in U$, there is some $N \in \N$ so that for every $n \gt N$, $a_n \in U$.

  Suppose that $M$ is a set, and let $\mathscr{F}$ be a set of pseudometrics on $M$. Let us call a subset $G \subseteq M$ open if for every $x \in M$, there are finitely many $p_1, \ldots, p_k \in \mathscr{F}$ and some $r \gt 0$ so that \[\set{y \in M \mid p_i(x, y) \lt r \text{ for each } i = 1, \ldots, k} \subseteq G.\]

  1. Prove that a set $G \subseteq M$ is open if and only if it is a union of finite intersections of sets of the form \[B_{p_i, r}(x) = \set{y \in M \mid p_i(x, y) \lt r}.\]

  We say a sequence $(a_n)_n$ in $M$ converges to $a \in M$ if for every open set $U \subseteq M$ with $a \in U$ there is some $N \in \N$ so that for every $n \gt N$, $a_n \in U$.

  2. Prove that every sequence in $M$ has at most one limit if and only if for every $x, y \in M$ there is some $p \in \mathscr{F}$ so that $p(x, y) \gt 0$.
  3. Let $\R^\R$ be the set of functions $\R \to \R$, and for each $x \in \R$, set \[p_x(f, g) = \abs{f(x) - g(x)}.\] Let $\mathscr{F} = \set{p_x \mid x \in \R}$. Show that a sequence of functions $(f_n)_n$ in $\R^\R$ converges to some $f \in \R^\R$ if and only if for each $x \in \R$, \[\lim_{n\to\infty} f_n(x) = f(x).\] (In this case, $(f_n)_n$ is said to converge pointwise to $f$.)

1. Distances and convergent sequences

   Let $(M, d)$ be a metric space.
   1. Let $(x_n)_n$ be a sequence in $M$, and $L \in M$. Prove that $(x_n)_n$ converges to $L$ if and only the sequence of real numbers $(d(x_n, L))_n$ converges to $0$.
   2. Suppose that $(a_k)_k$ and $(b_k)_k$ are sequences in $M$ which converge to $a$ and $b$ repsectively. Prove that \[\limni[{\color{red}k}] d(a_k, b_k) = d(a, b).\]

2. An interesting sequence of rational numbers

   Let $(q_n)_n$ be a sequence in $\Q_{\geq0}$ defined as follows: \[q_n = \begin{cases} \frac{a}{b} & \text{ if } n = 2^a3^b \text{ for some }a, b \in \N \\ 0 & \text{otherwise} \end{cases}.\] Show that for any $x \in \R_{\geq0}$ there is a subsequence of $(q_n)$ converging to $x$. (Hint: first show that every positive rational number occurs infinitely often in $(q_n)_n$, and recall that $\Q$ is dense in $\R$.)

3. Subsubsequences

   1. Suppose that $(M, d)$ is a metric space and $a \in M$. Suppose further that $(x_k)_k$ is a sequence in $M$ with the property that every subsequence of $(x_k)_k$ has a further subsequence which converges to $a$. Show that $(x_k)_k$ converges to $a$.
   2. Give an example of a sequence $(y_k)_k$ in some metric space, which does not converge but has the property that every subsequence has a further subsequence which does converge.

4. Square roots and convergent sequences

   1. Suppose that $(z_a)_a$ is a sequence in $\R_{\geq0}$ with \[\lim_{s\to\infty} z_s = z.\] Show that $(\sqrt{z_n})_n$ converges to $\sqrt z$. (Hint: it may be useful to treat the case $z = 0$ separately; it may also be useful to use the fact that $(\sqrt{z_t} - \sqrt{z})(\sqrt{z_t}+\sqrt{z}) = z_t - z$.)

   Let $a_1 = 1$ and for $n \in \N$, define $a_{n+1} = \sqrt{5+4a_n}$.

   2. Prove that for every $n \in \N$, we have $0 \leq a_n \leq a_{n+1} \leq 500!$.
   3. We will see later that Part A means $(a_n)_n$ must converge (monotonic sequences converge if and only if they are bounded). Assume that the limit of $(a_n)_n$ exists, and determine its value.

5. A compact set

   Suppose that $(a_n)_n$ is a sequence in a metric space $(M, d)$ which converges to a limit $a$. Prove that $\set{a_n\mid n \in \N} \cup \set a$ is compact.

Here are some further problems to think about out of interest. You do not need to attempt them, nor should you submit them with the assignment.

• Distances and convergent sequences

  Suppose that $(a_n)_n$, $(b_n)_n$ are sequences in a metric space $(M, d)$ so that \[\limni d(a_n, b_n) = 0.\] Prove that both sequences converge to the same limit, or provide a counterexample.

• An interesting sequence of rational numbers

  Let $(q_n)_n$ be the sequence from Question 2, and let $(a_n)_n$ be any sequence in $\Q$. Show that $(a_n)_n$ is a subsequence of $(q_n)_n$.

• Common subsequences

  Let $(M, d)$ be a compact metric space.
  1. Suppose that $(x_n)_n, (y_n)_n$ are sequences in $M$. Show that there is a common subsequence along which they both converge. (That is, show that there is an increasing sequence $(n_k)_k$ in $\N$ so that $(x_{n_k})_k$ and $(y_{n_k})_k$ both converge.)
  2. Suppose that $f_1, \ldots, f_T$ are sequences in $M$. (We might also write $(f_1(n))_n, (f_2(n))_n, \ldots, (f_T(n))_n$, but the double-indexing gets annoying.) Show that there is a common subsequence along which they all converge. (That is, show that there is an increasing function $n : \N \to \N$ so that $f_1\circ n, \ldots, f_T\circ n$ all converge; if we denote $n(k)$ by $n_k$, we might write $(f_1(n_k))_k, \ldots, (f_T(n_k))_k$ all converge.)
  3. Suppose that $(f_t)_t$ is a sequence of sequences in $M$ (so for each $t \in \N$, $f_t : \N \to M$). Show that there is a common subsequence along which they all converge. (That is, show that there is an increasing function $n : \N \to \N$ so that for all $t \in \N$, $f_t\circ n$ converges.)

• Topologies

  A topological space is a pair $(X, \mathscr{T})$ where $X$ is a set, and $\mathscr{T}$ is a collection of subsets of $X$ so that $\emptyset, X \in \mathscr{T}$, and $\mathscr{T}$ is closed under finite intersections and arbitrary unions (that is to say, if $G_1, \ldots, G_n \in \mathscr{T}$ then $G_1\cap\cdots\cap G_n \in \mathscr{T}$, and if $(G_\alpha)_\alpha$ is a collection of elements of $\mathscr{T}$ then $\bigcup_\alpha G_\alpha \in \mathscr{T}$). The elements of $\mathscr{T}$ are said to be open, and a set $F \subseteq X$ is said to be closed if $F^c \in \mathscr{T}$. We refer to $\mathscr{T}$ as a topology on $X$.

  Notice that if $(M, d)$ is a metric space, then $\mathscr{T}_d = \set{U \subseteq M \mid U \text{ is open with respect to } d}$ is a topology on $M$. We say that the topology $\mathscr{T}_d$ is induced by the metric $d$.

  A topological space $(X, \mathscr{T})$ is said to be metrizable if there is a metric on $X$ which induces $\mathscr{T}$. Note that this metric need not be unique!

  A sequence $(x_n)_n$ in a topological space $(X, \mathscr{T})$ is said to converge to $x \in X$ if for every open set $G \in \mathscr{T}$ with $x \in G$, there are only finitely many $n \in \N$ for which $x_n \notin G$. (Remember that we proved this was equivalent to our definition of convergence in metric spaces.)

  1. Let $X = \set{0, 1}$ and $\mathscr{T} = \set{\emptyset, X}$. Is $(X, \mathscr{T})$ a topological space? Is it metrizable?
  2. Are limits of sequences in topological spaces unique when they exist? Or can a sequence converge to more than one distinct point?
  3. Give an example of a topological space and two different metrics which give rise to the same topology.
  4. Formulate a necessary and sufficient condition for two metrics inducing the same topology.
  5. Suppose that $\mathscr{T}_1$ and $\mathscr{T}_2$ are topologies on a set $X$ with the property that any sequence in $X$ converges with respect to $\mathscr{T}_1$ if and only if it does with respect to $\mathscr{T}_2$. Must $\mathscr{T}_1 = \mathscr{T}_2$?

1. Intersections of non-compact sets can be badly behaved

   We showed in lecture that if $\set{K_\alpha}$ is a collection of compact subsets of $M$ so that the interesction of every finite subcollection is non-empty, then the intersection of all the $K_\alpha$ is non-empty.

   1. Show that this may fail if the $K_\alpha$ are merely assumed to be closed.
   2. Show that this may fail if the $K_\alpha$ are merely assumed to be bounded.
   3. Suppose that $\set{K_\alpha \mid \alpha\in\mathcal{I}}$ is a collection of compact subsets of $M$ so that the intersection $K_\alpha\cap K_\beta$ is non-empty for each $\alpha, \beta \in \mathcal{I}$. Show that it may nonetheless be the case that \[\bigcap_\alpha K_\alpha = \emptyset.\]

2. Compact sets are bounded

   Prove that compact sets are bounded.

3. Open sets in the plane

   Recall that $d_1(\mathbf{x}, \mathbf y) = \abs{x_1-y_1}+\abs{x_2-y_2}$, $d_2(\mathbf{x}, \mathbf{y}) = \sqrt{\abs{x_1-y_1}^2 + \abs{x_2-y_2}^2}$, and $d_\infty(\mathbf x, \mathbf y) = \max(\abs{x_1-y_1}, \abs{x_2-y_2})$ are all metrics on $\R^2$.

   Let $r \gt 0$ and $\mathbf x \in \R^2$.

   1. Prove that there is some $s \gt 0$ so that \[B_s^{d_1}(\mathbf x) \subseteq B_r^{d_2}(\mathbf x).\]
   2. Prove that there is some $s \gt 0$ so that \[B_s^{d_2}(\mathbf x) \subseteq B_r^{d_\infty}(\mathbf x).\]
   3. Prove that there is some $s \gt 0$ so that \[B_s^{d_\infty}(\mathbf x) \subseteq B_r^{d_1}(\mathbf x).\]
   4. Prove that if $G \subseteq \R^2$ is open with respect to any of the three metrics, then it is open with respect to all of them.

   (Note that there is no reason to find the best $s$ for a given $r$, just any one that works. It may be interesting to think about what the best is, though. Consider also what this says about drawing diamonds inside circles inside squares.)

4. Products of compact sets

   Suppose that $(X_1, d_1), (X_2, d_2)$ are compact metric spaces. Let $K = X_1 \times X_2$ be equipped with the metric $$d\paren{(x_1, x_2), (y_1, y_2)} = \sqrt{d_1(x_1, y_1)^2 + d_2(x_2, y_2)^2}.$$
   1. Suppose $G \subseteq K$ is open and $(x_1, x_2) \in G$. Show that for some $r \gt 0$, $$B_r^{X_1}(x_1) \times B_r^{X_2}(x_2) = \set{(y_1, y_2) \in K \middle\vert d_i(x_i, y_i) \lt r \text{ for } i = 1, 2} \subseteq G.$$
   2. Let $\mathscr{U}$ be an open cover of $K$, fix $x \in X_1$, and write $$\mathscr{U}_x = \set{ G \subseteq X_2 \middle\vert \begin{aligned} G \text{ is open, and } \exists r \gt 0 \text{ and } \\ E \in \mathscr{U} \text{ so that } B_r^{X_1}(x) \times G \subseteq E \end{aligned} }.$$ Prove that $\mathscr{U}_x$ is an open cover of $X_2$.
   3. Prove that there is $r_x \gt 0$ and a finite set $$\mathscr{V}_x \subseteq \mathscr{U}$$ which is an open cover of $B_{r_x}(x) \times X_2 \subseteq K$.
   4. Prove that $K$ is compact. (Hint: $\set{B_{r_x}(x) \mid x \in X_1}$ covers $X_1$.)
   5. Prove that if $(X_1, d_1), (X_2, d_2), \ldots, (X_n, d_n)$ are compact metric spaces, then so is $X_1 \times X_2 \times \cdots \times X_n$ when equipped with the metric $$d(\mathbf{x}, \mathbf{y}) = \sqrt{\sum_{i=1}^n d_i(x_i, y_i)^2},$$ where $\mathbf{x} = (x_1, \ldots, x_n)$ and $\mathbf{y} = (y_1, \ldots, y_n)$.

Here are some further problems to think about out of interest. You do not need to attempt them, nor should you submit them with the assignment.

• More compact products

  1. Repeat question 4, but using the metric $d_\infty(\mathbf{x}, \mathbf{y}) = \max\paren{d_i(x_i, y_i)}$ instead.
  2. Suppose that $\mathcal{I}$ is an infinite set, and that for each $i \in \mathcal{I}$, $(X_i, d_i)$ is a compact metric space with the property that for all $x, y \in X_i$, $d_i(x, y) \leq 1$. Let $$X = \prod_{i\in\mathcal{I}} X_i := \set{ f : \mathcal{I} \to \bigcup_{i\in\mathcal{I}} X_i \,\middle\vert\, \forall\,i \in \mathcal{I}, f(i) \in X_i }.$$ Then $X$ is a metric space when equipped with the metric $$d_\infty(f, g) = \sup\set{d_i(f(i), g(i)) \mid i \in \mathcal{I}}.$$ Prove that $X$ is compact, or show by example that this need not be the case.
  3. Suppose that for each $i \in \N$, $(X_i, d_i)$ is a compact metric space. Designate a fixed "base point" $0_i \in X_i$ for each $i$, and let $$Y = \set{ f : \N \to \bigcup_{i\in\N} X_i \,\middle\vert\, \forall\,i\in\N, f(i) \in X_i \text{ and } \sum_{i=1}^\infty d_i(f(i), 0_i)^2 \lt \infty}.$$ Then $Y$ is a metric space when equipped with the metric $$d(f, g) = \sqrt{\sum_{i=1}^\infty d_i(f(i), g(i))^2}.$$ Prove that $Y$ is compact, or show by example that this need not be the case.

• Intersections of non-compact sets can be badly behaved

  Find an example that shows the statement in problem 1 may fail if the $K_\alpha$ are closed and bounded, but not necessarily compact. (Hint: for this, you will need to work in a metric space other than $\R^n$.)

• Open sets in higher-dimensional Euclidean spaces

  1. Define $d_1, d_2, d_\infty$ on $\R^n$ analogously to how they are defined on $\R^2$. Prove that if $G \subseteq \R^n$ is open with respect to any of the three metrics, then it is open with respect to all of them.
  2. Let $p \gt 1$ and define the metric $d_p$ on $\R^n$ by $d_p(\mathbf x, \mathbf y) = \paren{\sum_{i=1}^n \abs{x_i-y_i}^p}^{1/p}$. Prove that $G \subseteq \R^n$ is open with respect to $d_p$ if and only if it is open with respect to $d_1$.

  (Note that there is no reason to find the best $s \gt 0$ for a given $r$, just any one that works. It may be interesting to think about what the best is, though. Consider what this says about drawing diamonds inside circles inside squares.)

• Unbounded sets and limit points

  Let $(M, d)$ be a metric space, and suppose that $E \subseteq M$ is not bounded. Prove that $E$ has an infinite subset with no limit points in $M$. Use this to show that compact sets are bounded.

  Note that this gives another way to prove that compact sets are bounded.

1. Open sets are unions of balls

   Show that if $U \subseteq M$ is an open set, then there is a set of balls whose union is $U$.

2. Interiors

   Let $(M, d)$ be a metric space. Recall that the interior of a subset $E \subseteq M$ is defined as \[E^{\intr} = \set{x \in M \mid \exists r \gt 0, B_r(x) \subseteq E}.\]
   1. Show that the interior of any set is open.
   2. Show that $E$ is open if and only if $E = E^\intr$.
   3. Prove that if $G \subseteq E$ is open, then $G \subseteq E^\intr$.
   4. Prove that the complement of the interior of $E$ is the closure of the complement of $E$. That is, show that \[\paren{E^\intr}^c = \overline{E^c}.\]
   5. Prove or provide a counterexample to the following claims:
      1. $\overline{E} = \overline{E^\intr}$.
      2. $E^{\intr} = \paren{\overline{E}}^\intr$.

3. Relatively open sets

   Suppose that $(M, d)$ is a metric space, and $X \subseteq M$. Recall that $X$ is therefore a metric space with metric inherited from $M$: for $x, y \in X$, we have $d_X(x, y) = d(x, y)$. However, the open balls in $X$ are different from those in $M$. We emphasize this by writing $B_r^X(x)$ or $B_r^M(x)$ to indicate where we are taking the ball. Explicitly, if $x \in X$, \[B_r^X(x) = \set{y \in X \mid d_X(x, y) \lt r}, \qquad\qquad\text{while}\qquad\qquad B_r^M(x) = \set{y \in M \mid d(x, y) \lt r}.\] It also follows that we have different notions of "open" between $X$ and $M$: if $G \subseteq X$, we say $G$ is open relative to $X$ if for every $x \in G$ there is $r \gt 0$ so that $B_r^X(x) \subseteq G$.
   1. Show that if $U \subseteq M$ is open relative to $M$, then $U \cap X$ is open relative to $X$. (Hint: notice that for $x \in X$, $B_r^X(x) = B_r^M(x) \cap X$.)
   2. Show that if $G \subseteq X$ is open relative to $X$, then there is some $U \subseteq M$ open relative to $M$ so that $G = U \cap X$. (Hint: use problem 1.)
   3. Give an explicit example of a metric space $M$ and sets $G \subseteq X \subseteq M$ so that $G$ is open relative to $X$ but not relative to $M$. (Hint: take $X$ to be a subset of $M$ which is not open.)
   4. Suppose $K \subseteq X$. Prove that $K$ is compact relative to $X$ if and only if it is compact relative to $M$. (Hint: use parts A and B to convert open covers relative to $M$ to open covers relative to $X$ and vice versa.)

4. Limit points

   1. Determine the limit points of the set $S = \set{3-\frac3{m}\mid m \in \N} \cup [0,2] \subset \R$.
   Let $(M, d)$ be a metric space, $E \subseteq M$, and $E'$ be the set of limit points of $E$.
   2. Show that $x \in E'$ if and only if every open set containing $x$ contains infinitely many elements of $E$.
   3. Prove that $x \in \overline{E}$ if and only if for every $r \gt 0$, $B_r(x) \cap E \neq \emptyset$.

5. Compact sets in the discrete metric

   Let $M$ be a set, and $d$ the discrete metric on $M$, which is given by \[d(x, y) = \begin{cases}0 & \text{ if } x = y \\ 1 & \text{ otherwise}\end{cases}.\] Which subsets of $M$ are compact?

Here are some further problems to think about out of interest. You do not need to attempt them, nor should you submit them with the assignment.

• Warm up

  Determine if each of the following statements is true or false.
  1. Every unbounded subset of $\R$ is infinite.
  2. Every infinite subset of $\R$ is unbounded.
  3. If $E$ is a bounded subset of a metric space $X$, then every subset of $E$ is also bounded.
  4. If $E$ is an unbounded subset of a metric space $X$, then every subset of $E$ is also unbounded.
  5. $\Q$ is a dense subset of $\R$.
  6. $\R$ is a dense subset of $\C$, where $\C$ is given the metric $d(a+ib, x+iy) = \sqrt{(a-x)^2+(b-y)^2}$.
  7. If $E$ is a subset of $X$, then $(E^c)^c = E$.
  8. If $E$ is an open subset of a metric space $X$, then $E^c$ is closed.
  9. If $E$ is a subset of a metric space which is not open, then it is closed.
  10. If $(M, d)$ is a metric space, then $M$ is open.
  11. If $(M, d)$ is a metric space, then $M$ is closed.
  12. If $(M, d)$ is a metric space, then $M$ is bounded.
  13. If $(M, d)$ is a metric space, then $M$ is unbounded.
  14. If $E$ is a bounded subset of a metric space, then it is either open or closed.
  15. Any finite subset of a metric space is closed.
  16. Any finite subset of a metric space is open.
  17. Any finite subset of a metric space is compact.
  18. No finite non-empty subset of a metric space is closed.
  19. No finite non-empty subset of a metric space is open.
  20. No finite non-empty subset of a metric space is compact.

• Limit points, II

  Let $(M, d)$ be a metric space, $E \subseteq M$, and $E'$ be the set of limit points of $E$.
  1. Show by example that $E$ and $E'$ need not have the same limit points; that is, show that $E'$ and $(E')'$ may not be equal.
  2. Prove or provide a counterexample to the claim that $(E')' \subseteq E'$.
  3. Prove that $E'$ is closed.

• Distances and compact sets

  (This problem can be solved with what we know now, but will be easier with more tools at our command. It may show up on a later assignment.)
  1. Let $K$ be a non-empty compact subset of a metric space $(M, d)$. For $x \in M$, define \[d(x, K) = \inf\set{d(x, y) \mid y \in K}.\] Show that there is a point $y\in K$ so that $d(x, K) = d(x, y)$. Is this point unique?
  2. Let $(M, d)$ be a metric space. Let $\mathscr{K} := \set{K \subseteq M \mid K \text{ is compact and non-empty}}$. Define \begin{align*} d_H : \mathscr{K}\times\mathscr{K} &\to \R_{\geq 0} \\ (K, F) &\mapsto \max\paren{\sup\set{d(x, K) \mid x \in F}, \sup\set{d(y, F) \mid y \in K}}. \end{align*} Show that $(\mathscr{K}, d_H)$ is a metric space.

• Nepo functions

  Let us say that a function $f : M_1 \to M_2$ between metric spaces $(M_1, d_1)$ and $(M_2, d_2)$ is nepo if the preimage of every open subset of $M_2$ is open in $M_1$. That is, if all sets of the form \[f^{-1}(U) = \set{x \in M_1 \mid f(x) \in U}\] where $U \subseteq M_2$ is open are themselves open, as subsets of $M_1$.
  1. Suppose that $K \subseteq M_1$ is compact and $f : M_1 \to M_2$ is nepo. Show that $f(K) = \set{f(x) \mid x \in K} \subseteq M_2$ is compact.

  2. Suppose that $M_1 \subseteq M_2$ and moreover that $d_1(x, y) = d_2(x, y)$ for all $x, y \in M_1$; that is, $M_1$ is a sub-metric space of $M_2$. Show that the inclusion function $\iota : M_1 \to M_2$ given by $\iota(x) = x$ is nepo.

     (Note that the metric space in which a set is considered is important here! The goal is to show that open subsets of $M_2$ have preimages in $M_1$ which are open as subsets of $M_1$. You may find it useful to first show that $\iota^{-1}(U) = U \cap M_2$.)

• Compactness in the rational numbers

  Let $S = \set{q \in \Q \mid q^2 \lt 2}$. Show that $S$ is closed and bounded as a subset of the metric space $\Q$, but is not compact. Is $S$ open in $\Q$? (Hint: use problem 4, and the fact that $\sqrt2 \notin \Q$.)

• Closures of balls versus closed balls

  1. Let $(M, d)$ be a metric space, $x\in M$, and $r \gt 0$. Show that \[\overline{B_r(x)} \subseteq \set{y \in M \mid d(x, y) \leq r}.\]
  2. Give an example to show that this inclusion may be proper. (Hint: consider $\Z$ as a metric space (although there are also many other examples).)

• Open double covers

  Let $(M, d)$ be a metric space. Call a collection $\mathscr{U}$ of open sets an open double cover of $E \subseteq M$ if every point $x \in E$ is contained in at least two elements of $\mathscr{U}$.
  1. Show that if $K \subseteq M$ is compact, then every open double cover of $K$ has a finite open double subcover. (That is, there is a finite subset of the original open double cover which remains an open double cover.)
  2. Is it true that if $K \subseteq M$ is such that every open double cover has a finite open double subcover, then $K$ is compact?

0. Warm-up

   Prove the following useful fact, which you may use later on this assignment. You do not need to submit this problem.

   Suppose that $M$ is a set and $f : M \times M \to \R_{\geq0}$ is such that for all $x, y \in M$, $f(x, y) = 0$ if and only if $x = y$, and $f(x, y) = f(y, x)$. Prove that if $x, y \in M$, we have \begin{align*} f(x, x) &\leq f(x, y) + f(y, x) \\ f(x, y) &\leq f(x, y) + f(y, y) \\ f(x, y) &\leq f(x, x) + f(x, y) \\ f(x, x) &\leq f(x, x) + f(x, x). \end{align*} Consequently, to show $f$ is a metric, it suffices to check that the triangle inequality holds for triples of distinct points.

1. Metrics?

   For each of the following, determine (with proof) if the given function is a metric on the given set.
   1. $S_A = \R$, $d_A(x, y) = \sqrt{\abs{x-y}}$
   2. $S_B = \Z$, $d_B(j, k) = \abs{j-k}^2$
   3. $S_C = \R$, $d_C(x, y) = \abs{x^5-y^5}$
   4. $S_D = \R$, $d_D(x, y) = \abs{x^4-y^4}$
   5. $S_E = \R$, $d_E(x, y) = \abs{x^5-y^3}$
   6. $S_F = \R$, $d_F(x, y) = \begin{cases}\abs{x - y} & \text{ if } xy \neq 0\\ 0 & \text{ if } x = y = 0 \\ 1 + \abs{x-y} & \text{ otherwise}\end{cases}.$
   7. Let $S_G = \set{f : \N \to \set{0, 1}}$ be the set of functions from $\N$ to $\set{0,1}$; note that an element of $S_G$ can be thought of as an infinitely long binary string. (E.g., the function $f(n)$ which is $1$ if $n \leq 3$ and $0$ otherwise corresponds to the string $11100000...$; the function $g(n)$ which is $0$ if $n$ is even and $1$ if $n$ is odd corresponds to the string $1010101010101...$.) If $f, g \in S_G$ are not equal, let $n_0 = \min\set{n \in \N \mid f(n) \neq g(n)}$, and set $d_G(f, g) = 2^{-n_0}$; if $f = g$, set $d_G(f, g) = 0$ instead.

2. Pullbacks of metrics along maps

   Recall that a function $f : X \to M$ is said to be injective or one-to-one if for every $x, y \in X$, $f(x) = f(y)$ implies $x = y$.

   Suppose $(M, d)$ is a metric space, $X$ is a set, and $f : X \to M$. Define \begin{align*} d_f : X\times X &\longrightarrow \R_{\geq0} \\ (x, y) &\longmapsto d(f(x), f(y)). \end{align*} Prove that $d_f$ is a metric on $X$ if and only if $f$ is injective.

3. Building product metrics

   Suppose that $S$ and $T$ are metric spaces with metrics $d_S$ and $d_T$ respectively. Recall $S \times T = \set{(s, t) : s \in S, t \in T}$.
   1. Take \begin{align*} d_1 : (S\times T) \times (S\times T) &\to \R_{\geq0} \\ ((s_1, t_1), (s_2, t_2)) &\mapsto d_S(s_1, s_2) + d_T(t_1, t_2). \end{align*} Show that $d_1$ is a metric on $S\times T$.
   2. Take \begin{align*} d_\infty : (S\times T) \times (S\times T) &\to \R_{\geq0} \\ ((s_1, t_1), (s_2, t_2)) &\mapsto \max\set{d_S(s_1, s_2), d_T(t_1, t_2)}. \end{align*} Show that $d_\infty$ is a metric on $S\times T$.

4. Some basic open/closed set problems

   Suppose $(M, d)$ is a metric space.
   1. Suppose $x \in M$. Prove that $\set{x}$ is closed.
   2. Suppose $x, y \in M$ are such that every open set containing $x$ also contains $y$. Prove that $x = y$.

5. De Morgan's Laws

   Let $M$ be a set. Given a subset $E \subseteq M$, we denote by $E^c$ the complement of $E$ in $M$: $E^c = M \setminus E = \set{x \in M \mid x \notin E}$. Note that this notation only makes sense when $M$ is clear.

   Verify the following identities, where $(E_\alpha)$ is a collection of subsets of $M$.

   1. \[\paren{\bigcap_{\alpha} E_\alpha}^c = \bigcup_\alpha E_\alpha^c\]
   2. \[\paren{\bigcup_{\alpha} E_\alpha}^c = \bigcap_\alpha E_\alpha^c\]

Here are some further problems to think about out of interest. You do not need to attempt them, nor should you submit them with the assignment.

• There are no interesting "anti-metrics"

  Let $S$ be a set. Call a function $d : S\times S \to \R_{\geq0}$ an anti-metric if for every $x, y, z \in S$:

  • $d(x, y) = 0$ if and only if $x = y$,
  • $d(x, y) = d(y, x)$, and
  • $d(x, z) \geq d(x, y) + d(y, z)$.
  Notice that an anti-metric is like a metric, but satisfies the opposite of the triangle inequality.

  Show that if $d$ is an anti-metric on $S$, then $S$ contains at most one element.

• Some more practice problems

  1. Show that if $M = \R^2$ with the usual metric and $E\subseteq \R^2$ is open, then $E \subseteq E'$, the set of limit points of $E$.
  2. Give an example of a metric space $(M, d)$ and an open set $E \subseteq M$ so that $E \nsubseteq E'$, the set of limit points of $E$.

• Embeddings

  Suppose $M$ and $X$ are metric spaces. We say $X$ embeds into $M$ (and write $X \hookrightarrow M$) if there is a function $f : X \to M$ which preserves distance: that is, if for all $x, y \in X$ we have $d_X(x, y) = d_M(f(x), f(y))$. Such a function $f$ is said to be an isometry. Notice that the function $f$ in Problem 2 is an isometry from $(X, d_f)$ to $(M, d)$. Also notice that an isometry is necessarily injective.

  1. Show that there is a finite metric space that does not embed into $\R$.
  2. Show that there is a finite metric space that does not embed into $\R^2$.
  3. Show that there is a finite metric space that does not embed into $\R^n$ for any $n \in \N$.
  4. Show that for any $n \in \N$, $\R^n \hookrightarrow \R^{n+1}$.
  5. Show that if $n, k \in \N$ then $\R^n \hookrightarrow \R^k$ if and only if $n \leq k$.

• Exponentials

  Fix $\beta \geq 1$.
  1. Show that if $a,c \in \Z$ and $b, d \in \N$ with $\frac ab = \frac cd$, then $$\paren{\beta^{1/b}}^a = \paren{\beta^{1/d}}^c.$$ We can therefore define $\beta^r$ consistently for any rational $r \in \Q$ (i.e., in a way that does not depend on the representation of $r$).
  2. Show that for any $p, q \in \Q$, $\beta^{p+q} = \beta^p\beta^q$.
  3. For $q \in \Q$, show that $$\beta^q = \sup\set{\beta^p : p \in \Q, p \leq q}.$$ (This requires showing both that the supremum exists, and that the quantites are equal.) We now define $\beta^x = \sup\set{\beta^p : p \in \Q, p \leq x}$ for $x \in \R$, and note that this agrees with our earlier definition of $\beta^q$ for $q \in \Q$; we also define $\gamma^x = \paren{\frac1\gamma}^{-x}$ for $0 \lt \gamma \lt 1$.
  4. Show that for any $x \in \R$, $\sup\set{\beta^p : p \in \Q, p \leq x} = \sup\set{\beta^p : p \in \Q, p \lt x}$. (This provides extra wiggle room will be useful in the next part.)
  5. Show that for all $x, y \in \R$, $\beta^{x+y} = \beta^x\beta^y$.
  6. Verify that this formal definition of exponential satisfies all the properties you're used to. For example:
     1. $\beta^{xy} = (\beta^{x})^y$;
     2. If $0 \lt \alpha \lt \gamma$ then $\alpha^x \lt \gamma^x$ for $x \gt 0$ and $\alpha^x \gt \gamma^x$ if $x \lt 0$.

• More metrics?

  1. Suppose that $S$ and $T$ are metric spaces with metrics $d_S$ and $d_T$ respectively. Take \begin{align*} d_2 : (S\times T) \times (S\times T) &\to \R_{\geq0} \\ ((s_1, t_1), (s_2, t_2)) &\mapsto \sqrt{d_S(s_1, s_2)^2 + d_T(t_1, t_2)^2}. \end{align*} Is $d_2$ a metric?
  2. Let $\mathcal{P} = \set{a_0 + a_1x + \cdots + a_nx^n \mid n \in \N_0, a_0, \ldots, a_n \in \R}$ be the set of polynomials with real coefficients. Define a map $d_\infty : \mathcal{P}\times\mathcal{P} \to \R$ by \[d_\infty(f, g) = \sup\set{\abs{f(x) - g(x)} : 0 \leq x \leq 1}.\] Is $d_\infty$ a metric?
  3. Suppose $S$ and $T$ are metric spaces with metrics $d_S$ and $d_T$ respectively. For which $p \in \R$ is \begin{align*} d_p : (S\times T)\times(S\times T) &\to \R_{\geq 0}\\ ((s_1, t_1), (s_2, t_2)) &\mapsto \paren{d_S(s_1, s_2)^p + d_T(t_1, t_2)^p}^{\frac1p} \end{align*} always a metric, no matter what $S$ and $T$ are? For which is it never a metric? For which does it depend on $S$ and $T$?
  4. Let $G = (V, E)$ be a graph. Define a metric on $V$ by setting $d_G(v, w)$ to be the length of the shortest path in $G$ from $v$ to $w$. Is $d_G$ a metric? If not, is there a simple way to change it to make it one?

• Some interesting questions entirely unrelated to the course

  Using only technology available 2000 years ago, how would you...
  1. ...measure the radius of the Earth in kilometers/miles/"human scale" units?
  2. ...measure the radius of the moon in Earth-radii?
  3. ...measure the speed of the moon in Earth-radii per second?
  4. ...measure the distance from the Earth to the moon?
  5. ...measure the radius of the Sun, in Earth-radii?
  There's a lot of fascinating reading about this on Wikipedia (see, e.g, On the Sizes and Distances and Astronomical unit: History). See also The Cosmic Distance Ladder, a talk by Terry Tao. (Here's another instance of the talk, but with slightly worse audio quality.)

1. Some useful facts

   Prove the following useful facts.
   1. If $T \subseteq \Z$ is non-empty and bounded above in $\R$, then $\sup T \in T$. (In particular, $\sup T \in \Z$.)

   2. Suppose that $\emptyset \subsetneq E_1 \subseteq E_2 \subseteq \R$. If $E_2$ is bounded above, then $\sup E_1$ exists and $\sup E_1 \leq \sup E_2$.

      (Note: the symbol "$\subsetneq$" means "is a proper subset of", so $A \subsetneq B$ means $A \subseteq B$ and $A \neq B$. Thus $\emptyset \subsetneq E_1$ means "$E_1$ is non-empty". In contrast, the symbol $\nsubseteq$ means "is not a subset of". The symbol "$\subset$" is inconsistently used, usually meaning $\subsetneq$ but sometimes meaning $\subseteq$, depending on the author.)

   3. If $x, y \in \R$ with $0 \leq x \leq y$ then $x^2 \leq y^2$. Moreover, assuming that $x^{1/2}, y^{1/2}$ exist in $\R$ with $0 \leq x^{1/2}, y^{1/2}$, prove that $x^{1/2}\leq y^{1/2}$.

      (We will soon see in lecture that $x^{1/2}$ and $y^{1/2}$ do indeed exist in $\R$, but we aren't there yet.)

   4. If $S$ is an ordered set, $E, F \subseteq S$ have suprema in $S$, and they have the property that for every $e \in E$ there is $f \in F$ with $e \preceq f$, then $\sup E \preceq \sup F$.

2. Some facts about suprema

   1. Let $(S, \preceq)$ be an ordered set, and $t \in S$. Prove that $\sup\set{s \in S \mid s \preceq t} = t$.
   2. Show by example that Part A need not hold if the $\preceq$ in the definition of the set is replaced by $\prec$.
   3. Show that, nonetheless, if $x \in \R$ then $$\sup\set{q \in \Q \mid q \lt x} = x.$$ (Note that, as a result, every real number is the supremum of some set of rational numbers.)

3. Suprema in the rationals are suprema in the reals

   1. Suppose that $E \subset \Q$ has least upper bound $t \in \Q$. Show that $t$ is also the least upper bound of $E \subset \R$.
   2. Next week we will prove that an irrational number exists. Use this to prove that $\Q$ does not have the Least Upper Bound Property.

4. Properties of irrational numbers

   1. Prove that if $q \in \Q$ and $t \in \R\setminus \Q$, then $q + t \in \R\setminus\Q$.
   2. Prove that if $q \in \Q$ and $t \in \R\setminus \Q$, then $qt \in \set{0}\cup(\R\setminus\Q)$.
   3. Prove that if $x, y \in \R$ with $x \lt y$, there is some $t \in \R\setminus\Q$ with $x \lt t \lt y$. To do so, you may use the fact that an irrational number exists; if it is convenient, you may use in particular the fact that $\sqrt2\in\R$.

Here are some further problems to think about out of interest. You do not need to attempt them, nor should you submit them with the assignment. They are coloured by approximate difficulty: easy/medium/hard.

• Variations on a theme from lecture

  1. Suppose that $(\F, \leq)$ is an ordered field, $E \subseteq \F$, and $\alpha \in \F$. Prove that $t \in \F$ is a lower bound for $E$ if and only if $t + \alpha$ is a lower bound for $E + \alpha$. Consequently, prove that $\inf E$ exists if and only if $\inf(E+\alpha)$ exists, in which case $(\inf E)+\alpha = \inf(E+\alpha)$.
  2. Formulate and prove a similar statement about upper bounds and suprema of sets, when multiplied by some $t \in \F$ with $t \gt 0$.
  3. Formulate and prove a similar statement when $t \lt 0$.
  4. Prove that $\Z$ is not bounded below in $\R$.
  5. Prove that $\N$ is not bounded above in $\R$.

• Ordered fields

  1. Prove that an ordered field cannot be bounded above.
  2. Prove that in any ordered field $(\F, \leq)$, $\inf\set{x \in \F \mid x \gt 0} = 0$.
  3. Prove that if $\F$ is an ordered field and $N \in \N$, $$\sum_{i=1}^N 1_\F = \underbrace{1_\F + 1_\F + \ldots + 1_\F}_{N \text{ times}} \neq 0.$$ (This is not true about fields in general. In fact, for any prime number $p$, there are fields within which $$\sum_{i=1}^p 1_\F = 0.$$ Such fields are said to be "of characteristic $p$". A field where $\sum_{i=1}^N 1_\F \neq 0$ for all $N \in \N$ is said to be "of characteristic $0$"; so $\R$, $\Q$, and $\C$ are all of characteristic $0$. See, e.g., Wikipedia for more information.)
  4. Prove that an ordered field cannot be finite.

1. An example order

   Suppose that $\mathcal{N}$ is a set with the following properties:
   1. $\emptyset \in \mathcal{N}$;
   2. if $n \in \mathcal{N}$, then $\sigma(n) := n \cup \set{n} \in \mathcal{N}$; and
   3. for any statement $P(x)$ so that $P(\emptyset)$ is true and so that for all $n \in \mathcal{N}$, $P(n)$ implies $P(\sigma(n))$, we have $P(n)$ is true for all $n \in \mathcal{N}$.
   Some elements of $\mathcal{N}$ are $$\emptyset, \set{\emptyset}, \big\{\emptyset, \set{\emptyset}\big\}, \Big\{\emptyset, \set{\emptyset}, \big\{\emptyset, \set{\emptyset}\big\}\Big\}, \bigg\{\emptyset, \set{\emptyset}, \big\{\emptyset, \set{\emptyset}\big\}, \Big\{\emptyset, \set{\emptyset}, \big\{\emptyset, \set{\emptyset}\big\}\Big\}\bigg\}, ... $$ Let $\preceq$ be a relation defined on $\mathcal{N}$ by, for $n, m \in \mathcal{N}$, setting $n \preceq m$ if and only if $n \subseteq m$ and either $n = m$ or $n \in m$. (Let us also write $n \prec m$ if $n \preceq m$ and $n \neq m$; note that this means $n \subseteq m$ and $n \in m$.) Notice that for all $n \in \mathcal{N}$, $n \prec \sigma(n)$.
   1. Prove that $\preceq$ is transitive and antisymmetric. You may assume that $\subseteq$ has these properties.
   2. Given $n \in \mathcal{N}$, let $$A(n) = \set{t \in \mathcal{N} \mid t \prec n}.$$ Prove that for all $n \in \mathcal{N}$, $A(n) = n$.
   3. Prove that $\preceq$ is total, and so an order on $\mathcal{N}$.
      Click for a hint.

      First prove that if $n \prec t$ then $\sigma(n) \preceq t$.

2. Properties of ordered sets

   Suppose $S$ is an ordered set with ordering $\preceq$.
   1. Prove that if $E \subseteq S$, then $\inf E$ is unique if it exists.
   2. Prove that if $e \in S$ is an upper bound for $E \subseteq S$ and $e \in E$, then $e = \sup E$.
   3. Suppose that $E \subseteq S$ is non-empty, that $x\in S$ is a lower bound for $E$, and that $y \in S$ is an upper bound for $E$. Prove that $x \preceq y$. Must it be true that $x \prec y$?
      (A word on notation: the statement "$E \subseteq S$ is non-empty" here means "$E$ is non-empty and a subset of $S$"; it does not mean "$E$ is a subset of $S$ and $S$ is non-empty".)
   4. Prove that if $E \subseteq S$ is finite and non-empty, then $\sup E$ exists in $S$ (hint: use induction). As a result, show that if $S$ is finite then it has the Least Upper Bound Property.
   5. Show that $\emptyset$ has a greatest lower bound if and only if $S$ has a maximum element. (An element $y \in S$ is the maximum of $S$ if $x \preceq y$ for every $x \in S$.)

3. Suprema depend on the ordered set

   1. Give an example of sets $E \subseteq S_1 \subseteq S_2 \subseteq S_3 \subseteq \Q$ such that $E$ has a least upper bound in $S_1$ and in $S_3$, but not in $S_2$.
   2. Prove that for any example with the properties above (not only the one you happened to write down), the least upper bound of $E$ in $S_1$ must be different from the least upper bound of $E$ in $S_3$.
   3. Does there exist an example with the above properties such that $E = S_1$? Provide an example or prove that it is impossible.

4. Some explicit extrema

   1. Prove that $\sup\set{x + y - z \mid x, y, z \in \Q, 0 \gt x \geq y \gt -z} = 0$.
   2. Determine which of the following extrema exist in $\Q$, and find their values. You need not supply proofs, but you should convince yourself that you could produce a proof if you were asked to do so.
      1. $\inf\set{x + y + z \mid x, y, z \in \Q, 2 \lt x \lt y \lt z}$
      2. $\inf\set{x - y + z \mid x, y, z \in \Q, 2 \lt x \lt y \lt z}$
      3. $\inf\set{x + y - z \mid x, y, z \in \Q, 2 \lt x \lt y \lt z}$
      4. $\sup\set{x + y - z \mid x, y, z \in \Q, 2 \lt x \lt y \lt z}$
      5. $\sup\set{x + y - 2z \mid x, y, z \in \Q, 2 \lt x \lt y \lt z}$

Here are some further problems to think about out of interest. You do not need to attempt them, nor should you submit them with the assignment. They are coloured by approximate difficulty: easy/medium/hard.

• Ordering

  Let $\mathcal{P}$ be the set of polynomial functions from $\Q \to \Q$. Define a relation on $\mathcal{P}$ by $p \sqsubseteq q$ if and only if $p(10) \leq q(10)$. Is $\sqsubseteq$ an order?

• Further musings on Problem 3

  1. Is there an infinite chain of sets as in 2.A.? That is, is there a sequence of sets $S_n$ so that $E \subseteq S_n \subseteq S_{n+1} \subseteq \Q$ holds for every $n \in \N$, and $E$ has a supremum in $S_n$ if and only if $n$ is odd?
  2. Is there a set $E \subseteq \Q$ so that $E$ has a supremum in $\Q$ which is different from its supremum in $\R$?

• Well-orderings

  An order $\preceq$ on a set $S$ is said to be a well-order if every $T \subseteq S$ contains a minimum element.
  1. Show that every finite set admits a well-ordering.
  2. Show that the standard order on $\N$ is a well-order.
  3. Show that the standard order on $\Z$ is not a well-order.
  4. Show that $\Z$ admits a well-ordering.
  5. Show that the standard order on $\Q$ is not a well-order.
  6. Does every set admit a well-ordering?

• Partial orders can be extended to orders

  A partial order on a set $S$ is a relation $\preceq$ on $S$ which is transitive and antisymmetric (that is, if $x, y \in S$ with $x \preceq y$ and $y \preceq x$ then $x = y$, and if $x, y, z \in S$ with $x \preceq y$ and $y \preceq z$ then $x \preceq z$). In particular, note that $S$ may have incomparable elements: $x, y \in S$ so that neither $x \preceq y$ nor $y \preceq x$.

  Prove that if $\preceq$ is a partial order on $S$, there is an order on $S$ which extends $\preceq$: that is, an order $\preceq'$ on $S$ so that if $x, y \in S$ with $x \preceq y$, then $x \preceq' y$.

  To prove this, you may assume the following:

  Zorn's Lemma. Suppose that $Z$ is a set and $\preceq$ is a partial order on $Z$ with the property that every totally-ordered subset of $Z$ is bounded above in $Z$. Then $Z$ contains a maximal element. (A subset $W \subseteq Z$ is totally ordered if $\preceq$ restricted to $W$ is an order, i.e., if whenever $x, y \in W$ we have either $x \preceq y$ or $y \preceq x$. An element $x \in Z$ is maximal if whenever $y \in Z$ with $x \preceq y$, we have $y = x$.)