Navigation 
 Home 
 Search 
 Site map 

 Contact Graeme 
 Home 
 Email 
 Twitter

 Skip Navigation LinksMath Help > Calculus > Limit > Uncountability of Reals

The Real Numbers are Uncountable

This means there is no sequence x1, x2, x3,... that contains all the real numbers.

Proof, based on Cantor's first uncountability proof 

Suppose x1, x2, x3,... has all of R as its range.

Start by finding the first two elements of x that are different from one another. Call the first one xi and the second xj. Let a1=min(xi,xj) and b1=max(xi,xj). Consider the first "j" elements of sequence x as having been "examined".

Now, having found an and bn, examine elements of sequence x that haven't yet been examined until you find two, xi and xj, that are different from one another and also between an and bn. Let an+1=min(xi,xj) and bn+1=max(xi,xj).

The two strictly monotone sequences, a and b, move toward each other.

By completeness of the reals, since sequence a is bounded above, sequence a has a "supremum", or least upper bound, c. c is larger than every element of a, because if c=an for any n, then c < an+1 and so c would not be the supremum of sequence a.

c is smaller than every element of sequence b, because if c≥bn for any n, then bn+1 (which is smaller than bn) would be a smaller upper bound than c of sequence a, and so c would not be the least upper bound of sequence a.

Since c is larger than every element of a and smaller than every element of b, it follows that c is contained in every open interval (an,bn). If c were equal to any element of sequence x, say, xi, then upon examination of xi, c=xi would have been one of the two numbers chosen as an+1 or bn+1, contradicting the inclusion of c in every open interval.

Therefore, c is not one of x1, x2, x3,..., contradicting the assertion that sequence x has all of R as its range.

Internet references

Completeness, from the Wikipedia

Cantor's first uncountability proof, from the Wikipedia

Related pages in this website

Upper Bound and Least Upper Bound (Supremum)


The webmaster and author of this Math Help site is Graeme McRae.