The real numbers are more numerous than the natural numbers. Moreover, has the same number of elements as the power set of Symbolically, if the cardinality of is denoted as , the cardinality of the continuum is
This was proven by Georg Cantor in his uncountability proof of 1874, part of his groundbreaking study of different infinities. The inequality was later stated more simply in his diagonal argument in 1891. Cantor defined cardinality in terms of bijective functions: two sets have the same cardinality if, and only if, there exists a bijective function between them.
Between any two real numbers a < b, no matter how close they are to each other, there are always infinitely many other real numbers, and Cantor showed that they are as many as those contained in the whole set of real numbers. In other words, the open interval (a,b) is equinumerous with This is also true for several other infinite sets, such as any n-dimensional Euclidean space (see space filling curve). That is,
A variation of Cantor's diagonal argument can be used to prove Cantor's theorem, which states that the cardinality of any set is strictly less than that of its power set. That is, (and so that the power set of the natural numbers is uncountable). In fact, one can show that the cardinality of is equal to as follows:
Define a map from the reals to the power set of the rationals, , by sending each real number to the set of all rationals less than or equal to (with the reals viewed as Dedekind cuts, this is nothing other than the inclusion map in the set of sets of rationals). Because the rationals are dense in , this map is injective, and because the rationals are countable, we have that .
Let be the set of infinite sequences with values in set . This set has cardinality (the natural bijection between the set of binary sequences and is given by the indicator function). Now, associate to each such sequence the unique real number in the interval with the ternary-expansion given by the digits , i.e., , the -th digit after the fractional point is with respect to base . The image of this map is called the Cantor set. It is not hard to see that this map is injective, for by avoiding points with the digit 1 in their ternary expansion, we avoid conflicts created by the fact that the ternary-expansion of a real number is not unique. We then have that .
(This is true even in the case the expansion repeats, as in the first two examples.)
In any given case, the number of digits is countable since they can be put into a one-to-one correspondence with the set of natural numbers . This makes it sensible to talk about, say, the first, the one-hundredth, or the millionth digit of π. Since the natural numbers have cardinality each real number has digits in its expansion.
Since each real number can be broken into an integer part and a decimal fraction, we get:
where we used the fact that
On the other hand, if we map to and consider that decimal fractions containing only 3 or 7 are only a part of the real numbers, then we get
the transcendental numbers
We note that the set of real algebraic numbers is countably infinite (assign to each formula its Gödel number.) So the cardinality of the real algebraic numbers is . Furthermore, the real algebraic numbers and the real transcendental numbers are disjoint sets whose union is . Thus, since the cardinality of is , the cardinality of the real transcendental numbers is . A similar result follows for complex transcendental numbers, once we have proved that .