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

Mathematicians Measure Infinities, Find They’re Equal

quantamagazine.org

Post reply on HN
Print view View original

121–130 of 170 posts

Re: Mathematicians Measure Infinities, Find They’re Equal

#121

Post by waqf »

yorwba wrote: post #56
iamlucaswolf wrote: post #28

Earlier quoted context omitted.

Phew, you have some courage, questioning the foundations of modern Mathematics in a place like this. But I can relate to your concerns about Cantor's argument. When I first heard it, it also felt artificial and unconvincing to me. What helped me (as with many proofs and concepts in Math) was an image, a visual metaphor if you like. Imagine a very, very large paper on which you place infinitely many dots in a grid. Th…

That's a very nice intuition, but for the wrong concept. What you have been describing is the difference between a dense set (almost no holes) and a nowhere-dense set (holes everywhere). It turns out that there is a nowhere-dense set that is still uncountably infinite: https://en.wikipedia.org/wiki/Cantor_set

No, iamlucaswolf is correct, describing a countable dense set (the dyadic rational points) and an uncountable dense set.

Re: Mathematicians Measure Infinities, Find They’re Equal

#122

Post by ars »

zelah wrote: post #111
adenadel wrote: post #106

Earlier quoted context omitted.

This is equivalent to asking what is the average number of digits necessary to represent an arbitrary natural number. If you assume that this is a finite number you can quickly arrive at a contradiction.

So there are natural numbers with an infinite number of digits and that is my point. The average can't be larger than the largest number.

> necessary to represent an arbitrary natural number

What makes you think this number exists? Infinities can not be added and divided this way.

> The average can't be larger than the largest number.

But it can be equal to it. You mistake is not realizing that infinity minus 1 = infinity.

So the average is "smaller" than the largest, and yet equal to it. Because like I said at the start, you can not just add infinities in the normal way you can manipulate finite numbers.

Re: Mathematicians Measure Infinities, Find They’re Equal

#123

Post by Others »

abnry wrote: post #94
samoright wrote: post #79

> In a breakthrough that disproves decades of conventional wisdom, two mathematicians have shown that two different variants of infinity are actually the same size I thought there are only two types of infinity and Cantor already proved that they are different. * Uncountable infinity which is the cardinality of the set of real numbers * Countable infinity which is the cardinality of the set of integers Cantor has alr…

If you take the power set of an infinite set, you /always/ get a cardinality bigger than the original set. So there are an infinite number of infinities.

This is a good point. But to be super pedantic, there isn't a size of infinity large enough to describe how many sizes of infinity there are.

Re: Mathematicians Measure Infinities, Find They’re Equal

#124

Post by zelah »

lisper wrote: post #120
zelah wrote: post #119

Earlier quoted context omitted.

I will just diagonalize forever before I give the set to Cantor. If he claims that he can diagonalize the set to generate a new number not in the set then I will say "Oh, yeah - I missed one. I wasn't really done after all. Give it back to me and I will add some more to it before you get your hands on it!". As you can see, Cantor will never get a list because I will never really be done generating it. I could just gi…

> Cantor will never get a list because I will never really be done generating it. That would be true even if you weren't diagonalizing because the list is infinite. In fact, just a single item in the list is potentially infinite. So you can't generate the whole list regardless. What you have to do is to produce an algorithm that takes any two natural numbers i and j as input and produces as output in finite time the…

Why is it that Cantor can do an infinite procedure of diagonalization but I can't? If he can diagonalize then I can too. Is it possible that Cantor's "algorithm" is not really an algorithm? Knuth says an algorithm must be correct and must also terminate.

Regardless, I have a lot to ponder.

Re: Mathematicians Measure Infinities, Find They’re Equal

#125

Post by chriswarbo »

lisper wrote: post #117
chriswarbo wrote: post #112

Earlier quoted context omitted.

> The proof is like a game. It says: give me any procedure for (putatively) making a list of all of the real numbers, and I will give you back a number that is not in the list. The game isn't fair though; we have to write down our complete solution (e.g. in the form of a never-halting, co-recursive computer program), then Cantor can take as much time as he likes (any finite number of steps) to analyse the source code…

> if we make him write it down (as a computer program) He did. Diagonalization is an algorithm. It's a non-halting algorithm (because it operates on infinite input and produces infinite output) but it is nonetheless a perfectly well defined algorithm that can be implemented by a Turing Machine. > we can always (eventually) find a program which will trick it No, you can't.

You're right about diagonalization when it's given our choices as input. When I said 'writing down' I meant 'in a self-contained way', i.e. without taking any input (such as our choices).

This rules out diagonalization, since that can't be run until it has a list of numbers to diagonalize. In the 'reverse' game, we're first running the counter-example-outputting program that Cantor provides, and then using its output to pick our numbers. If Cantor gives us a diagonalization program, we'll get a deadlock. In fact, the strategy to beat Cantor in this reverse game is simply the identity function: if Cantor's program claims that "X" isn't in our list, we can refute it by outputting "X".

The way I think about it is this: if we give Cantor our program up-front, he can run it to see what we're going to choose, then pick his 'move' accordingly (e.g. via diagonalization); if Cantor gives us his (self-contained) program up-front, we can run it to see what 'move' he's going to choose, and pick ours accordingly (e.g. via the identity function).

Both games are a win for whoever goes second.

Alternatives to the 'up-front' approach include:

- Interleaving or concurrent outputs, in which case there would be no winner: each time a number is added to the list, diagonalization extends its counter-example with another digit; each time the counter-example is extended, a number with matching prefix is added to the list.

- Interleaving or concurrent programs, with access to each others' source. I think the winner would be whoever has the most computing power (and can hence simulate their opponent further into the future).

Re: Mathematicians Measure Infinities, Find They’re Equal

#126

Post by [deleted] »

lisper wrote: post #120
zelah wrote: post #119

Earlier quoted context omitted.

I will just diagonalize forever before I give the set to Cantor. If he claims that he can diagonalize the set to generate a new number not in the set then I will say "Oh, yeah - I missed one. I wasn't really done after all. Give it back to me and I will add some more to it before you get your hands on it!". As you can see, Cantor will never get a list because I will never really be done generating it. I could just gi…

> Cantor will never get a list because I will never really be done generating it. That would be true even if you weren't diagonalizing because the list is infinite. In fact, just a single item in the list is potentially infinite. So you can't generate the whole list regardless. What you have to do is to produce an algorithm that takes any two natural numbers i and j as input and produces as output in finite time the…

[deleted]

Re: Mathematicians Measure Infinities, Find They’re Equal

#127

Post by [deleted] »

lisper wrote: post #120
zelah wrote: post #119

Earlier quoted context omitted.

I will just diagonalize forever before I give the set to Cantor. If he claims that he can diagonalize the set to generate a new number not in the set then I will say "Oh, yeah - I missed one. I wasn't really done after all. Give it back to me and I will add some more to it before you get your hands on it!". As you can see, Cantor will never get a list because I will never really be done generating it. I could just gi…

> Cantor will never get a list because I will never really be done generating it. That would be true even if you weren't diagonalizing because the list is infinite. In fact, just a single item in the list is potentially infinite. So you can't generate the whole list regardless. What you have to do is to produce an algorithm that takes any two natural numbers i and j as input and produces as output in finite time the…

[deleted]

Re: Mathematicians Measure Infinities, Find They’re Equal

#128

Post by adenadel »

zelah wrote: post #111
adenadel wrote: post #106

Earlier quoted context omitted.

This is equivalent to asking what is the average number of digits necessary to represent an arbitrary natural number. If you assume that this is a finite number you can quickly arrive at a contradiction.

So there are natural numbers with an infinite number of digits and that is my point. The average can't be larger than the largest number.

The only way to reason about this is as a limit.

lim n->infty sum(1..n)/n.

This limit diverges. Your intuition is breaking down. It might be useful for your understanding to study real analysis where these sorts of questions are handled rigorously.

Re: Mathematicians Measure Infinities, Find They’re Equal

#129

Post by mcguire »

lisper wrote: post #12
zelah wrote: post #3

I find Cantor's diagonal argument unconvincing. The claim is that there are more real numbers in the range from zero to one than there are natural numbers. To see that this is false simply realize that you don't actually have to write a decimal point to specify the real numbers in this range. Without the decimal point these real numbers just become natural numbers. Can a rational person believe that there are infinit…

> Without the decimal point these real numbers just become natural numbers. No, they don't, because the vast majority of them have an infinite number of digits to the right of the decimal point. That's the key: there are more numbers with an infinite number of non-zero digits (the reals) than there are numbers with a finite number of non-zero digits (the naturals). > The problem with Cantor's argument comes down to t…

"the vast majority of them have an infinite number of digits to the right of the decimal point."

Technically, I believe all of the real numbers have an infinite number of digits to the right of the decimal point.

A vanishingly small portion of them have a repeating series of digits, such as 0. :-)

Re: Mathematicians Measure Infinities, Find They’re Equal

#130

Post by yongjik »

zelah wrote: post #124
lisper wrote: post #120

Earlier quoted context omitted.

> Cantor will never get a list because I will never really be done generating it. That would be true even if you weren't diagonalizing because the list is infinite. In fact, just a single item in the list is potentially infinite. So you can't generate the whole list regardless. What you have to do is to produce an algorithm that takes any two natural numbers i and j as input and produces as output in finite time the…

Why is it that Cantor can do an infinite procedure of diagonalization but I can't? If he can diagonalize then I can too. Is it possible that Cantor's "algorithm" is not really an algorithm? Knuth says an algorithm must be correct and must also terminate. Regardless, I have a lot to ponder.

Okay, let me try to write these "algorithms" in a concrete term.

Assume that you have a way of generating a sequence R_1, R_2, R_3, ... of real numbers in [0, 1]. (For simplicity, let's just consider [0, 1], because it still has the same cardinalityas R.) You have your "algorithm":

    generate_digit(i, j):
        Somehow compute the j'th digit of R_i.
        return the digit
You are allowed to spend infinitely long time to return each digit. (That is, you can use constructions that are not even computable in finite time, as long as you can prove that given i and j, there is exactly one digit that satisfies your criterion.)

Cantor's objective is to defeat your algorithm by generating a real number not in the list. Similarly as above, it can be written as a function that returns the j'th digit, given j. Behold it in its full glory:

    defeat_indexing(j):
        digit = generate_digit(j, j)
        return (digit + 1) % 10
That's it.
Post reply on HN