I'm not sure about this. We often make calculations with computer representations of real numbers. We can calculate quantities based on algebraic or transcendental numbers with arbitrary precision (optimizations, navigation), or we can use them as a basis (image processing) and represent rational numbers in their terms. Real numbers are all over computer applications.
Suppose we are only working with rational multiples of Pi. Then we can ONLY have finite calculations of irrational numbers and it's impossible to have a finite calculation of a rational number (except for multiplication by 0).
>Representing rationals isn't affected by the paper's findings, because they have the same cardinality as the naturals.
The Natural numbers are still infinite which presents its own inherent difficulty. It's not as though countability lends itself better to programming.
> The Natural numbers are still infinite which presents its own inherent difficulty. It's not as though countability lends itself better to programming
Actually countability does lend itself to programming, essentially by definition. You cannot write a function to enumerate all the real numbers precisely because they're uncountable, even if you had an infinite amount of time. You can trivially do this with a "merely" countably infinite set, like the naturals or rationals.
> Suppose we are only working with rational multiples of Pi. Then we can ONLY have finite calculations of irrational numbers and it's impossible to have a finite calculation of a rational number (except for multiplication by 0).
It sounds like you're suggesting we can store an irrational number in a finite representation by generating it with a finite function (e.g. multiply a rational number of times). But that doesn't work. You can't represent a number N in a finite number of steps if you can't represent all factors of N in a finite number of steps.
This fact follows from the field axioms for the same reason that all products of irrationals and rationals are themselves irrational. Simply put, if you can't do it for Pi, you can't do it for a rational multiple of Pi.
Even with infinite amount of time your enumeration function will not generate all of the natural numbers even though the natural number are countable.
You're right that we can't write a function to determine an immediate successor but we can write successor functions.
>It sounds like you're suggesting we can store an irrational number in a finite representation by generating it with a finite function (e.g. multiply a rational number of times). But that doesn't work. You can't represent a number N in a finite number of steps if you can't represent all factors of N in a finite number of steps.
We are getting a few concepts muddled. Storing an irrational number as a finite representation is trivially easy. For example: "pi". Alternatively I could write an algorithm to generate the decimal expansion of the square root of 2. Where it's difficult is when we talk about numbers that aren't describable in a finite number of terms, i.e. Uncomputable. There is a certain unknowable quality to these numbers and I would suggest that this isn't inherent from the cardinality of the real numbers and that we run into similar problems when trying to compute some natural numbers, like random numbers.
Huh? You can trivially write a function to generate all natural numbers:
def increment(x):
return increment(x + 1)
increment(1)
> Where it's difficult is when we talk about numbers that aren't describable in a finite number of terms, i.e. Uncomputable.
This is not what uncomputable means. Uncomputable means we cannot calculate a number to any precision, not that the number has an infinite decimal expansion.
Pi is not uncomputable. You can’t store its entire decimal expansion in finite space but it is certainly computable - we compute it all the time. However, almost all real numbers are strictly uncomputable. Among many other proofs, this is evident from the simple fact that the set of all possible Turing machines is countable. Since the reals are uncountable, it follows that almost all reals must not be computable by any Turing machine.
Likewise, there are many potential calculations involving real numbers for which a computer will output a strictly incorrect - not just imprecise - result because its real solution is uncomputable. This does not happen in the naturals or rationals.
Did you mean “for any precision, we cannot compute to that precision” or “we cannot compute to every precision”?
I might be nitpicking here, but uncomputable != indescribable. For example, Chaitin’s constant [1] is uncomputable but perfectly describable (and in fact limit-computable [2]). The set of arithmetically-definable [3] numbers is even larger than that of limit-computable numbers. Computable and limit-computable numbers lie at levels Δ^0_1 and Δ^0_2 of this hierarchy, respectively.
[1] https://en.wikipedia.org/wiki/Chaitin%27s_constant
How would you start? You can't put a rational multiple of pi exactly into a computer. You can't get a rational multiple of pi exactly out of a computer. You can calculate rational numbers on the computer and scale them by a factor of pi outside the computer, if you really want, but that doesn't mean the computer is working with irrationals.
> It's not as though countability lends itself better to programming.
Huh? Yes it does; countable sets are still infinite but they're better-behaved than bigger sets.
Of course we can: "1/2*pi"
>You can't get a rational multiple of pi exactly out of a computer.
Using the same limitations you seem to have in mind, we can't get one third exactly either.
>...countable sets are still infinite but they're better-behaved than bigger sets.
Yes, and that is surprising because we do have numerous clever applications that skirt around most of the intractability of exotic real numbers. That is why I think this paper is a bid deal, especially because it points to the cardinality of the real numbers instead of, say, their inclusion of the uncomputable numbers.
We can work with exact rationals; we can do arithmetic on them and normalize them. In particular, we can compute whether two rationals are equal (in finite time), which we can't do with reals.
We also often make calculations with finite subsets of rational numbers. We don't work with all of the rational numbers.
> We can only approximate the real numbers with finite precision.
The same can be said for rational numbers. It really matters that we can be arbitrarily precise when we talk about .333333... (one third), 1.41421... (square root of 2) or 3.14159... (pi) because we can be as exact as our calculations demand.
First, yes the rationals are already countable. But the reals are uncountable. You cannot write a function to generate all real numbers - not even if you allowed the function to run for an infinite amount of time.
Second, most of the reals are individually uncomputable, which literally means no, we cannot calculate them to arbitrary precision (or any exact precision).
Likewise we cannot just redefine the set of real numbers to be restricted to the set of computable reals. Analysis rapidly breaks down when you do so and it follows that the real field is no longer closed (by definition, and therefore no longer subject to the field axioms).
Whilst this is true, I feel it should be noted that there exist constructive and computable versions of analysis which exist to work under under assumptions like "all the reals are computable".
Of course, the big difference is that we've mostly agreed on a single canonical version of the classical reals and of classical analysis, whilst there are numerous versions of different constructive analyses depending on what exactly you mean by "constructive".
Additionally many theorems of classical analysis "split up" into multiple independent versions which would be equivalent classically, but only some of which are true constructively.
Worse than that, often there is not a single definition of the "reals" any more. For example, two definitions of the reals (Dedekind Cuts and Cauchy Sequences) may result in entirely different objects constructively speaking. And, in fact, it may be that neither one is actually a good way of capturing the concept of a "real" "number" in that particular universe, so you need yet another definition.
As terrible as this might make it sound, it is worth the effort, in my opinion. In trying model the real world, classical mathematics throws away just a little bit too much information, in my opinion. This messiness is not just the result of wanting to work under some weird axioms, but an actual statement about the messiness of reality. Trying to sweep these issues under the rug is not a sustainable strategy if you eventually want to solve real-world problems.
Using classical mathematics is fine as a first-pass. It's a good way of investigating the problem under some simplifying assumptions and getting some good and useful results. But after that is done, it's not always enough to just declare the problem "solved" (or "unsolvable"). You need to consider what the practical version of the results will be, especially if you want to write a program to use them.
I am glad that the world is moving towards more computable and constructive versions of mathematics. It is still early days, and there are still way too many different takes on trying to solve the same mathematical issues, but soon enough we'll converge on a select few "generally acceptable" versions of constructive mathematics (in particular, something based on some form of constructive Type Theory) and we'll be able to reform our mathematical and scientific knowledge on a more stable base.
All the Dedekind cuts and Cauchy sequences do is tell us, in essence: "yes, the axiomatized reals you're using are correct and fine because there are constructive proofs of their existence." Moreover, the point of those proofs (and analysis more generally) is to demonstrate mathematical continuity and uncountability. No matter how you slice this problem, if you construct analysis you will lose computability along the way.
You are correct that under classical assumptions of logic ("normal" mathematics), the Dedekind Cuts and Cauchy Sequences indeed result in the construction of isomorphic objects.
However, under constructive assumptions of the logical axioms of mathematics, such as intuitionism (not accepting the law of excluded middle, i.e., assuming that the statement "P and NOT P" is not necessarily true for all P), the construction of the Dedekind Cuts and the Cauchy Sequences may result in different objects, i.e., it may no longer provable that they are equivalent.
I was with you until you wrote that Analysis would break down. We can easily do analysis with dense subsets of the reals and also extensions of the reals, like in Non-Standard Analysis.
1. For x and y you cannot prove that x<=y or x=>y
2. Every function is continuous
See this submission from two months ago: https://news.ycombinator.com/item?id=18411935
Edit: for instance, you could imagine a representation (think object of a virtual class in c++) that gives you a fraction and a 1/2^n bound for error, where you can query the number for whatever n you see fit. Still, in some cases it's undecidable to determine which number is greater.
And floats are really a whole other beast than fractions or naturals or real numbers. As I wrote earlier - the "+" operator isn't associative. Python snippet:
def before():
x = 0.0
x += 1.0
for i in xrange(1000):
x += 1e-17
return x
def after():
x = 0.0
for i in xrange(1000):
x += 1e-17
x += 1.0
return x
print before() == 1.0
print after() == 1.0
True
False