Is the set of all pairs of natural numbers countable? 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?
 A: 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.
A: Yes, you do the diagonalization like with rational numbers which is basically the same thing.
A: 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)$
A: 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)

A: 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.
A: 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.$$
