Advanced Analysis

Metric Spaces

1. Metric Spaces Defined

Definition
A metric space \((X,d)\) is a set \(X\) of elements called points and a function \(d : X \times X \rightarrow [0,\infty)\) called the metric. It must satisfy the following properties:
  1. For any \(x,y \in X\), \(d(x,y) \geq 0\) with equality if and only if \(x=y\).
  2. (Symmetry) For any \(x,y \in X\), \(d(x,y) = d(y,x)\).
  3. (Triangle Inequality) For any \(x,y,z \in X\),
    \[ d(x,z) \leq d(x,y) + d(y,z). \]
Example
For points \(x,y \in {\mathbb R}\), defining \(d(x,y) := |x-y|\) makes \(({\mathbb R},d)\) a metric space.
Example
If \(X\) is the space of continuous functions on some compact interval \(I\) and
\[ d(f,g) := \sup_{x \in I} |f(x) - g(x)|, \]
Then \((X,d)\) is a metric space.
Example
Let \(X\) be the space of all possible plain text files. We define an edit of a document \(f \in X\) to be any one of the following operations:
  • A single new character is inserted somewhere in \(f\) (e.g., ‘word’ \(\rightarrow\) ‘sword’)
  • An existing character is changed somewhere in \(f\) (e.g., ‘word’ \(\rightarrow\) ‘work’)
  • An existing character is removed somewhere in \(f\) (e.g., ‘word’ \(\rightarrow\) ‘ord’) Note that every edit operation can be undone by another edit operation.
Given two documents \(f,g \in X\), the edit distance from \(f\) to \(g\) is the minimum number of edits required to transform document \(f\) into document \(g\). For example, the distance from ‘happy’ to ‘sad’ is 4: change h to s, the first p to a d, then remove the remaining p and y (and no combination of only 3 edits could make the change because at least one of the 4 letters hppy would still have to appear in the final draft).

The pair (X,d) is a metric space:
  1. \(d(f,g) = 0\) means no changes are required to convert \(f\) to \(g\), so \(f=g\). Also trivially \(d(f,g) = 0\) when \(f\) and \(g\) are known to be equal.
  2. Any sequence of operations converting \(f\) to \(g\) can be reversed in an equal number of steps. That means that the minimal number of steps to go from \(g\) to \(f\) can never be more than the reverse direction, i.e., \(d(g,f) \leq d(f,g)\). However, repeating the process gives \(d(g,f) \leq d(f,g) \leq d(g,f)\), so \(d(f,g) = d(g,f)\).
  3. If the edit distance from \(f\) to \(h\) is \(A\) and the edit distance from \(h\) to \(g\) is \(B\), then concatenating the two edit processes shows that there is a way to edit \(f\) to arrive at \(g\) in \(A+B\) steps. This may not necessarily be minimal, though, so \(d(f,g) \leq A+B = d(f,h) + d(h,g)\).

2. Metric Balls, Open and Closed Sets

Given a metric space \((X,d)\) we define the metric ball \(B_\delta(x)\) for \(x \in X\) and \(\delta > 0\) to equal
\[ B_\delta(x) := \{ y \in X \ : \ d(x,y) < \delta \}. \]
Note specifically that the inequality is strict.
Example
If \((X,d)\) is the space of documents with edit distance and \(i\) is the document 'Declaration of Independence', then \(B_{1/2}(i)\) is the collection of all documents which can be transformed into \(i\) in fewer than \(1/2\)-many operations. Since the metric is only integer-valued, \(B_{1/2}(i) = \{i\}\).
Definition
  • A set \(U \subset X\) is called open when it can be written as a union of metric balls.
  • A set \(E \subset X\) is called closed when its complement can be written as a union of metric balls.
  • The interior \(E^{\rm{o}}\) of a set \(E \subset X\) is defined to be the union of all metric balls contained in \(E\). Equivalently, the interior is the union of all open sets contained in \(E\).
  • The closure \(\overline{E}\) of a set \(E \subset X\) is the intersection of all closed sets containing \(E\). Equivalently, it is the complement of the union of all metric balls not intersecting \(E\).
Analogues of all the basic topological facts for \({\mathbb R}^n\) continue to hold:
  1. Both \(\emptyset\) and \(X\) are open and closed.
  2. A set \(U \subset X\) is open if and only if every point \(x \in U\) admits some positive radius \(\delta\) such that \(B_\delta(x) \subset U\).
  3. Arbitrary unions and finite intersections of open sets are open.
  4. Finite unions and arbitrary intersections of closed sets are closed.
  5. Some sets are neither open nor closed; some are both open and closed.
Example
The space of documents with the edit distance is an example of what's called a discrete metric space. Discrete metric spaces are those in which every set is open (and consequently every space is closed). Topologically, discrete spaces tend not to be all that interesting, but they can still have very interesting properties as metric spaces.
Important
Given a metric space \((X,d)\) it is always possible to find other metrics on \(X\) which lead to the exact same notions of open and closed sets. For example, multiplying any existing metric by a fixed positive factor gives a new metric but the sets which are open with respect to this new metric must also be open with respect to the old one and vice-versa.
Example
Suppose that \(V\) is a normed vector space. Then \(d(x,y) := ||x-y||\) defines
a metric on \(V\) such that \((V,d)\) becomes a metric space.
  1. \(d(x,y) = 0\) if and only if \(x = y\) because \(||x-y|| = 0\) iff \(x=y\).
  2. \(d(x,y) = d(y,x)\) because \(||x-y|| = ||y-x||\).
  3. \(d(x,y) \leq d(x,z) + d(z,y)\) because \(||x-y|| \leq ||x-z|| + ||z-x||\). Often there are many different norms which generate the same topology on \(V\).

3. Compactness and Connectedness Defined

In a metric space \((X,d)\), a set \(E \subset X\) is called compact when every open cover of \(E\) admits a finite subcover. (Here “open cover” means what you expect it to–a collection of open sets whose union contains \(E\).)

In a metric space \((X,d)\), a set \(E\) is called disconnected when there exist open sets \(A\) and \(B\) such that
  1. Every point \(x \in E\) belongs to either \(A\) or \(B\).
  2. No point \(x \in E\) belongs to both \(A\) and \(B\).
  3. Neither of \(A\) or \(B\) contains the entire set \(E\) (and as a corollary, both \(A\) and \(B\) contain some point in \(E\).)
    A set which is not disconnected is called connected.
We will encounter both of these concepts in much greater depth shortly.