Hacker News Reader

Comment by nico | Hacker News Reader

> But for the set of real numbers, no matter what sequence we choose, we will never ever find the diagonalized number in our sequence.

So then it’s only proving that if you choose the ordering ahead of time, you won’t be able to do it, because real numbers don’t have a predefined order. You can only order them as you produce them.

If you re-sort after each iteration (or insert them in order), you can count as many real numbers as you want.

In any case, for practical applications, you could never count anything infinite, at some point you’d run out of physical storage to keep the count.

How many bits can be encoded in the universe? That will give the limit of what could ever be counted. And it’s not infinite.

View on HN

> So then it’s only proving that if you choose the ordering ahead of time, you won’t be able to do it, because real numbers don’t have a predefined order. You can only order them as you produce them.

What's the problem? You just produce the diagonalized number at the same time as you produce your order. Every order you produce them in has its own corresponding diagonalized number that will never be produced.

> If you re-sort after each iteration (or insert them in order), you can count as many real numbers as you want.

You can count as many real numbers as you want, but none of them will ever be equal to the diagonalized number. (That is, in finite time, you will always be able to find a digit that differs between the two numbers.)

> How many bits can be encoded in the universe? That will give the limit of what could ever be counted. And it’s not infinite.

How do you know the universe isn't infinite?

Regardless, I don't see why we shouldn't consider formal systems in which infinite amounts of information can be manipulated. Even in our finite light cone, mathematical statements about infinite sets can help us separate the possible from the impossible. For instance, mathematics tells us that adding 1 to any integer will never produce the same integer. There are infinitely many integers, so we can't experimentally verify this in the real world. But if we accept that abstract statement, then we know what to expect when we do try to physically add one object to a group of objects.

If as you say, the infinity of the real numbers lacks the property of predefinable order, whereas the infinity of the natural numbers does have that property, does it not strike you that those infinities may be fundamentally different in some way relating to size, and therefore mapability?

It only strikes me that we are trying so hard to know the unknowable.

Infinite essentially mean unknown. How could you possible compare the size of two unknowns?

You just can’t, but we want to be able to reduce something infinite/unknowable, to a finite symbol that we can use in our limited language.

Edit: for sibling comment -> how would you know the cardinality of a set without counting it? And if you have two infinite sets, how would you ever finish counting them to determine their cardinality and compare them?

It doesn’t even make sense to talk about the cardinality of an infinite set, infinity is not a number.

We pretend that the infinity symbol can somehow magically summarize and quantize something that is essentially unknowable.

The infinity symbol doesn’t make something magically finite.

The cardinality of an infinite set is unknowable. It is not “infinity”.

> Infinite essentially mean unknown. How could you possible compare the size of two unknowns?

The point is, that's not really what infinite means. A set being infinite just means that we can start listing elements, and we'll always be able to find a new element that we haven't listed before.

To compare two infinite sets A and B, we can consider functions F that take any element from A and output some element from B.

If A and B have the same cardinality, then we can always describe a certain function F that can potentially output any element from B, if we know the right input from A.

But if B has a greater cardinality than A, then we cannot find any such function. No matter which function F we choose, there will always be certain values in B that can never be output by F given any input in A. Thus, we say that B has "more elements" than A in a certain sense.

In the case of Cantor's argument, A is the set of natural numbers, B is the set of real numbers, and F is the ordering we choose.

A variation of Cantor's argument can be expressed fully in terms of finite objects. Suppose we have a function F such that F(i) = f_i, where f_i is a function such that f_i(j) represents the jth digit of the ith real number in the sequence.

Then, we can write a new function g(j) = (F(j)(j) + 2) mod 10, or some variation. This function g(j) similarly represents a real number.

Now, we can take any i we want and start comparing f_i(1) vs. g(1), f_i(2) vs. g(2), etc. After a finite amount of time, we'll always reach a point where the two functions differ. This means that the two functions represent two different real numbers.

Therefore, the real number represented by g is not represented by any of the f_i, no matter which function F we start with.

Thank you, I really appreciate your thoughtful explanation.

> A set being infinite just means that we can start listing elements, and we'll always be able to find a new element that we haven't listed before.

You can do that for the real numbers, by keeping a set of all the unique real numbers you’ve produced before, then adding one random real number at a time, always checking that is not in the set already.

And if you could go forever, then the probability of generating every real number is 1.

However, infinity is unknowable. You can’t just say that the “infinite” cardinality of a set can just be reduced to a symbol, that is like saying you finished doing the calculation and that you know there’s a final result. But there isn’t a final result.

The arguments in your explanation only prove that you cannot predict or choose an ordering for the real numbers before counting them. But if you produce random real numbers at each step and re-order them, you don’t need a predefined order. In fact the order can just be the order in which the real number was generated, regardless of its value, then you don’t even need to reorder them.

Edit: replying to reply to this by LegionMammal978 as the nesting level doesn’t let me reply under it

Thank you for the engaging conversation.

You found the issue: Cantors argument assumes you can finish an infinite process and then add an extra step…

Please see this other comment: https://news.ycombinator.com/item?id=35311403

> However, infinity is unknowable. You can’t just say that the “infinite” cardinality of a set can just be reduced to a symbol, that is like saying you finished doing the calculation and that you know there’s a final result. But there isn’t a final result.

We put a symbol on cardinality because it lets us make statements about the properties of sets, like whether or not we're able to map them one-to-one with other sets. In turn, this often helps us with proving statements about finite objects. (Technically, they let us quantify over different scenarios: say what can't happen, or can happen, or might not happen, or must always happen.) To repeat my example, we say with symbols that x + 1 > x for all the infinitely many numbers x, even though we can't physically check all of them. But if you hand me some physical number X and I add 1 to it, I can apply the abstract statement to know that I'll get a bigger number in that scenario.

> The arguments in your explanation only prove that you cannot predict or choose an ordering for the real numbers before counting them. But if you produce random real numbers at each step and re-order them, you don’t need a predefined order. In fact the order can just be the order in which the real number was generated, regardless of its value, then you don’t even need to reorder them.

I don't understand what you're trying to say here. In more finite terms (given that random real numbers already contain infinite information), the diagonalization argument says, "You can keep generating individual real numbers as long as you want, by any process. But there'll always be at least one real number that you'll never ever count to, no matter how long you keep generating numbers." (You can't say the same thing about the natural numbers: some methods of counting them will, in fact, reach every number sooner or later. That's the crucial distinction.)

This does not require any kind of "predefined order". In fact, the diagonalization has to listen to all the numbers we generate just to provide an example of an unreachable number. So at any given point in the process, we can't know in full what the unreachable number is (without knowing the generation process); we only know its initial digits. But the limit of these partial answers is the full unreachable number, which had already been there in the first place.

(I hope you accept the idea of an arithmetic limit; without it, we'd have trouble with basic things like justifying that 0.999... = 1, or resolving Zeno's paradoxes of motion. It's an intrinsic part of what a real number is.)

We're talking about infinity, not practical considerations.

> (or insert them in order),

There is no order. You can't describe one, and it is proven that no order exists.

> you can count as many real numbers as you want

No, you can't count more than 0% of them, even in infinite steps.

The order is arbitrary. What is the order of natural numbers? If you say they are in ascending order, that’s just the order in which you count them.

The same way, I can just generate random real numbers, then define my set as in ascending order, and insert them in that order.

Which is what we essentially do with natural numbers as well. Except that the order is a sort of mainstream standard and has been drilled into our minds since babies.

> The same way, I can just generate random real numbers, then define my set as in ascending order, and insert them in that order.

To perform the diagonalization, we can simply look at each real number that you randomly generate and add digits to the diagonalized number based on that order. It doesn't matter how much you shuffle them around afterward: the diagonalized number will still be different from all the generated numbers.

What you are saying is:

1) I will produce an infinite amount of numbers, then stop

2) I will look at the infinite amount of numbers and then produce a number which is not within the infinite numbers

3) Hey look, the number I produced in 2) is not within the infinite set, so there must be a larger infinite set

The issue is that you can never finish 1). That’s the error/illusion.

But if you get to cheat, then I can also add a step 4) As long as you add digits to my numbers to generate an additional number, I will reorder the set of generated real numbers and assign each of them a natural number.

Of course the order will change from iteration to iteration. But in this way the generated real numbers will always have a corresponding natural number.

Where did I imply 1)? We never finish producing the numbers, so unless our production order was fixed from the beginning, we never know the full value of the diagonalized number. But the partial diagonalized number (which we refine at each step by looking at the produced number) will gradually converge to a limit, which is a real number different from any number we will ever produce. At no point in the process do we know the limit exactly, but it is there nonetheless.

> Of course the order will change from iteration to iteration. But in this way the generated real numbers will always have a corresponding natural number.

The real numbers that you generate will always have a corresponding natural number. But the diagonalized number will never have a corresponding natural number, no matter how much you shuffle your generated values.

You are saying that when you stop counting, the diagonal number will be different.

That means that you stop. Which implies you are not going to infinity.

If you are going to infinity, there is no side that “wins” (real or naturals). You can always keep generating an additional one for either side.

The same way, we could continue this discussion forever if we just want to keep going back and forth (although HN does impose a limit of replies). And you could only make an assertion about the length of each side of the conversations, after the conversation ends. But if the conversation keeps going forever, you could never say to talked more than the other. Unless you specify a finite range for which you want to measure.

Naturals and Reals are both infinite. Saying that the cardinality of one is different than the cardinality of the other, is just comparing the ideas of cardinality about them that we have come with, but their actual cardinality can never be known.

> You are saying that when you stop counting, the diagonal number will be different.

Where, in all my comments, do I say that we must stop counting? You're putting words in my mouth here.

Since we don't stop counting, we never know the diagonal number's full value (unless our order is predefined). All we know is that the diagonal number exists, and it is different from all the real numbers we will ever count.

> If you are going to infinity, there is no side that “wins” (real or naturals). You can always keep generating an additional one for either side.

Of course. I am not disputing this. If we count through two different sets in the same way, then the subsets of values we count through will have the same cardinality (equal to the cardinality of the set of natural numbers).

But there's an important distinction. If we count through the natural numbers one-by-one without stopping, it's possible to exhaust the whole set of natural numbers, such that every single number will eventually get counted to.

Meanwhile, if we count through the real numbers one-by-one, it is impossible to reach all of them. There will always be a bunch of real numbers that we will never ever count to. That's why we say that there are more real numbers than can be counted: there are uncountably many.

> Where, in all my comments, do I say that we must stop counting? You're putting words in my mouth here.

You didn’t say it explicitly. But you are implying it when you assume you can count the naturals.

By assigning a label (eg. aleph-null) to infinity, is assuming you can finish counting them. The only way to finish is by stopping.

We assign the label ℵ₀ to an infinite set when we want to express the property that any given element can eventually be reached in a finite time if we keep counting for long enough. That's what it means, no more and no less. I don't see what it has to do with "assigning a label to infinity" or "assuming you can finish counting them". We don't use cardinalities to magically make the infinite finite (well, I don't, but I'm sure some pop-math explanations do), we use them to compare and contrast the properties of infinite sets, and refusing to acknowledge these properties doesn't make them go away.

> We assign the label ℵ₀ to an infinite set when we want to express the property that any given element can eventually be reached in a finite time if we keep counting for long enough.

Look at your definition: “if we keep counting long enough”

You are reducing infinity to “long enough” and using that as a label for infinity.

You can’t know ahead of time that you will be able to finish without finishing.

You are saying you can know the unknown. But you won’t until you go and try to count the numbers.

You will never be able to count all the natural numbers. Regardless of what you think the formulas/symbols mean.

Math doesn’t happen by itself, it needs an interpreter to “execute the operations”. Without an operator, math is just a bunch of symbols.

The operator will never finish counting natural numbers. Or any other sequence/set/group of numbers that is infinite.

Perhaps I have not been as clear as I should be. The sequence of counted numbers is infinite, and we would never be able to finish counting all of it. But all we care about for defining ℵ₀ is whether or not the sequence contains some particular value. If it does contain the value, then we can confirm that in finite time, even though the sequence is infinite.

Let me try reframing it a bit. First, you think of some natural number N (e.g., 978) and keep it to yourself. Then, I start counting, "0, 1, 2, 3, 4, 5, ..." and never stop. You listen to me count until you hear N. Then, you can stop listening, even though I'll never stop counting. At that point, you already know that my sequence contains N, and you don't have to keep listening.

I hope you agree that no matter which N you choose, you'll hear me say it sooner or later, as long as I keep counting up by 1. If N is a smaller number, you'll hear me say it sooner; if N is a bigger number, you'll hear me say it later. But there's no N you can choose that forces you to listen to me forever. (And again, just because you stop listening doesn't keep me from talking forever.)

The same thing cannot be done with the real numbers. If you think of some real number R that I don't know, then there's no way for me to count through the real numbers to guarantee that you will eventually hear R and stop listening. Even if I do try to pick a certain sequence, there's a very good chance that you'll never hear R and you'll have to keep listening forever.

Ascending order is just one of many arbitrary orders. An ordering is a first output of a generator function, a second output, a third output, etc, where for any arbitrarily chosen element X of the set (such as the positive integers or reals), we can show that the generator will reach X in N steps, for some finite N.

That is why ascending order is the norm for the positive integers. For any positive integer X, it is clear that we will reach it in X steps using that generator function. So, it’s not a matter of being mainstream, it’s just the simplest.

The difference between the infinity of the reals and the positive integers is that there is no such generator function for the reals. No matter what function you give me, I can write a finite number that you will not reach in a finite number of steps.

Feel free to give me a generator function and I will give you a finite number that it cannot reach in finite steps. On the other hand, try giving me a finite positive integer that I cannot reach in finite steps.

Neither the reals nor the naturals “exist”. We produce them as we need them.

Reals and naturals both have the same number of symbols: unknowable (“infinity”).

> Feel free to give me a generator function and I will give you a finite number that it cannot reach in finite steps.

f(n)=n

If you give n to that formula, it will generate n in 1 step.

> On the other hand, try giving me a finite positive integer that I cannot reach in finite steps.

Can’t come up with one. As long as is finite you can always just output the number itself.

Anything finite is countable. Anything infinite is unknowable.

Nono. F(n) where n is the number of steps, not the desired number. You’ve got it backwards. The number is the output, not the input.

N was the number of steps, but sure:

F(x)=x, will give you x in one step.

Reply on news.ycombinator.com