Cantor diagonalisation

Re:Cantor diagonalisation by Smaug123 on Saturday March 11, 2017 @02:39AM (#13844669)

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".

[ Parent | on HN ]

Re:Cantor diagonalisation by _rpd on Saturday March 11, 2017 @01:35PM (#13846520)

> 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.

[ Parent | on HN ]

Re:Cantor diagonalisation by Smaug123 on Saturday March 11, 2017 @01:42PM (#13846550)

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.

[ Parent | on HN ]

Re:Cantor diagonalisation by pwdisswordfish on Saturday March 11, 2017 @03:18PM (#13847017)

> 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.

[ Parent | on HN ]

Re:Cantor diagonalisation by Smaug123 on Monday March 13, 2017 @04:56PM (#13862265)

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.

[ Parent | on HN ]