Thus, since r and f(i) differ in their i-th digits, r differs from any value taken by f. Therefore, f is notsurjective (there are values of its result type which it cannot return).
Consequently, no function from the natural numbers to the reals is surjective. A further theorem dependent on the axiom of choice turns this result into the statement that the reals are uncountable.
This is just a specialcase of a diagonal proof that a function from a set to its power set cannot be surjective:
Let f be a function from a set S to its power set, P(S) and let U =x in S: x not in f(x) . Now, observe that any x in U is not in f(x), so U != f(x); and any x not in U is in f(x), so U != f(x): whence U is not in f(x) : x in S . But U is in P(S). Therefore, no function from a set to its power-set can be surjective.