# Help proving there is a sequence of rational numbers

I'm trying to prove the following:

Let $$\Bbb Q$$ be the countable set of rational numbers and $$\{x_n\}_{n=1}^\infty$$ be a sequence such that for every q $$\in$$ $$\Bbb Q$$ there is a $$n \in \Bbb N$$ with $$x_n = q$$. Prove that there is such a sequence $$\{x_n\}$$.

My initial thoughts for an attempt at a solution:

We know that $$|\Bbb Q| = |\Bbb N|$$ by the Cantor Theorem. Further, I can show that there is a bijection between $$\Bbb Q$$ and $$\Bbb N$$.

If I define $$\{x_n\}_{n=1}^\infty$$ as some relation between $$(p,q) \in \Bbb Z \times \Bbb Z$$, will ths properly prove that such a sequence exists?

• For an explicit bijection, see -math.stackexchange.com/questions/7643/… – Thomas Shelby Dec 9 '18 at 17:15
• Thanks Thomas! This is wonderful to see! – user624612 Dec 9 '18 at 17:20
• What is the definition of an infinite sequence $\{x_n\}_{n\in \Bbb N}$? It's a function $f$ with domain $\Bbb N,$ except we write $x_n$ for $f(n)$..... And $|\Bbb Q|=|\Bbb N$| is an abbreviation for, or an equivalent to, the statement that there exists a bijection $f:\Bbb N\to \Bbb Q.$ And that's all there is to it. – DanielWainfleet Dec 9 '18 at 20:19
• You may enjoy the small book Stories About Sets, by Vilenkin. – DanielWainfleet Dec 9 '18 at 20:22

It is actually quit easy once you know that $$|\mathbb{Q}|=|\mathbb{N}|$$ as this implies that there exists a bijection $$f:\mathbb{N}\rightarrow \mathbb{Q}$$. Now simply let $$x_n = f(n)$$.
The answer to this question is going to depend upon what you have available as definitions. Where I come from, a sequence of elements from a set $$S$$ is just a function $$f:\mathbb{N}\rightarrow S$$; if that is the case for you, since you already know there is a bijection from $$\mathbb{N}$$ to $$\mathbb{Q}$$ you are done!
If you wanted to explicitly write down such a sequence, then yes, you will probably want to start with a surjection from $$\mathbb{N}$$ to $$\mathbb{Z}\times \mathbb{Z}$$, and then a surjection from $$\mathbb{Z}\times \mathbb{Z}$$ to $$\mathbb{Q}$$. The composition of these functions will be a sequence that hits every rational number.
How to build such surjections? You could define $$f:\mathbb{N}\rightarrow \mathbb{Z}\times \mathbb{Z}$$ in pieces, say by sending numbers of the form $$2^i3^j$$ to $$(i,j)$$, numbers of the form $$5^i7^j$$ to $$(-i,-j)$$, numbers of the form $$11^i13^j$$ to $$(i,-j)$$, and numbers of the form $$17^i19^j$$ to $$(-i,j)$$, with everything else sent to $$(0,0)$$. You could define $$g:\mathbb{Z}\times \mathbb{Z} \rightarrow \mathbb{Q}$$ by sending $$(0,q)$$ and $$(p,0)$$ to $$0$$, and all other $$(p,q)$$ to $$p/q$$.