Proof that the reals are uncountable.

Consider a probability distribution on naturals where each natural has positive probability. We know there are lots of such distributions; pick your favorite.

(This probabilistic language is convenient, but just a way of talking about convergent positive series.)

Consider also an arbitrary map (or even partial function) from naturals to reals. Applying this to the distribution above induces probabilities of drawing each real.

We will show that there is some real whose probability of being drawn is zero. This real must not be in the image of the arbitrary map. Thus, no map from naturals to reals is surjective.

We find this real by building a transfinite sequence of increasing reals eventually terminating in it.

Specifically, we build a well-ordered sequence of reals, following the rule that each value in our sequence is the total probability of drawing any of the prior values.

The first value of such a sequence must be 0.

The second value must be P(0) [where P(r) is the probability of r].

The third value must be P(0) + P(P(0)).

And so on.

This keeps going transfinitely.

The ωth value must be the sum of P(the nth value) for finite n.

The (ω + 1)th value must be the sum of P(the nth value) for finite n, + P(the ωth value).

And so on.

Our rule uniquely determines everything about this sequence, except for when to end the sequence.

We will keep going for as long as we can.

Given any sequence S of this sort, we can almost always extend it to a longer such sequence by tacking on another value at the end, the total probability of all the values in S.

The only situation where we fail to be able to extend S this way is when S already has a maximum element and the probability of this maximum element is zero. Then the total probability of S is just the same as its existing maximum element, and is not something new we can tack on.

As we said, we will continue our sequence for as long as possible according to our rule. The subset of the reals we produce is the longest possible S, some S which cannot be extended. And so it must terminate in a maximum element whose probability is zero.

I.e., an element not in the range of our arbitrary map from naturals to reals, thus witnessing that this map was not a surjection. QED.

No diagonalization necessary. This is also different from Cantor's original proof of the uncountability of the reals (which wasn't phrased in terms of diagonalization, though diagonalization can be seen as a special case of a cleaned up abstraction of it).