Cantor diagonalisation • Hacker News Board

Re: Cantor diagonalisation

#61

Post by petters » Sat, Mar 11, 2017, 10:43 PM UTC

sdenton4 wrote: post #55

t0mek wrote: post #50

This theorem blew my mind on the Set Theory 101. A particularly interesting implication is that we can't say anything about the vast majority of the real numbers. Anything we say or write, all texts created by the humanity now and in the future creates a countable set. Since the real numbers are not countable, we can't assign them with the definitions.

For some added fun: algebraic numbers are the set of all numbers which are roots of rational polynomials. You know, things like sqrt 2, along with all the rationals themselves. Algebraic numbers comprise the vast majority of real numbers we ever have a reason to actually use. These are also merely countable...

t0mek noted that all possible definitions of a number are countable. That would include all algebraic numbers.

Re: Cantor diagonalisation

#62

Post by effie » Sat, Mar 11, 2017, 10:48 PM UTC

t0mek wrote: post #50

This theorem blew my mind on the Set Theory 101. A particularly interesting implication is that we can't say anything about the vast majority of the real numbers. Anything we say or write, all texts created by the humanity now and in the future creates a countable set. Since the real numbers are not countable, we can't assign them with the definitions.

> we can't say anything about the vast majority of the real numbers.

It depends on which majority is at question. For that majority that is irrational, we can say any member can be approximated arbitrarily closely by a rational number.

Re: Cantor diagonalisation

#63

Post by erodommoc » Sun, Mar 12, 2017, 8:45 PM UTC

This seems to come up over and over again, and it always comes down to what assumptions you start with. If you accept all of the axioms and methods, the proof holds. If you don't, it doesn't. Articles like this one, aimed at an audience that already assumes that its techniques are valid, are never going to convince a non-mathematical audience that doesn't know what the basic assumptions are, because that's not their goal.

Re: Cantor diagonalisation

#64

Post by Smaug123 » Mon, Mar 13, 2017, 8:56 PM UTC

pwdisswordfish wrote: post #57

Smaug123 wrote: post #25

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

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

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.