# Distance in at most countable metric spaces

I am trying to show that in an at most countable metric space $X$, there exists some distance $\delta \gt 0$, such that for all $x, y \in X$, $d(x, y) \neq \delta$.

I am trying to show this by contradiction: I suppose that for every $\delta \gt 0$, there exists some $x, y \in X$, such that $d(x, y)=\delta$, and then show there is an injection from the positive reals to $X$, implying that $X$ is uncountable and giving me my contradiction.

I was just wondering if someone could help me define that injection. I am having trouble making it well defined.

Thanks.

-

The image of the distance map $d:X\times X\to[0,\infty)$ has cardinality less or equal than the cardinality of $X\times X$, which is at most countable.

-
So as opposed to defining an injection from $\mathbb R^+$ to $X$, you suggest I define a surjection from $X$ to $\mathbb R^+$? – Ernest Singleton Jan 18 '13 at 0:58

you have a function $$d : X \times X \rightarrow \mathbb{R}^{+}$$ since $X$ is countable the image of $d$ is at most countable. So there is something in$\mathbb{R}^+$ that is not hit by $d$.

-
If a Mod happens to see this: You can merge this account with my usual one if you want. I couldn't remember my password when I posted this. – Deven Ware Jan 18 '13 at 5:08

Your approach will work, though as other answers have implicitly pointed out, it’s the hard way. If $X$ is countable, so is $X\times X$, so there is an injection $\varphi:X\times X\to\Bbb N$. For each real $r\ge 0$ let $$P_r=\big\{\langle x,y\rangle\in X\times X:d(x,y)=r\big\}\;;$$ your assumption, hoping to get a contradiction, is that $P_r\ne\varnothing$ for each real $r\ge 0$. It follows from that assumption that $\varphi[P_r]\ne\varnothing$ for each real $r\ge 0$. But every non-empty subset of $\Bbb N$ has a least element, so the function

$$\psi:[0,\to)\to\Bbb N:r\mapsto\min\varphi[P_r]$$

is well-defined. If $r$ and $s$ are distinct non-negative reals, then $P_r\cap P_s=\varnothing$. Moreover, $\varphi$ is an injection, so $\varphi[P_r]\cap\varphi[P_s]=\varnothing$, and therefore $\psi(r)\ne\psi(s)$. Thus, $\psi$ is an injection from $[0,\to)$ into $\Bbb N$, and you have your desired contradiction.

-

Find an enumeration of the set of unordered pairs $\{x,y\}$. Then you've got an enumeration of the set of distances $d(x,y)$ (some distances may appear more than once, but if you omit repeated ones, you've got a bijection from $\{1,2,3,\ldots\}$ to the set of distances). Thus the set of distances is a countable subset of $\mathbb R$.

-

The better tactic of arguing positively was given in two answers, so now it's time to turn our head into defining the injection:

First we write $X=\{x_n\mid n\in\mathbb N\}$. Now we define for $\delta>0$ the set $X_\delta=\{(x,y)\in X^2\mid d(x,y)=\delta\}$. Note that under our assumption there is no $\delta>0$ such that $X_\delta=\varnothing$.

Let $f(n,m)=k$ be a pairing function from $\mathbb N^2$ to $\mathbb N$, and define the following function:

$$F(\delta)=\min\{k\mid f^{-1}(k)\in X_\delta\}$$

You can easily verify this is an injection, and this is the wanted contradiction.

-