Edit made on March 21, 2010 by ColinWright at 09:12:07
Deleted text in red /
Inserted text in green
WW
HEADERS_END
Georg Cantor made the starting assumption that a set is countably infinite if it can be put in one-one correspondence with the natural numbers.
It is fairly easy to show that even numbers, integers and square numbers are all countably infinite.
ARE THE RATIONAL NUMBERS COUNTABLE?
Form an (infinite) grid like this. Only the first six rows and columns are shown.
| 1/1 | 1/2 | 1/3 | 1/4 | 1/5 | 1/6 |
| 2/1 | 2/2 | 2/3 | 2/4 | 2/5 | 2/6 |
| 3/1 | 3/2 | 3/3 | 3/4 | 3/5 | 3/6 |
| 4/1 | 4/2 | 4/3 | 4/4 | 4/5 | 4/6 |
| 5/1 | 5/2 | 5/3 | 5/4 | 5/5 | 5/6 |
| 6/1 | 6/2 | 6/3 | 6/4 | 6/5 | 6/6 |
We want to show that these can be put into one-to-one correspondence with the natural numbers,
and there are two easy ways to think about this.
COLUMN_START^
Zig-zag back and forth through the above table:
* 1/1, 1/2, 2/1, 3/1, 2/2, 1/3, 1/4, 2/3, 3/2, 4/1, 5/1, 4/2, 3/3, 2/4, 1/5, 1/6, 2/5, ...
** !/ Put your finger on the table and trace the path that these makes ... !/
COLUMN_SPLIT^
List all those whose numerator and denominator add to two, then to three, then to four, etc, like this:
* 1/1,
* 1/2, 2/1,
* 1/3, 2,2, 3/1,
* 1/4, 2/3, 3/2, 4/1,
* /etc/
COLUMN_END
Each of these two ways will form a list of all the rational numbers. Therefore there exists a one-to-one correspondence with the natural numbers. So the rational numbers are countably infinite.
The size of countable sets is given the transfinite number EQN:\aleph_0 (pronounced aleph null) (see transfinite numbers)
Are all sets countable? (see Uncountable sets)
See Countable Set and delete this page soon.