2
$\begingroup$

$\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.

$\endgroup$
  • 1
    $\begingroup$ Do you suspect your proof has any gaps? It is injective by the fundamental theorem of arithmetic. $\endgroup$ – spaceisdarkgreen Sep 13 '18 at 3:48
  • 1
    $\begingroup$ To make the proof more idiomatic, you can say "without loss of generality $k_1 \gt k_2$" $\endgroup$ – Mark Sep 13 '18 at 3:51
  • 1
    $\begingroup$ @LeAnhDung isn’t $2^5$ divisible by $2^2$? $\endgroup$ – Anurag A Sep 13 '18 at 3:51
  • 1
    $\begingroup$ 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$ $\endgroup$ – Mark Sep 13 '18 at 3:54
  • 2
    $\begingroup$ @LeAnhDung It should have been the only thing you mentioned. All the rest is unnecessary. $\endgroup$ – spaceisdarkgreen Sep 13 '18 at 3:58
3
$\begingroup$

Here is a short proof based on @spaceisdarkgreen's comment:

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.