Uncountable
A set is said to be uncountable if there is no injection
. Every set that is not uncountable is either finite or countably infinite. The most common example of an uncountable set is the set of real numbers
.
Proof that
is uncountable
We give an indirect proof here. This is one of the most famous indirect proofs and was first given by Georg Cantor.
Suppose that the set is countable. Let
be any enumeration of the elements of
. Consider the decimal expansion of each
, say
for all
. Now construct a real number
by choosing the digit
so that it differs from
by at least 3 and so that not every
is equal to 9 or 0. It follows that
differs from
by at least
, so
for every
and
. However,
is clearly a real number between 0 and 1, a contradiction. Thus our assumption that
is countable must be false, and since
we have that
is uncountable.
See Also
This article is a stub. Help us out by expanding it.