This question already has an answer here:

How can I prove $\Bbb N$x$\Bbb N$ is countably infinite?
Is the proof in some book about sets?
Somebody help please.


marked as duplicate by Asaf Karagila elementary-set-theory Feb 14 '17 at 5:52

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.


Are you familiar with the proof that the rationals are countably infinite? This is precisely the same idea.

Think if you lay out elements in a grid as follows:

$$\begin{bmatrix} (1,1) & (1,2) & (1,3) & \ldots \\ (2,1) & (2,2) & (2,3) & \ldots \\ (3,1) & (3,2) & (3,3) & \ldots \\ \vdots & \vdots & \vdots & \ddots \end{bmatrix}$$ Now enumerate them on the diagonals:


(2,1), (1,2)

(3,1), (2,2), (1,3)

(4,1), (3,2), (2,3), (1,4)

etc. etc.

Can you see how you'll get every element of $\mathbb{N} \times \mathbb{N}$? If the element $(x,y)$ is such that $x+y = n$, then you'll encounter it on the $(n-1)$st diagonal.

  • $\begingroup$ yes it's clear, and then how I proceed? $\endgroup$ – Jacob S. Feb 14 '17 at 3:08
  • 1
    $\begingroup$ Well then you're essentially done, you've shown that you can enumerate all of the elements of $\mathbb{N} \times \mathbb{N}$ in a list. The first element of the list is $(1,1)$, the second element is $(2,1)$, the third is $(1,2)$, and so on. In other words you have established a bijection between $\mathbb{N}$ and $\mathbb{N} \times \mathbb{N}$. This is the definition of "countably infinite." $\endgroup$ – Badam Baplan Feb 14 '17 at 3:33
  • $\begingroup$ I see, thanks Badam Baplan $\endgroup$ – Jacob S. Feb 14 '17 at 3:49

Do you know that a countable union of countable sets is countable? If so, you could write

$\mathbb{N} \times \mathbb{N} = \bigcup_{i=1}^\infty E_i$

Where each $E_i = \{i\}\times \mathbb{N}$ is countable.

Also, if you interpreted a ratio $a/b$ as a pair $(a,b)$, there is the following trick: http://www.homeschoolmath.net/teaching/rational-numbers-countable.php This technique can be found and described many different places by google searching for an enumeration of the rational numbers.


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