I have to construct a bijection between $\Bbb N$ the natural numbers and $\Bbb S$, where $\Bbb S$ is the set of finite rows of natural numbers.
S=$\{(n_0,n_1,…,n_k)|k\in \Bbb N,n_i\in \Bbb N\}$
I did a similar problem here:bijection between natural numbers and set of strictly growing finite rows but can figure it out for this one.
Best Answer
I will write rows with $[ ~~]$ brackets. (If you also admit an empty row $\emptyset$ you can just extend the bollow definition with $f(\emptyset) := 1$).
Then we can define a bijection $f : \mathbb{S} \rightarrow \mathbb{N}_{>1}$ by \begin{align} f([a_1, \dots, a_k]) := p_1^{a_1} \dots p_{k-1}^{a_{k-1}} \cdot p_k^{1 + a_k} \end{align} Where $p_k$ is the $k$-th prime. It is then easy to get a bijection $\mathbb{S} \rightarrow \mathbb{N}$ by combining $f$ with a bijection $\mathbb{N}_{>1} \to \mathbb{N}$.
Proof of Surjectivity:
Any $n > 1$ has a biggest ($k$-th) prime number $p_k$ with exponent $e > 0$ s.t. $n = x \cdot p_k^e$ and $p_k \not \mid x$.
If $x = 1$ we have $ f ([\underbrace{0, \dots ,0}_{k-1 \text{ times}},e-1] ) = p_k^{1 + (e-1)} = x \cdot p_k^e = n $
If $x > 1$ then we have $x < n$, and therefore by complete induction $x$ has a preimage $[x_1, \dots, x_l]$. Then we have \begin{align} f ( [ x_1 , \dots , 1 + x_l, ~\color{Blue}{0, \dots ,0}, ~e-1 ] ) = p_1^{x_1} \dots p_l^{1 + x_l} \cdot p_k^{1 + (e-1)} = x \cdot p_k^e = n \end{align} Where we need to put $\color{blue}{\text{$(k-l)-1$ zeros}}$ between $(1 + x_l)$ and $(e-1)$ to make sure the latter is the $k$-th entry of the tuple. Note that we must have $l < k$ since the biggest prime in $n$ was $p_k$ and all primes $p_l$ appearing in $x$ must be smaller. $\Box$
Proof of Injectivity:
Assume $f([a_1, \dots, a_n]) = f([b_1, \dots, b_m])$, then $$ p_1^{a_1} \dots p_n^{1 + a_n} = p_1^{b_1} \dots p_m^{1 + b_m} $$ where both sides are prime factorisations of the same number. Since $\color{Red}{\text{said number is bigger then } 1}$, we can conclude $n = m$ and $a_j = b_j$ by the uniqueness of prime factorizations. $\Box$
Note that it is in the proof for injectivity, that the (seemingly odd) $+1$ in the power of the last prime number $\color{Red}{\text{plays its crucial role}}$. Without it, the proof would not work.