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

111–120 of 170 posts

Re: Mathematicians Measure Infinities, Find They’re Equal

#111

Post by zelah »

adenadel wrote: post #106
zelah wrote: post #103

Please answer me this one question: What is the average number of bits that are necessary to represent an arbitrary natural number? If the average number of bits is finite then I will shut up!

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.

Re: Mathematicians Measure Infinities, Find They’re Equal

#112

Post by chriswarbo »

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 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 and find a Real it'll never output.

Yet we can turn the tables to play a different game: whatever counter-example-finder Cantor chooses, if we make him write it down (as a computer program), we can always (eventually) find a program which will trick it: outputting only a countable number of Reals, but always a superset of those checked for by Cantor's program.

Of course, if we're representing the players of the game using computer programs, then we can go one step further and show that only the Computable numbers (a subset of the Reals) can ever be generated, and the computables are countable! (We can count them by pairing off all programs with all runtimes)

Re: Mathematicians Measure Infinities, Find They’re Equal

#114

Post by davidivadavid »

ColinWright wrote: post #108
davidivadavid wrote: post #102

Is it me or they forgot a step in the diagonalization argument? (adding/subtracting 1)

They say to change every number, and that's enough. Although they don't explicitly say so you can change each number in (nearly) any way you like.

My bad, skipped that part somehow.

Re: Mathematicians Measure Infinities, Find They’re Equal

#115

Post by jtc1983 »

mturmon wrote: post #100
logfromblammo wrote: post #78

Earlier quoted context omitted.

Fine, then. Just use the smallest positive nonzero real number, instead. Edit: I really hope I'm not the only one laughing.

"...only one laughing..." You are illustrating the reason that mathematicians generally disparage the concept of an "infinitesimal", when it's used as proof rather than conceptual aid. (Yes, I know about https://en.wikipedia.org/wiki/Non-standard_analysis ) Not only do you get wrong conclusions, you get tedious, hard-to-adjudicate arguments.

I agree with your thought, and that of the majority of mathematicians for many years, that infinitesimals are better construed heuristically than literally.

You mention that you know of non-standard analysis and indicate that it's irrelevant. Though I don't know why you think this, I agree with you. I just wanted to plug non-standard analysis as both mathematically interesting and also very useful. One can jettison the philosophical thought that NSA "vindicates" the historical use of infinitesimals (as I think we should), while still seeing NSA as the wonderful and deep piece of math that it in fact is.

Re: Mathematicians Measure Infinities, Find They’re Equal

#116

Post by gumby »

Photos of humans in an article about math are pretty useless but nevertheless I find it interesting that the article included a photo of the male collaborator, Saharon Shelah, and another male mathematician, but not one of the female collaborator, Maryanthe Malliaris.

Re: Mathematicians Measure Infinities, Find They’re Equal

#117

Post by lisper »

chriswarbo wrote: post #112
lisper wrote: post #12

Earlier quoted context omitted.

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

Re: Mathematicians Measure Infinities, Find They’re Equal

#118

Post by jkaoiyssrz »

gumby wrote: post #116

Photos of humans in an article about math are pretty useless but nevertheless I find it interesting that the article included a photo of the male collaborator, Saharon Shelah, and another male mathematician, but not one of the female collaborator, Maryanthe Malliaris.

There's no photo (of her) on her academic homepage or her own Web articles either. The obvious inference is that she doesn't supply photos to journalists.

Re: Mathematicians Measure Infinities, Find They’re Equal

#119

Post by zelah »

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.

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 give him the list and say that whatever he adds is precisely what I would have added had I continued. This is like an infinite lazy list in programming.

Re: Mathematicians Measure Infinities, Find They’re Equal

#120

Post by lisper »

zelah wrote: post #119
lisper wrote: post #117

Earlier quoted context omitted.

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

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 j'th digit of the i'th number in the list. Because you have to produce your digit in finite time you can only diagonalize a finite number of times, so Cantor can always do you one better and produce a number not on your list.

Post reply on HN