# $\Bbb N$x$\Bbb N$ is countably infinite [duplicate]

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

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:

(1,1)

(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.

• yes it's clear, and then how I proceed? – Jacob S. Feb 14 '17 at 3:08
• 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." – Badam Baplan Feb 14 '17 at 3:33
• I see, thanks Badam Baplan – 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.