Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Cantor diagonalisation

cs.virginia.edu

Post reply on HN
Print view View original

51–60 of 64 posts

Re: Cantor diagonalisation

#51

Post by openasocket »

btilly wrote: post #47
openasocket wrote: post #46

Earlier quoted context omitted.

You can't just define the reals to be something, you have to show that your construction is identical to the other constructions of the reals, like Dedekind cuts or Cauchy sequences. And yours doesn't: you can't represent Chaitin's constant in your definition, which is a real number.

If you wish to take that approach, you have to show that the other constructions of the reals actually construct something that exist. Which you can't. Just like you can't prove that ZFC is consistent. That's why this is a philosophical question that is foundational for mathematics.

> If you wish to take that approach, you have to show that the other constructions of the reals actually construct something that exist

First you said the reals are countable, now you're saying they don't exist at all?

What does it mean for something to "exist"? I can construct these sets from the axioms of ZFC, and under ZFC I can show your proof doesn't work.

Philosophy only enters into it when you are considering which axioms to take.

Re: Cantor diagonalisation

#52

Post by _rpd »

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

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

Re: Cantor diagonalisation

#53

Post by Smaug123 »

_rpd wrote: post #52
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".

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

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.

Re: Cantor diagonalisation

#54

Post by [deleted] »

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

[deleted]

Re: Cantor diagonalisation

#55

Post by sdenton4 »

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

Re: Cantor diagonalisation

#56

Post by btilly »

openasocket wrote: post #51
btilly wrote: post #47

Earlier quoted context omitted.

If you wish to take that approach, you have to show that the other constructions of the reals actually construct something that exist. Which you can't. Just like you can't prove that ZFC is consistent. That's why this is a philosophical question that is foundational for mathematics.

> If you wish to take that approach, you have to show that the other constructions of the reals actually construct something that exist First you said the reals are countable, now you're saying they don't exist at all? What does it mean for something to "exist"? I can construct these sets from the axioms of ZFC, and under ZFC I can show your proof doesn't work. Philosophy only enters into it when you are considering…

Philosophy only enters into it when you are considering which axioms to take.

I agree that by the time you start assuming ZFC, you're well past the realm of philosophy. The flip side of it is that in a discussion of philosophy you shouldn't make assertions based on axioms that have not yet been agreed on.

In any constructivist axiom system, the usual constructions of the real numbers do not define anything sensible. If you try to make sense of Cauchy sequences from a constructivist point of view, then you'll necessarily wind up with a definition that is very much like the one that I gave.

So you get the result that I stated. From a constructivist point of view, the usual "constructions" of the real numbers are nonsense and construct nothing, while the definition that I gave constructs something that can be reasonably called the real numbers. According to classical mathematics, both sets of constructions are well-defined, and the one that I gave is both complicated and different than the usual reals.

Which version you accept depends on your philosophical beliefs. Seeing what a different philosophical belief will lead to is very hard the first time you do it. But if you believe that it makes no sense to talk about the "truth" of unverifiable statements, you won't wind up debating the finer points of whether to accept C in ZFC...

Re: Cantor diagonalisation

#57

Post by pwdisswordfish »

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.

Re: Cantor diagonalisation

#58

Post by btilly »

wayn3 wrote: post #33
btilly wrote: post #12

Earlier quoted context omitted.

The truth of your statement depends on what philosophy of mathematics you accept. Which itself is not something that can ever be settled by pure reason. Here is a definition of the reals to consider. A real number is a computer program which implements a function f from positive integers N to the rationals such that |f(n) - f(m)| But now consider. There are a finite number of symbols that we build programs out of. Th…

tl;dr: Your argument doesn't make any sense. Don't copy math arguments from hipster blogs or wikipedia. They rarely make any sense. I am fully aware of the constructionist approach to mathematics. But your argument goes somewhat like this: The reals are real In computer programs however, we can only do so much Every computer program represents a real number For every bounded amount of bits, there is only a countable…

You are quick to dismiss the argument in every way possible, including ad hominem attacks, but you failed to actually try to comprehend it. Just as you failed to try to verify your ad hominem attack about my mathematical ignorance. (Here is a hint. People whose expertise comes from quoting "hipster blogs and wikipedia" usually can't turn around and point to things like http://dspace.library.uvic.ca:8080/bitstream/handle/1828/277... as evidence that they actually know some math.)

But let's move on to the critical point. You said this:

The real numbers are not accessible to in a "reality" way. They lie fully in the realm of arcane mathematics. Like many other things do.

You are lecturing me on the nature of the nature of existence of things which cannot be described or verified by any process that can be carried out or imagined by any process that can exist in our universe. In a discussion about whether we should accept any existence for such things. And are failing to address the point that assuming axioms that lead to the conclusion of existence is an entirely unprovable assumption!

Do you see the obvious problem here?

Re: Cantor diagonalisation

#59

Post by pwdisswordfish »

alok-g wrote: post #31

Genuinely asking: Consider decimal numbers between 0 and 1 in binary. Here's how I am going to synthesize this set. Step 1: Take non-decimal binary numbers and consider them to be padded with an infinite of zeros at the left. ...0000000 ...0000001 ...0000010 ...0000011 ...0000100 ...0000101 ...0000110 .......... Do we agree that this will contain all the non-decimal non-negative binary numbers? In particular, is the…

> decimal positive binary numbers

Make up your mind.

Re: Cantor diagonalisation

#60

Post by alok-g »

pwdisswordfish wrote: post #59
alok-g wrote: post #31

Genuinely asking: Consider decimal numbers between 0 and 1 in binary. Here's how I am going to synthesize this set. Step 1: Take non-decimal binary numbers and consider them to be padded with an infinite of zeros at the left. ...0000000 ...0000001 ...0000010 ...0000011 ...0000100 ...0000101 ...0000110 .......... Do we agree that this will contain all the non-decimal non-negative binary numbers? In particular, is the…

> decimal positive binary numbers Make up your mind.

Clarifications:

decimal: Not base 10, but fractional, those with a decimal point binary: Not just 0 or 1, but base 2.

0.01 is a binary positive decimal number which is 0.25 in base 10.

Post reply on HN