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

How real are real numbers? (2004)

arxiv.org

Post reply on HN
Print view View original

251–260 of 275 posts

Re: How real are real numbers? (2004)

#251

Post by zamalek »

CogitoCogito wrote: post #40

The continuity of real numbers provides a clean theoretical basis for continuity of functions. I personally view it as more of a theoretical tool that seems to do pretty well and instead steer clear of the philosophical questions. One thing that I think is important to note though is that the jump from real numbers to complex numbers is nothing compared to the jump from integers/rational numbers/etc. to real numbers.…

Given my experience when learning about complex numbers, I would rather say:

> The complex numbers come about by simply adding back the missing dimension

Mathematics makes so much more sense with complex numbers. Trigonometry a great example of this.

Re: How real are real numbers? (2004)

#252

Post by stymaar »

moefh wrote: post #87
stymaar wrote: post #62

Earlier quoted context omitted.

> Consider that great big set. It's still countable. You didn't prove that statement, and actually Cantor's diagonal arguments [1] proves you wrong: Consider the set of «all real numbers which you can actually specify IN ANY FASHION AT ALL». If you can count it, you can order them in a certain fashion: n0, n1, n2, n3 … It's easy to specify a number X which is not part of this set (which is in contradiction with the d…

I don't think that argument works. How do you guarantee that you can compute the n-th decimal of the n-th number in the list? In fact, from what I understand, this paper[1] shows how to specify exactly a number can't be computed like that. [1] https://arxiv.org/pdf/1003.0480.pdf

Why do you need to compute the n-th decimal of a number for this proof to work ? let Ω be a Chaitin Omega number it's decimal are non-computable, yet for every x, Ω + x is a perfectly valid number.

Then `floor(Ω.10^(n))-10.floor(Ω.10^n-1)` is also a number (a natural one) and actually it's the n-th decimal of Ω. It cannot be computed, but it still exist no matter what.

Re: How real are real numbers? (2004)

#253

Post by stymaar »

gertef wrote: post #76
stymaar wrote: post #62

Earlier quoted context omitted.

> Consider that great big set. It's still countable. You didn't prove that statement, and actually Cantor's diagonal arguments [1] proves you wrong: Consider the set of «all real numbers which you can actually specify IN ANY FASHION AT ALL». If you can count it, you can order them in a certain fashion: n0, n1, n2, n3 … It's easy to specify a number X which is not part of this set (which is in contradiction with the d…

The number you are paraphrasing cannot be precisely identified in finite time.

Oh, you're right. For that I would need to explicit the construction of the sequence n0, n1, … but that's impossible : if I can find such sequence, my proof holds but at the same time such sequence shows that the set is countable => contradiction, hence there is no such sequence.

But well, now that we've proven that such sequence doesn't exist, we've proven that the given set is not countable !

Not the most elegant proof ever, but I think it works.

Re: How real are real numbers? (2004)

#254

Post by btilly »

mbid wrote: post #215
Confusion wrote: post #213

Earlier quoted context omitted.

A surjection seems silly: doesn't that imply that some reals would be indistinguishable? Or can you indeed not prove that more than the natural number of reals are distinguishable in constructive mathematics?

Honestly, the result hinted at in the wikipedia article caught me by surprise as well: There are some flavors of constructive mathematics (notably CZF), that are still consistent if you also add the statement "There is a subset A of the natural numbers such that there is a surjection from A onto the real numbers". Note that this does not imply that you can prove this in CZF, it only means that you cannot disprove it.…

And this is the key result that I am thinking of.

Furthermore if we limit all mathematics to things that can in principle be done on a Turing machine, then this statement is trivially true because all possible Turing machines is a countable set.

Moving from Turing machines to a Turing-complete programming language, we could define a real number as an equivalence class of functions from positive integers to fractions such that for each function |f(n) - f(m)| The question of whether a given function is actually a real number is in general undecidable. The question of whether two functions represent the same real number is also undecidable. However it is easy to create a set of functions that will definitely include all real numbers under this definition (and a few things that are not), but some of those real numbers will be included multiple times.

And the really important point about this is that suddenly "uncountable" doesn't mean "more". It just means that there is an undecidable question or three creating complexity in the way of generating the mapping.

Re: How real are real numbers? (2004)

#255

Post by bjourne »

jamelk wrote: post #248
bjourne wrote: post #223

Earlier quoted context omitted.

Here is how you do it. Have a function p(r) which evaluates to the previous real number. Then your mapping function is: f(r) = if (r == 0) { 0 } { else f(p(r)) + 1 } If your objection is "You can't determine what the previous real number is." Then my counter-objection is "Please prove that you can't." Which I don't think is possible without first assuming reals are uncountable.

Your definition of f is circular: to calculate f(r) we need to know p(r), which in turn depends on f(r). Cantor's diagonal argument shows that any mapping from the natural numbers to the real numbers must necessarily miss some real numbers out. It takes some time to get your head around if you aren't used to mathematical proofs, but it's definitely worth looking it up and trying to work through it if you're intereste…

p(r) is given a real number and retrieves its predecessor. Why is it circular?

Re: How real are real numbers? (2004)

#256

Post by tel »

pron wrote: post #242
tel wrote: post #239

Earlier quoted context omitted.

I think you're right on the money bringing Turing into this. I don't have a real, formal horse in this race, but the way that I have things arranged in my mind is that these are all disagreements on the notion two things in logical foundations: the need to consider time/resources and the conception of logical systems as closed or open. Brouwer and Hilbert accept that time is a factor, but handle it in different impli…

> I think you're right on the money bringing Turing into this. Well, his most famous paper, the one in he was first discovered the essence of what computation is (rather than merely asking what functions can be computed by a "definite procedure"), was named On Computable Numbers , and he uses the very problem of the real numbers as a segue into the more general topic of computation. > Free choice can't be modeled for…

> it is as impossible to determine whether two lawful sequences are equal as it is to determine whether two lawless sequences are

I also think that's enough.

I think when you mention that it's easier to build a mechanistic theorem prover on an intuitionistic foundation that it's a bit more "foundational" a problem than it seems. Theorem provers need (some kind of partial) equality on propositions and on proofs in order to function, but propositions are too rich to support finite equality. This backs you into a more intuitionistic approach.

Re: How real are real numbers? (2004)

#257

Post by abcdefgxdf »

bjourne wrote: post #255
jamelk wrote: post #248

Earlier quoted context omitted.

Your definition of f is circular: to calculate f(r) we need to know p(r), which in turn depends on f(r). Cantor's diagonal argument shows that any mapping from the natural numbers to the real numbers must necessarily miss some real numbers out. It takes some time to get your head around if you aren't used to mathematical proofs, but it's definitely worth looking it up and trying to work through it if you're intereste…

p(r) is given a real number and retrieves its predecessor. Why is it circular?

Suppose there exists an r' such that for some real number r, p(r)=r', where p(r) gives the real number that precedes r. What does that mean? Does it mean there are no numbers between r and r'? Because that's what I think predecessor means, even though it's trivial to prove that there are numbers between r' and r. For example, (r'+r)/2, the average of r and r', is between the two numbers. And there are also numbers between r and (r'+r)/2, and between r' and (r'+r)/2. So there can't possibly be a real that is the predecessor to another real, because there are always more real numbers between any two reals.

Re: How real are real numbers? (2004)

#258

Post by petercerno »

upquark wrote: post #66
eatitraw wrote: post #47

Earlier quoted context omitted.

Even though you defined the number, you can't really do usual stuff with it: e.g. you can't compare it to other numbers. IMO, these kind of numbers are no more "real" than infinitesimals: https://en.wikipedia.org/wiki/Hyperreal_number

Oh it's definitely more real, as in it belongs to R and not to any of its extensions. You guys realize that the definition of R is non-controversial in modern math, right? There are fringe theories like constructivist logic and other groups that reject all infinite constructions, but this is not the consensus view among practicing mathematicians... The way you defined that number makes it a perfectly valid element of…

> Plus, you can actually empirically compute a finite set of initial digits (a specific Turing machine can be analyzed to see if it terminates or not).

Well, the fact that the number is not computable means that there will exist an index i, for which you will not be able to compute a_i (no matter how hard you try). In other words, you will not be able to analyze the Turing Machine i, i.e. it will not be possible to prove the termination or non-termination of the Turing Machine i.

So this specific digit will be a mystery forever, and you would not be able to compare it to anything.

Re: How real are real numbers? (2004)

#259

Post by pron »

tel wrote: post #256
pron wrote: post #242

Earlier quoted context omitted.

> I think you're right on the money bringing Turing into this. Well, his most famous paper, the one in he was first discovered the essence of what computation is (rather than merely asking what functions can be computed by a "definite procedure"), was named On Computable Numbers , and he uses the very problem of the real numbers as a segue into the more general topic of computation. > Free choice can't be modeled for…

> it is as impossible to determine whether two lawful sequences are equal as it is to determine whether two lawless sequences are I also think that's enough. I think when you mention that it's easier to build a mechanistic theorem prover on an intuitionistic foundation that it's a bit more "foundational" a problem than it seems. Theorem provers need (some kind of partial) equality on propositions and on proofs in ord…

> but propositions are too rich to support finite equality

Why do you say that? The finitary deduction rules of all logic systems provide both equivalence () and partial order (=> or |-) relations. Classical logic gives rise to a boolean algebra, while intuirionistic logic forms a Heyting algebra, of which boolean algebra is a special case. The latter is more general, but both are bounded lattices, and both are perfectly fine.

Re: How real are real numbers? (2004)

#260

Post by Dr_Segfault »

bjourne wrote: post #223
jonreem wrote: post #187

Earlier quoted context omitted.

A set being "countably infinite" only means that you can write a function that maps each distinct entry in the set to exactly one natural number (0, 1, 2, etc.) without duplicates. That's it. So for example, the set of natural numbers is countably infinite and we know this because we can write a function that maps each natural number to exactly one natural number: the id function. We can extend this and say that the…

Here is how you do it. Have a function p(r) which evaluates to the previous real number. Then your mapping function is: f(r) = if (r == 0) { 0 } { else f(p(r)) + 1 } If your objection is "You can't determine what the previous real number is." Then my counter-objection is "Please prove that you can't." Which I don't think is possible without first assuming reals are uncountable.

What is your definition of "previous real number"? If you define p(r) such that p(r) Given real number r, assume there exists a real number q such that q If you take issue with this, then I suggest you read up on the standard construction of the number systems from the naturals up to the reals. This is all very rigorously defined in terms of ZFC set theory.
Post reply on HN