Metric Spaces, Part 3
To Infinity—And No More!
In Part 1 we defined (pseudo-)metric spaces and how they generalize the notions of distance/similarity and continuity. In Part 2 we discussed how they generalize the notions of limits and convergence with Cauchy sequences. In this final installment, Part 3, we discuss how to “fill in” any missing limits. This will allow us to extend our finite premises to generalized premises, which are states of information that can deal with infinite domains with an infinite number of distinctions, while being approximated arbitrarily closely by finite premises.
Completeness
Definition. If every one of its Cauchy sequences is convergent, then we say that pseudo-metric space (𝑆,𝑑) is complete.
The standard example of an incomplete metric space is (ℚ,𝑒), the rational numbers with Euclidean distance. Another example would be the positive real numbers, (ℝ⁺,𝑒); this is an incomplete metric space because one can construct Cauchy sequences that get arbitrarily close to 0, which is not in ℝ⁺.
The standard example of a complete metric space is (ℝ,𝑒), the real numbers with Euclidean distance. (ℤ,𝑒), the integers with Euclidean distance, is another; it is trivially complete because any two distinct integers have a distance of at least 1, so any Cauchy sequence inevitably ends with infinite repetitions of the same integer.
If there is an isometry 𝑓 from pseudo-metric space (𝑆₁,𝑑₁) onto pseudo-metric space (𝑆₂,𝑑₂), then either they are both complete or they are both incomplete: 𝑓 maps Cauchy sequences in (𝑆₁,𝑑₁) to Cauchy sequences in (𝑆₂,𝑑₂), and likewise maps non-Cauchy sequences to non-Cauchy sequences.
Completeness is a very convenient property to have. Imagine how awkward it would be to discuss the length of the hypotenuse of a right triangle with legs of equal length 1 if we were limited to the rational numbers—the best we could say is that it lies between positive numbers 𝑥 and 𝑦 whenever 𝑥² < 2 and 𝑦² > 2:
Likewise, when we define our pseudo-metric space of premises we will find that it is incomplete, and we will want to remedy this. We’ve already seen this awkwardness in previous articles on deriving the uniform distribution and the Poisson distribution, where we could find premises that produced probabilities arbitrarily close to a very simple form, but never quite reached it.
Completion of a pseudo-metric space
Since working with an incomplete pseudo-metric space can be awkward, we might want to extend it to a complete pseudo-metric space. This motivates the following:
Definition. We say that pseudo-metric space (𝑆′,𝑑′) is a completion of pseudo-metric space (𝑆,𝑑) if
(𝑆′,𝑑′) is complete,
𝑆 is a dense subset of (𝑆′,𝑑′), and
𝑑′(𝑥,𝑦) = 𝑑(𝑥,𝑦) for all 𝑥,𝑦 ∈ 𝑆.
This definition implies that any element of 𝑆′ that is not already in 𝑆 is a limit of some Cauchy sequence whose elements all come from 𝑆. It also implies that 𝑑′ is entirely determined by 𝑑:
If 𝑥,𝑦 ∈ 𝑆 then 𝑑′(𝑥,𝑦) = 𝑑(𝑥,𝑦). That is, a copy of (𝑆,𝑑) is embedded in (𝑆′,𝑑′).
If 𝑥 ∈ 𝑆 and 𝑦 ∉ 𝑆 then 𝑦 corresponds to some Cauchy sequence (𝑦ᵢ) in 𝑆, and
\(d'(x,y)=\lim_{n\to\infty}d\left(x,y_{n}\right).\)If 𝑥,𝑦 ∉ 𝑆 then 𝑥 corresponds to some Cauchy sequence (𝑥ᵢ) and 𝑦 to some Cauchy sequence (𝑦ᵢ) in 𝑆, and
\(d'(x,y)=\lim_{n\to\infty}d\left(x_{n},y_{n}\right).\)
A completion of a complete pseudo-metric space is more-or-less the same space. Specifically:
If (𝑆′,𝑑′) is a completion of (𝑆,𝑑) and (𝑆,𝑑) itself is already complete, then any 𝑥′ ∈ 𝑆′ that is not already in 𝑆 is superfluous in the sense that it is equivalent to some point already in 𝑆: 𝑑′(𝑥,𝑥′) = 0 for some 𝑥 ∈ 𝑆.
This implies that any complete metric space is its own completion, and its only completion.
Existence of unique completion for metric spaces
Roughly speaking, every pseudo-metric space has a unique completion. Roughly speaking. The specifics are simplest in the case of an actual metric space, so let’s start there.
Theorem. Every metric space (𝑆₀,𝑑₀) is isometric to a metric space (𝑆,𝑑) that has a completion.
Since isometric metric spaces are essentially duplicates of each other except for a trivial renaming of elements, it is common to treat (𝑆₀,𝑑₀) and (𝑆,𝑑) as if they were the same metric space, and just say that every metric space has a completion.
Theorem. If metric spaces (𝑆₁,𝑑₁) and (𝑆₂,𝑑₂) are both completions of the same metric space (𝑆,𝑑), then there is an isometry 𝑓 from 𝑆₁ onto 𝑆₂ that maps 𝑆 onto itself: 𝑓(𝑥) = 𝑥 whenever 𝑥 ∈ 𝑆. That is, not only are the two completions isometric, but there is an isometry between them that leaves 𝑆 fixed; it only renames the additional points not in 𝑆.
This is the sense in which a metric space has a unique completion.
(Pseudo-)isometric pseudo-metric spaces
Before generalizing the above theorems to arbitrary pseudo-metric spaces, we need to generalize the notion of isometric metric spaces.1
Definition. Pseudo-metric spaces (𝑆₁,𝑑₁) and (𝑆₂,𝑑₂) are isometric if there is a one-to-one isometry 𝑓 from (𝑆₁,𝑑₁) onto (𝑆₂,𝑑₂). (Recall that “onto” means that every element of 𝑆₂ is 𝑓(𝑥) for some 𝑥 ∈ 𝑆₁.)
This definition implies that the isometry 𝑓 is invertible, and that its inverse 𝑓⁻¹ is also a one-to-one isometry from (𝑆₂,𝑑₂) onto (𝑆₁,𝑑₁). The two pseudo-metric spaces are essentially copies of each other, except for a renaming of elements. This definition reduces to the one previously given specifically for metric spaces when applied to two metric spaces.
Definition. Pseudo-metric spaces (𝑆₁,𝑑₁) and (𝑆₂,𝑑₂) are pseudo-isometric if their abstractions are isometric. That is, there is a distance-preserving map that sets up a one-to-one correspondence between the equivalence classes of (𝑆₁,𝑑₁) and the equivalence classes of (𝑆₂,𝑑₂).
Two pseudo-isometric pseudo-metric spaces are not exactly copies of each other, but the differences, up to renaming, lie only in the sizes of the equivalence classes. We can also characterize what it means to be pseudo-isometric a bit more directly. First we define a weakened notion of “onto” function.
Definition. An isometry 𝑓 from (𝑆,𝑑₁) into (𝑆,𝑑₂) is said to be pseudo-onto if
That is, although 𝑆₂ may contain elements that are not in the range of 𝑓, any such element is equivalent to some value in the range of 𝑓. So 𝑓 is, in some sense, an onto function, if we substitute equivalence for equality.
Now for the alternative characterization:
Theorem. Pseudo-metric spaces (𝑆₁,𝑑₁) and (𝑆₂,𝑑₂) are pseudo-isometric iff there is a pseudo-onto isometry from (𝑆₁,𝑑₁) into (𝑆₂,𝑑₂).
This neatly parallels the definition of “isometric” for metric spaces: they are isometric iff there is an onto isometry from one to the other.
Existence of unique completion for pseudo-metric spaces
Now we can state the more general theorems for arbitrary pseudo-metric spaces.
Theorem. Every pseudo-metric space (𝑆₀,𝑑₀) is isometric to a pseudo-metric space (𝑆,𝑑) that has a completion.
This is identical to the corresponding theorem for metric spaces, just putting “pseudo” in front of “metric.”
Theorem. If pseudo-metric spaces (𝑆₁,𝑑₁) and (𝑆₂,𝑑₂) are both completions of the same pseudo-metric space (𝑆,𝑑), then they are pseudo-isometric. Furthermore, there is a pseudo-onto isometry 𝑓 from 𝑆₁ into 𝑆₂ that maps 𝑆 onto itself: 𝑓(𝑥) = 𝑥 whenever 𝑥 ∈ 𝑆. That is, not only are the two completions pseudo-isometric, but there is a pseudo-onto isometry between them that leaves 𝑆 fixed.
This then is the sense in which the completion of a pseudo-metric space is, roughly speaking, unique.
Constructing the completion of a pseudo-metric space
So let’s take a look at an explicit procedure for constructing the completion (𝑆₁,𝑑₁) of a pseudo-metric space (𝑆₀,𝑑₀). It’s pretty straightforward:
𝑆₁ is the set of Cauchy sequences for (𝑆₀,𝑑₀).
The distance between Cauchy sequences (𝑥ᵢ) and (𝑦ᵢ) is just what the distance between their limits would be, if they had limits:
\(d_{1}\left((x_{i}),(y_{i})\right)\triangleq\lim_{n\to\infty}d_{0}\left(x_{n},y_{n}\right).\)(I recommend you verify for yourself that this is a valid pseudo-metric.)
Define 𝜄 : 𝑆₀ → 𝑆₁ to be
\(\iota(x)\triangleq (x,x,x,\ldots),\)i.e. 𝜄 maps 𝑥 ∈ 𝑆₀ to an infinite sequence of 𝑥’s, which is trivially a Cauchy sequence.
Define 𝑆 to be the range of 𝜄:
\(S\triangleq\left\{ \iota(x)\colon x\in S_{0}\right\} \)Define 𝑑 to be the restriction of 𝑑₁ to 𝑆.
It’s easy to see that 𝑑(𝜄(𝑥),𝜄(𝑦)) = 𝑑₀(𝑥,𝑦), so 𝜄 is an isometry from (𝑆₀,𝑑₀) onto (𝑆,𝑑); that is, (𝑆₀,𝑑₀) and (𝑆,𝑑) are isometric, the latter being just a copy of the former with 𝑥 renamed to 𝜄(𝑥).
The important part, which I won’t prove here, is this:
Theorem. (𝑆₁,𝑑₁) is a completion of (𝑆,𝑑).
Ignoring for the moment the difference between 𝑥 and 𝜄(𝑥) = (𝑥,𝑥,…), treating them as the same thing, we have started with a pseudo-metric space (𝑆₀,𝑑₀), then extended 𝑆₀ by defining the limit (actually, a limit) of the Cauchy sequence (𝑥ᵢ) to be… the Cauchy sequence (𝑥ᵢ) itself.
To infinity and…
It’s no surprise then that Cauchy sequences in 𝑆 converge in 𝑆₁. If (𝑦ᵢ) is a sequence in 𝑆 then 𝑦ₙ = 𝜄(𝑥ₙ), where (𝑥ᵢ) is a sequence in 𝑆₀. If the sequence (𝑦ᵢ) is Cauchy in 𝑆 then the sequence (𝑥ᵢ) is Cauchy in 𝑆₀, and hence (𝑥ᵢ) itself belongs to 𝑆₁… and is obviously the limit of (𝑦ᵢ):
You might notice, though, that by extending 𝑆₀ with new elements we’ve also potentially created new Cauchy sequences. We now have limits for all the old Cauchy sequences, but what about the new ones? Are we going to have to repeat this process of adding missing limits? And then repeat it again… and again… and again, with no guarantee of ever finishing the process? Is this going to be an endless game of whack-a-mole?
Luckily, no. This is a one-shot process. We do not have to go “to infinity—and beyond!”, rather we go “to infinity—and we’re done!” (Somewhat tedious proof omitted.)
Note, by the way, that if (𝑆₀,𝑑₀) is a metric space and you want a completion that is also a metric space, just take the abstraction of (𝑆₁,𝑑₁).
Constructing the reals by completing the rationals
To finish, I’ll mention that this process is one way of constructing the real numbers, starting with the rational numbers:
Consider two Cauchy sequences of rational numbers (𝑥ᵢ) and (𝑦ᵢ) to be equivalent if
\(\lim_{n\to\infty}\left|x_{n}-y_{n}\right|=0,\)i.e., if the distance between them is zero using the pseudo-metric on Cauchy sequences we defined above.
Define a real number to be an equivalence class of Cauchy sequences of rational numbers, and identify a rational number 𝑥 with [𝜄(𝑥)] to inject the rational numbers into the real numbers.
Define the arithmetic operations on real numbers as the limits of the corresponding operations on the elements of the Cauchy sequences:
\(\left(x_{i}\right)+\left(y_{i}\right)\triangleq\lim_{n\to\infty}\left(x_{n}+y_{n}\right)\)and so on.
Next up
In the next article we’ll start applying this to constructing a notion of generalized premises.
The definitions given in this section are not standard; they are my own terminology, created to facilitate the discussion.