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

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?

marked as duplicate by Asaf Karagila♦ elementary-set-theory StackExchange.ready(function() { if (StackExchange.options.isMobile) return; $('.dupe-hammer-message-hover:not(.hover-bound)').each(function() { var$hover = $(this).addClass('hover-bound'),$msg = $hover.siblings('.dupe-hammer-message');$hover.hover( function() { $hover.showInfoMessage('', { messageElement:$msg.clone().show(), transient: false, position: { my: 'bottom left', at: 'top center', offsetTop: -7 }, dismissable: false, relativeToBody: true }); }, function() { StackExchange.helpers.removeMessages(); } ); }); }); Feb 14 '17 at 5:52

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.