[avani]

In a similar vein, Cantor's original diagonalization proof of uncountability is one of the most satisfying results in real analysis. From https://www.cs.virginia.edu/luther/blog/posts/124.html:

"Any real number can be rep­re­sented as an inte­ger fol­lowed by a dec­imal point and an infi­nite sequence of dig­its. Let’s ignore the inte­ger part for now and only con­sider real numbers between 0 and 1. Now we need to show that all pair­ings of infi­nite sequences of dig­its to inte­gers of neces­sity leaves out some infi­nite sequences of dig­its.

Let’s say our can­di­date pair­ing maps pos­i­tive inte­ger i to real number r_i. Let’s also denote the digit in posi­tion i of a real number x as x_i. Thus, if one of our pair­ings was (17, 0.651249324…) then r_17^4 would be 2. Now, con­sider the spe­cial number z, where z_i is the bot­tom digit of r_i^i + 1.

The number z above is a real number between 0 and 1 and is not paired with any pos­i­tive inte­ger. Since we can con­struct such a z for any pair­ing, we know that every pair­ing has at least one number not in it. Thus, the lists aren’t the same size, mean­ing that the list of real numbers must be big­ger than the list of inte­gers."

[kmill]

Before the diagonalization argument, Cantor had another proof of the uncountability of the reals. Looking it up again, it's actually pretty much the Alice-Bob game!

See theorem 2: https://www.maa.org/sites/default/files/pdf/upload_library/2...

(To see the correspondence, it's helpful to think of limits as being a kind of game. You claim the limit is a particular value, another party challenges you with an epsilon, and then you respond to the challenge by saying an index in the sequence after which all the entries are within epsilon of the claimed limit.)

[jwilk]

The proof on this page has a small gap: it fails to take into account that some numbers don't have unique decimal expansion.

For example, if all digits on the diagonal were 8, then z = 0.(9) = 1, which is not between 0 and 1.

[eru]

Yes. Though that problem is repairable.

[eru]

Cantor's diagonal argument is interesting, because it's not just a nifty proof, but seen as an entirely new proof strategy. Those don't get invented often.