Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.


share|cite|improve this question
up vote 4 down vote accepted

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.

share|cite|improve this answer
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$.

share|cite|improve this answer
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.

share|cite|improve this answer

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$.

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.