4 ms·

No, to "do mathematics", e.g., show that the Riemann integral exists, that e and pi exist, etc., we want completeness. Then we are done: The reals are the only

by graycat 13y ago

No, to "do mathematics", e.g., show that the Riemann integral exists, that e and pi exist, etc., we want completeness. Then we are done: The reals are the only complete Archemedean ordered field! So, we have no choice!

justinpombrio 13y ago
On the contrary, we do have a choice! We could use computable numbers instead of reals. A computable number is any number which is output by some Turing machine, or, equivalently, any number which can be found by some algorithm. e and pi are computable. You are right that Riemann integrals won't exist, but if you modify definitions somewhat, derivatives and integrals can be defined just as easily for computable numbers as for reals and you can do calculus with them (see second link). Unlike reals, computable numbers are countable, and are all describable. (That is, there are aleph-null of them, so there are exactly as many computable numbers as natural numbers, and fewer than real numbers). And while almost all real numbers aren't computable (by the argument in the article), essentially every number you'd ever stumble upon in a math class is. I prefer computable numbers to reals because I have trouble accepting that a thing exists when it by principal cannot be defined. https://en.wikipedia.org/wiki/Computable_number https://en.wikipedia.org/wiki/Computable_number http://www.amazon.com/Computable-Calculus-Oliver-Aberth/dp/0120417529 http://www.amazon.com/Computable-Calculus-Oliver-Aberth/dp/0...
- ColinWright 13y ago
  Numbers that can be computed by Turing Machines are countable, so list them: c_0, c_1, c_2, etc. Take any interval [a0,b0] (with a0 and b0 computable), and cross out your computable numbers until you find one, say, c_i, in the interval (including an endpoint). Take some strict sub-interval [a1,b1] (again with computable endpoints) within [a0,b0] such that a0<a1, b1<b0, and c_i is not in [a1,b1]. Now continue crossing off computable numbers, each time taking a sub-interval with computable endpoints to exclude any that happen to be in the interval currently under consideration. The left hand end-points, a0, a1, a2, etc, form a strictly increasing sequence of computable points. This sequence is bounded above, and so we would like there to be a least upper bound. And yet it cannot be one of the numbers you first chose, because each has been excluded at some stage. So here we have a strictly increasing, bounded above sequence of computable numbers such that there is no limit in the computable numbers. This proves the computable numbers are not complete, and that makes analysis really messy.
  - justinpombrio 13y ago
    There's two related arguments you (may) be making. One is philosophical, and to that I say: can you give an algorithm to compute a0, a1, ...? If you can't (and I suspect you can't), I'd be hesitant to say that such a sequence exists. But I don't think there's a useful argument to have here ;-). But more concretely: no, the computable numbers aren't complete. Why would this make analysis messy? I didn't find the presentation and results in Computable Analysis (the book) all that different from what you find in an ordinary analysis course. Is there something it makes hard which I'm missing? (This might be impossible to answer without specific knowledge of Computable Analysis; remember that the definitions of, e.g. limits, are different.)
- btilly 13y ago
  And while almost all real numbers aren't computable (by the argument in the article), essentially every number you'd ever stumble upon in a math class is. Not every number though. It turns out that there are numbers that are describable but not computable. What is the difference? Well here's an example. A Chaitin omega number is the probability that a valid program randomly constructed according to a specific set of rules will eventually halt. It is describable - indeed I just described it. Yet Chaitin has proven that an algorithm to compute it will lead to an algorithm that solves the halting problem, so it cannot be computable. So there you have it. A class of perfectly describable numbers that are not computable. Indeed it can be proven that we cannot know more than a fixed number of digits for any particular one without increasing the size of our axiom system.
tome 13y ago
I'm afraid I'm not a good enough logician to answer your objection properly, but there are, I believe, credible approaches to doing mathematics on a countable carrier set, for example: http://arxiv.org/pdf/math/0509245 http://arxiv.org/pdf/math/0509245
- graycat 13y ago
  "Credible", likely yes. Likely also awkward. To weasel out, I just said we "want completeness". When you look at the alternatives, you may conclude that you still want completeness and, thus, are stuck with the reals with no alternative you "want"!
  - tome 13y ago
    Awkward I would agree with, but probably only because we're much more used to the usual approach (cf the "awkwardness" of Haskell). Still, you'll see in that paper that the reals he constructs are complete. The get out clause is that they are not a set, but a class.
    - graycat 13y ago
      > The get out clause is that they are not a set, but a class. Good grief! In axiomatic set theory, introducing 'classes' was the "get out clause" from the Russell paradox of the the set of all sets that are not members of themselves. So, the patch, the time I studied one version of axiomatic set theory, was to say that there are some sets and we know what they are and we know that the Russell paradox can't happen now, so let's go on. It appears that the OP and alternatives to the usual treatment of the real numbers are based on what can be described. This issue doesn't impress, or, really, concern me. To me, for just an easy answer, there is the real line with points, and that's description enough for me. Apparently the OP wants a description in terms of digits and is bothered that uncountably infinitely many reals need countably infinitely many decimal digits to be described. Okay, if don't like all those digits, then just return to the points on the line and let those points be the description. Good enough for me, but at this point I have quite different fish to fry getting my business going, really like the real numbers and what classic pure and applied math do with them, and see no good reason to change the foundations of what I do. More generally, it appears that computer science is struggling to find something to do beyond the biggies of quicksort, heap sort, merge sort, AVL trees, red-black trees, BNF, YACC, LALR parsing, relational database, P versus NP, etc. So computer science wants to take parts of statistics, optimization, control theory, and now the foundations of math for its own and, in those fields, do things differently. Maybe I'm missing a point: Maybe the idea is to have all the 'numerical' data computing works with be describable in some finite way, that is, not just a countably infinite sequences of digits, and, thus, get rid of, say, numerical error. Maybe. Seems a bit far fetched.
JadeNB 13y ago
You argued (without much detail, but I'll buy it) for completeness, but then snuck in ordered-ness and Archimedean-ness. As a p-adic analyst, I object to taking these latter two characteristics for granted as necessary for mathematics. (Also, one has to be careful about the meaning of 'complete' in the uniqueness statement; i.e., it must be understood to mean complete as an ordered field (satisfying the least-upper-bound property), not just complete as a uniform space (having every Cauchy sequence converge). See Paul Sally's "Tools of the trade" (http://www.amazon.com/Tools-Trade-Paul-J-Sally/dp/0821846345 http://www.amazon.com/Tools-Trade-Paul-J-Sally/dp/0821846345) for some discussion of this.)
- graycat 13y ago
  I was assuming that for counting, measuring, and arithmetic, we want a field (you know, addition, multiplication, both with an identity element and inverses, associativity, a distributed law, commutativity). We want order -- that is bigger and smaller. And likely we want Archimedean order. So, if we was also want each nonempty set bounded above to have a least upper bound, then we are stucko with the usual reals. For algebra, and in particular number theory, already in undergraduate school one of my math profs declared that I'm an analyst and not an algebraist. The difference? As that math prof explained, it: "Analysis has an idea behind it. Algebra is just pushing symbols around." I can think intuitively about analysis and often convert the intuitive ideas into good proofs; in algebra, mostly I can't do such a thing. I ended up writing my honors paper in group representations -- I didn't like such concentration on algebra. For using strange constructions from algebra or computer science to replace the reals, I will have to decline to buy in based if only on ignorance of the offering. But somehow I suspect that the reals are the right answer!

by graycat 13y ago

justinpombrio 13y ago

On the contrary, we do have a choice! We could use computable numbers instead of reals. A computable number is any number which is output by some Turing machine, or, equivalently, any number which can be found by some algorithm. e and pi are computable. You are right that Riemann integrals won't exist, but if you modify definitions somewhat, derivatives and integrals can be defined just as easily for computable numbers as for reals and you can do calculus with them (see second link). Unlike reals, computable numbers are countable, and are all describable. (That is, there are aleph-null of them, so there are exactly as many computable numbers as natural numbers, and fewer than real numbers). And while almost all real numbers aren't computable (by the argument in the article), essentially every number you'd ever stumble upon in a math class is. I prefer computable numbers to reals because I have trouble accepting that a thing exists when it by principal cannot be defined. https://en.wikipedia.org/wiki/Computable_number https://en.wikipedia.org/wiki/Computable_number http://www.amazon.com/Computable-Calculus-Oliver-Aberth/dp/0120417529 http://www.amazon.com/Computable-Calculus-Oliver-Aberth/dp/0...

ColinWright 13y ago
Numbers that can be computed by Turing Machines are countable, so list them: c_0, c_1, c_2, etc. Take any interval [a0,b0] (with a0 and b0 computable), and cross out your computable numbers until you find one, say, c_i, in the interval (including an endpoint). Take some strict sub-interval [a1,b1] (again with computable endpoints) within [a0,b0] such that a0<a1, b1<b0, and c_i is not in [a1,b1]. Now continue crossing off computable numbers, each time taking a sub-interval with computable endpoints to exclude any that happen to be in the interval currently under consideration. The left hand end-points, a0, a1, a2, etc, form a strictly increasing sequence of computable points. This sequence is bounded above, and so we would like there to be a least upper bound. And yet it cannot be one of the numbers you first chose, because each has been excluded at some stage. So here we have a strictly increasing, bounded above sequence of computable numbers such that there is no limit in the computable numbers. This proves the computable numbers are not complete, and that makes analysis really messy.
- justinpombrio 13y ago
  There's two related arguments you (may) be making. One is philosophical, and to that I say: can you give an algorithm to compute a0, a1, ...? If you can't (and I suspect you can't), I'd be hesitant to say that such a sequence exists. But I don't think there's a useful argument to have here ;-). But more concretely: no, the computable numbers aren't complete. Why would this make analysis messy? I didn't find the presentation and results in Computable Analysis (the book) all that different from what you find in an ordinary analysis course. Is there something it makes hard which I'm missing? (This might be impossible to answer without specific knowledge of Computable Analysis; remember that the definitions of, e.g. limits, are different.)
btilly 13y ago
And while almost all real numbers aren't computable (by the argument in the article), essentially every number you'd ever stumble upon in a math class is. Not every number though. It turns out that there are numbers that are describable but not computable. What is the difference? Well here's an example. A Chaitin omega number is the probability that a valid program randomly constructed according to a specific set of rules will eventually halt. It is describable - indeed I just described it. Yet Chaitin has proven that an algorithm to compute it will lead to an algorithm that solves the halting problem, so it cannot be computable. So there you have it. A class of perfectly describable numbers that are not computable. Indeed it can be proven that we cannot know more than a fixed number of digits for any particular one without increasing the size of our axiom system.

tome 13y ago

I'm afraid I'm not a good enough logician to answer your objection properly, but there are, I believe, credible approaches to doing mathematics on a countable carrier set, for example: http://arxiv.org/pdf/math/0509245 http://arxiv.org/pdf/math/0509245

graycat 13y ago
"Credible", likely yes. Likely also awkward. To weasel out, I just said we "want completeness". When you look at the alternatives, you may conclude that you still want completeness and, thus, are stuck with the reals with no alternative you "want"!
- tome 13y ago
  Awkward I would agree with, but probably only because we're much more used to the usual approach (cf the "awkwardness" of Haskell). Still, you'll see in that paper that the reals he constructs are complete. The get out clause is that they are not a set, but a class.
  - graycat 13y ago
    > The get out clause is that they are not a set, but a class. Good grief! In axiomatic set theory, introducing 'classes' was the "get out clause" from the Russell paradox of the the set of all sets that are not members of themselves. So, the patch, the time I studied one version of axiomatic set theory, was to say that there are some sets and we know what they are and we know that the Russell paradox can't happen now, so let's go on. It appears that the OP and alternatives to the usual treatment of the real numbers are based on what can be described. This issue doesn't impress, or, really, concern me. To me, for just an easy answer, there is the real line with points, and that's description enough for me. Apparently the OP wants a description in terms of digits and is bothered that uncountably infinitely many reals need countably infinitely many decimal digits to be described. Okay, if don't like all those digits, then just return to the points on the line and let those points be the description. Good enough for me, but at this point I have quite different fish to fry getting my business going, really like the real numbers and what classic pure and applied math do with them, and see no good reason to change the foundations of what I do. More generally, it appears that computer science is struggling to find something to do beyond the biggies of quicksort, heap sort, merge sort, AVL trees, red-black trees, BNF, YACC, LALR parsing, relational database, P versus NP, etc. So computer science wants to take parts of statistics, optimization, control theory, and now the foundations of math for its own and, in those fields, do things differently. Maybe I'm missing a point: Maybe the idea is to have all the 'numerical' data computing works with be describable in some finite way, that is, not just a countably infinite sequences of digits, and, thus, get rid of, say, numerical error. Maybe. Seems a bit far fetched.

JadeNB 13y ago

You argued (without much detail, but I'll buy it) for completeness, but then snuck in ordered-ness and Archimedean-ness. As a p-adic analyst, I object to taking these latter two characteristics for granted as necessary for mathematics. (Also, one has to be careful about the meaning of 'complete' in the uniqueness statement; i.e., it must be understood to mean complete as an ordered field (satisfying the least-upper-bound property), not just complete as a uniform space (having every Cauchy sequence converge). See Paul Sally's "Tools of the trade" (http://www.amazon.com/Tools-Trade-Paul-J-Sally/dp/0821846345 http://www.amazon.com/Tools-Trade-Paul-J-Sally/dp/0821846345) for some discussion of this.)

graycat 13y ago
I was assuming that for counting, measuring, and arithmetic, we want a field (you know, addition, multiplication, both with an identity element and inverses, associativity, a distributed law, commutativity). We want order -- that is bigger and smaller. And likely we want Archimedean order. So, if we was also want each nonempty set bounded above to have a least upper bound, then we are stucko with the usual reals. For algebra, and in particular number theory, already in undergraduate school one of my math profs declared that I'm an analyst and not an algebraist. The difference? As that math prof explained, it: "Analysis has an idea behind it. Algebra is just pushing symbols around." I can think intuitively about analysis and often convert the intuitive ideas into good proofs; in algebra, mostly I can't do such a thing. I ended up writing my honors paper in group representations -- I didn't like such concentration on algebra. For using strange constructions from algebra or computer science to replace the reals, I will have to decline to buy in based if only on ignorance of the offering. But somehow I suspect that the reals are the right answer!