"Counting" may seem like a simple topic, but there's more to
it than you might think.

**Countable**

In this topic, we'll consider whether a set can be counted. That means
whether it can be put in one-to-one correspondence with the "counting
numbers". The counting numbers are the positive integers, which I
will denote N. By definition, N = {1, 2, 3, ...}. (Note: some
authors include zero in the "natural" numbers, but I do not.) Although
N is
an infinite set, it is considered "countable" because if you start at
the beginning, and keep counting, each element will eventually be counted, even
though it will never be the case that all elements will be counted."One-to-one correspondence"
of set A with set B means there is a
function, f, whose domain is A and whose range is B. This function maps
each element of A to a single element of B. If set A is in one-to-one
correspondence with set B and set B is countable, then set A is countable, too.

Adding a finite number of elements to a countable set results in another
countable set. So the set of nonnegative integers, {0, 1, 2, 3, ...} is
countable. If a set can be put in one-to-one correspondence with any
countable set, then both sets are countable.

The set of integers is countable. To show that, you put the set in
one-to-one correspondence with the natural numbers this way:

Z |
N |

0 |
1 |

1 |
2 |

-1 |
3 |

2 |
4 |

-2 |
5 |

3 |
6 |

-3 |
7 |

It may surprise you to learn that the set of ordered pairs of integers, Z^{2},
is countable, too. Click here
to see the one-to-one correspondence.

That means the set of rationals, Q = {p/q | p is an integer, and q is a
nonzero integer} is also countable. You can show this by putting Q = {p/q}
in one-to-one correspondence with Z^{2} = {(p,q)}

### Related pages in this website

The Peano Postulates --
Proving the properties of natural numbers using the Peano Postulates, which
have been formulated so that zero is *not* included in the set of natural
numbers. (There's quite a debate about this
point.)

Is
Zero a Natural Number? -- a discussion of the fact that some authors
include zero, and others do not.

Construction -- Construction of sets
of numbers, starting with the original Peano Axioms, formulated so that zero *is*
included in the set of natural numbers.

Set Theory -- an introduction to sets, including
examples of some standard sets.

Counting Ordered Pairs of
Integers -- An explanation of the "square spiral" that puts the
set of natural numbers in one-to-one correspondence with the set of rational
numbers.

The webmaster and author of this Math Help site is
Graeme McRae.