0

I am working on this problem for weeks without a good solution.

Let $S\subset\Bbb R^d$ be a set in which $\rho(s_1,s_2)\in\Bbb Q$ for any $s_1,s_2\in S$, where $\rho$ is the Euclidean distance in $\Bbb R^d$. Show that $S$ is countable.

If possible, can I request a proof not only some hints, since I've been working on it for weeks. I have some vague idea to attack it, but I can't make it rigorous.

Thank you!

YYF
  • 2,917

2 Answers2

2

This is based on Yuval Filmus' idea.

Let $n+1$ the maximum number of affinely independent points among the given ones. We have $n\le d$. Let $p_1$,$\ldots$, $p_{n+1}$, $n+1$ affinely independent and $A$ their affine span. Our set will be contained in $A$. For any $n+1$ nonnegative numbers $d_1$, $\ldots$, $d_{n+1}$ there exists at most one point $p$ in $A$ so that $d(p, p_i) = d_i$. We have therefore an imbedding of $A$ into $\mathbb{R}^{d+1}$ ( into an algebraic subset of $\mathbb{R}^{d+1}$ -- we have an algebraic relation between the distances of $d+2$ points in an affine $d$-dimensional space). Our set gets mapped injectively into $\mathbb{Q}^{d+1}$ so it is countable.

orangeskid
  • 53,909
0

Consider any fixed $d$ points $p_1,\ldots, p_d$ and distances $x_1,\ldots, x_d$. There is a finite number of points at distance $x_i$ from $p_i$ for each $i$. In your case there are countably many choices for the distances.

Yuval Filmus
  • 57,157
  • why there are finite number of points at distance $x_i$ from $p_i$? – YYF Sep 14 '14 at 18:03
  • @Y.Fan the intersection of $d$ balls has dimension zero and so is finite. For example, two circles in the plane intersect in at most two points. – Yuval Filmus Sep 14 '14 at 18:17
  • I thought the intersection of $n$-dimensional balls should be a $n-1$-dimensional sphere, right? So, how to prove the result for higher dimension such as $d\geq3$. – YYF Sep 14 '14 at 18:26
  • @Y.Fan You have to intersect more than two of them. My answer intersects $d$ of them. – Yuval Filmus Sep 14 '14 at 18:37
  • But how do you prove that every point in $S$ is some intersection of $d$ balls in $\Bbb R^d$? From my understanding, basically you are solving a system of linear equations with coefficients being coordinates of $p_1,...,p_d$ and unknowns being the coordinates of any points in $S$, right? But, how do you prove that the coefficient matrix has full rank? – YYF Sep 14 '14 at 18:47
  • Intuitively, I understand your method. But, somehow, I can't fill in all the technical details. – YYF Sep 14 '14 at 18:47
  • @Y.Fan it's not a set of linear equations since squared distance is a quadratic form. You're right that something needs to be proved here. What you need is some elementary algebraic geometry. At any rate, this is the idea of the solution. In my view the idea is more important than its technical implementation. – Yuval Filmus Sep 14 '14 at 18:52