Real Analysis: Metric Spaces
Metric Spaces
Metrics
Pythagoras gave us the formula for the distance between two points on the plane. The earlier section on Euclidean Space laid out the notion of a $p$-norm, which is a generalization of the Pythagorean distance formula from the origin to a point in in $\mathbb{R}^n$ that uses the $p$th power and root, rather than strictly the second. Here, we generalize the notion of distance even further by considering distances between arbitrary elements of arbitrary sets, rather than points in $\mathbb{R}^n$. A function that measures distance in this way is called a metric. If we can prove things in terms of metrics in general, then the results we come up with will be valid for any metric in particular.
A metric on a set $X$ is a function $d : X \times X \rightarrow \mathbb{R}$ such that for all $x, y, z \in X$:
- Identity: $d(x, x) = 0$
- Positivity: $d(x, y) > 0$ if and only if $x \neq y$
- Symmetry: $d(x, y) = d(y, x)$
- Triangle Inequality: $d(x, z) \leq d(x, y) + d(y, z)$
As you can verify, the Manhattan norm and Euclidean norm on the difference of two vectors both form metrics on $\mathbb{R}^n$.
Metric Spaces
The tuple $(X, d)$ of a set $X$ and a metric $d$ on $X$ is called a metric space. We often refer to the set $X$ itself as the metric space for brevity, as the metric $d$ is either inferred as a customary default, such as the Euclidean metric on $\mathbb{R}^n$, understood to be arbitrary, or stated clearly nearby. Thus, if you see $\mathbb{R}^2$ referred to as a metric space itself, or with the "usual metric," know that it implies the Euclidean metric.
Metric Subspaces and Metric Superspaces
Consider the metric spaces $(X, d)$ and $(Y, g)$. $(X, d)$ is a metric subspace of $(Y, g)$ and $(Y, g)$ is a metric superspace of $(X, d)$ if and only if $X$ is a subset of $Y$ and $d$ is a restriction of $g$. Recall that a restriction of a function is just the portion of that function that's left over when we limit its domain to a smaller subset. For example, if $d$ is the Euclidean metric on $\mathbb{R}$, then $(\mathbb{N}, d|\mathbb{N})$, $(\mathbb{Z}, d|\mathbb{Z})$, and $(\mathbb{Q}, d|\mathbb{Q})$ are all metric subspaces of $(\mathbb{R}, d)$.
Problems
The discrete metric on any set $X$ is defined as follows:
$d(x, y) = \left\{ \begin{array}{ll} 0 & \text{if } x = y \\ 1 & \text{if } x \neq y \end{array} \right.$
Verify that the discrete metric is a metric.
The identity and positivity requirements are satisfied by definition. To show symmetry, if $x=y$, then $d(x, y) = d(x, x) = 0 = d(y, y) = d(y, x)$, and if $x \neq y$, then $d(x,y) = 1 = d(y,x)$. To show the triangle inequality, we proceed by cases.
-
If $x = y = z$, then $d(x, z) = 0 \leq d(x, y) + d(y, z) = 0$.
-
If $x=y\neq z$, then $d(x,z) = 1 \leq d(x, y) + d(y, z) = 0 + 1 = 1$.
-
If $x\neq y = z$, then $d(x,z) = 1 \leq d(x, y) + d(y, z) = 1 + 0 = 1$.
-
If $x = z \neq y$, then $d(x, z) = 0 \leq d(x, y) + d(y, z) = 1 + 1 = 2$.
-
If $x \neq y \neq z$, then $d(x,z) = 1 \leq d(x, y) + d(y, z) = 1 + 1 = 2$.
-
Show that the Manhattan norm of the difference between two points in $\mathbb{R}^n$ is a metric. Namely, show that
$$d(\textbf{x}, \textbf{y}) = \|\textbf{x} - \textbf{y}\|_1 = \sum\limits_{i=1}^n |x_i - y_i|$$
is a metric on $\mathbb{R}^n$.
-
Identity:
$ d_p(x, x) = \sum\limits_{i=1}^n |x_i - x_i|\\ d_p(x, x) = \sum\limits_{i=1}^n 0 \\ d_p(x, x) = 0 \\ $
-
Positivity: If $x \neq y$, then there is at least one pair of terms $x_k$ and $y_k$ such that $x_k \neq y_k$ for some $k \in 1, \ldots n$. Therefore $x_k - y_k \neq 0$, so $|x_k - y_k| > 0$. Since all the terms in the sum are non-negative, we see that $0 < |x_k - y_k| \leq \sum\limits_{i=1}^n |x_i - y_i| = d(x, y)$.
-
Symmetry:
$ d(x, y) = \sum\limits_{i=1}^n |x_i - y_i| \\ d(x, y) = \sum\limits_{i=1}^n |-(x_i - y_i)| \\ d(x, y) = \sum\limits_{i=1}^n |-(-y_i + x_i)| \\ d(x, y) = \sum\limits_{i=1}^n |y_i - x_i| \\ d(x, y) = d(y, x) \\ $
-
Triangle Inequality:
$ d(x, z) = \sum\limits_{i=1}^n |x_i - z_i| \\ d(x, z) = \sum\limits_{i=1}^n |(x_i - y_i) + (y_i - z_i)| \\ d(x, z) \leq \sum\limits_{i=1}^n |x_i - y_i| + |y_i - z_i| \\ d(x, z) \leq \sum\limits_{i=1}^n |x_i - y_i| + \sum\limits_{i=1}^n |y_i - z_i| \\ d(x, z) \leq d(x, y) + d(y, z) \\ $
-
If $d$ is a metric on $X$ and $c$ is a positive constant, show that $f(x, y) = cd(x, y)$ is also a metric on $X$.
-
Identity: $f(x, y) = cd(x, x) = c0 = 0$.
-
Positivity: $f(x, y) = cd(x, y) > 0$ when $x \neq y$ by the second ordering axiom.
-
Symmetry: $f(x, y) = cd(x, y) = cd(y, x) = f(y, x)$.
-
Triangle Inequality:
$ f(x, z) = cd(x, z) \\ f(x, z) \leq c(d(x, y) + d(y, z)) \\ f(x, z) \leq cd(x, y) + cd(y, z) \\ f(x, z) \leq f(x, y) + f(y, z)$
-
Let $(X, d)$ be a metric space. Show that $|d(x, y) - d(y, z)| \leq d(x, z)$.
By the triangle inequality, we see that $d(x, y) \leq d(x, z) + d(z, y)$. Then $d(x, y) - d(z, y) \leq d(x, z)$. By the same inequality, we see that $d(z, y) \leq d(x, z) + d(x, y)$, and likewise that $d(z, y) - d(x, y) \leq d(x, z)$. Since $-(d(x, y) - d(z, y)) = d(z, y) - d(x, y)$, we conclude that $|d(x, y) - d(z, y)| = |d(x, y) - d(y, z)| \leq d(x, z)$.
Let $(X, d)$ and $(Y, f)$ be metric spaces. Determine whether $(X \times Y, g)$ is a metric space where $g(a, b) = d(a_x, b_x)f(a_y, b_y)$.
Consider the points $(a, b), (a, c) \in X \times Y$ where $b \neq c$. The two points are not equal, but $g((a, b), (a, c)) = d(a, a)f(b, c) = 0f(b, c) = 0$. Therefore $g$ does not fulfill the identity axiom for metrics, so $(X \times Y, g)$ is not a metric space.
Let $f : X \rightarrow \mathbb{R}$ be an injective function, and consider the function $d : X \times X \rightarrow \mathbb{R}$ where $d(x, y) = |f(x) - f(y)|$. Show that $d$ is a metric on $X$.
Identity: $d(x, x) = |f(x) - f(x)| = 0$.
Non-negativity: Let $x, y \in X$ where $x \neq y$. Then $d(x, y) = |f(x) - f(y)| > 0$, since $f(x) \neq f(y)$ by injectivity.
Symmetry: Let $x, y \in X$. Then
$ d(x, y) = |f(x) - f(y)| \\ d(x, y) = |-(f(x) - f(y))| \\ d(x, y) = |f(y) - f(x)| \\ d(x, y) = d(y, x) $
Triangle Inequality: First assume $f(x) - f(z)$ is non-negative. Then
$ d(x, z) = f(x) - f(z) \\ d(x, z) = (f(x) - f(z)) + (f(y) - f(y)) \\ d(x, z) = (f(x) - f(y)) + (f(y) - f(z)) \\ d(x, z) \leq |f(x) - f(y)| + |f(y) - f(z)| \\ d(x, z) \leq d(x, y) + d(y, z) \\ $
Conversely, if $f(x) - f(z)$ is negative, then
$ d(x, z) = f(z) - f(x) \\ d(x, z) = (f(z) - f(x)) + (f(y) - f(y)) \\ d(x, z) = (f(z) - f(y)) + (f(y) - f(x)) \\ d(x, z) \leq |f(z) - f(y)| + |f(y) - f(x)| \\ d(x, z) \leq |f(x) - f(y)| + |f(y) - f(z)| \\ d(x, z) \leq d(x, y) + d(y, z) \\ $
Show that the Euclidean norm of the difference between two points in $\mathbb{R}^n$ is a metric. Namely, show that
$$d(\textbf{x}, \textbf{y}) = \|\textbf{x} - \textbf{y}\|_2 = \sqrt{\sum\limits_{i=1}^n |x_i - y_i|^2}$$
is a metric.
Identity: $d(\textbf{x}, \textbf{x}) = \sqrt{\sum\limits_{i=1}^n |x_i - x_i|^2} = \sqrt{\sum\limits_{i=1}^n 0^2} = 0$.
Positivity: $d(\textbf{x}, \textbf{y}) = \sqrt{\sum\limits_{i=1}^n |x_i - y_i|^2} \geq 0$ because every term of the sum is a square and thus non-negative, thus the sum is non-negative, and so its square root is well-defined and non-negative.
Symmetry: $d(\textbf{x}, \textbf{y}) = \sqrt{\sum\limits_{i=1}^n |x_i - y_i|^2} = \sqrt{\sum\limits_{i=1}^n |y_i - x_i|^2} = d(\textbf{y}, \textbf{x})$.
Triangle Inequality:
$ d(\textbf{x}, \textbf{z})^2 = \sum\limits_{i=1}^n |(x_i - z_i)|^2 \\ d(\textbf{x}, \textbf{z})^2 = \sum\limits_{i=1}^n |(x_i - y_i) + (y_i - z_i)|^2 \\ d(\textbf{x}, \textbf{z})^2 \leq \sum\limits_{i=1}^n |(x_i - y_i)|^2 + |(y_i - z_i)|^2 \\ d(\textbf{x}, \textbf{z})^2 \leq \sum\limits_{i=1}^n |(x_i - y_i)|^2 + \sum\limits_{i=1}^n|(y_i - z_i)|^2 \\ d(\textbf{x}, \textbf{z}) \leq \sqrt{\sum\limits_{i=1}^n |(x_i - y_i)|^2 + \sum\limits_{i=1}^n|(y_i - z_i)|^2} \\ d(\textbf{x}, \textbf{z}) \leq \sqrt{\sum\limits_{i=1}^n |(x_i - y_i)|^2} + \sqrt{\sum\limits_{i=1}^n|(y_i - z_i)|^2} \\ d(\textbf{x}, \textbf{z}) \leq d(\textbf{x}, \textbf{y}) + d(\textbf{y}, \textbf{z}) $
The second to last step follows from the algbraic property of the square root operation proven in the prior Algebra on $\mathbb{R}$ section.
Consider the unit circle $C_1 = \{ (x, y) \in \mathbb{R}^2 : \sqrt{x^2 + y^2} = 1 \}$, and consider $d|C_1$ as the Euclidean distance between points in $C_1$. Now consider the following argument: $(C_1, d|C_1)$ is not a subspace of $\mathbb{R}^2$ because the distance traveled between points goes outside $C_1$. Is this reasoning sound?
No. Remember that the definition of a subspace needs to meet two conditions. The first is that the set be a subset, and the second is that the function be a restriction. We can see that $C_1 \subset \mathbb{R}^2$ by definition, and $d|C_1$ is also a restriction of the Euclidean metric by definition. Thus $(C_1, d|C_1)$ is a metric subspace of $(\mathbb{R}^2, d)$. Whether we may visualize the distance between two points in $C_1$ as a line that goes outside of $C_1$ is irrelevant. More specifically, the fact that it may be impossible to construct a geometric path through the subspace between two points whose length matches the distance determined by the metric is not a requirement.
Show that if $d(a, b) < \varepsilon$ for all $\varepsilon > 0,$ then $a = b.$
Proof by contradiction. Assume $a \neq b.$ Then $d(a, b) > 0.$ Pick $\varepsilon = \frac{1}{2}d(a, b).$ Then $d(a, b) < \frac{1}{2}d(a, b),$ which means that $\frac{1}{2}d(a, b) < 0$ and thus $d(a, b) < 0.$ However, this is a contradiction, as $d$ is a metric which is always non-negative. Therefore $a = b$ after all.
Show that the Euclidean distance function $d(a, b) = |a - b|$ does not form a metric on $\overline{\mathbb{R}}.$
There are two problems with extending the Euclidean metric $d(a, b) = |b - a|$ to $\overline{\mathbb{R}}.$
The first is that the identity property does not hold, as $d(\infty, \infty) = |\infty - \infty|,$ which is undefined. However, we could try to fix this by defining $d(\infty, \infty) = 0.$ Unfortunately, even if we accomplished that, for any $a \in \mathbb{R}$ we see that $d(a, \infty) = |\infty - a| = \infty \notin \mathbb{R},$ so $\mathbb{R}$ is not the codomain of $d$ as required. As a result, the Euclidean metric can't be salvaged for the extended real numbers.
Show that if $h$ is a bijection from $X$ to $Y$ and $d_Y$ is a metric on $Y,$ then $d_X(a, b) = d_Y(h(a), h(b))$ is a metric on $X.$
Assume $h : X \rightarrow Y$ is bijective, and let $d_Y$ be a metric on $Y.$
-
Identity: Consider $a \in X.$ Then $d_X(a, a) = d_Y(h(a), h(a)) = 0.$
-
Positivity: Let $a, b \in X$ where $a \neq b.$ Then because $h$ is bijective, $h(a) \neq h(b),$ and so $d_X(a, b) = d_Y(h(a), h(b)) > 0.$
-
Symmetry: Let $a, b \in X.$ Then
$ d_X(a, b) = d_Y(h(a), h(b)) \\ d_X(a, b) = d_Y(h(b), h(a)) \\ d_X(a, b) = d_X(b, a).$
-
Triangle Inequality: Let $a, b, c \in X.$ Then
$ d_X(a, c) = d_Y(h(a), h(c)) \\ d_X(a, c) \leq d_Y(h(a), h(b)) + d_Y(h(b), h(c)) \\ d_X(a, c) \leq d_X(a, b) + d_X(b, c)$
-