When Does a Metric Space Have Infinite Metric Dimension?

examplesmetric-spacesmg.metric-geometry

Definition 1 A subset $B$ of a metric space $(M,d)$ is called a metric basis for $M$ if and only if $$[\forall b \in B,\,d(x,b)=d(y,b)] \implies x = y \,.$$

Definition 2 A metric space $(M,d)$ has "metric dimension" $n \in \mathbb{N}$ if there exists a minimal (in terms of cardinality) metric basis consisting of $n+1$ points. If $M$ does not have metric dimension $n$ for any $n \in \mathbb{N}$, then it has "infinite metric dimension".

Question: What general characteristics or properties of a metric space would automatically force it to have infinite metric dimension? (Perhaps any infinite set with the discrete metric?)

At the very least, are there any straightforward, but perhaps non-representative, examples of metric spaces which obviously must have infinite metric dimension?

(Perhaps unsurprisingly, Euclidean spaces have been shown to have finite metric dimension.)

Note: The definition 1 comes from the paper A Metric Basis Characterization of Euclidean Space by Grattan P. Murphy, Pacific Journal of Mathematics Vol.60, No. 2, 1975. Definition 2 is based on my (possibly faulty) understanding/interpretation of the following results in that paper.

Best Answer

I'll try to make a couple of remarks. it'll be easier for me to write only a bit at a time.

The metric category of metric spaces and metric maps (i.e. Lipschitz with constant $1$, i.e. never stretching) has a certain rigidity to it so that the idea of a metric base seems attractive. However, I feel that the metric dimension makes sense only for a somewhat limited class of, rather than for all, metric spaces. (Possibly, more than one of several competing definitions can make sense).

Consider (see the Question above):

Property G   A subset $B$ of a metric space $(M,d)$ is called a metric g-set for $M$ if and only if $$ \forall_{b \in B}\ d(x,b)=d(y,b)\ \ \implies\ \ x = y $$

Every such set $B$ was called a metric basis above. Let $B$ be one, and let $\ B\subseteq C\subseteq M.\ $ Then $$ \forall_{c \in C}\ d(x,c)=d(y,c)\ \ \implies\ \ x = y $$

Thus, $\ C\ $ has the metric g-set property too. We see that declaring Property G as a definition of metric basis goes against the spirit of basis in general. Instead, Property G corresponds to the general notion of a generating set.

 

It took quite a long time to arrive at the topological definition of a curve and of the topological dimension (from Cantor's curves in $\ \mathbb R^2,\ $ to Brouwers-Urysohn-Menger, then to the algebraic topological dimensions, etc.).

It took also considerable time to arrive at a general definition of basis which ultimately led to matroids.

In this thread, the topic is rather something like the metric variations of the independent sets and of a basis. Perhaps one should eye matroids for a comparison. These days things go much faster than in the past but the process of obtaining one or more of such sound metric notions may still take some tries and patience.

Thus let's examine the property of a basis, and more generally, of independent sets for matroids: let $X$ be a matroid; then

  1. if $\ A\subseteq X\ $ is an independent set, and $\ b\in X,\ $ then there exists $\ a\in A\ $ such that $\ (A\setminus\{a\})\cup\{b\}\ $ is independent;

  2. if $\ A\subseteq X\ $ is an independent set (resp. basis), and $\ b\in X\ $ depends on $\ A\ $ (resp. $\ b\in X\ $ is arbitrary), then there exists $\ a\in A\ $ such that $\ (A\setminus\{a\})\cup\{b\}\ $ generates the same set as $\ A\ $ (resp. $\ (A\setminus\{a\})\cup\{b\}\ $ is a basis).

Now let's look at some metric spaces.

EXAMPLE 1   Let $\ X:=\{0\ 1\ 2\ 3\},\ $ and let $\ d\ $ be a metric (thus, symmetric, etc) in $\ X,\ $ such that: \begin{eqnarray} d(0\ n) &:=& 2-\frac 1n&\qquad \mbox{for }\ \ n=1\ 2\ 3\\ d(k\ n) &:=& 2&\qquad \mbox{for every}\ \ 0<k<n\le3 \end{eqnarray} We see that there is a $1$-element basis $\ \{0\}\ $ in $\ (X\ d)\ $ in the sense of Question while there is no other $1$-element basis. However, in the spirit of matroids (see the above properties 1. and 2.), every $1$-element subset of $X$ should be a basis. Well, this is not so.

ALSO:   Every $2$-element set $\ X\subset\{0\ 1\ 2\}\ $ is a minimal G-set (basis). These three $2$-element sets and $\ \{0\}\ $ are the only minimal G-sets; thus, there are four of them altogether.

 

Turning to continuous spaces will not help:

EXAMPLE 2   Let $\ X:=[1;\infty)\ $ be a closed half-line, and let $\ d\ $ be a metric (thus, symmetric, etc) in $\ X,\ $ such that: \begin{eqnarray} d(1\ x) &:=& 2-\frac 1x&\qquad \mbox{for every}\ \ x > 1\\ d(x\ y) &:=& 2&\qquad \mbox{for every}\ \ 1<x<y \end{eqnarray} We see that there is a $1$-element basis $\ \{1\}\ $ in $\ (X\ d)\ $ in the sense of Question while there is no other $1$-element basis. Again, in the spirit of matroids, every $1$-element subset of $X$ should be a basis.

Thus, continuity didn't help.

ALSO:   In addition to $\ \{0\},\ $ the only other minimal G-sets are sets $\ X\subset[0;\infty)\ $ such that $\ |[0;\infty)\setminus X|=1$.

 

CONCLUSION If (a big if) we had to continue with the definition of basis from Question then we would have to restrict the class of the metric spaces under consideration. The first candidate which comes to mind would be the class of transitive space (i.e. such that for every two points there is an isometry of the space onto itself, which sends one of the points onto the other one).

(I might continue later on)