$\Bbb N\times\Bbb N$ is countable.
In this proof, I try to not use The Fundamental Theorem of Arithmetic, so the proof may be needless long :)
My attempt:
We define $f:\Bbb N\times\Bbb N\to\Bbb N$ by
$$f(i,j)=i+\sum\limits_{k=0}^{i+j}k$$
Next we prove that $f$ is injective.
For $(i_1,j_1),(i_2,j_2)\in \Bbb N\times\Bbb N$, $f(i_1,j_1)=f(i_2,j_2)\iff i_1+\sum\limits_{k=0}^{i_1+j_1}k = i_2+\sum\limits_{k=0}^{i_2+j_2}k$. Without loss of generality, we can assume that $i_1+j_1\le i_2+j_2$. Thus we have only two cases.
- $i_1+j_1 = i_2+j_2$
Then $\sum\limits_{k=0}^{i_1+j_1}k = \sum\limits_{k=0}^{i_2+j_2}k$ and thus $i_1=i_2$. It also follows that $j_1=j_2$. Hence $(i_1,j_1)=(i_2,j_2)$.
- $i_1+j_1 < i_2+j_2$
$i_1+\sum\limits_{k=0}^{i_1+j_1}k = i_2+\sum\limits_{k=0}^{i_2+j_2}k \iff \sum\limits_{k=0}^{i_2+j_2}k - \sum\limits_{k=0}^{i_1+j_1}k = i_1-i_2\iff \sum\limits_{k = i_1+j_1+1}^{i_2+j_2}k=i_1-i_2$.
$\sum\limits_{k = i_1+j_1+1}^{i_2+j_2}k \ge i_1+j_1+1 \iff i_1-i_2\ge i_1+j_1+1 \iff 0\ge -i_2\ge j_1+1$. This inequality is clearly a contradiction.
To sum up, we have only one possible cases in which $i_1+j_1 = i_2+j_2$.
Thus $f(i_1,j_1)=f(i_2,j_2)\iff (i_1,j_1)=(i_2,j_2)$. Hence $f$ is injective and $\Bbb N\to\Bbb N$ is countable.
Does this proof look fine or contain gaps? Do you have suggestions? Many thanks for your dedicated help!
One can create a injective function from $\Bbb N$ to $\Bbb N^2.$ Construct a function $f:\Bbb N^2\rightarrow\Bbb N$. $f(x,y)=2^x3^y$ is also injective. Since we can create an injection both way, there exists a bijection.
Function2: Consider $a_1=\sum^n_{i=0}10^ik_1$ and $a_2=\sum^n_{i=0}10^ij_1$
Then $n=\overline{k_1j_1k_2j_2...}$