[Smaug123]

Cantor's theorem is better stated as "Let X be infinite. If f: powerset(X) to X, then f is not injective.". This is completely uncontroversial, and its proof is by diagonalisation in a context where it really does intuitively "just work". Set X to the naturals, and prove that the reals are equipotent with the powerset of N, to obtain "the reals are uncountable".

[_rpd]

> This is completely uncontroversial

I think it is still intuitively surprising that some infinite sets somehow have more elements than other infinite sets. The powerset operator is very special because it can create this difference.

[Smaug123]

I suppose I really meant "why should one expect that f might be injective anyway?" Once you're no longer in the context of a set like N which is very familiar, there's just no obvious reason for the theorem to be false.

[pwdisswordfish]

> Let X be infinite.

That assumption is unnecessary. Cantor's theorem works just as well for finite sets: it's simply the statement that 2ⁿ > n.

[Smaug123]

True, thanks. I thought the proof I knew of Cantor only worked for infinite sets, and that a separate proof was required for the finite case; but actually the same proof works for both.