Next: Cantor's Bijection Theorem Up: Finiteness09february2012 Previous: Cantor's Power Set Theorem;

## A surjection: ; the reals are uncountable

If we may define a real number using binary expansion:
• .

For example we have:
• .
• For any positive integer , we have:

Here we have used the standard formula for the sum of a geometric series:

Next we have:
• For any , we have .
Also if and only if , whereas if and only if .
• For any subset of , we have
• For any subsets and of , we have:

• The set is a finite set if and only if exists, if and only if and there exists a positive integer such that is an integer.
Here the minimum such integer is .
• When is finite, with , we define:

Then we have:

In particular, since , we have .
But then we have:

So and yet .
So the map is not injective.
In general, from the theory of binary expansions for real numbers, the map has the properties:
• is a well-defined surjective map from to the real interval .
To prove surjectivity, given the real number in the interval , we construct a sequence of approximations where is a finite set, such that and , for each .

For example for we have:

Continuing in this vein, we find that:

Check: we have:

This procedure can be carried out for any real in and in the limit as we have and then obeys .
• For and subsets of , with , we have if and only if (exactly) one of the sets or is a finite non-empty set:
• Then if is finite and non-empty, we have .
• Alternatively, if is finite and non-empty, we must have .
• So, given a real number , the number of solutions of the equation with is:
• Exactly one, if and only if no solution is a finite non-empty set, if and only if is 0 or or is never an integer, for any positive integer .
• Exactly two, if and only if there is a solution , which is a finite non-empty set, if and only if is not 0 or , but is an integer, for some positive integer , in which case the other solution is the set .
Now suppose that the reals form a countable set.
Then the real interval must also be countable.
Now the surjective map gives the formula:

As discussed above, for any , the set contains either exactly one element of , or exactly two elements.
In either case the set is countable.
So if is countable the formula: writes as a countable union of countable sets, so is countable.
This contradicts Cantor's Power Set Theorem, which says in particular, that the set is uncountable, since is countably infinite, so , so is uncountable.
So we have proved that the reals are uncountable and we are done.

Next: Cantor's Bijection Theorem Up: Finiteness09february2012 Previous: Cantor's Power Set Theorem;
George A. J. Sparling 2012-02-09