Metric Spaces, Part 2

Getting Cozy

In Part 1 we defined (pseudo-)metric spaces and how they allow us to generalize the notions of distance/similarity and continuity. In Part 2 we look at how they also allow us to generalize the notions of limits and convergence. This will allow us to say what it means for a sequence of premises to, in some sense, “converge.”

Terminology

Some terminology we’ll use:¹

• Euclidean metric: this is 𝑒(𝑥,𝑦) ≜ |𝑥-𝑦|.

• Strict pseudo-metric: a pseudo-metric that is not a metric (because 𝑑(𝑥,𝑦) = 0 for some 𝑥 ≠ 𝑦). Every pseudo-metric is either a metric or a strict pseudo-metric.

• The abstraction of a pseudo-metric space (𝑆₀,𝑑₀): the metric space of equivalence classes of 𝑆₀, as discussed in Part 1. Recall that we consider 𝑥,𝑦 ∈ 𝑆₀ to be equivalent, 𝑥 ∼ 𝑦, if 𝑑₀(𝑥,𝑦) = 0. Defining 𝑆 to be the set of equivalence classes of 𝑆₀, and 𝑑([𝑥],[𝑦]) ≜ 𝑑₀(𝑥,𝑦), then (𝑆,𝑑) is a metric space, and we call it the abstraction of (𝑆₀,𝑑₀). The elements of 𝑆₀ are concrete representations of the more abstract entities that are the elements of 𝑆. If (𝑆₀,𝑑₀) is already a metric space, then it and (𝑆,𝑑) are isometric.

Cauchy sequences

You may recall the notion of a Cauchy sequence from your calculus class. It is a way of defining what it means for a sequence of values to be “converging” in some sense… without needing to say just what it is converging to… and without requiring that the limiting value actually exist. That last feature is especially important, as it allows one to “fill in” missing limits through a process called completion.

The definition of a Cauchy sequence on an arbitrary pseudo-metric space is identical to the familiar definition on the real numbers, except replacing |𝑥-𝑦| with 𝑑(𝑥,𝑦):

Definition. A Cauchy sequence for a pseudo-metric space (𝑆,𝑑) is an infinite sequence (𝑥ᵢ) = 𝑥₁, 𝑥₂, … of values from 𝑆 such that

\(\begin{flalign*} & \mbox{for any }\varepsilon>0\\ & \quad\mbox{there exists }N>0\\ & \quad\quad\mbox{such that for all }m,n>N\\ & \quad\quad\quad d\left(x_{m},x_{n}\right)<\varepsilon. \end{flalign*}\)

That is, the values in the sequence become and remain arbitrarily close to each other if we go far enough out into the sequence.

Example: Cauchy sequence with no limit

A Cauchy sequence need not have a limit in its pseudo-metric space. Consider the sequence (𝑥ᵢ) of rational numbers defined by

\(\begin{align*} x_{1} & =1\\ x_{i+1} & =\left(x_{i}+2/x_{i}\right)/2. \end{align*}\)

This can be shown to be a Cauchy sequence for (ℚ,𝑒), the rational numbers with Euclidean distance; the first few members are (approximately)

\(1,\;1.5,\;1.41667,\;1.41422,\;1.41421,\;\ldots\)

If you solve for 𝑥 in

\(x=\left(x+2/x\right)/2\)

you find 𝑥 = √2, which is not a rational number. Thus we have defined a Cauchy sequence for ℚ that has no limit. There are, of course, many such Cauchy sequences for ℚ.

Example: strict pseudo-metric

For an example not involving a metric space, consider the strict pseudo-metric space (ℚ₀,𝑒₀) of ordered pairs of integers representing rational numbers, where ℚ₀ is the set of integer pairs (𝑎,𝑏) with 𝑏 ≠ 0, and

\(\begin{gather*} e_{0}\left((a_{1},b_{1}),(a_{2},b_{2})\right)\triangleq e\left(\frac{a_{1}}{b_{1}},\frac{a_{2}}{b_{2}}\right)=\left|\frac{a_{1}}{b_{1}}-\frac{a_{2}}{b_{2}}\right|. \end{gather*}\)

Note that the function

\(f\left(a,b\right)=\frac{a}{b}\)

is an isometry of (ℚ₀,𝑒₀) onto (ℚ,𝑒). Now consider a sequence (𝑦ᵢ) in ℚ₀ that 𝑓 maps to the sequence (𝑥ᵢ):

\(\begin{align*} y_{i} & =\left(a_{i},b_{i}\right)\\ a_{1} & =1\\ b_{1} & =1\\ a_{i+1} & =a_i^{2}+2b_i^{2}\\ b_{i+1} & =2a_ib_i. \end{align*}\)

It is straightforward to verify by induction that 𝑎ᵢ/𝑏ᵢ = 𝑥ᵢ, hence

\(e_{0}\left(y_{m},y_{n}\right)=e\left(x_{m},x_{n}\right)\)

and hence (𝑦ᵢ) is a Cauchy sequence for (ℚ₀,𝑒₀).

The above illustrates a general property: if (𝑆₀,𝑑₀) is a pseudo-metric space and (𝑆,𝑑) is its abstraction, then (𝑥ᵢ) is a Cauchy sequence for (𝑆₀,𝑑₀) iff ([𝑥ᵢ]) is a Cauchy sequence for (𝑆,𝑑), because the mapping 𝑥 ↦ [𝑥] is an isometry from (𝑆₀,𝑑₀) into (𝑆,𝑑).

Limits and convergence

Definition. If (𝑥ᵢ) is a sequence in pseudo-metric space (𝑆,𝑑), and 𝑦 ∈ 𝑆, we say that (𝑥ᵢ) converges to 𝑦 (in (𝑆,𝑑)) if

\(\begin{flalign*} & \mbox{for all }\varepsilon>0\\ & \quad\mbox{there exists }N>0\\ & \quad\quad\mbox{such that for all }n>N\\ & \quad\quad\quad d\left(x_{n},y\right)<\varepsilon. \end{flalign*}\)

That is, the elements of the sequence become and remain arbitrarily close to 𝑦. In this case we also say that 𝑦 is a limit of the sequence (𝑥ᵢ); if 𝑑 is in fact a metric then this limit is unique (the limit, not just a limit) and we write

\(y=\lim_{n\to\infty}x_{n}.\)

We can summarize this by saying that

\(\lim_{n\to\infty}x_{n}=y\quad\Longleftrightarrow\quad\lim_{n\rightarrow\infty}d\left(x_{n},y\right)=0\)

where the limit on the right is the one you learned in beginning calculus, the limit with respect to the real numbers with Euclidean distance.

Example: let 𝑥ₙ ≜ 1-1/𝑛; then the sequence (𝑥ᵢ) converges to 1 in the metric space (ℚ,𝑒).

Sometimes we only care that (𝑥ᵢ) converge to some 𝑦 ∈ 𝑆; we express this by saying that (𝑥ᵢ) is a convergent sequence. Note that the triangle inequality guarantees that every convergent sequence is also a Cauchy sequence, although the converse is not generally true.

Dense subsets

Related to the notion of convergent sequences is that of a dense subset of a pseudo-metric space (𝑆,𝑑).

Definition. We say that 𝑇 ⊆ 𝑆 is dense in (𝑆,𝑑) if

\(\begin{flalign*} & \mbox{for every }x\in S\mbox{ and }\varepsilon>0\\ & \quad\mbox{there exists }y\in T\\ & \quad\quad\mbox{such that }d\left(x,y\right)<\varepsilon. \end{flalign*}\)

That is, every 𝑥 ∈ 𝑆 can be approximated arbitrarily closely by some element of 𝑇. Equivalently, every 𝑥 ∈ 𝑆 is the limit of some sequence in 𝑇. The standard example of a dense subset is the rational numbers: ℚ is a dense subset of (ℝ,𝑒).

A dense subset provides a potentially much smaller, simpler set that can approximate the full pseudo-metric space arbitrarily closely. The rational numbers are an easily-described and enumerable set.² The real numbers, on the other hand, are uncountable and hence literally indescribable: no matter how we extend our mathematical notation, for almost all real numbers 𝑥 there will exist no mathematical expression equal to 𝑥.³

Cauchy equivalence

In Part 1 we discussed two kinds of equivalence for pseudo-metrics:

• topologically equivalent pseudo-metrics result in the same notion of continuity;

• uniformly equivalent pseudo-metrics result in the same notion of uniform continuity.

For our purposes a third kind of equivalence will be more important:

Definition. Pseudo-metrics 𝑑₁ and 𝑑₂ on the same set 𝑆 are Cauchy equivalent if they have the same Cauchy sequences: i.e., a sequence is Cauchy w.r.t. 𝑑₁ iff it is Cauchy w.r.t. 𝑑₂.

Later on we will define a pseudo-metric on the space of premises, but it will turn out that use of that specific pseudo-metric is not important—any Cauchy-equivalent pseudo-metric will do just as well for our purposes.

Cauchy equivalence is intermediate in strength between the other two:

\(\mbox{uniform equiv}\Longrightarrow\mbox{Cauchy equiv}\Longrightarrow\mbox{topological equiv.}\)

The converse, however, does not generally hold: we can find (pseudo-)metrics that are Cauchy equivalent but not uniformly equivalent, or topologically equivalent but not Cauchy equivalent. This is discussed in detail here.

One way of describing the difference between topological equivalence and Cauchy equivalence is this:

• Topological equivalence: the two pseudo-metrics have the same convergent sequences.

• Cauchy equivalence: the two pseudo-metrics have the same Cauchy sequences.

Thus we can have topological equivalence without Cauchy equivalence only if there are non-convergent Cauchy sequences. As an example, let ℝ⁺ be the set of strictly positive real numbers and for 𝑥,𝑦 ∈ ℝ⁺ define

\(e'\left(x,y\right)\triangleq e\left(x^{-1},y^{-1}\right).\)

Consider the sequence (𝑥ᵢ) in ℝ⁺ defined by 𝑥ₙ = 𝑛. We have

• 𝑒′(𝑥ₘ,𝑥ₙ) < 1/min(𝑚,𝑛) and so (𝑥ᵢ) is a Cauchy sequence for 𝑒′; but

• 𝑒(𝑥ₘ,𝑥ₙ) ≥ 1 for 𝑚 ≠ 𝑛, and so (𝑥ᵢ) is not a Cauchy sequence for 𝑒.

Nonetheless, since the inverse is a continuous function on ℝ⁺, the metrics 𝑒 and 𝑒′ have the same convergent sequences, and hence are topologically equivalent.

Coming next

In Part 3 we’ll see how we can extend any (pseudo-)metric space so that all Cauchy sequences have limits. This will allow us to define the notion of a generalized premise as the limit of a Cauchy sequence of finite premises.

1. Except for “Euclidean metric,” these are my own terms, not standard terminology.

2. We can list all the rational numbers, one by one, using Cantor's diagonal construction.

3. A mathematical expression is a string of symbols taken from either a finite or countably infinite set of symbols, and there are only countably many such strings.