Ian Charlesworth

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. Suppose that $f : [a, b] \to \R$ is bounded, and continuous except at finitely many points. Prove that $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. 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$.

4. Uniform convergence and boundedness

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

5. 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.\](The notation $f \equiv 0$ means $f(t) = 0$ for all $t$ in the domain of $f$.)
   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$.)

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?

• 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 Riemann-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.\]

  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.

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. $f\circ g$ and $g$ are differentiable but $f$ is not.
   4. $f\circ g$ and $f$ are differentiable but $g$ is not.

3. More derivatives

   Recall that $\sin$ and $\cos$ are differntiable functions $\R\to[-1,1]$ with the properties that $\sin'(x) = \cos(x)$, $\cos'(x) = -\sin(x)$, $\sin(x) \gt 0$ for $x \in (0, \pi)$, $\cos(x) = \sin(x + \frac\pi2)$ (from which the other translations follow, e.g. $\sin(x) = \sin(x+2\pi)$, $\cos(x) = \cos(x+2\pi)$, ...), $\sin(0) = 0$, and $\cos(0) = 1$. (In fact, $\sin$ is the only differentiable function on $\R$ with $\sin'' = -\sin$, $\sin(0) = 0$, and $\sin'(0) = 1$, but showing this is difficult, and defining $\sin$ as the unique function with these properties makes it rather difficult to show basic properties such as periodicity.)

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

   1. Show that $f$ is differentiable on $\R$, and find its derivative.
   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)$, \[g'(f(x)) = \frac1{f'(x)}.\]

5. Positive derivative at a point

   Show that there is a differentiable function $f : \R \to \R$ with $f'(0) \gt 0$, but so that there is no $\delta\gt0$ with $f$ monotonically increasing on $(-\delta, \delta)$. (I.e., there is no $\delta \gt 0$ so that for all $x, y\in\R$ with $-\delta \lt x \lt y \lt \delta$ we have $f(x) \leq f(y)$.)

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

  Does there exist a differentiable function $f : \R\to\R$ which is not monotonic on any open interval? (This is not an easy question to answer.)

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.
   3. Define a relation $\sim$ on $M$ by $x \sim y$ if and only if there is a connected set $A \subseteq M$ with $x, y \in A$. Prove 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 $\sim$ is an equivalence relation, the connected components of $M$ are disjoint. Since every point of $M$ is in some connected component, it is easy to check 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$.
   1. 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$. Show that $\sim_p$ is an equivalence relation.

   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 non-empty, open, and connected, then $E$ is path connected.

   It is not true that connected sets are path connected in general. Consider, 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.\] It can be shown that while $T$ is connected, the two pieces above are distinct path components of $T$.

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 Y$ 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}x^2 & \text{ if } x \in \Q \\ 0 & \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$!)

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 on connected components

  1. Prove that if $C \subseteq M$ is a connected component of $M$, then $C$ is closed.
  2. Prove that if $M$ has a finite number of connected components, then each component is open.

1. Sequential characterization of continuity

   Prove that a function $f : X \to Y$ is continuous if and only if for every convergent sequence $(a_n)_n$ in $X$, the sequence $(f(a_n))_n$ is convergent in $Y$ with \[f\paren{\limni a_n} = \limni f(a_n).\]

2. 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.

3. Equivalent metrics

   Let $M$ be a set. Two metrics $d$ and $d'$ on $M$ are said to be strongly equivalent if there are constants $c, C \in \R_{\gt0}$ so that for every $x, y \in M$, \[cd(x, y) \leq d'(x, y) \leq Cd(x, y).\]

   Now, let $d$ and $d'$ be strongly equivalent metrics on $M$.

   1. Show that $U \subseteq M$ is open with respect to $d$ if and only if it is open with respect to $d'$.
   2. Suppose that $X$ is another set, with strongly equivalent metrics $d_X$ and $d_X'$. Show that $f : M \to X$ is continuous with respect to $d$ and $d_X$ if and only if it is continuous with respect to $d'$ and $d_X'$.

4. Continuous functions on dense sets

   Suppose that $f, g : X \to Y$ are continuous, and $E \subseteq X$ is dense.
   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.)

5. 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$.)
   4. Show that if $f$ is merely assumed to be continuous, it may not have a continuous extension.

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.

• Coordinates functions

  1. Show that the metric $d_\infty$ on $\R^n$ defined by \[d_\infty\paren{\vec{x}, \vec{y}} = \max\set{\abs{x_i - y_i} \mid 1 \leq i \leq n}\] is strongly equivalent to the usual metric \[d\paren{\vec{x}, \vec{y}} = \paren{\sum_{i=1}^n \abs{x_i-y_i}^2}^{\frac12}.\]
  2. Suppose that $f : M \to \R^n$, and let $f_1, \ldots, f_n : M \to \R$ be the coordinates of $f$, so that \[f(x) = \paren{f_1(x), \ldots, f_n(x)}.\] Show that $f$ is continuous if and only if all the $f_i$ are.

• Distances

  Let $M$ be a metric space, and define a metric on $M\times M$ by \begin{align*} d_2 : (M \times M) \times (M \times M) &\longrightarrow \R_{\geq0}\\ ((x_1, y_1), (x_2, y_2)) &\longmapsto \sqrt{d_M(x_1, x_2)^2 + d_M(y_1, y_2)^2}. \end{align*} (You may take for granted that this is a metric; notice that if $M = \R$, $d_2$ is the usual distance on $\R^2$.)

  Prove that the original metric on $M$, $d_M : M \times M \to \R_{\geq0}$, is continuous on the metric space $(M\times M, d_2)$.

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

1. Limits and order properties

   Clarification: in this question and the rest of the course, unless otherwise specified, the metric we take on $\R$ is the usual distance: $d(x, y) = \abs{y-x}$.
   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.\]
   6. Show that if $(a_n)_n$ is a sequence in some metric space $(M, d)$, then $(a_n)_n$ converges to some $x \in M$ if and only if \[\lim_{n\to\infty} d(a_n, x) = 0.\]

2. Examining completions

   Let $(M, d)$ be a metric space. Recall that we constructed the completion of $M$ as \[\overline{M} = \set{\text{Cauchy sequences in } M} / \sim,\] where $(a_n)_n \sim (b_n)_n$ if and only if \[\lim_{n\to\infty} d(a_n, b_n) = 0.\] We then considered an isometry (i.e., distance-preserving function) $i : M \hookrightarrow \overline{M}$ given by \[i(x) = [(x)_n]_\sim.\]
   1. Show that for any $x \in M$, \[i(x) = \set{(a_n)_n \mid (a_n)_n \text{ is a sequence in } M \text{ with } \lim_{n\to\infty}a_n = x}.\]
   2. We saw that $\overline{M}$ is complete, but let's examine how limits there actually behave. Show that if $(a_n)_n$ is a Cauchy sequence in $M$, \[\lim_{n\to\infty} i(a_n) = [(a_n)_n]_\sim.\] (That is, Cauchy sequences in $M$ give sequences in $\overline{M}$ which converge to the equivalence class of the original sequence in $M$.)

3. 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.)

4. 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 \color{red}{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 \color{red}{\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.

• 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?

• The empty metric space is silly

  Let $d : \emptyset\times\emptyset \to \R_{\geq 0}$ be a metric on $\emptyset$.
  1. Show that $\emptyset \subseteq \emptyset$ is not bounded.
  2. Show that $\emptyset$ is compact.
  3. Let $(M, d_M)$ be a metric space. Are all compact subsets of $M$ bounded?

• Pseudometrics

  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)$.
  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

  1. Prove 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.\]

  2. 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$.

  3. 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$.
  4. Let $M$ 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 $M$ converges to some $f \in M$ 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$.)

Due to cancelled classes, I have not had time to cover most of the material which was going to form the core of this assignment, and so the selection of problems is somewhat interesting. This assignment is optional. Any points earned will be added as bonus points to your other assignments.

1. Cauchy sequences

   1. Prove that if $(a_n)_n$ is a Cauchy sequence in some metric space $(M, d)$ with a convergent subsequence, then $(a_n)_n$ itself converges.
   2. Use the previous problem to prove that if $(K, d)$ is a compact metric space, then every Cauchy sequence in $K$ converges in $K$. (There is a proof of this fact in Rudin which uses some facts about diameters of sets to prove this. The goal of this problem is to come up with a different proof.) (Apparently I accidentally proved this in lecture.)
   3. Prove that if $(c_k)_k$ is a Cauchy sequence in some metric space $(M, d)$, then $(c_k)_k$ is bounded.

2. Completions are unique

   Suppose that $(M, d)$ and $(X, d_X)$ are metric spaces. An isometry of $M$ into $X$ is a distance preserving function $i : M \hookrightarrow X$, i.e., one so that for all $a, b \in M$, \[d(a, b) = d_X(i(a), i(b)).\]
   1. Prove that isometries are always one-to-one.

   Suppose that $(M, d), (X, d_X)$, and $(Y, d_Y)$ are metric spaces, and that $i_X : M \hookrightarrow X$ and $i_Y : M \hookrightarrow Y$ are isometries of $M$ into $X$ and $Y$ respectively. Let us also suppose that $X$ and $Y$ are complete: that is, that every Cauchy sequence in $X$ converges to a limit in $X$, and similar for $Y$. Finally, assume that $i_X(M) = \set{i_X(a) \mid a \in M}$ is dense in $X$ (that is, $X = \overline{i_X(M)}$).

   2. Prove that there is an isometry $I : X \hookrightarrow Y$ of $X$ into $Y$ so that $i_Y(a) = I(i_X(a))$ for all $a \in M$.
   3. Prove that the isometry $I : X \hookrightarrow Y$ above is unique.
   4. Prove that if $i_Y(M)$ is dense in $Y$, then the isometry $I : X \hookrightarrow Y$ from (C) has an inverse $J : Y \hookrightarrow X$ which is also an isometry, and that $i_X(a) = J(i_Y(a))$ for all $a \in M$.

   Two metric spaces $(X, d_X)$ and $(Y, d_Y)$ are called isometric if there are isometries $I : X \hookrightarrow Y$ and $J : Y \hookrightarrow X$ which are inverses of one another. What we have now shown is that any two complete metric spaces containing $M$ as a dense manner are isometric to each other, in a way that aligns the copy of $M$ inside each. This fact is often stated as "the completion of $M$ is unique up to isometry".

3. The real numbers as the completion of the rationals

   We will see in lecture this week that if $M$ is a metric space, there is a complete metric space $\overline{M}$ into which $M$ includes as a dense subset, and by the previous problem we know that this completion is unique. We also know that $\Q$ is a dense subset of the metric space $\R$, so $\R = \overline{\Q}$ (after applying a distance-preserving invertible function).

   Recall that earlier in the course, we merely asserted that an ordered field with the least upper bound property existed, but we didn't prove it. It is tempting to use this as our definition of what the real numbers are: to define $\R$ as $\overline{\Q}$. After making this definition, it is not so bad to show that $\R = \overline{\Q}$ has the properties of an ordered field and has the least upper bound property.

   However, there is a subtle flaw with doing this. Why is it not valid to define $\R$ as $\overline{\Q}$ in this way? What could we do to avoid this problem? (No proofs needed here; just explain the problem and give a suggestion about how to avoid it.)

1. Closures and limits

   Let $E$ be a subset of a metric space $(M, d)$. Show that $x \in \overline{E}$ if and only if there is a sequence in $E$ which converges to $x$.

2. Square roots and convergent sequences

   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$.)

3. A recursively defined sequence

   Let $(a_n)_n$ be the sequence defined as follows: $a_1 = 1$, and for $n \in \N$, $a_{n+1} = \sqrt{10+3a_n}$.
   1. Prove that for every $n \in \N$, we have $0 \leq a_n \leq a_{n+1} \leq 10^{100}$.
   2. We will see later that Part A means $(a_n)_n$ must converge (monotonic sequences converge if and only if they are bounded). Find $\lim_{n\to\infty} a_n$.

4. 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.

5. 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 \color{red}{\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$.)

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

   We saw 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. 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}$.

   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.)

3. 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$.

4. 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 be emphasize where we are taking the ball. Explicitly, if $x \in X$, \[B_r^X(x) = \set{y \in X \mid d(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$, $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 3.)
   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.)

5. 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$.)

   An earlier version of this problem had the condition "$q \gt 0$" on the set, which of course makes it fail to be closed. This has been removed.

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 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.

• Open double covers

  Let $(M, d)$ be a metric space. 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?

• 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$.)

• 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$.)

0. Warm up (not to be submitted)

   Determine if each of the following statements is true or false. Some of these require a bit of thought, and some are almost directly from the lectures. Do not submit this problem.
   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. $\Q$ is a dense subset of $\R$.
   5. $\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}$.
   6. If $E$ is a subset of $X$, then $(E^c)^c = E$.
   7. If $E$ is an open subset of a metric space $X$, then $E^c$ is closed.
   8. If $E$ is a subset of a metric space which is not open, then it is closed.
   9. If $(M, d)$ is a metric space, then $M$ is open.
   10. If $(M, d)$ is a metric space, then $M$ is closed.
   11. If $(M, d)$ is a metric space, then $M$ is bounded.
   12. If $E$ is a bounded subset of a metric space, then it is either open or closed.
   13. Any finite subset of a metric space is closed.
   14. Any finite subset of a metric space is open.
   15. Any finite subset of a metric space is compact.
   16. No finite non-empty subset of a metric space is closed.
   17. No finite non-empty subset of a metric space is open.
   18. No finite non-empty subset of a metric space is compact.

1. De Morgan's Laws

   Verify the following identities, where $(E_\alpha)$ is a collection of subsets of a set $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\]

2. Limit points

   Let $(M, d)$ be a metric space, $E \subseteq M$, and $E'$ be the set of limit points of $E$.
   1. Show that $x \in E'$ if and only if every open set containing $x$ contains infinitely many elements of $E$.
   2. Prove that $E'$ is closed.
   3. Prove that $E$ and $\overline{E}$ have the same limit points.
   4. Prove that $E$ and $E'$ must have the same limit points, or show by example that this need not be the case.

3. 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$.

4. 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?

5. 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).)

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. If $(M, d)$ is a metric space, $x, y \in M$ are such that every open set containing $x$ also contains $y$, then $x = y$.
  2. If $(M, d)$ is a non-empty metric space, show that any unbounded subset of $M$ contains infinitely many points.
  3. 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$.
  4. 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$.

1. Some useful facts which would have been nice to have earlier

   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".)

   3. If $x, y \in \R$ with $0 \leq x \leq y$ then $x^2 \leq y^2$ and $x^{1/2} \leq y^{1/2}$.
   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. 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. Use the above to show that $\Q$ does not have the Least Upper Bound Property. (Hint: consider a set like $\set{q \in \Q \mid q^2 \lt 2}$.)

3. Metrics?

   For each of the following, determine 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^3-y^3}$
   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}.$

4. 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 \sup\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$.

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.

• 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. Extend this definition to $0 \lt \gamma \lt 1$ by setting $\gamma^x = \paren{\frac1\gamma}^{-x}$.
  7. 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$ is a set and $M$ is a metric space with metric $d_M$. Let $f : S \to M$ be a function. Show that the map $d_f : S\times S \to \R_{\geq0}$ given by $d_f(s, t) = d_M(f(s), f(t))$ is a metric if and only if $f$ is injective.
  2. 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?
  3. 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?
  4. 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$?
  5. 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?

1. Properties of ordered sets

   Suppose $S$ is an ordered set with ordering $\preceq$.
   1. Prove that if $E \subseteq S$, then $\sup E$ is unique if it exists.
   2. Prove that if $e \in S$ is a lower bound for $E$ and $e \in E$, then $e = \inf 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 least upper bound if and only if $S$ has a minimum element. (An element $y \in S$ is the minimum of $S$ if $y \preceq x$ for every $x \in S$.)

2. 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.

3. Properties of ordered fields

   Let $\F$ be an ordered field.
   1. Show that $\F$ does not have a minimum element.
   2. Show that $\F$ does not have a minimum positive element: that is, there is no minimum element of the subset $\F_+ = \set{x \in \F \mid x \gt 0}$.
   3. Suppose that $E \subseteq \F$ has a least upper bound, and let $x \in \F$. Show that $\sup\set{x + e \mid e \in E} = x + \sup E$.
   4. Suppose again that $E \subseteq \F$ has a least upper bound, and let $x \in \F$. Denote by $xE$ the set $\set{xe \mid e \in E}$. Show that if $0 \preceq x$ then $\sup(xE) = x\sup E$, while if $x \preceq 0$ then $\inf(xE) = x\sup E$.

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 $\R$, 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, 1 \lt x \lt y \lt z}$
      2. $\inf\set{x - y + z \mid x, y, z \in \Q, 1 \lt x \lt y \lt z}$
      3. $\inf\set{x + y - z \mid x, y, z \in \Q, 1 \lt x \lt y \lt z}$
      4. $\sup\set{x + y - z \mid x, y, z \in \Q, 1 \lt x \lt y \lt z}$
      5. $\sup\set{x + y - 2z \mid x, y, z \in \Q, 1 \lt x \lt y \lt z}$

5. 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$.

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.

• Further musings on Problem 2

  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$?

• 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$.)