6
$\begingroup$

I am looking for a subset $A$ of the real numbers such that given a real number $z$ not equal to $0$ there exists a unique $x,y \in A$ such that $x-y=z$. Or for any real number $z$ not equal to $0$, $x-y=z$ for $x,y \in A$ has one and only one solution.

Some examples of what can't happen:
If $A=\{0,1,2\}$ then if $z=1$ we have two solutions, $2-1=1$ and $1-0=1$.
If $A=\mathbb{Z} $ then $z=.5$ has no solutions.

Another way I have been looking at this problem is as points on a number line where there is always exactly one set of points any given distance apart.

EDIT: dropped largest/maximal from the question given Patrick's lemma.

$\endgroup$
19
  • $\begingroup$ taking plus instead of minus would also be helpful (a section of the transcendent numbers comes to my mind: $x-y$ (or $x+y$) algebraic then $x\notin A$ or $y\notin A$) if i remember correctly you can get ony by choice axiom :-) $\endgroup$
    – Max
    Oct 1, 2015 at 20:27
  • $\begingroup$ @Max, I'm not sure I understood your second comment. How would $x+y$ change the problem? $\endgroup$
    – Math Man
    Oct 1, 2015 at 20:41
  • $\begingroup$ @MathMan What do you mean by "largest"? If it exists, $A$ must be uncountable and hence $\mathbb{R}$-sized, because there must be uncountably many differences among its members. (Assuming continuum hypothesis and choice and whatever I need for that.) $\endgroup$ Oct 1, 2015 at 20:43
  • 1
    $\begingroup$ @PatrickStevens Yes, if it exists $A$ must definitely be uncountable but if more than one set happens to exist satisfying the conditions I am interested in which one is a superset of the others (if one is indeed a superset of the others). (This is kind of by the way though. I'm mostly just looking for a set $A$ satisfying the conditions.) $\endgroup$
    – Math Man
    Oct 1, 2015 at 20:47
  • 1
    $\begingroup$ The title is quite different from the body of the question! Firstly, the title says "from $0$ to $1$", but there is no such restriction in the body of the question. Secondly, the title says nothing about requiring, for all $z$, $x,y \in A$ with $z=x-y$. $\endgroup$
    – TonyK
    Oct 1, 2015 at 23:30

1 Answer 1

3
$\begingroup$

(Work in progress.)

Say a subset $A$ of $\mathbb{R}$ is difference-unique if for all $z \not = 0, z \in \mathbb{R}$ there is at most one pair $a_z, b_z \in A$ with $a_z - b_z \in A$. Say $A$ is nice if additionally for all $z \not = 0, z \in \mathbb{R}$ there is exactly one $a_z, b_z \in A$ with $a_z - b_z = z$. (That is, your property.) It is immediately obvious that nice sets must be uncountable, because they must have uncountably many differences-of-two-elements, and they must be unbounded, because arbitrarily large differences must be formed.

WLOG also that if $A$ is difference-unique (or nice), then $0 \in A$. Indeed, if not, we may select an element $a \in A$ and consider $A - a$, which has exactly the same difference-uniqueness/niceness status as $A$.

Lemma: Let $A$ be nice. Then $A$ is not a strict subset of another nice set.
Indeed, if $B$ were any set with $A \subset B$, then say $b \in B \setminus A$, and pick some other $c \in B$. Then there is unique $x, y \in A$ with $x-y = c-b$; but $x, y$ are in $B$ also, so $B$ is not nice.


A Zorn's lemma proof will hopefully be possible.

Lemma: the union of a nested collection of difference-unique sets is difference-unique. (That is, chains in the poset of difference-unique sets, ordered by inclusion, have upper bounds.)
Proof: suppose $\cup_I A_i$, a union of difference-unique sets, were not difference-unique. Then there would be $a, b, c, d$ in the union which had $a-b = c-d$, with $a \not = c, b \not = d$, $a \not = b$, $c \not = d$. Then all $a,b,c,d$ appear in some $A_i$, contradicting the difference-uniqueness of each $A_i$.

Therefore, by Zorn's lemma, there is a maximal difference-unique set. We just need one of these to be nice.


The obvious greedy algorithm ("find the first integer which is not a difference, add it to the last integer in our sequence, and append that sum to the sequence") fails to build an "integer-nice" $A$: a set of integers such that every integer appears exactly once as a difference. It builds $\{0, 1, 3, 7, 12, 20, 30, 44\}$ and then attempts to add $59$ to the list (while attempting to get $15$ as a difference), which has $29 = 59 - 20 = 30 - 1$.

$\endgroup$
3
  • $\begingroup$ Yes, such a set $A$ is automatically maximal, so you don't need to specify that it's maximal. $\endgroup$
    – TonyK
    Oct 1, 2015 at 21:04
  • 2
    $\begingroup$ Talking of integers and the greedy algorithm, you might want to mention oeis.org/A005282 (or A025582). $\endgroup$ Oct 1, 2015 at 23:20
  • $\begingroup$ @PatrickStevens I liked where you were going with this. Did you ever get any farther on it? $\endgroup$
    – Math Man
    Sep 16, 2018 at 6:05

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .