Tuesday, September 17, 2002

Experience Mathematics #14 - Uncountable sets

Many of the infinite sets we have encountered are countable. Even numbers, the set of prime numbers, integers and rational numbers, all have the same number of elements as $N$, the set of natural numbers. Are there any infinite sets that have more elements than the natural numbers?

This question was answered by Cantor, who showed that the real numbers outnumber the natural numbers. All the real numbers between $0$ and $1$ have a decimal expansion such as $x=0.13212987\dots$. Cantor showed that all numbers of this form cannot be put into one-to-one correspondence with the set of natural numbers. To be able to understand his proof, find a number that differs from $x$ in the first decimal place. Take any number $y$ with $2$ in the first decimal place. Since $2$ is different from $1$, $y$ differs from $x$ in the first decimal place.

To return to Cantor’s proof, suppose that you are able to find a one-to-one correspondence between the natural numbers and all the real numbers in the interval $(0,1)$. Let us denote by $x_1$ the number corresponding to $1$; $x_2$, the number corresponding to $2$, and so on. Now consider a number $y$ (between $0$ and $1$) that is different from $x_1$ in the first place after the decimal; different from $x_2$ in the second place after the decimal; and so on. Clearly, $y$ cannot appear in the list, since it is different from all the $x$’s. Thus we have found a real number between $0$ and $1$ that is not in the above correspondence. This contradiction shows that no such correspondence is possible. In other words, the real numbers are uncountable in number.

Are there any infinite sets that have more elements than $N$ but less elements than the set of real numbers?

No comments: