Prove: the union of all n-tuples is countable Prove: $\mathbb N^*=\bigcup_{n\in \mathbb N} \mathbb N^n$ is countable. 
My idea is to show this for $\mathbb N^2$ first, which is not difficult. After this I say, that every tuple, could be reduced to a 2-tuple:
$(n_1,n_2,n_3,n_4) \mapsto ((n_1,n_2),n_3,n_4)$, 
$((n_1,n_2),n_3,n_4) \mapsto (((n_1,n_2),n_3),n_4)$ and so on.
Can I do this? If yes, is it formally correct? If not, does someone has hints?
 A: You have to at some point give a function which does what you want it to. In particular, you need to show there is a bijection from the entire union of all of the $\mathbb{N}^n$ to $\mathbb{N}$, not just from each one in particular. Your idea might be able to be fleshed out to give you something that works, but in my opinion there's a simpler way using the fundamental theorem of arithmetic.
I'll assume $0 \notin \mathbb{N}$. If you really need to include it then it's not too difficult to modify the following argument.
Let $f_n \colon \mathbb{N}^n \to \mathbb{N}$ be given by $f_n((m_1,\ldots, m_n)) = p_1^{m_1} p_2^{m_2}\cdots p_n^{m_n}$ where $p_i$ is the $i$th prime number.
Let $f \colon \mathbb{N}^\ast \to \mathbb{N}$ be given by $f(x) = f_n(x)$ for the appropriate $n$ for which $x \in \mathbb{N}^n$.
Can you see why this is an injection?
A: I don't see why not. The countable union of countable sets is countable, so all you have to show is $\mathbb{N}^n$ is countable for each n. I would do this inductively using the fact that if A and B are countable then $A \space \times B$ is countable. There are contexts in which $\mathbb{N}^n$ and $\mathbb{N} \times \mathbb{N} \cdots \times \mathbb{N}$ are not the same thing, but for naïve set theory they are.
A: This will work, to prove by by induction on $n\in \Bbb N$ that $\Bbb N^n$ is countable for all $n\in \Bbb N.$ 
The case $n=1$ is trivial. 
Prove the case $n=2.$ Let $F_2:\Bbb N^2\to \Bbb N$ be a bijection. 
There is a bijection $G_n: \Bbb N^{n+1} \to \Bbb N^n\times \Bbb N.$ So if there is a bijection $F_n:\Bbb N^n\to \Bbb N,$ then for $x\in \Bbb N^{n+1},$ let $G_n(x)=(g_n(x),h_n(x)),$ with $g_n(x)\in \Bbb N^n$ and $h_n(x)\in \Bbb N$, and let $$F_{n+1}(x)= F_2(\;(F_n(g_n(x)), h_n(x)\;). $$ 
