# $\Bbb N\times\Bbb N$ is countable

$\Bbb N\times\Bbb N$ is countable

My attempt:

Lemma: $A$ is countable if and only if there exists a injectve mapping from $A$ to $\Bbb N$.

We define a mapping $f:\Bbb N\times\Bbb N \to \Bbb N$ by $f(k,l)= 2^k3^l$. Next we prove $f$ is injective.

Suppose that $(k_1,l_1)$ and $(k_2,l_2)\in\Bbb N\times\Bbb N$ and that $f(k_1,l_1) = f(k_2,l_2)$. Then $2^{k_1}3^{l_1}=2^{k_2}3^{l_2}$.

If $k_1>k_2$, then $2^{k_1}$ is not divisible by $2^{k_2}$. Furthermore, $2^{k_1}$ is not divisible by $3^{l_2}$ since $2$ and $3$ are prime numbers. It follows that $2^{k_1}$ is not divisible by $2^{k_2}3^{l_2}=2^{k_1}3^{l_1}$. Thus $2^{k_1}$ is not divisible by $2^{k_1}3^{l_1}$, which is clearly a contradiction.

By assuming $k_1<k_2$, or $l_1<l_2$, or $l_1>l_2$, we can easily obtain similar contradictions. Thus $k_1=k_2$ and $l_1=l_2$. Hence $(k_1,l_1)$ = $(k_2,l_2)$.

As a result, $f$ is injective and hence $\Bbb N\times\Bbb N$ is countable.

Does this proof look fine or contain gaps? Do you have suggestions? Many thanks for your dedicated help!

Update: On the basis of @spaceisdarkgreen's commnet, I should explicitly mention that $f$ is injective by The Fundamental Theorem of Arithmetic.

• Do you suspect your proof has any gaps? It is injective by the fundamental theorem of arithmetic. – spaceisdarkgreen Sep 13 '18 at 3:48
• To make the proof more idiomatic, you can say "without loss of generality $k_1 \gt k_2$" – Mark Sep 13 '18 at 3:51
• @LeAnhDung isn’t $2^5$ divisible by $2^2$? – Anurag A Sep 13 '18 at 3:51
• You can avoid having to define prime numbers and also fundamental theorem of arithmetic at the cost of defining rationals: $2^{k_1 - k_2} = 3^{l_2 - l_1}$. The left hand side is integer, so then the right hand side is as well ($l_2 \ge l_1$). But taking both sides mod 2, you obtain a contradiction unless $k_1 = k_2$ – Mark Sep 13 '18 at 3:54
• @LeAnhDung It should have been the only thing you mentioned. All the rest is unnecessary. – spaceisdarkgreen Sep 13 '18 at 3:58

Define $f(k,l)= 2^k3^l$. By the fundamental theorem of arithmetic, $f$ is injective. QED.