Comment by hhm | Hacker News Reader

Comment by hhm | Hacker News Reader

Parent Full thread

I never really accepted Cantor's idea. First off if you have a sequence ...1 and ...0 at infinity they are the same number so saying you flip the last bit does not demonstrate that the above number is not in your set.

It doesn't work like that. You want to show that you can't enumerate all reals, so what do you do? You start enumerating all reals. Then you build a new number, whose Nth bit is different from the Nth bit of the Nth real number. You can do that because you have enumerated them, and we have never talked about an infinite N so we are never flipping the last bit of the last number nor anything similar. We are only flipping the Nth bit of the Nth number. Number 819439243? We flip the 819439243th bit. That's all we do.

What do you do then? Well, you compare that new number you created, with the first number, the second number, and so on. And you see that this number is different to all the other numbers.

What does it mean? That it doesn't matter what your enumeration scheme is, there is at least one number that will always be out of your enumeration scheme, and so your enumeration scheme will fail (so this is an absurd also, as we were supposing that this specific enumeration scheme -that could be any enum scheme- was complete). So you don't have as many integers as reals, so QED.

Secondly, if you take the Integer set and say N = the sum of all numbers > 0 you have counted, then you will never reach N as you go to infinity.

As you see, it doens't matter, as in this proof you never need to do the sum of all numbers.

Countability is considered a one-to-one correspondence with the infinite set of natural numbers.

Well let's count the natural numbers in binary, ..0000, ..0001, ..0010, ..0011, etc.

Now take the first digit of the first number and flip it,1 and the send digit of the second number and flip it, 1, etc. This is 2^x - 1. Is it countable because the natural numbers are countable? It's the same type of number you created on Cantor's diagonal. But it's never in the set you have counted. However, the same thing is true of x + 1.

The problem when constructing such numbers is there is not a final number in the set. So saying go to Infinity and add one or take 2 to the power of that and subtract one has no meaning.

PS: I think people don't equate them because they assume there is a difference between making a number larger and making a fraction more precise. So, 0.1, 0.11, 0.111, 0.1111 means something different than 1, 11, 111, 1111 etc.

You aren't undestanding the proof well; the proof isn't flawed. The best way to see it is to read it on a math book with full symbols and so on. Then you can see that there is no flaw, as every step follows from the previous one and that there is no philosophical reasoning about it, only maths.

I think the problem with how you are understanding it is that you think that your enumeration is finite at any time. That's not true.

Let's suppose we are only wanting to enumerate numbers between 0 and 1. So, you have to enumerate them like this:

0 -> some real

1 -> some real

...

n -> some real

for all naturals, so that you have infinite reals in your enumeration scheme. Now, you build your new real number, let's call it R. R is such that its Nth digit after the point is different than the Nth digit after the point of the Nth number. Let's suppose our procedure goes like this:

0 -> 0.1

1 -> 0.11111

2 -> 0.0001

3 -> 0.10101010101010....

4 -> 0.111011

What is R? R is a real number. It has a well-defined value for every one of its digits, so why wouldn't it be a real number? So we have, a real number between 0 and 1, and an infinite enumeration of reals.

Let's see the value of R:

0 -> 0.1

1 -> 0.11111

2 -> 0.0001

3 -> 0.10101010101010....

4 -> 0.111011

so R is:

0.00110 and so on.

Is R 0.00110? R has more digits, is more like 0.00110abcdefg with abcdefg being some more digits we should calculate. R has infinite digits, not only those, and we could calculate all of them by a finite procedure, so we aren't doing anything magical here. What those digits' value is we don't mind, as you'll see.

What we mind about is this: R is different to the first number. How can we know? Because by construction, the first digit of R is different from the first digit of the first number. Now, let's see if R is in our countable set. If R was in our countable set, R would be in a place, for example in the position M of the enumeration. Now, in the position M of the enumeration we have the Mth number, and by construction, the Mth number is different to the R number, as they have at least a digit that is different between them (and we can even say: the Mth digit is different between them).

So, how could R be in the enumeration scheme if we can't place it at any M? Now, that's why we have an absurd here, and that's why every enumeration scheme for reals will be incomplete.

I wish this solves your doubts about it. Please only focus on the mathematical demonstration, we aren't saying nothing about countability, infinities, or very large numbers excepting when we have to.

Let's use your approach to define every other number the other uses the classic counting method.

Every other number will be the same as your number for N-1 digits. So at infinity your number is the same except for the last digit but two real numbers N and N + 1/infinity are the same.

Let's see if I understand it well:

You define a numbering scheme that goes like this:

- the first number is, say, 0

- the Nth number is so that, its Mth digit for M<N is different to the Mth digit in M

Do I understand you well?

If that's what you mean, then I define a new number, R, that is different to all numbers in the sequence. It's defined as usual.

How do I know that this R number is different to all numbers in your sequence? Well, I can take any M number from your sequence and compare it to R. However, the Mth number is different to R in its Mth digit.

About the limit in the infinite... it doesn't matter at all... You can't take a M value that's infinite, as we have only numbers that have a finite size (there are infinite numbers with finite size, that's the trick on this; there aren't integers with an infinite size for example). And if you take an M that's finite, then you have to say that such Mth element is different to my R.

And so on for any sequence you can build (even for sequences you can't build, like random sequences).

Edit: possibly the big thing that's confusing you is that you can't have an infinite number, even if there are infinite numbers. So, taking the limit of a function is something that has a very restrict meaning that is actually not directly related to the concept of infinity. If you check the definition of limit it doesn't talk about infinities but about deltas, and if you use such definition your proposed problem stops being a problem. http://en.wikipedia.org/wiki/Limit_(mathematics)#Formal_definition

possibly the big thing that's confusing you is that you can't have an infinite number, even if there are infinite numbers

Yep, that's new to me. So one followed by infinite zeros is not a rational number number. I have read otherwise, but I assume it was a sloppy definition of infinity that works when your not talking about countable numbers.

Real numbers can have infinite digits, but only after the point, such as pi. The size of any number, even if it's real, can't be infinitely big (a real is between two integer numbers, and integer numbers have to be finite). So yes, 1000(...)00000 with infinite 0s doesn't exist as a number.

Nice conversation anyway.

Reply on news.ycombinator.com