Uncountable

Revision as of 06:00, 5 November 2006 by Bubka (talk | contribs)

This article is a stub. Help us out by expanding it.

A set $S$ is said to be uncountable if there is no injection $f:S\to\mathbb{N}$. A well-known example of an uncountable set is the set of real numbers $\mathbb{R}$.

Proof that $\mathbb{R}$ is uncountable

We give an indirect proof here. This is one of the most famous indirect proofs and was given by George Cantor.

Suppose that the set $A=\{x\in\mathbb{R}:0<x< 1\}$ is countable. Let $\{\omega_1, \omega_2, \omega_3, ...\}$ be any enumeration of the elements of $A$. Consider the binary expansion of each $\omega_i$. For diedic rationals, take only the expansion terminating in an infinite chain of zeros, so that we have a unique binary expansion for each element of $A$. Say $\omega_i=(.b_{i1}b_{i2}b_{i3}...)_2$ for all $i$. Now construct $\omega=(.b_1b_2b_3...)_2$ such that $b_i=1-b_{ii}$ for all $i$. So $\omega$ is different from $\omega_i$ for all $i$. So $\omega\not\in A$. But $\omega\in\mathbb{R}:0<\omega<1$, a contradiction. So $\mathbb{R}$ is uncountable.

See Also