.md .pdf

repository open issue

Contents

3.1. Introduction

3.1.1. Distance Functions

Definition 3.1 (Distance function/Metric)

Let $X$ be a nonempty set. A function $d:X\times X\to \mathbb{R}$ is called a distance function or a metric if it satisfies the following properties for any elements $x,y,z\in X$:

1. Non-negativity: $d(x,y)\ge 0$

2. Identity of indiscernibles: $d(x,y)=0⟺x=y$

3. Symmetry: $d(x,y)=d(y,x)$

4. Triangle inequality: $d(x,y)\le d(x,z)+d(z,y)$

• It is customary to call the elements of a set $X$ associated with a distance function as points.

• Distance functions are real valued.

• Distance functions map an ordered pair of points in $X$ to a real number.

• Distance between two points in the set $X$ can only be non-negative.

• Distance of a point with itself is 0. In other words, if the distance between two points is 0, then the points are identical. i.e. the distance function works as a discriminator between the points of the set $X$.

• Symmetry means that the distance from a point $x$ to another point $y$ is same as the distance from $y$ to $x$.

• Triangle inequality says that the direct distance between two points can never be longer than the distance covered through an intermediate point.

3.1.2. Metric Spaces

Definition 3.2 (Metric space)

Let $d$ be a distance function on a set $X$. Then we say that $(X,d)$ is a metric space. The elements of $X$ are called points.

• In general, a set $X$ can be associated with different metrics (distance functions) say $d_1$ and $d_2$. In that case, the corresponding metric spaces $(X,d_1)$ and $(X,d_2)$ are different.

• When a set $X$ is equipped with a metric $d$ to create a metric space $(X,d)$, we say that $X$ has been metrized.

• If the metric $d$ associated with a set $X$ is obvious from the context, we will denote the corresponding metric space $(X,d)$ by simply $X$. E.g., $|x-y|$ is the standard distance function on the set $\mathbb{R}$.

• When we say that let $Y$ be a subset of a metric space $(X,d)$, we mean that $Y\subset X$.

• Similarly, a point in a metric space $(X,d)$ means the point in the underlying set $X$.

Note

Some authors prefer the notation $d:X\times X\to {\mathbb{R}}_{+}$. With this notation, the non-negativity property is embedded in the type signature of the function (i.e. the codomain specification) and doesn’t need to be stated explicitly.

3.1.3. Properties of Metrics

Proposition 3.1 (Triangle inequality alternate form)

Let $(X,d)$ be a metric space. Let $x,y,z\in X$.

$$|d(x,z)-d(y,z)|\le d(x,y).$$

Proof. From triangle inequality:

$$d(x,z)\le d(x,y)+d(y,z)⟹d(x,z)-d(y,z)\le d(x,y).$$

Interchanging $x$ and $y$ gives:

$$d(y,z)-d(x,z)\le d(y,x)=d(x,y).$$

Combining the two, we get:

$$|d(x,z)-d(y,z)|\le d(x,y).$$

3.1.4. Metric Subspaces

Definition 3.3 (Metric subspace)

Let $(X,d)$ be a metric space. Let $Y\subset X$ be a nonempty subset of $X$. Then, $Y$ can be viewed as a metric space in its own right with the distance function $d$ restricted to $Y\times Y$, denoted as $d{|}_{Y\times Y}$. We then say that $(Y,d{|}_{Y\times Y})$ or simply $Y$ is a metric subspace of $X$.

It is customary to drop the subscript $Y\times Y$ from the restriction of $d$ and write the subspace simply as $(Y,d)$.

Example 3.1

$[0,1]$ is a metric subspace of $\mathbb{R}$ with the standard metric $d(x,y)=|x-y|$ restricted to $[0,1]$. In other words, the distance between any two points $x,y\in [0,1]$ is calculated by viewing $x,y$ as points in $\mathbb{R}$ and using the standard metric for $\mathbb{R}$.

3.1.5. Examples

Example 3.2 (${\mathbb{R}}^n$ p-distance)

For some $1\le p<\mathrm{\infty }$, the function $d_p:{\mathbb{R}}^n\times {\mathbb{R}}^n\to \mathbb{R}$:

$$d_p(x,y)\triangleq {(\sum _{i=1}^n|x_i-y_i{|}^p)}^{\frac{1}{p}}$$

is a metric and $({\mathbb{R}}^n,d_p)$ is a metric space.

Example 3.3 (${\mathbb{R}}^n$ Euclidean space)

The $d_2$ metric over ${\mathbb{R}}^n$:

$$d_2(x,y)\triangleq {(\sum _{i=1}^n|x_i-y_i{|}^2)}^{\frac{1}{2}}$$

is known as the Euclidean distance and the metric space $({\mathbb{R}}^n,d_2)$ is known as the n-dimensional Euclidean (metric) space.

The standard metric for ${\mathbb{R}}^n$ is the Euclidean metric.

Example 3.4 (Discrete metric)

Let $X$ be a nonempty set:

Define:

$$\begin{array}{r}d(x,y)=\{\begin{array}{ll}0& x=y\\ 1& x\ne y\end{array}.\end{array}$$

$(X,d)$ is a metric space. This distance is called discrete distance and the metric space is called a discrete metric space.

Discrete metric spaces are discussed in depth in Discrete Metric Space. They help clarify many subtle issues in the theory of metric spaces.

Example 3.5 ($\bar{\mathbb{R}}$ A metric space for the extended real line)

Consider the mapping $\phi :\bar{\mathbb{R}}\to [-1,1]$ given by:

$$\begin{array}{r}\phi (x)=\{\begin{array}{ll}\frac{t}{1+|t|}& x\in \mathbb{R}\\ -1& x=-\mathrm{\infty }\\ 1& x=\mathrm{\infty }\end{array}.\end{array}$$

$\phi$ is a bijection from $\bar{\mathbb{R}}$ onto $[-1,1]$.

$[-1,1]$ is a metric space with the standard metric for the real line $d_{\mathbb{R}}(x,y)=|x-y|$ restricted to $[-1,1]$.

Consider a function $d:\bar{\mathbb{R}}\times \bar{\mathbb{R}}\to \mathbb{R}$ defined as

$$d(s,t)=|\phi (s)-\phi (t)|.$$

The function $d$ satisfies all the requirements of a metric. It is the standard metric on $\bar{\mathbb{R}}$.

Example 3.6 (${\ell }^p$ Real sequences)

For any $1\le p<\mathrm{\infty }$, we define:

$${\ell }^p=\{\{a_n\}\in {\mathbb{R}}^{\mathbb{N}}|\sum _{i=1}^{\mathrm{\infty }}|a_i{|}^p\}$$

as the set of real sequences $\{a_n\}$ such that the series $\sum a_n^p$ is absolutely summable.

It can be shown that the set ${\ell }^p$ is closed under sequence addition.

Define a map $d_p:{\ell }^p\times {\ell }^p\to \mathbb{R}$ as

$$d_p(\{a_n\},\{b_n\})=\sum _{i=1}^{\mathrm{\infty }}|a_i-b_i{|}^p.$$

$d_p$ is a valid distance function over ${\ell }^p$. We metrize ${\ell }^p$ with $d_p$ as the standard metric.

3.1.6. Products of Metric Spaces

Definition 3.4 (Finite products of metric spaces)

Let $(X_1,d_1),(X_2,d_2),\dots ,(X_n,d_n)$ be $n$ metric spaces.

Let $X=X_1\times X_2\times \cdots \times X_n$. Define a map $\rho :X\times X\to \mathbb{R}$ as:

$$\rho ((a_1,a_2,\dots ,a_n),(b_1,b_2,\dots ,b_n))=\sum _{i=1}^n{d}_i(a_i,b_i).$$

$\rho$ is a distance function on $X$. The metric space $(X,\rho )$ is called the product of metric spaces $(X_i,d_i)$.

3.1.7. Distance between Sets and Points

Definition 3.5 (Distance between a point and a set)

The distance between a nonempty set $A\subseteq X$ and a point $x\in X$ is defined as:

$$d(x,A)\triangleq inf\{d(x,a)\mathrm{\forall }a\in A\}.$$

• Since $A$ is nonempty, hence the set $D=\{d(x,a)\mathrm{\forall }a\in A\}$ is not empty.

• $D$ is bounded from below since $d(x,a)\ge 0$.

• Since $D$ is bounded from below, hence it does have an infimum.

• Thus, $d(x,A)$ is well-defined and finite.

• Since $A$ is non-empty, hence there exists $a\in A$.

• $d(x,a)\in D$.

• Thus, $D$ is bounded from above too.

• Thus, $0\le d(x,A)\le d(x,a)$.

• If $x\in A$, then $d(x,A)=0$.

Theorem 3.1

If $x\in A$, then $d(x,A)=0$.

Example 3.7

1. Let $X=\mathbb{R}$ and $A=(0,1)$.

2. Let $x=0$.

3. Then $d(x,A)=0$.

4. However, $x\notin A$.

5. Thus, $d(x,A)=0$ doesn’t imply that $x\in A$.

Distance of a set with its accumulation points is 0. See Theorem 3.21.

3.1.8. Distance between Sets

Definition 3.6 (Distance between sets)

The distance between two nonempty sets $A,B\subseteq X$ is defined as:

$$d(A,B)\triangleq inf\{d(a,b)|a\in A,b\in B\}.$$

previous

3. Metric Spaces

next

3.2. Metric Topology