Math 104 Assignment 2

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?