## Countable Sets

A countable set is a set that can be matched one to one with some subset of the set of natural numbers. Every finite set is countable. A set that is not countable is called uncountable. For instance the set of all even numbers is countable, with the matching provided by and so is the set of all rational fractions with the mapping illustrated in the table below. In exactly the same way the set of points in the xy plane with integer coordinates can be put in a one - to one correspondence with the set of natural numbers: The correspondence generates a square spiral, shown below. Hence is countable, and by induction so is and for  is not countable.

Proof: Assume that is countable. Each can be expressed as an infinite decimal. Suppose the 1-to-1 correspondence with is :   such that every real number appears in the list on the right.

Choose a real number such that etc.

This real number is different from all those in the list, and hence there cannot exist such a 1-to-1 correspondence between and the whole of so is uncountable. 