20
$\begingroup$

Let $A_0=\{0\}$. For every $n\ge 0$, let $B_n=\bigcup_{k\ge 0}A_n+k$, and let $A_{n+1}=f(B_n)$, where $f:[0,\infty)\to[0,1):x\mapsto\frac{x}{x+1}$.

Let $q\in\Bbb Q\cap [0,1)$. Can we prove that $q\in A_n$ for some $n\ge 0$? Equivalently, I would like to prove or disprove that: $$\bigcup_{n\ge 0}A_n=Q\cap [0,1)$$

To illustrate: $B_0=\Bbb N$ (including $0$). Then, $A_1=\{0,\frac12,\frac23,\frac34,\ldots\}$. For any natural $k$, we have $\frac12+k=\frac{2k+1}{k}\in B_1$. Thus, $\frac{2k+1}{3k+1}\in A_2$. Et cetera.

Random thought: can this be argued using continued fractions?

$\endgroup$
33
$\begingroup$

Yes, you've constructed the Calkin-Wilf tree. $A_n \mapsto B_n$ corresponds to moving any number of steps to the right. $B_n \mapsto A_{n+1}$ corresponds to moving one step to the left.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.