|
|
"Counting" may seem like a simple topic, but there's more to it than you might think.
"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, Z2, 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 Z2 = {(p,q)}
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.