(sec:ms:intro)=
# Introduction
## Distance Functions
```{index} Metric, Distance
```
```{prf:definition} Distance function/Metric
:label: def-ms-distance-function
Let $X$ be a nonempty set.
A {prf:ref}`function ` $d : X \times X \to \RR$
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) \geq 0$
1. Identity of indiscernibles: $d(x, y) = 0 \iff x = y$
1. Symmetry: $d(x, y) = d(y, x)$
1. Triangle inequality: $d(x,y) \leq 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.
## Metric Spaces
```{index} Metric space
```
```{prf:definition} Metric space
:label: def-ms-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 $\RR$.
* 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 \RR_+$.
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.
```
## Properties of Metrics
```{prf:proposition} Triangle inequality alternate form
:label: res-ms-triangle-ineq-2nd-form
Let $(X, d)$ be a metric space. Let $x,y,z \in X$.
$$
|d (x, z) - d(y, z)| \leq d(x,y).
$$
```
```{prf:proof}
From triangle inequality:
$$
d (x, z) \leq d(x, y) + d (y, z) \implies d (x, z) - d(y, z) \leq d (x, y).
$$
Interchanging $x$ and $y$ gives:
$$
d (y, z) - d (x, z) \leq d (y, x) = d (x, y).
$$
Combining the two, we get:
$$
|d (x, z) - d(y, z)| \leq d(x,y).
$$
```
## Metric Subspaces
```{index} Metric subspace
```
```{prf:definition} Metric subspace
:label: def-ms-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$
{prf:ref}`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)$.
```
```{prf:example}
:label: ex-ms-metric-subspace-1
$[0,1]$ is a metric subspace of $\RR$ 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 $\RR$ and using the standard metric for $\RR$.
```
## Examples
```{prf:example} $\RR^n$ p-distance
:label: ex-ms-rn-p-distance-as-metric
For some $1 \leq p \lt \infty$, the function $d_p : \RR^n \times \RR^n \to \RR$:
$$
d_p (x, y) \triangleq \left ( \sum_{i=1}^n |x_i - y_i|^p \right )^{\frac{1}{p}}
$$
is a metric and $(\RR^n, d_p)$ is a metric space.
```
```{prf:example} $\RR^n$ Euclidean space
:label: ex-ms-rn-as-euclidean-space
The $d_2$ metric over $\RR^n$:
$$
d_2 (x, y) \triangleq \left ( \sum_{i=1}^n |x_i - y_i|^2 \right )^{\frac{1}{2}}
$$
is known as the *Euclidean distance* and
the metric space $(\RR^n, d_2)$ is known as the
*n-dimensional Euclidean (metric) space*.
The standard metric for $\RR^n$ is the Euclidean metric.
```
```{prf:example} Discrete metric
:label: ex-ms-discrete-metric-1
Let $X$ be a nonempty set:
Define:
$$
d(x,y) = \begin{cases}
0 & x = y \\
1 & x \neq y
\end{cases}.
$$
$(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
{ref}`sec:ms:discrete-metric-space`. They help clarify
many subtle issues in the theory of metric spaces.
```{prf:example} $\ERL$ A metric space for the extended real line
:label: ex-ms-erl-as-metric-space
Consider the mapping $\varphi : \ERL \to [-1, 1]$ given by:
$$
\varphi(x) = \begin{cases}
\frac{t}{1 + |t|} & x \in \RR \\
-1 & x = -\infty \\
1 & x = \infty
\end{cases}.
$$
$\varphi$ is a bijection from $\ERL$ onto $[-1, 1]$.
$[-1, 1]$ is a metric space with the standard metric
for the real line $d_{\RR}(x, y) = |x - y|$ restricted to $[-1, 1]$.
Consider a function $d: \ERL \times \ERL \to \RR$ defined as
$$
d (s, t) = | \varphi(s) - \varphi(t)|.
$$
The function $d$ satisfies all the requirements of a metric.
It is the standard metric on $\ERL$.
```
```{prf:example} $\ell^p$ Real sequences
:label: ex-ms-l1-real-seq-metric-space
For any $1 \leq p < \infty$, we define:
$$
\ell^p = \left \{ \{ a_n \} \in \RR^{\Nat} \ST \sum_{i=1}^{\infty} |a_i|^p \right \}
$$
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 \RR$ as
$$
d_p (\{a_n \}, \{ b_n \}) = \sum_{i=1}^{\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.
```
## Products of Metric Spaces
```{index} Metric space; finite product
```
```{prf:definition} Finite products of metric spaces
:label: def-ms-finite-product-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 \dots \times X_n$.
Define a map $\rho : X \times X \to \RR$ 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)$.
```
## Distance between Sets and Points
```{index} Distance; point and set
```
```{prf:definition} Distance between a point and a set
:label: def-ms-point-set-distance
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) \Forall a \in A \}.
$$
```
* Since $A$ is nonempty, hence the set
$D = \{ d(x,a) \Forall a \in A \}$ is not empty.
* $D$ is bounded from below since $d(x, a) \geq 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 \leq d(x, A) \leq d(x, a)$.
* If $x \in A$, then $d(x, A) = 0$.
```{prf:theorem}
:label: res-ms-set-distance-member-zero
If $x \in A$, then $d(x, A) = 0$.
```
```{prf:example}
:label: res-ms-set-distance-zero-1
1. Let $X = \RR$ and $A = (0, 1)$.
1. Let $x = 0$.
1. Then $d(x, A) = 0$.
1. However, $x \notin A$.
1. Thus, $d(x,A) = 0$ doesn't imply that $x \in A$.
```
Distance of a set with its accumulation points is 0.
See {prf:ref}`res-ms-set-accumulation-point-distance`.
## Distance between Sets
```{index} Distance; set and set
```
```{prf:definition} Distance between sets
:label: def-ms-set-set-distance
The distance between two nonempty sets $A,B \subseteq X$
is defined as:
$$
d(A, B) \triangleq \inf \{ d(a,b) \ST a \in A, b \in B \}.
$$
```