We consider the function

. We must show that this function provides a 1-1 mapping between the natural numbers and the pairs

of natural numbers.

To do this we must show:

1.

(i.e. the range of

lies in

)

2. For any natural number

we can find a unique pair of natural numbers

such that

The first part is obvious if we just consider the different choices of

modulo 2 to see that

is always an even number and thus

.

For the second part, we notice that

can be expressed recursively according to:

This shows us how to construct any natural number and thus for any natural number

we can find a pair of natural numbers

such that

as required. It remains to show uniqueness. Actually this is obvious from the construction, but I'll prove it explicitly:

Suppose

where

. Suppose first that

and without loss of generality suppose

. Then

which is a contradiction. Hence we must have

.

Suppose then, without loss of generality, that

, or in other words

. Then we have (noting that

is monotone in the first variable):

In other words

, which is again a contradiction.

Hence we have that

if and only if

and

, which establishes uniqueness.