Way Too Many Points on The Plane

Calculus Level 2

Is there a set of points on the plane such that every positive real number appears as a distance between exactly one pair of them?

Note: The solution might involve the axiom of choice

No Yes

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

2 solutions

R Mathe
May 27, 2018

Fix d = 2 d=2 . The proof can be done for d > 2 d>2 by first projecting down to a 2 2 -dimensional subspace.

Defn 0. A set X R d X\subseteq\mathbb{R}^{d} is called a cobweb , if and only if for all r R + r\in\mathbb{R}^{+} there exists at most one pair of points { x , y } [ X ] 2 \{x,y\}\in[X]^{2} with d ( x , y ) = r d(x,y)=r .

Defn 1. For X R d X\subseteq\mathbb{R}^{d} set ϕ ( X ) = { d ( x , y ) ( x , y ) X × X Δ } \phi(X)=\{d(x,y)\mid (x,y)\in X\times X\setminus\Delta\} .

Hence X X is a cobweb if and only if for all r ϕ ( X ) r\in \phi(X) there exists exactly one pair of points { x , y } [ X ] 2 \{x,y\}\in[X]^{2} with d ( x , y ) = r d(x,y)=r .

Under this terminology we want to ultimately prove, that there exists a cobweb A R d A\subseteq\mathbb{R}^{d} with ϕ ( A ) = R + \phi(A)=\mathbb{R}^{+} .

Defn 2. For x , y R d x,y\in\mathbb{R}^{d} with x y x\neq y set E ( x , y ) : = { p R d d ( p , x ) = d ( p , y ) } E(x,y):=\{p\in\mathbb{R}^{d}\mid d(p,x)=d(p,y)\} .

Note that E ( x , y ) = { p R d p 1 2 ( x + y ) y x } E(x,y)=\{p\in\mathbb{R}^{d}\mid p-\frac{1}{2}(x+y)\perp y-x\} which is a hyperplane and for d = 2 d=2 a line.

Defn 3. For X R d X\subseteq\mathbb{R}^{d} set X : = X x X , r ϕ ( X ) B ( x , r ) ( x , y ) X × X Δ E ( x , y ) \langle X\rangle:=X\cup\bigcup_{x\in X,~r\in \phi(X)}\partial B(x,r)\cup\bigcup_{(x,y)\in X\times X\setminus\Delta}E(x,y) .

Lemma. If d = 2 d=2 and X R d X\subseteq\mathbb{R}^{d} is a non-empty cobweb of cardinality X < 2 0 |X|<2^{\aleph_{0}} , then for each r R + r\in\mathbb{R}^{+} , there exists a cobweb X X X'\supseteq X with r ϕ ( X ) r\in \phi(X') and X X + 1 < 2 0 |X'|\leq|X|+1<2^{\aleph_{0}} .

Proof. If r ϕ ( X ) r\in \phi(X) , then let X = X X'=X . Otherwise r ϕ ( X ) r\notin \phi(X) . In this case, fix p X p\in X . We will find q R d q\in\mathbb{R}^{d} with d ( p , q ) = r d(p,q)=r and so that X : = X { q } X':=X\cup\{q\} is a cobweb (which necessarily satisfies the cardinality condition and furthermore r = d ( p , q ) r ( X ) r=d(p,q)\in r(X') ). Let S : = B ( p , r ) S:=\partial B(p,r) . We will now show that S X S\setminus\langle X\rangle is nonempty. To do this it suffices to show that S X < 2 0 = S |S\cap \langle X\rangle|<2^{\aleph_{0}}=|S| .

  • S X = S\cap X=\emptyset , since r ϕ ( X ) r\notin \phi(X) .
  • For x X x\in X and s ϕ ( X ) s\in\phi(X) the intersection S B ( x , s ) S\cap B(x,s) is EITHER the necessarily empty intersection of two circles with the same centre (in the case of x = p x=p ) but different radii , since s r s\neq r by virtue of r ϕ ( X ) r\notin \phi(X) ; OR an intersection of two circles with different centres , and thus consists of at most 2 2 points. Since 2 X × ϕ ( X ) 2 X 3 < 2 0 2\cdot|X\times\phi(X)|\leq 2\cdot|X|^{3}<2^{\aleph_{0}} , we have S x X , s ϕ ( X ) B ( x , r ) < 2 0 |S\cap\bigcup_{x\in X,~s\in \phi(X)}\partial B(x,r)|<2^{\aleph_{0}} .
  • For ( x , y ) X × X Δ (x,y)\in X\times X\setminus\Delta the intersection S E ( x , y ) S\cap E(x,y) is an intersection between a circle and and a line, which contains at most 2 2 points. Since 2 X × X Δ 2 X 2 < 2 0 2\cdot|X\times X\setminus\Delta|\leq 2\cdot|X|^{2}<2^{\aleph_{0}} , we have once more S ( x , y ) X × X Δ E ( x , y ) < 2 0 |S\cap\bigcup_{(x,y)\in X\times X\setminus\Delta}E(x,y)|<2^{\aleph_{0}} .

From these three observations, it follows that S X < 2 0 |S\cap \langle X\rangle|<2^{\aleph_{0}} . Hence, S X S\setminus \langle X\rangle is non-empty. Thus there exists a point q S X q\in S\setminus\langle X\rangle . Observe

  • d ( q , p ) = r d(q,p)=r since q S = B ( p , r ) q\in S=\partial B(p,r) .
  • q X q\notin X since q X q\notin \langle X\rangle .
  • d ( x , q ) d ( y , q ) d(x,q)\neq d(y,q) for all ( x , y ) X × X Δ (x,y)\in X\times X\setminus \Delta by virtue of q E ( x , y ) q\notin E(x,y) .
  • d ( x , q ) d ( y , z ) d(x,q)\neq d(y,z) for all x , y , z X x,y,z\in X with y z y\neq z by virtue of q B ( x , s ) q\notin \partial B(x,s) for s : = d ( y , z ) r ( X ) s:=d(y,z)\in r(X) .

The last three points imply that X : = X { q } X':=X\cup\{q\} is a cobweb, and furthermore r = d ( p , q ) r ( X ) r=d(p,q)\in r(X') . QED.

Theorem. Working in ZFC \text{ZFC} there exists a set of points in R d \mathbb{R}^{d} for each d > 1 d>1 , with the property that every positive real occurs as the distance between exactly one pair of points.

Proof. By the discussion at the start it suffices to work with d = 2 d=2 . By AC \text{AC} , there exists an infinite cardinal κ > 0 \kappa>\aleph_{0} and a bijection α κ r α R + \alpha\in\kappa\mapsto r_{\alpha}\in\mathbb{R}^{+} . By the above definitions we need to show that there exists a cobweb, A A with ϕ ( A ) R + \phi(A)\supseteq\mathbb{R}^{+} . We shall construct, utilising the axiom of choice a monotone increasing sequence of countable cobwebs ( A α ) α < κ (A_{\alpha})_{\alpha<\kappa} of R d \mathbb{R}^{d} , such that ϕ ( A α ) { r ξ : ξ < α } \phi(A_{\alpha})\supseteq\{r_{\xi}:\xi<\alpha\} and A α α + 1 |A_{\alpha}|\leq\alpha+1 for all α < κ \alpha<\kappa . The construction is carried out per transfinite recursion:

  • Step α = 0 \alpha=0 . Fix A 0 : = { 0 } A_{0}:=\{0\} .
  • Step α > 0 \alpha>0 . Assume that ( A ξ ) ξ < α (A_{\xi})_{\xi<\alpha} has already been constructed with the desired properties. By the cardinality constraints and monotonicity, it holds that the union X : = ξ < α A ξ X:=\bigcup_{\xi<\alpha}A_{\xi} is of cardinality X α |X|\leq\alpha . As a union of an increasing sequence of cobwebs, it is also easy to see that X X remains a cobweb. Furthermore, by monotonicity ϕ ( X ) = ξ < α ϕ ( A ξ ) ξ < α { r γ : γ < ξ } \phi(X)=\bigcup_{\xi<\alpha}\phi(A_{\xi})\supseteq\bigcup_{\xi<\alpha}\{r_{\gamma}:\gamma<\xi\} . If α \alpha is a limit ordinal, then ϕ ( X ) { r ξ : ξ < α } \phi(X)\supseteq\{r_{\xi}:\xi<\alpha\} and one may set A α : = X A_{\alpha}:=X . Otherwise ϕ ( X ) { r ξ : ξ < α 1 } \phi(X)\supseteq\{r_{\xi}:\xi<\alpha-1\} . By the above Lemma , since X α < κ = 2 0 |X|\leq\alpha<\kappa=2^{\aleph_{0}} there exists a cobweb X X X'\supseteq X such that r α 1 ϕ ( X ) r_{\alpha-1}\in \phi(X') and X X + 1 α + 1 |X'|\leq|X|+1\leq|\alpha|+1 . In this case set A α : = X A_{\alpha}:=X' .

Finally set A : = α < κ A α A:=\bigcup_{\alpha<\kappa}A_{\alpha} . As a union of a monotone increasing sequence of cobwebs, A A is a cobweb. Furthermore, by monotonicity ϕ ( A ) = α < κ ϕ ( A α ) α < κ { r ξ : ξ < α } = { r ξ : ξ < κ } = R + \phi(A)=\bigcup_{\alpha<\kappa}\phi(A_{\alpha})\supseteq\bigcup_{\alpha<\kappa}\{r_{\xi}:\xi<\alpha\}=\{r_{\xi}:\xi<\kappa\}=\mathbb{R}^{+} . Hence A A is a cobweb with ϕ ( A ) = R + \phi(A)=\mathbb{R}^{+} . QED.


Note Δ A : = { ( x , x ) x A } \Delta_{A}:=\{(x,x)\mid x\in A\} for any set A A . If the Set is clear from the context, then one simply denotes this as Δ \Delta .

Thanks for the solution. I just started reading it. Can you clarify a few things:

  1. > there exists at most pair of points

I think you meant "there exists at most one pair of points".

  1. What do you mean by X × X Δ X\times X\setminus\Delta ? Do you mean all 2 element subsets of X X ?

Agnishom Chattopadhyay - 2 years, 11 months ago

Log in to reply

Thanks for the remark. Corrected the missing word. Both your inferences are correct. More precisely Δ : = G p h ( id ) \Delta:=\mathcal{G}\mathrm{ph}(\text{id}) the set of pairs with equal components, so the complement is actually the set of ordered pairs of distinct elements (for whatever the given set in the context is). By contrast, [ X ] 2 = { { x , y } x , y X , x y } [X]^{2}=\{\{x,y\}\mid x,y\in X,~x\neq y\} the set of sets of size 2, with no concern taken as to the order. (In general [ X ] κ = { A X : A = κ } [X]^{\kappa}=\{A\subseteq X: |A|=\kappa\} for any cardinal, including infinite cardinals.)

R Mathe - 2 years, 11 months ago

Log in to reply

My understanding of the axiom of choice is very rudimentary. Could you explain why AC implies the following?

By AC \text{AC} , there exists an infinite cardinal κ > 0 \kappa>\aleph_{0} and a bijection α κ r α R + \alpha\in\kappa\mapsto r_{\alpha}\in\mathbb{R}^{+} .

Or am I missing something very simple about cardinals?

Agnishom Chattopadhyay - 2 years, 11 months ago

Log in to reply

@Agnishom Chattopadhyay Background: Cardinals in themselves are not enough: we use ordinals to carry out transfinite recursion. Now, without AC there is no guarantee that set ( N ) \wp(\mathbb{N}) underlying the cardinal 2 0 2^{\aleph_{0}} is bijectively equivalent to an ordinal, i. e. more generally there is not guarantee that any set can be put into bijection with an ordinal. There isn’t even a guarantee, that one can even compare the cardinalities of any two arbitrary sets! (See lemma below.) But the axiom of choice guarantees all of this. In fact, this is guarantee is equivalent (within ZF set theory) to the axiom of choice. The reverse direction is trivial, if you think about it. I’ll show the non-trivial direction (although the proof is straightforward).

Satz. Under ZF AC is equivalent to WOP (well-ordering principle: for every set X X there exists an ordinal α \alpha , such that α = X |\alpha|=|X| in the sense of bijective equivalence). Pf. If WOP holds, then it is easy to show that AC holds. I’ll skip that part. Suppose now that AC holds. Let X X be an arbitrary set. If X X is empty, then X = 0 |X|=|0| , where 0 = 0=\emptyset is the 0th ordinal. Otherwise by AC there exists a choice function c : ( X ) { } X c:\wp(X)\setminus\{\emptyset\}\longrightarrow X . Suppose that X α |X|\leq|\alpha| for some ordinal α \alpha . Then let f : X α f:X\longrightarrow \alpha witness this injection. Since f ( X ) α f(X)\subseteq\alpha is well-ordered as a subspace, and all well-ordered sets are bijectively equivalent to an ordinal, one has that X X is bijectively equivalent to an ordinal. Suppose (†) that X α |X|\nleq|\alpha| for all ordinals α O r d \alpha\in\mathrm{Ord} . Then no injective function p : α X p:\alpha\longrightarrow X is surjective, so that X p ( α ) X\setminus p(\alpha)\neq\emptyset for all injective p : α X p:\alpha\longrightarrow X . This in-turn allows us to carry out the following recursion indefinitely:

  • x α : = c ( X { x ξ ξ α } ) x_{\alpha} := c(X\setminus \{x_{\xi}\mid \xi\in\alpha\}) for all α O r d \alpha\in\mathrm{Ord}

since for each stage α \alpha by induction p α : ξ α x ξ p_{\alpha}:\xi\in\alpha\mapsto x_{\xi} is injective, so that X p α ( α ) X\setminus p_{\alpha}(\alpha)\neq\emptyset by the above property. This means that the class { ( α , x α ) α O r d } \{(\alpha,x_{\alpha})\mid \alpha\in\mathrm{Ord}\} is the graph of an injection f : O r d X f:\mathrm{Ord}\longrightarrow X . By the comprehension axiom, r a n ( f ) X \mathrm{ran}(f)\subseteq X exists as a set and finally by the replacement axiom, this means that O r d \mathrm{Ord} must be a set—which is a contradiction. Hence the Assumption (†) was wrong, and X X is bijectively equivalent to an ordinal. QED


Lemma. Under ZF AC is equivalent to the following condition: for all sets X , Y X,Y either X Y |X|\leq|Y| or Y X |Y|\leq|X| , that is, there exist an injection from X Y X\longrightarrow Y or one from from Y X Y\longrightarrow X .

Pf. The sufficiency of this condition is trivial. I’ll skip it. For the necessary-part: Within ZF AC is equivalent to Zorn’s lemma. By Zorn’s lemma there exists a maximal element in P : = { p X × Y p the gph of an injective partial function \mathbb{P}:=\{p\subseteq X\times Y\mid p~\text{the gph of an injective partial function} ordered by inclusion. (One needs to check that the Zorn conditions hold, but this is easy.) Let f f be this maximal element. Note that as a partial injection, f f is a bijection f : A B f:A\longrightarrow B for some A X A\subseteq X and B Y B\subseteq Y . Claim: either A = X A=X or B = Y B=Y . Suppose not. Then there exists an a X A a\in X\setminus A and a b Y B b\in Y\setminus B . Let f : = f { ( a , b ) } f':=f\cup\{(a,b)\} . Then by construction, f f f'\supset f strictly and is an injection. But this contradicts the maximality of f f in P \mathbb{P} ! Hence the claim is true. If A = X A=X , we have X Y |X|\leq|Y| as witnessed by f f ; and if B = Y B=Y , we have Y X |Y|\leq|X| as witnessed by f 1 f^{-1} . QED

R Mathe - 2 years, 11 months ago

I borrowed this proof from Alon Amit's answer on Quora .

The proof involves transfinite induction . This means the proof involves the following steps:

  1. Fix an well ordering < w <_w on R \mathbb{R} .
  2. For each α R \alpha \in \mathbb{R} , build a set A α i n R A_\alpha in \mathbb{R} such that the following conditions holds:
    • α < w β A α A β \alpha <_w \beta \implies A_\alpha \subseteq A_\beta
  3. Let P ( A α ) P(A_\alpha) denote the fact that there are two elements in A α A_\alpha such that their distance is exactly α \alpha and furthermore, all the distances in A α A_\alpha are unique. Then, show the two following induction steps:
    • P ( A 0 ) P(A_0)
    • Given that P P holds for all A α A_\alpha with α < w β \alpha <_w \beta , we want to construct A β A_\beta such that P ( A β P(A_\beta ) holds.

Now, we can do step 1 using the axiom of choice . The first part of step 3 trivially holds.

To construct such a set A β A_\beta , we first consider the union S S of all sets A α A_\alpha where α < w β \alpha <_w \beta . Now, if β \beta occurs as a distance between two points of S S , we are already done. Otherwise, since β \beta is strictly lesser than 2 ω 2^\omega , there must be some point in the circle of radius β \beta away from one of the points in S S such that it does not create a duplication.


I agree that this proof has got a lot of technicalities which should be explained better. I am new to the idea of transfinite induction, and would really like to see a proof from someone more experienced.

Otherwise, since β \beta is strictly lesser than 2 ω 2^\omega , [ \leftarrow irrelevant ] there must be some point in the circle of radius β \beta away from one of the points in S S such that it does not create a duplication.

Everything else in your argument is the easy part. This part here, which you have given hand-wavy argument for, is the crux. And I don’t think it goes through. Please justify, that there must exist a point q x S B ( x ; β ) q\in\bigcup_{x\in S}\partial B(x;\beta) , such that S { q } S\cup\{q\} has the desired unique-distance property. Your ‘since’ claim bears no relevance to the argument. Furthermore the new point must not just avoid these circles, it must avoid certain lines, so as to avoid creating duplicate distances: for every x , y S x,y\in S with x y x\neq y it must hold that d ( q , x ) d ( q , y ) d(q,x)\neq d(q,y) . The set of points E ( x , y ) : = { p R 2 d ( p , x ) = d ( p , y ) } E(x,y):=\{p\in\mathbb{R}^{2}\mid d(p,x)=d(p,y)\} forms a line, so q q must avoid all of these lines. Luckily each line intersects the new circle at most 2 times, and there are fewer than continuum lines to avoid, so that eliminate fewer than continuum many points on the circle we want q q to lie in.

Btw. it’s not crucial, but your property P P is a bit sloppily stated. This property really has two arguments: the set, and the desired distance. Properties cannot ‘see’ what the index of the object is, that you insert into them.

R Mathe - 3 years ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...