How many real numbers exist? New proof moves closer to an answer • Hacker News Board

Re: How many real numbers exist? New proof moves closer to an answer

#181

Post by gowld » Thu, Jul 15, 2021, 9:13 PM UTC

IncRnd wrote: post #137

dexwiz wrote: post #136

I'm no mathematician, but I have always found it strange infinities are talked about as physical states (towers of tall towers, etc), and not functions. Integer number counting is essentially a successor function; take N, add 1, output N+1. One input, one output. Real number counting is a bit more loose. To find the numbers between .1 and .2, you find all fractionals of a given size, normally 1/10. So we get .10, .11…

I'm not a mathematician, either, but I believe your comment shows why not all infinities are equal. When you attempt to enumerate .1, .2, .3, .4, etc. you get an infinite count of numbers. However, when you perform that same operation on .05, .15, .2, .25, and so on, you will get "twice as many numbers" as the first time around. In this way, the second infinite sequence has "twice as many numbers" as the first infini…

No, it doesn't. Then have the same number, as can be plainly seen by lining them up and counting the elements in order.

Re: How many real numbers exist? New proof moves closer to an answer

#182

Post by Rinum » Thu, Jul 15, 2021, 9:16 PM UTC

daxfohl wrote: post #174

A related thing that occurred to me the other day: there's some number in [0, 1] that encodes every state of every possible Turing machine (the number of Turing machines is countable, the duration of its run is countable, and the states at each step are countable, so you can diagonalize that and make a real number out of it). I'm pretty sure you can take that further and show that all possible mathematical proofs, in…

I think you'll like this - https://youtu.be/HeQX2HjkcNo

Re: How many real numbers exist? New proof moves closer to an answer

#183

Post by bonzini » Thu, Jul 15, 2021, 9:17 PM UTC

victorbojica wrote: post #166

phkahler wrote: post #163

You can map all the real numbers to the interval 0 0.0 => 0 0.1 => 1 0.2 => 2 ... 0.14159 => 95141 The argument against this is that there are real numbers with an infinite number of digits, which will not have a specific integer associated with them. Or do they? Can there be an "infinitely large integer?" or are there just infinitely many of them? I think this question gets to the core of the problem.

But if you assign them randomly, then it should work 1->5.85916 2->8.7599 ... Or even randomize the order for the integers 5->7.52256951 77->848.455 ...

You can't, this is Cantor's diagonal counterexample.

Re: How many real numbers exist? New proof moves closer to an answer

#184

Post by sharpener » Thu, Jul 15, 2021, 9:25 PM UTC

The mileage of others may vary, but it has been my experience that there is no cogent solid proof of uncountability that can withstand concerted critique.[0]

Being charitable one might argue that the meanings of terminology had been lost in translation over time and that perhaps Cantor was trying to create non-standard analysis, but then the diagonal argument seems to represent nothing more than the truism that finite numbers are smaller than transfinite ones.

Hence I worry about people who are still worrying about this issue, and I worry for the future of science and AI in particular if folks can't get clear of it.

[0] https://www.researchgate.net/publication/328568169_The_Case_...

Yes, I'm that guy who wrote that.

Re: How many real numbers exist? New proof moves closer to an answer

#185

Post by rssoconnor » Thu, Jul 15, 2021, 9:26 PM UTC

bryan0 wrote: post #171

rssoconnor wrote: post #102

Earlier quoted context omitted.

Mostly because it implies that some Turing machines halt that actually do not halt. That is unless you are willing to accept that a Turing machine can halt in some number of steps that is beyond any number that can be written. And I don't mean can't be written in the sense that we don't have enough paper. Just cannot be written in principle at all by our notation for numbers.

But isn’t this what the busy beaver numbers are? Numbers that we cannot write for arbitrary n but they do exist?

I think this is a great question.

The difference here is that with busy beaver numbers, e.g. BB(101) we can, presumably, write their values with our notation; it's just that we often cannot prove that any particular value written in our notation does indeed denote the value for that function. So if we write 100000...0000 with an unholy number of 0s there, it might be the value of BB(101), in particular we might not be able to prove that it isn't.

On the other hand, for a non-standard number, c, it is definitely the case that 100000...0000 is not c, because, whatever c is, it is strictly greater than 100000...0000, or any other number we can write down.

And thus when it comes to proofs about the termination of Turing machines that do not actually terminate, the unsound system is claiming that some machine terminates, but it doesn't terminate in 1 step, nor 2 steps, nor 3 steps, nor ... nor 100000...0000 steps, nor 100000...0001 steps, nor 100000...0002 steps, nor .... However, regarding the BB(101), the (presumably) sound systems we use such as PA, or ZFC, do not claim that BB(101) isn't 100000...0000. They just may not be able to prove anything one way or the other.

Re: How many real numbers exist? New proof moves closer to an answer

#186

Post by svachalek » Thu, Jul 15, 2021, 9:34 PM UTC

123pie123 wrote: post #138

I've always been brought up to realise that math(s) is not real. It's more of a (extremely) good system to model stuff, say like a map isn't real, but just a representation so this proof is pushing the system of this math(s) system

The deeper physics goes, the more apparent it is that our perception of reality is a good model for what is happening at our scale in the universe and the forces that are dominant at that scale. Our intuition breaks down at larger and smaller scales, but the math still works. So in some sense, math is the truest access we have to reality.

Re: How many real numbers exist? New proof moves closer to an answer

#187

Post by Decker87 » Thu, Jul 15, 2021, 9:47 PM UTC

Honest question, what is the usefulness of proving such an obvious thing?

Re: How many real numbers exist? New proof moves closer to an answer

#188

Post by plus » Thu, Jul 15, 2021, 9:48 PM UTC

phkahler wrote: post #163

You can map all the real numbers to the interval 0 0.0 => 0 0.1 => 1 0.2 => 2 ... 0.14159 => 95141 The argument against this is that there are real numbers with an infinite number of digits, which will not have a specific integer associated with them. Or do they? Can there be an "infinitely large integer?" or are there just infinitely many of them? I think this question gets to the core of the problem.

> The argument against this is that there are real numbers with an infinite number of digits, which will not have a specific integer associated with them. Or do they?

If it was possible to construct your mapping, then there would be a well-defined sorting of the reals between 0 and 1 based on their integer representation (e.g. we could sort the set {0.05, 0.1, 0.2} => {50, 1, 2} to [0.1, 0.2, 0.05] => [1, 2, 50]).

How would you sort the list {0.5, 1 / sqrt(2), pi - 3}?

Re: How many real numbers exist? New proof moves closer to an answer

#189

Post by plus » Thu, Jul 15, 2021, 9:51 PM UTC

red_trumpet wrote: post #175

phkahler wrote: post #163

You can map all the real numbers to the interval 0 0.0 => 0 0.1 => 1 0.2 => 2 ... 0.14159 => 95141 The argument against this is that there are real numbers with an infinite number of digits, which will not have a specific integer associated with them. Or do they? Can there be an "infinitely large integer?" or are there just infinitely many of them? I think this question gets to the core of the problem.

> You can map all the real numbers to the interval 0 Even easier use a well-established function such as arctan to map the reals bijectively to the interval -π/2 < x < π/2, and then scale and shift the interval to 0 < x < 1.

This allows you to map the real range (0, 1) to (-infinity, infinity). It does not allow you to map the integers to the reals.

Re: How many real numbers exist? New proof moves closer to an answer

#190

Post by quickthrower2 » Thu, Jul 15, 2021, 9:56 PM UTC

thehappypm wrote: post #124

helen___keller wrote: post #30

Earlier quoted context omitted.

Others have addressed why it matters (or doesn't matter) when viewed from outside mathematics. But within mathematics, unsolved problems usually matter for two reasons: (1) When lots of really smart people spend lots of time trying to solve something, and fail to do so, it becomes even more interesting for other smart people. A well-known example is the Collatz Conjecture[0] which, by most accounts is a meaningless p…

I mean, at its simplest, the Collatz conjecture is a type of random walk, with the sequence either exponentially growing or exponentially shrinking, basically at random. It's statistically impossible that that any random walk will continue one direction forever, and once it randomly decays to 1 you're done.

Loops are the other option you’d need to prove don’t exist.

I think I can see why trying to solve this problem is popular. It almost feels like it should be easy to solve but it just quite isn’t!