"Large" metric spaces

Question

I'm studying Functional Analysis from Joseph Muscat's book. The author says the non separable spaces are very large. This makes sense too as finite metric spaces and countable spaces are trivially separable and so the only metric spaces which can be non-separable must be uncountable. This is what he says to justify to say that non-separable spaces are too large.

Can someone explain to me what he means by computing distances "precisely", "approximately" and "to any accuracy"? Given two points, we know distance between those points, so, where does the impreciseness occur here?

Answer 1

I emailed the author and he saw this question and his response was the following (which I decided to add as an answer and which I believe might be helpful):

The answer given by CyclotomicField is accurate for the first two examples, but is out of point for the non-separable spaces because he/she is using a different concept of separability.

The main issue is that an algorithm can only work with finite data. So it can only handle a countable number of points, each of which is described by a finite amount of data. Let's take some examples to illustrate what's written:

The rationals $\mathbb{Q}$ are an example of a countable metric space: each number requires just two integers to describe it, and the distance between two rationals can be worked out precisely, i.e., exactly. Rationals with extremely large numerators and denominators will take longer to work out because additions and multiplications of them take longer.

The reals $\mathbb{R}$ are an example of a separable metric space: most real numbers cannot be specified by a finite amount of data, but that doesn't mean we cannot work out, say, $|\pi - e|$ as an approximation. First find rational numbers close to each of them, say, $3.141592654$ and $2.718281828$, then subtract. If one wants a better approximation, take better rational approximations of them. So it is not possible in general to find the exact value of the distance between two reals, but one can approximate it as closely as one wishes.

Finally take an example of a non-separable metric space, the set of bounded integer sequences with the infinity norm; that is, $d(\mathbf{x},\mathbf{y})=\sup_n|x_n-y_n|$. Then the algorithm needs to calculate the differences $|x_n-y_n|$ (where $x_n$ and $y_n$ are both integers) but it can never decide that it has reached the supremum, not even approximately. Even if it calculates the differences for $n=1,\ldots ,10^6$, and then take the maximum, there are still an infinite number of terms that follow them to check. For example, suppose the differences happen to be $0$ for $n$ less than a million; the algorithm cannot decide that $d(x,y)=0$ (even approximately), because there could be a large difference at the $2$ millionth position. This argument does not apply to the reals example above; if two reals have agreeing decimals up to the millionth place, then $x$ is very close to $y$ and the algorithm can conclude that the distance is less than $10^{-1000000}$.

Answer 2

It's useful to examine some concrete examples. Consider $\mathbb{Q}$ as a metric space. I can calculate the distance between two points exactly because $|y-x|$ is a rational number which takes up a finite amount of space as two relatively prime numbers are sufficient to describe it exactly. If the numbers are arbitrarily large this could take a long time to do.

Now if we consider $\mathbb{R}$ as a metric space we run into a problem, which is that most numbers are not computable. This means there is no finite length algorithm to describe the number, so encoding it would require an infinite amount of storage. However $\mathbb{Q}$ is a dense subset in $\mathbb{R}$ and because the space is separable we can approximate some real number by a rational number close to it. Formally this means that given some error term $\epsilon > 0$, typically small, that for every $x \in \mathbb{R}$ there exists a rational number $q \in \mathbb{Q}$ such that $|x-q| < \epsilon$. We can't describe the real number exactly but we can find a rational that is close enough for practical purposes.

Now, non-seperable spaces run into an overcrowding problem. Because points can't be separated we can't always tell them apart. This means there isn't some unique representation for the number so calculations using distances alone aren't sufficient to specify which is which. Consider a sequence of open sets given by $(-1/n,1/n)$ with $n \in \mathbb{N}$. The intersection of all these sets would be $\{0\}$ which is unique, but what if every open set contained other open number that we couldn't separate from zero, say $0'$. This means all the open sets would have to contain both of them and the intersection would be $\{0,0'\}$. Since the solution is not unique we can't tell if the answer is $0$ or $0'$ using topological methods. For metric spaces this means distances are insufficient to find unique solutions.

Answer 3

What Muscat means is that if a metric space $(X,d)$ has finitely many points, then you can specify the metric in a form of a finite list. In fact, if there are $n$ points $x_1, \ldots, x_n$, then this list has $\frac{n(n-1)}{2}$ entries $d_{ij} = d(x_i,x_j)$ with $1 \le i < j \le n$.

Listing is no longer possible if there are infinitely many points.

However, if there are "only" countably many points $x_1, x_2, x_3, \ldots$, then one still has the chance that there is an algorithm determing the exact value of all $d(x_i,x_j)$. This requires a function $f : \mathbb N^2 \to \mathbb R$ which is effectively computable.

If there are uncountably many points, then no algorithm will help to calculate the precise value of $d(x,x')$ for all $x,x' \in X$ - simply because there are uncountably many of these values. Muscat says that in a separable metric space one can at least determine distances $d(x,x')$ approximately up to any desired precision. What does this mean? $X$ contains a countable dense subset $D \subset X$ and there may an algorithm computing $d(p,p')$ for all $p, p' \in D$. But each $x \in X$ can be approximated arbitrarily close by elements of $D$; therefore given $x, x' \in X$ and $\epsilon > 0$, there exist $p, p' \in D$ such that $d(x,p) < \epsilon/2, d(x',p') < \epsilon/2$. Then $\lvert d(x,x') - d(p,p') \rvert < \epsilon$ and if we know the precise value of $d(p,p')$ we have found an approximation for $d(x,x')$ with a deviation smaller $\epsilon$ from the precise value.

At first glance this seems to be an absolutely reasonable approach, but in my opinion it is questionable. The problem is to explicitly find $p, p'$ as above. Sure, we know that such points exist, but in practice it only works if

1. we can explicitly specify a sequence $(p_n)$ in $D$ such that $p_n \to x$

2. we can explicitly specify an error estimate for each $n$, i.e an upper bound for $d(x,p_n)$.

Let us consider $X = \mathbb R$ with $d(x,x') = \lvert x - x' \rvert$. The rationals $\mathbb Q$ form a countable dense subset. For many irrational numbers $x$ we can successfully carry out the above steps 1. and 2.; as examples take roots of rational numbers, $e$, $\pi$. But this is a circular dependency: It works for irrational numbers $x$ which can be specified by some algorithm; if we do not have such an algorithm, we do not even have a name for $x$ and are floating in a sort of nirvana.

My conclusion: The approximation approach only works for the subset $X' \subset X$ of points which can be specified algorithmically. All other points are not really tangible, beyond their mere existence we do not know anything concrete about them and will not be able to find approximations for their distance to other points. BUT: This is no drama because we only want to have information about the distance of points which we can explicitly describe.