# $\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?
Somebody help please.

## 2 Answers

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.