# Is the set of all pairs of natural numbers countable? [duplicate]

Say that $\Bbb N \times \Bbb N$ is the set of all pairs $(n_1, n_2)$ of natural numbers. Is it countable? My hypothesis is yes it is countable because sets are countable. But I am unable to come up with a proof. Is my hypothesis correct? How is it countable?

## marked as duplicate by Martin R, draks ..., Najib Idrissi, Martin Sleziak, Chris CulterMay 22 '15 at 8:57

• It is countable. But what do you mean sets are countable? $\mathbb{R}$ is a set which is not countable. – Moya May 22 '15 at 7:35
• – Martin Sleziak May 22 '15 at 8:29

Consider the function $f: \mathbb{N} \times \mathbb{N} \longrightarrow \mathbb{N}$ defined by $f(a,b)=2^a \, 3^b$. Then this function is one-one. Consequently cardinality of $\mathbb{N} \times \mathbb{N}$ is "no more than" (if I may use this phrase) that of $\mathbb{N}$, hence countable.

• Could you explain "cardinality of N×N is "no more than" (if I may use this phrase) that of N" a little bit more. I am not quite understand what you mean by that? – Rajesh May 22 '15 at 19:06
• @Rajesh Suppose $f: A \longrightarrow B$ is an injective function. We know that image of $A$ under $f$ will be a subset of $B$. Thus $|f(A)| \leq |B|$. However by injectivity we also know that $|A|=|f(A)|$ hence $|A| \leq |B|$. The reason I used the phrase "if I may say" is because we are dealing with cardinal numbers so less than or equal to should be dealt with carefully unlike finite numbers. For more see en.wikipedia.org/wiki/Cardinality – Anurag A May 22 '15 at 21:24

First, list the pairs in which the sum is $0$:

$$(0,0)$$

Then those in which the sum is $1$:

$$(1,0),(0,1)$$

Then those in which the sum is $2$:

$$(2,0),(1,1),(0,2)$$

Then those in which the sum is $3$:

$$(3,0),(2,1),(1,2),(0,3)$$

And so on.

Yes, you do the diagonalization like with rational numbers which is basically the same thing.

Yes, here is a bijection example, where $p_k$ is the $kth$ prime number:

• $f(x,y)=p_x^{p_y}$

• $g(x)=(x,x)$

Another easy way :take a pair, write down the numbers in any numeration basis. For example (decimal) 1234 and 987. Add extra zeros where needed so they are the same length, and shuffle them

1 2 3 4
0 9 8 7
--------
10293847


Reverse operation : take digits with even (resp. odd) positions.

EDIT: and of course there are explicit formulas, here given as 3 recursive Python functions

def combine(a,b):
return 0 if a==0 and b==0 else 10*combine(b/10, a) + (b % 10)
def second(n):
return 0 if n==0 else 10*second(n/100)+ (n%10)
def first(n):
return second(n/10)


Here is an explicit formula for a bijection with $\mathbf N$, using the ordering first by ‘total degree’, then by first coordinate (known as grlex order on $\mathbf N\times\mathbf N$):

$$f(n_1,n_2)=\frac{(n_1+n_2)(n_1+n_2+1)}2+n_1+1.$$