Problem #WSP-5262

Problem

The whole idea of problems with Hilbert’s Hotel is about assigning numbers to elements of an infinite set. We say that a set of items is countable if and only if we can give all the items of the set as gifts to the guests at the Hilbert’s hotel, and each guest gets at most one gift. In other words, it means that we can assign a natural number to every item of the set. Evidently, the set of all the natural numbers is countable: we gift the number $n$ to the guest in room $n$.

The set of all integers, $\mathbb{Z}$, is also countable. We gift the number $n$ to the guest in room $n$. Then we ask everyone to take their gift and move to the room double their original number. Rooms with odd numbers are now free ($1,3,5,7,\dots$). We fill these rooms with guests from an infinite bus and gift the number $-k$ to the guest in room $2k+1$. Yes, that’s right: the person in the first room will be gifted the number $0$.

Prove now that the set of all positive rational numbers, ${\mathbb{Q}}^{+}$, is also countable. Recall that a rational number can be represented as a fraction $\frac{p}{q}$ where the numbers $p$ and $q$ are coprime.