3 ms·

I think having a language that helps understand those limitations is a useful achievement. Much of mathematics does have that. A notable exception is the defin

I think having a language that helps understand those limitations is a useful achievement. Much of mathematics does have that. A notable exception is the definition of real numbers. They are usually presented as a string of infinite decimals, or a converging sequence, or a set of numbers less than something. All of those notions obscure the basic limitation of knowing the real number and give a veneer of similarity to rational number. Rational numbers are numbers that we can have in our hand while irrational numbers are ones which we can never have. It is important to have a setup that respects that difference. This is what motivated me to come up with a new definition of real numbers, namely, they are objects (I call them oracles) that answer Yes or No when asked if the number ought to be between two given rational numbers. Abstracting out what properties such an object should have, one can come up with a space of these oracles, define an arithmetic, and prove that they satisfy the axioms of real numbers. For details: https://github.com/jostylr/Reals-as-Oracles/ https://github.com/jostylr/Reals-as-Oracles/ In many ways, this is giving a definitional support to the use of interval analysis which is, of course, a very practical concern. It also brings our some cool stuff about mediants and continued fractions (nothing new about that, but nicely motivated). It also fits in with the adjacent post about busy beaver numbers and its conclusion about knowing a number is in an interval.

auggierose 3y ago
> It is important to have a setup that respects that difference. No, it is not. Or rather, which differences matter depends on your application. A circle of radius 1 is a very natural thing to me. I don't think 3/4 is more natural.
ginnungagap 3y ago
It's not clear to me what this approach offers over Dedekind cuts, you are specifying a real number by saying in which rational intervals it lies, a Dedekind cut specifies a real number by saying which rationals are below it and which are above, and translating back and forth between the two is immediate
- deleted 3y ago
  [deleted]
- jostylr 3y ago
  In part, it is about framing it. The oracle approach is not the set of all rational intervals containing a real number, but rather it a rule that acts on a given rational number. You cannot literally hand over a set of all rational intervals that contain the square root of 2. But you can specify the rule that tells you whether the rational interval contains it, namely, if a<b is the rational interval to test, then the rule sees if a^2<2<b^2. Dedekind cuts can similarly by recast as a function that gives -1,0, or 1 if a number is below, the same, or above the real number. This would be a great improvement over the usual presentation. But beyond that difference, consider the solution to f(x) = 0 in terms of the intermediate value theorem for an increasing function. The Dedekind cut solution is A = {x | f(x) < 0}. That is the answer. From the perspective of Dedekind cuts, there is nothing further to compute and it has provided nothing to compute with. The oracle answer would be the rule that says yes to a<b if f(a)*f(b) <=0. This gives a direct mechanism for testing intervals and the idea of narrowing intervals by picking a point inside a Yes interval is very natural from this perspective. I do not see that suggestion popping out of the Dedekind cut approach. The rational interval approach specifically is targeting narrowing solutions to the answer with error bounds built into it. If I tell you that 3 is in the set A, you have no intrinsic sense of how good of an approximation that is. But if I tell you that the target is in the interval 3 to 3.1, then you have a sense of the precision. Oracles promote having accuracy as foundational.
gunnihinn 3y ago
> they are objects (I call them oracles) that answer Yes or No when asked if the number ought to be between two given rational numbers. So a real number is a function from pairs of rationals to a two-element set (plus some sanity conditions)? Why is that better than the other constructions?
- jostylr 3y ago
  Yes. The basic reason is lazy evaluation and answering the primary question most people care about when using an actual real number in a computation. The lazy evaluation is that defining the real number is about having a way of answering the question when presented with the rational interval, but one does not actually need to have the answers until asked. From this perspective, a program that computes Yes or No when given a rational interval via the rule "a<b Yes iff a^2< 2 < b^2" can be said to be the square root of 2. For the usual presentations of the other definitions, they cannot be embodied in a computer. One cannot literally have all the infinite elements of a Cauchy sequence, or the infinite sequence of digits in a decimal representation, or the uncountably many elements of a Dedekind cut, represented in a computer memory. One can have a function in memory. The other definitions can also be presented, in various ways, as functions as well, but I think, fundamentally, what we want in practice from a real number is an interval of small enough size to be of use in whatever we are doing with the real number. That is what the oracles facilitate.
  - ginnungagap 3y ago
    One can have a function in memory when the real number is nice in some sense, your example is algebraic. But what if I want to represent an uncomputable number? Or regardless of that, under any reasonable encoding of programs that can be held in memory by a computer, there are only countably many programs.
    - jostylr 3y ago
      We also cannot represent all natural numbers or rational numbers in a computer. But the ones we care about, we generally can. I guess one question is whether there are uncomputable numbers that we need to compute for some purpose other than just computing it as a challenge? And if there are such things, how is it usually done? The theoretical definition of an oracle is not problematized by being uncomputable by Turing machines, but it is in uncomfortable tension with the driving purpose of the definition. I think that is a bonus. I think we should pause to consider the relevance of numbers that are uncomputable. There are a number of real numbers that one can define which can depend on whether we can prove something or not. It may turn out that we can never prove it and the number is never resolved. My attitude, which may not be satisfactory, is that we do what we can and we should have a language/framework for facilitating that. I think the oracle approach highlights what we know and marks what we can't compute clearly. I call it the resolution of the oracle. I don't want known precision to be lacking just because of a poor definition of what a real number is. As for the example being algebraic, it is a particularly nice example and it is the same example in every example of a Dedekind cut. Another example of such a rule, one which is not algebraic, would be whether pi is in an interval or not. Given a<b, one rule could be that it is No if b < 3 or a > 4 or sin(a)sin(b) > 0. Alternatively, it would say Yes if a >= 3 and b<= 4 and sin(a)sin(b) <= 0. To compute this, one needs to compute sine of a and b sufficiently precisely to determine their sign. The flavor I am trying to convey is having a definition convey a useful goal. The interval approach says that we are trying to generate precision about our inaccuracy. I think this is something which would greatly benefit those learning about real numbers. Most of the time, the error is presented as secondary and an annoyance, the concerns of the error propagation in further computations is pushed to the side, and it is all relegated to experts or computers. The expansionary nature of arithmetic in error propagation is pushed to a usually unsatisfactory discussion about significant digits. My goal here is to change the mental framework so that these concerns come to the forefront. Ideally, they also come with useful tools to handle the uncertainties such as ways to compute how narrow the input intervals need to be when doing a computation. And maybe, just maybe, students could become more comfortable with fractions.
monkeyjoe 3y ago
> Rational numbers are numbers that we can have in our hand while irrational numbers are ones which we can never have. It is important to have a setup that respects that difference. Do you mean physically? Basic shapes like circles, squares and triangles allow us to hold irrational numbers in our hands as distances. Children playing with blocks can sense that root 2 does not conform nicely with other (rational) distances.
- jostylr 3y ago
  I did not mean physically. I meant, having it explicitly written out in a way that rational numbers can be. If I write 3/4 + 1/2, I can compute out 5/4 and that is infinitely accurate. If I want to compute pi + e, an infinitely accurate version is pi + e. That's about it. So what we are actually looking for in this computation is an estimation algorithm, one which can be made as accurate as we wish, but finitely so. The natural way to express this is with rational intervals as rationals are precise and intervals give a containment of the numbers. For arithmetic, we can have a mechanism for figuring out how precise the input approximations need to be in order to get a given precision for the final computation. The perspective presented here naturally leads to that as a matter of defining and establishing the arithmetic of oracles. As for playing around with physical representations of irrational numbers, keep in mind that there is no way to prove that, say, something that looks like a unit square to us is really a perfect square down to infinite precision. And without that, we can easily have that the unit square is only very close to such a figure, but is actually a rational rectangle with a rational diagonal that very closely approximates the square root of 2.
  - ginnungagap 3y ago
    This is irrelevant to your point, just change the numbers used as example, but we do not know whether pi+e is irrational! (Even though nobody believes it to be rational)

auggierose 3y ago

> It is important to have a setup that respects that difference. No, it is not. Or rather, which differences matter depends on your application. A circle of radius 1 is a very natural thing to me. I don't think 3/4 is more natural.

ginnungagap 3y ago

It's not clear to me what this approach offers over Dedekind cuts, you are specifying a real number by saying in which rational intervals it lies, a Dedekind cut specifies a real number by saying which rationals are below it and which are above, and translating back and forth between the two is immediate

deleted 3y ago
[deleted]
jostylr 3y ago
In part, it is about framing it. The oracle approach is not the set of all rational intervals containing a real number, but rather it a rule that acts on a given rational number. You cannot literally hand over a set of all rational intervals that contain the square root of 2. But you can specify the rule that tells you whether the rational interval contains it, namely, if a<b is the rational interval to test, then the rule sees if a^2<2<b^2. Dedekind cuts can similarly by recast as a function that gives -1,0, or 1 if a number is below, the same, or above the real number. This would be a great improvement over the usual presentation. But beyond that difference, consider the solution to f(x) = 0 in terms of the intermediate value theorem for an increasing function. The Dedekind cut solution is A = {x | f(x) < 0}. That is the answer. From the perspective of Dedekind cuts, there is nothing further to compute and it has provided nothing to compute with. The oracle answer would be the rule that says yes to a<b if f(a)*f(b) <=0. This gives a direct mechanism for testing intervals and the idea of narrowing intervals by picking a point inside a Yes interval is very natural from this perspective. I do not see that suggestion popping out of the Dedekind cut approach. The rational interval approach specifically is targeting narrowing solutions to the answer with error bounds built into it. If I tell you that 3 is in the set A, you have no intrinsic sense of how good of an approximation that is. But if I tell you that the target is in the interval 3 to 3.1, then you have a sense of the precision. Oracles promote having accuracy as foundational.

gunnihinn 3y ago

> they are objects (I call them oracles) that answer Yes or No when asked if the number ought to be between two given rational numbers. So a real number is a function from pairs of rationals to a two-element set (plus some sanity conditions)? Why is that better than the other constructions?

jostylr 3y ago
Yes. The basic reason is lazy evaluation and answering the primary question most people care about when using an actual real number in a computation. The lazy evaluation is that defining the real number is about having a way of answering the question when presented with the rational interval, but one does not actually need to have the answers until asked. From this perspective, a program that computes Yes or No when given a rational interval via the rule "a<b Yes iff a^2< 2 < b^2" can be said to be the square root of 2. For the usual presentations of the other definitions, they cannot be embodied in a computer. One cannot literally have all the infinite elements of a Cauchy sequence, or the infinite sequence of digits in a decimal representation, or the uncountably many elements of a Dedekind cut, represented in a computer memory. One can have a function in memory. The other definitions can also be presented, in various ways, as functions as well, but I think, fundamentally, what we want in practice from a real number is an interval of small enough size to be of use in whatever we are doing with the real number. That is what the oracles facilitate.
- ginnungagap 3y ago
  One can have a function in memory when the real number is nice in some sense, your example is algebraic. But what if I want to represent an uncomputable number? Or regardless of that, under any reasonable encoding of programs that can be held in memory by a computer, there are only countably many programs.
  - jostylr 3y ago
    We also cannot represent all natural numbers or rational numbers in a computer. But the ones we care about, we generally can. I guess one question is whether there are uncomputable numbers that we need to compute for some purpose other than just computing it as a challenge? And if there are such things, how is it usually done? The theoretical definition of an oracle is not problematized by being uncomputable by Turing machines, but it is in uncomfortable tension with the driving purpose of the definition. I think that is a bonus. I think we should pause to consider the relevance of numbers that are uncomputable. There are a number of real numbers that one can define which can depend on whether we can prove something or not. It may turn out that we can never prove it and the number is never resolved. My attitude, which may not be satisfactory, is that we do what we can and we should have a language/framework for facilitating that. I think the oracle approach highlights what we know and marks what we can't compute clearly. I call it the resolution of the oracle. I don't want known precision to be lacking just because of a poor definition of what a real number is. As for the example being algebraic, it is a particularly nice example and it is the same example in every example of a Dedekind cut. Another example of such a rule, one which is not algebraic, would be whether pi is in an interval or not. Given a<b, one rule could be that it is No if b < 3 or a > 4 or sin(a)sin(b) > 0. Alternatively, it would say Yes if a >= 3 and b<= 4 and sin(a)sin(b) <= 0. To compute this, one needs to compute sine of a and b sufficiently precisely to determine their sign. The flavor I am trying to convey is having a definition convey a useful goal. The interval approach says that we are trying to generate precision about our inaccuracy. I think this is something which would greatly benefit those learning about real numbers. Most of the time, the error is presented as secondary and an annoyance, the concerns of the error propagation in further computations is pushed to the side, and it is all relegated to experts or computers. The expansionary nature of arithmetic in error propagation is pushed to a usually unsatisfactory discussion about significant digits. My goal here is to change the mental framework so that these concerns come to the forefront. Ideally, they also come with useful tools to handle the uncertainties such as ways to compute how narrow the input intervals need to be when doing a computation. And maybe, just maybe, students could become more comfortable with fractions.

monkeyjoe 3y ago

> Rational numbers are numbers that we can have in our hand while irrational numbers are ones which we can never have. It is important to have a setup that respects that difference. Do you mean physically? Basic shapes like circles, squares and triangles allow us to hold irrational numbers in our hands as distances. Children playing with blocks can sense that root 2 does not conform nicely with other (rational) distances.

jostylr 3y ago
I did not mean physically. I meant, having it explicitly written out in a way that rational numbers can be. If I write 3/4 + 1/2, I can compute out 5/4 and that is infinitely accurate. If I want to compute pi + e, an infinitely accurate version is pi + e. That's about it. So what we are actually looking for in this computation is an estimation algorithm, one which can be made as accurate as we wish, but finitely so. The natural way to express this is with rational intervals as rationals are precise and intervals give a containment of the numbers. For arithmetic, we can have a mechanism for figuring out how precise the input approximations need to be in order to get a given precision for the final computation. The perspective presented here naturally leads to that as a matter of defining and establishing the arithmetic of oracles. As for playing around with physical representations of irrational numbers, keep in mind that there is no way to prove that, say, something that looks like a unit square to us is really a perfect square down to infinite precision. And without that, we can easily have that the unit square is only very close to such a figure, but is actually a rational rectangle with a rational diagonal that very closely approximates the square root of 2.
- ginnungagap 3y ago
  This is irrelevant to your point, just change the numbers used as example, but we do not know whether pi+e is irrational! (Even though nobody believes it to be rational)