Math 104 Assignment 3

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$
   4. $S_D = \R$, $d_D(x, y) = \abs{x^2-y^2}$
   5. $S_E = \R$, $d_E(x, y) = \abs{x^5-y^3}$
   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 $k = \min\set{n \in \N \mid f(n) \neq g(n)}$, and set $d_G(f, g) = 2^{-k}$; if $f = g$, set $d_G(f, g) = 0$ instead.
   8. $S_H = \set{4}$, $d_H(x, y) = x^2 + y^2 - 2x - 2y - 16$

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 a product metric

   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}$. Prove that \begin{align*} d_2 : (S\times T) \times (S\times T) &\longrightarrow \R_{\geq0} \\ ((x_1, x_2), (y_1, y_2)) &\longmapsto \sqrt{d_S(x_1, y_1)^2 + d_T(x_2, y_2)^2}. \end{align*} is a metric on $S \times T$.

   (Note that, as a consequence, the Euclidean metric is a metric on $\R^2$; induction will show that it is also a metric on $\R^n$ for any $n \in \N$.)

4. Some open/closed set problems

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

   1. Prove that finite subsets of $M$ are closed.
   2. Suppose $x, y \in M$ are such that every open set containing $x$ also contains $y$. Prove that $x = y$.
   3. Suppose that $d$ is the discrete metric on $M$; that is, that $d(x, y) \in \set{0,1}$ for every $x, y \in M$. Determine which subsets of $M$ are open, and determine which subsets of $M$ are closed.
   4. Let $n \in \N$, and $T, a_1, \ldots, a_n \in \R$. Prove that \[\set{x \in \R^n \mid a_1x_1 + \ldots + a_nx_n \lt {\color{red}T}}\] is open (in $\R^n$ with respect to the Euclidean distance $d_2$).

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.

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

• 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.
     1. Take \begin{align*} d_1 : (S\times T) \times (S\times T) &\longrightarrow \R_{\geq0} \\ ((s_1, t_1), (s_2, t_2)) &\longmapsto d_S(s_1, s_2) + d_T(t_1, t_2). \end{align*} Is $d_1$ a metric on $S\times T$?
     2. Take \begin{align*} d_\infty : (S\times T) \times (S\times T) &\longrightarrow \R_{\geq0} \\ ((s_1, t_1), (s_2, t_2)) &\longmapsto \max\set{d_S(s_1, s_2), d_T(t_1, t_2)}. \end{align*} Is $d_\infty$ a metric on $S\times T$?
  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_C = \R$. Is $d_C(x, y) = \abs{x^3-y^3}$ 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) &\longrightarrow \R_{\geq 0}\\ ((s_1, t_1), (s_2, t_2)) &\longmapsto \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?
  6. Suppose $S_F = \R$. Is $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}$ a metric?

• Open sets and polynomial inequalitites

  Let $n \in \N$, and let $p : \R^n \to \R$ be any polynomial function in $n$ variables. Let $T \in \R$. Prove that the set \[\set{ x \in \R^n \mid p(x) \lt T }\] is open (in $\R^n$ with respect to the Euclidean distance $d_2$).

  (Later in the course, once we have the right tools, this will be much easier statement to prove. Without any technology, though, it's fairly challenging.)

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

Useful fact: a lot of the content of this website is rendered with a Javascript plugin called MathJax. If you right-click on any displayed math, one of the options is "Show Math As > TeX Commands", which will show you what $\LaTeX$ I used to generate it. However, I've defined a few custom commands that are not standard $\LaTeX$, so you can't *quite* copy-paste directly into a document. Nonetheless, if you're wondering how to typeset something, that's a way to find out.