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
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.
Thanks for the solution. I just started reading it. Can you clarify a few things:
I think you meant "there exists at most one pair of points".
Log in to reply
Thanks for the remark. Corrected the missing word. Both your inferences are correct. More precisely Δ : = G p h ( 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 } the set of sets of size 2, with no concern taken as to the order. (In general [ X ] κ = { A ⊆ X : ∣ A ∣ = κ } for any cardinal, including infinite cardinals.)
Log in to reply
My understanding of the axiom of choice is very rudimentary. Could you explain why AC implies the following?
By AC , there exists an infinite cardinal κ > ℵ 0 and a bijection α ∈ κ ↦ r α ∈ R + .
Or am I missing something very simple about cardinals?
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 ) underlying the cardinal 2 ℵ 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 there exists an ordinal α , such that ∣ α ∣ = ∣ 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 be an arbitrary set. If X is empty, then ∣ X ∣ = ∣ 0 ∣ , where 0 = ∅ is the 0th ordinal. Otherwise by AC there exists a choice function c : ℘ ( X ) ∖ { ∅ } ⟶ X . Suppose that ∣ X ∣ ≤ ∣ α ∣ for some ordinal α . Then let f : X ⟶ α witness this injection. Since f ( X ) ⊆ α is well-ordered as a subspace, and all well-ordered sets are bijectively equivalent to an ordinal, one has that X is bijectively equivalent to an ordinal. Suppose (†) that ∣ X ∣ ≰ ∣ α ∣ for all ordinals α ∈ O r d . Then no injective function p : α ⟶ X is surjective, so that X ∖ p ( α ) = ∅ for all injective p : α ⟶ X . This in-turn allows us to carry out the following recursion indefinitely:
since for each stage α by induction p α : ξ ∈ α ↦ x ξ is injective, so that X ∖ p α ( α ) = ∅ by the above property. This means that the class { ( α , x α ) ∣ α ∈ O r d } is the graph of an injection f : O r d ⟶ X . By the comprehension axiom, r a n ( f ) ⊆ X exists as a set and finally by the replacement axiom, this means that O r d must be a set—which is a contradiction. Hence the Assumption (†) was wrong, and X is bijectively equivalent to an ordinal. QED
Lemma. Under ZF AC is equivalent to the following condition: for all sets X , Y either ∣ X ∣ ≤ ∣ Y ∣ or ∣ Y ∣ ≤ ∣ X ∣ , that is, there exist an injection from X ⟶ Y or one from from Y ⟶ 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 ordered by inclusion. (One needs to check that the Zorn conditions hold, but this is easy.) Let f be this maximal element. Note that as a partial injection, f is a bijection f : A ⟶ B for some A ⊆ X and B ⊆ Y . Claim: either A = X or B = Y . Suppose not. Then there exists an a ∈ X ∖ A and a b ∈ Y ∖ B . Let f ′ : = f ∪ { ( a , b ) } . Then by construction, f ′ ⊃ f strictly and is an injection. But this contradicts the maximality of f in P ! Hence the claim is true. If A = X , we have ∣ X ∣ ≤ ∣ Y ∣ as witnessed by f ; and if B = Y , we have ∣ Y ∣ ≤ ∣ X ∣ as witnessed by f − 1 . QED
I borrowed this proof from Alon Amit's answer on Quora .
The proof involves transfinite induction . This means the proof involves the following steps:
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 β , we first consider the union S of all sets A α where α < w β . Now, if β occurs as a distance between two points of S , we are already done. Otherwise, since β is strictly lesser than 2 ω , there must be some point in the circle of radius β away from one of the points in 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 β is strictly lesser than 2 ω , [ ← irrelevant ] there must be some point in the circle of radius β away from one of the points in 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 ; β ) , such that S ∪ { 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 with x = y it must hold that d ( q , x ) = d ( q , y ) . The set of points E ( x , y ) : = { p ∈ R 2 ∣ d ( p , x ) = d ( p , y ) } forms a line, so 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 to lie in.
Btw. it’s not crucial, but your property 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.
Problem Loading...
Note Loading...
Set Loading...
Fix d = 2 . The proof can be done for d > 2 by first projecting down to a 2 -dimensional subspace.
Defn 0. A set X ⊆ R d is called a cobweb , if and only if for all r ∈ R + there exists at most one pair of points { x , y } ∈ [ X ] 2 with d ( x , y ) = r .
Defn 1. For X ⊆ R d set ϕ ( X ) = { d ( x , y ) ∣ ( x , y ) ∈ X × X ∖ Δ } .
Hence X is a cobweb if and only if for all r ∈ ϕ ( X ) there exists exactly one pair of points { x , y } ∈ [ X ] 2 with d ( x , y ) = r .
Defn 2. For x , y ∈ R d with x = y set E ( x , y ) : = { p ∈ R d ∣ d ( p , x ) = d ( p , y ) } .
Note that E ( x , y ) = { p ∈ R d ∣ p − 2 1 ( x + y ) ⊥ y − x } which is a hyperplane and for d = 2 a line.
Defn 3. For X ⊆ R d set ⟨ X ⟩ : = X ∪ ⋃ x ∈ X , r ∈ ϕ ( X ) ∂ B ( x , r ) ∪ ⋃ ( x , y ) ∈ X × X ∖ Δ E ( x , y ) .
Lemma. If d = 2 and X ⊆ R d is a non-empty cobweb of cardinality ∣ X ∣ < 2 ℵ 0 , then for each r ∈ R + , there exists a cobweb X ′ ⊇ X with r ∈ ϕ ( X ′ ) and ∣ X ′ ∣ ≤ ∣ X ∣ + 1 < 2 ℵ 0 .
Proof. If r ∈ ϕ ( X ) , then let X ′ = X . Otherwise r ∈ / ϕ ( X ) . In this case, fix p ∈ X . We will find q ∈ R d with d ( p , q ) = r and so that X ′ : = X ∪ { q } is a cobweb (which necessarily satisfies the cardinality condition and furthermore r = d ( p , q ) ∈ r ( X ′ ) ). Let S : = ∂ B ( p , r ) . We will now show that S ∖ ⟨ X ⟩ is nonempty. To do this it suffices to show that ∣ S ∩ ⟨ X ⟩ ∣ < 2 ℵ 0 = ∣ S ∣ .
From these three observations, it follows that ∣ S ∩ ⟨ X ⟩ ∣ < 2 ℵ 0 . Hence, S ∖ ⟨ X ⟩ is non-empty. Thus there exists a point q ∈ S ∖ ⟨ X ⟩ . Observe
The last three points imply that X ′ : = X ∪ { q } is a cobweb, and furthermore r = d ( p , q ) ∈ r ( X ′ ) . QED.
Theorem. Working in ZFC there exists a set of points in R d for each 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 . By AC , there exists an infinite cardinal κ > ℵ 0 and a bijection α ∈ κ ↦ r α ∈ R + . By the above definitions we need to show that there exists a cobweb, A with ϕ ( A ) ⊇ R + . We shall construct, utilising the axiom of choice a monotone increasing sequence of countable cobwebs ( A α ) α < κ of R d , such that ϕ ( A α ) ⊇ { r ξ : ξ < α } and ∣ A α ∣ ≤ α + 1 for all α < κ . The construction is carried out per transfinite recursion:
Finally set A : = ⋃ α < κ A α . As a union of a monotone increasing sequence of cobwebs, A is a cobweb. Furthermore, by monotonicity ϕ ( A ) = ⋃ α < κ ϕ ( A α ) ⊇ ⋃ α < κ { r ξ : ξ < α } = { r ξ : ξ < κ } = R + . Hence A is a cobweb with ϕ ( A ) = R + . QED.
Note Δ A : = { ( x , x ) ∣ x ∈ A } for any set A . If the Set is clear from the context, then one simply denotes this as Δ .