Countable Subset of rational numbers

Question

Let $S = \{ x \in \mathbb Q \mid \sqrt 2 < x < \sqrt 3 \}$. Then $S$ is an infinite subset of $\mathbb Q$ hence countable. How do I construct a bijective mapping from $\mathbb N$ ?

Answer 1

Here's a construction.

Imagine a computer program which lists out each rational number in $S$, one at a time. Of course this program would never stop, because $S$ is infinite. Nonetheless there does exist such a program which, if it were allowed to run forever, would list each element of $S$ exactly once in a sequence $x_1,x_2,x_3,x_4,...$. In other words, the program would construct a bijection $\mathbb N \mapsto S$.

Now, write the program!

Here's a few hints.

Start with denominator $1$: there aren't any.

Next do denomonator $2$: there's one, namely $x_1 = \frac{3}{2}$.

Next do denominator $3$: there's one, namely $x_2 = \frac{5}{3}$.

There's no new ones with denominator $4$, one new one with denominator $5$ namely $x_3 = \frac{8}{5}$, and so on...

Now continue with increasing denominator $n$. For fractions $\frac{m}{n}$ with denominator $n$, you write a preliminary list of all fractions starting with numerator $m=n+1$ and continuing up to numerator $m=2n-1$ (i.e. your preliminary list contains only those fractions in the interval $1 < x < 2$). Now go through that preliminary list, and add to your main list those fractions $\frac{m}{n}$ which are in lowest terms and which satisfy the inequality $2 = (\sqrt{2})^2 < \frac{m^2}{n^2} < (\sqrt{3})^2 = 3$.