Characterizing a Recursively Defined Rational Set

Question

Let $S$ be the smallest set of rational numbers that contains $\tfrac{1}{2}$, as well as the reciprocal of the sum of any two elements that are already in $S$. Prove or disprove that $S=\mathbb{Q} \cap [\tfrac{1}{2},1]$

Note that the two elements may be identical.

This is a repost of my previous post, which was answered partially as follows by @Tony Matthew (which I agree with):

Partial answer

Let's try building the set $S$ by starting with $\frac{1}{2}$ and adding new elements by taking two elements from the current set and calculating $f(a,b) \equiv \frac{1}{a + b}$. One possible value for $S$ is the steady-state limit of this process.

Since $\frac{1}{2}$ is the only element initially, the next new element must be $f(\frac{1}{2}, \frac{1}{2}) = 1$, so that our set becomes $\left\lbrace\frac{1}{2}, 1\right\rbrace$. Then, $f(1,1) = \frac{1}{2}, f(\frac{1}{2},1) = \frac{2}{3}$, so the set next grows to $\left\lbrace\frac{1}{2}, \frac{2}{3}, 1\right\rbrace$. Now the induction hypothesis: if the elements of the set lie between $\frac{1}{2}$ and $1$, then so too will any new element generated via $f(a,b)$. This can be proven by the following, $$\frac{1}{2}\leq a,b \leq 1 \rightarrow 1 \leq a + b \leq 2 \rightarrow \frac{1}{2}\leq f(a,b) \leq 1$$

Hence, since the set has started within the bounds of $\frac{1}{2}$ and $1$, it will remain within those bounds, and so too $S$. Therefore, since each new element must be a rational number, $$S \subseteq \mathbb{Q} \cap [\tfrac{1}{2},1]$$

I find this problem similar to that of the Calkin–Wilf tree, except the condition that two parent elements generate one child element is a bit more difficult to handle.

In comments:

For example, to obtain 5/7 I would try to find two elements such that their sum is 7/5, such as 3/5 and 4/5. These can generated by (2/3,1) and (3/4,1/2). 1 is generated by (1/2,1/2), 2/3 is generated by (1/2,1), 3/4 is generated by (2/3,2/3).

Answer 1

Your examples have essentially found all the important information when generalised:

• If you start with two rationals $a,b$ then $f(a,b)$ is rational so $S \subset \mathbb Q$
• If you start with two numbers $a, b$ both in $\left[\tfrac{1}{2},1\right]$ then $f(a,b)\in \left[\tfrac{1}{2},1\right]$ so $S \subset \left[\tfrac{1}{2},1\right]$
• You have $\frac12$ and $1=\frac11=f\left(\frac{1}{2},\frac{1}{2}\right)$ in $S$ and these have the smallest possible denominators
• If you have some positive integers $n, k$ with $k \lt n$ then $\frac{n+k}{2n} = f\left(\frac{n}{n+k},\frac{n}{n+k}\right)$ with smaller integer denominators
• If you have some positive integers $n, k$ with $k \le n$ then $\frac{n+k}{2n+1} = f\left(\frac{n}{n+k},\frac{n+1}{n+k}\right)$ with smaller integer denominators

So using strong induction over the denominators, you can generate all rationals from $\frac12$ through to $1$ and so $S=\mathbb{Q} \cap \left[\tfrac{1}{2},1\right]$.