Infinity 147

by the association of n with 2n, we may place A in one-to-one correspondence with a

set of even numbers. Similarly, by composing with the map n → 2n + 1, we may place

B in one-to-one correspondence with a set of odd natural numbers. In this way, the two

correspondences can be performed simultaneously, leading to a one-to-one correspondence

of the union A ∪ B with a set of natural numbers.

Second proof. Another way to think about it is that if A is countable and nonempty, then

we may enumerate the elements of A as a

0

, a

1

, a

2

, and so on. And similarly, if B is

countable and nonempty, we may enumerate the elements as b

0

, b

1

, b

2

, and so on. Thus,

we may enumerate the elements of A ∪ B simply by interleaving these two enumerations:

a

0

, b

0

, a

1

, b

1

, a

2

, b

2

,...

Thus, the union set is countable. If either set is empty, then the union reduces to the other

one, and so in any case, the union of two countable sets is countable.

Corollary 107. The set of integers Z = {...,−2, −1, 0, 1, 2,...} is countable.

Proof. The set of integers is the union of two countable sets, namely, the natural num-

bers {0, 1, 2,...} and the negative integers {−1, −2, −3,...}, and is therefore countable by

theorem 106.

One can also see that Z is countable by enumerating it like this:

0, 1, −1, 2, −2, 3, −3,...

Theorem 108. There are just as many pairs of natural numbers as natural numbers. In

other words, N × N is equinumerous with N. Indeed, there is a bijective function p :

N × N → N for which p(x, y) is a polynomial function in the two variables.

We shall give several proofs, although the polynomial claim will arrive only with the

third proof.

First proof. The first proof is to use our earlier manner of handling Hilbert’s train. Namely,

we associate any pair of natural numbers (n, m) with the number 3

n

5

m

. This provides a

function d : N × N → N, which is injective because of the uniqueness of prime factoriza-

tions. Thus, N × N is in one-to-one correspondence with a set of natural numbers, and so

it is countable.

Second proof. For a second proof, we provide a bijection between N and N × N. The set

N × N consists of the lattice points in a grid, as pictured below at the left. Let us imagine

taking a walk through this grid on the winding path pictured at the right. The path starts at

the origin and then proceeds to zig and zag progressively up and down the diagonals. The

main point is that we shall eventually encounter any given lattice point on this path, if we