Rational numbers - countability I have to show that the set of all finite sequences
$$
(q_1,q_2,\dotsc,q_k),\quad k \in \mathbb{N}
$$
 of rational numbers is countable. 
To prove that the set $\mathbb{Q}$ of all rational numbers is countable, I used that the set $\mathbb{Z}\times\mathbb{N}$ is countable and can be listed as
$$
(a_1,b_1),(a_2,b_2),(a_3,b_3),\dotsc
$$ 
and then making a list of all elements in $\mathbb{Q}$:
$$
\frac{a_1}{b_1}, \frac{a_2}{b_2}, \frac{a_3}{b_3}.
$$
But how can I show for all finite sequences?
 A: As $\mathbb Q$ is countable, you can solve the question for the $k$-uples of naturals instead (every rational can be traded for an integer).
Then for every $n$, you can enumerate the natural solutions of
$$\sum_{j=1}^k q_j=n$$ (by choosing all possible values of $q_k\in[1,n]$ and recursively solving $\sum_{j=1}^{k-1} q_j=n-q_k$), so by increasing $n$ you can enumerate all sequences. (No sequence will be missed, because every sum is enumerated, and for a given sum, no solution is missed. Also note that no sequence will be duplicated, but this inessential.)

The result also holds for sequences of arbitrary lengths (all $k$), by enumerating the pairs $(n,k)$ with the same method.
A: You already have all the ingredients for your proof. You just need to assemble them.
Since you know $\mathbb{Z} \times \mathbb{N}$ is countable and that $\mathbb{N}$ and $\mathbb{Q}$ have the same cardinalty (countable) you know $\mathbb{Z} \times \mathbb{Q}$ is countable. Then you know that the subset
$\{0,1, \ldots, k\} \times \mathbb{Q}$ is countable for each $k$.  Those are the sets of finite sequences of rationals. Their union is a countable union of countable sets, hence countable.
(The union of countably many countable sets is countable because it's essentially $\mathbb{N} \times \mathbb{N}$, thought of a row at a time.)
A: The general result you need is that the set of ordered pairs (x,y), where each of x, y is a member of a countable set, is itself a countable set.  This is the essence of the proof that $\mathbb{Q}$ is countable.  I leave it to you to figure out how to apply this to your problem (hint: induction on number of indices).
