Finite Cartesian product of naturals is countably infinite + notation. $\newcommand{\N}{\mathbb{N}}$
I tried to prove $ |\N| = |\N^n| $ for all $n \in \N$ by mathematical induction.

*

*base step: $|\N| = |\N|$ is trivial


*inductive step: Let $|\N| = |\N^n|$. Then, there is a bijection $f: \N \to \N^n$. We can define $g: \N \times \N \to \N \times \N^n$ such that
$$
\forall i, j \in \N: g(i, j) = (i, f(j))
$$
$g$ is bijective. Let $h: \N \times \N \to \N^{n+1}$ be defined as
$$
\forall i, j \in \N:\forall k \le n+1: (\pi_k \circ h)(i,j)
=
\begin{cases}
i, & k = 1\\
(\pi_{k-1} \circ f)(j), & k \neq 1
\end{cases}
$$
$h$ is also bijective. Since $|\N| = |\N \times \N|$, there is a bijection from $\N$ onto $\N^{n+1}$
Questions:

*

*Is this a valid proof?

*I defined $h$ from $g$ using a canonical projection $\pi_k$ to explicitly show the existence of a bijection to $\N^{n+1}$. This is somewhat redundant, but $g(i, j) = (g_1, (g_2, g_3,\cdots))$ is actually not what we are looking for. When I am supposed to write them in a technical paper, should I explicitly define $h$? This question is not confined to my proof.

 A: Your proof has a gap at $n=2$, because your induction step uses the isomorphism $\Bbb N \cong \Bbb N^2$ you are supposed to prove to exist in this stage. Moreover it is not as concise as it could be. In particular I don’t understand what $g$ and $h$ have to do with each other, so I don’t understand your second question. I would propose a proof along the following lines.
Define $f_1=\operatorname{id}:\Bbb N \rightarrow \Bbb N$ and
$$\begin{array}{rcl}
f_2:\Bbb N \times \Bbb N&\rightarrow & \Bbb N\\
(m,n) & \mapsto & n + \psi(m+n)
\end{array}$$
where $\psi(k) = \sum_{i=1}^k i$, $\psi(0)=0$. This $f_2$ is just one of the standard bijections made explicit. Its inverse is given by the map
$$\begin{array}{rcl}
\Bbb N & \rightarrow & \Bbb N^2\\
N & \mapsto & (k_N - (N - \psi(k_N)), N - \psi(k_N))
\end{array}$$
where $k_N = \max\{k \mid \psi(k)\leq N\}$.
For the induction assume we have found a bijection $f_n: \Bbb N^n \rightarrow \Bbb N$. Then the composite
$$f_{n+1}:\Bbb N^{n+1} = \Bbb N \times \Bbb N^n \overset{\operatorname{id}\times f_n}\longrightarrow \Bbb N \times \Bbb N \overset{f_2}\longrightarrow \Bbb N$$ is a bijection as composite of bijections, hence finishes the proof.
Note that the real work is not in the induction step, but in the case $n=2$…
