6 ms·

If you define the reals axiomatically, you still need an existence proof. Which will involve addition and multiplication algorithms.

yakubin 6y ago
Not algorithms. There will be infinite addition involved, and algorithms are finite. Thinking of multiplication as repeated addition also won't explain anything about it. It's a separate operation. Deal with it. For similar reasons, you can't calculate x-th power of a number, when x is irrational, by decomposing it into exponentiation and roots. This metaphor is just training wheels. At some point you should lose it. Together with the notion that "multiplication is repeated addition" comes the notion that numbers are quantities. Only some of them are, and this isn't really what makes them numbers. Now what exactly gets repeated, when you don't have quantities?
- titzer 6y ago
  Algorithms can work on symbolic formulas, and symbols can represent anything; infinite objects, operations on infinite objects, infinite sets of operations on infinite objects, and so on.
- prionassembly 6y ago
  Multiplication on the naturals is repeated addition. You might see the natural numbers as training wheels for higher mathematics, but number theorists might disagree...
  - yakubin 6y ago
    Number theorists work with integers, not naturals. And they too will agree with me, as they mostly work with polynomials, which show exactly that. I also didn't say natural numbers are training wheels, just this metaphor, which to use HN lingo: doesn't scale.
    - alisonkisk 6y ago
      Number theorists work with complex numbers and irrational numbers too https://www.britannica.com/science/Riemann-zeta-function https://www.britannica.com/science/Riemann-zeta-function
- gugagore 6y ago
  Algorithms are not finite. E.g. Newton's method.
  - yakubin 6y ago
    First sentence on Wikipedia[1]: > In mathematics and computer science, an algorithm (/ˈælɡərɪðəm/ (About this soundlisten)) is a finite sequence of well-defined, computer-implementable instructions, typically to solve a class of problems or to perform a computation. Newton's method is finite too. You perform finitely many iterations. It doesn't calculate roots. It calculates their approximations. [1]: <https://en.wikipedia.org/wiki/Algorithm https://en.wikipedia.org/wiki/Algorithm>
    - gugagore 6y ago
      If you use a termination condition that has to do with convergence of iterates instead of a number of iterations (often the case), then you generally don't know beforehand the length of the finite sequences. Maybe you know a bound, but in general you might not even have that. In an important sense, it only becomes a finite algorithm. It isn't one. You cannot write the finite sequence of instructions down. It's got loops. To your point about approximations vs not, if you have an algorithm that, for any desired approximation accuracy can compute the square root to that accuracy in a finite number of steps, then that process is as much "the square root" as anything involving the real numbers.
      - yakubin 6y ago
        > To your point about approximations vs not, if you have an algorithm that, for any desired approximation accuracy can compute the square root to that accuracy in a finite number of steps, then that process is as much "the square root" as anything involving the real numbers. Not really, since approximations, no matter how accurate, don't preserve algebraic properties. You only get to know what it's bigger/smaller than.
        gugagore 6y ago
- bopbeepboop 6y ago
  Algorithms aren’t necessarily finite, eg “while True, print 1”. Also, an irrational exponent is the product of component factors. b = Prod(0,inf) a^[x_i * 10^(-i)] = a^x So even with irrational numbers, operations can be decomposed - such as exponentiation into multiplication of integer exponents and roots. Which makes sense, because in the sequence definition of reals you need a way to generate the resulting sequence from the two original sequences. I think you’re trying to claim more than is true.
- eru 6y ago
  > There will be infinite addition involved, and algorithms are finite. People are just bit sloppy, and say algorithm when they mean something slightly different. See https://stackoverflow.com/questions/28841260/what-is-the-difference-between-codata-and-data https://stackoverflow.com/questions/28841260/what-is-the-dif... and https://en.wikipedia.org/wiki/Corecursion https://en.wikipedia.org/wiki/Corecursion Basically, you don't want an 'algorithm' here to produce the whole number. All you need is some scheme that will produce the next digit in finite time (and the next one and the next one etc).
  - alisonkisk 6y ago
    Which is a technical way of saying "in real life people use finite rational or algebraic approximations for reals, so uncountability of reals and infinite precision aren't a problem".
    - eru 6y ago
      Not quite. Consider the following real number made of binary digits: Enumerate all Turing machines and all possible inputs, iff the i-th machine/input combination holds, the i-th binary digit in our number is 0, otherwise 1. This number is well-defined (once you fix your enumeration scheme). But there's no finite algorithm to produce approximations in your sense. What I was after were what's also called Computable numbers (https://en.wikipedia.org/wiki/Computable_number https://en.wikipedia.org/wiki/Computable_number). But I used the more general term of co-recursion, that also applies to arbitrary other data-structures like infinite lists, or with some generalization, infinite event-loops where the important condition is that each run through the body of the loop only takes finite time.
qsort 6y ago
Well, no, not really. The standard definition of the reals is as the unique nontrivial totally-ordered, Dedekind-complete, Archimedean field up to isomorphism. So what you would really need is a uniqueness proof, with addition and multiplications "provided" by the hypothesis.
- howling 6y ago
  And how do you prove that a totally-ordered, Dedekind-complete, Archimedean field does not lead to contradiction besides constructing it explicitly by bootstrapping from natural numbers?
  - qsort 6y ago
    Nothing in the construction requires you to show an algorithm that given x, y \in R allows you to compute x+y and xy. You would make the usual Dedekind construction and show it satisfies the axioms of such a field. (as a matter of fact, no such algorithm exists in full generality!) It's probably a tomato/tomato kind of thing, but I'm only objecting to the 'algorithm' part of parent's comment.

yakubin 6y ago

Not algorithms. There will be infinite addition involved, and algorithms are finite. Thinking of multiplication as repeated addition also won't explain anything about it. It's a separate operation. Deal with it. For similar reasons, you can't calculate x-th power of a number, when x is irrational, by decomposing it into exponentiation and roots. This metaphor is just training wheels. At some point you should lose it. Together with the notion that "multiplication is repeated addition" comes the notion that numbers are quantities. Only some of them are, and this isn't really what makes them numbers. Now what exactly gets repeated, when you don't have quantities?

titzer 6y ago
Algorithms can work on symbolic formulas, and symbols can represent anything; infinite objects, operations on infinite objects, infinite sets of operations on infinite objects, and so on.
prionassembly 6y ago
Multiplication on the naturals is repeated addition. You might see the natural numbers as training wheels for higher mathematics, but number theorists might disagree...
- yakubin 6y ago
  Number theorists work with integers, not naturals. And they too will agree with me, as they mostly work with polynomials, which show exactly that. I also didn't say natural numbers are training wheels, just this metaphor, which to use HN lingo: doesn't scale.
  - alisonkisk 6y ago
    Number theorists work with complex numbers and irrational numbers too https://www.britannica.com/science/Riemann-zeta-function https://www.britannica.com/science/Riemann-zeta-function
gugagore 6y ago
Algorithms are not finite. E.g. Newton's method.
- yakubin 6y ago
  First sentence on Wikipedia[1]: > In mathematics and computer science, an algorithm (/ˈælɡərɪðəm/ (About this soundlisten)) is a finite sequence of well-defined, computer-implementable instructions, typically to solve a class of problems or to perform a computation. Newton's method is finite too. You perform finitely many iterations. It doesn't calculate roots. It calculates their approximations. [1]: <https://en.wikipedia.org/wiki/Algorithm https://en.wikipedia.org/wiki/Algorithm>
  - gugagore 6y ago
    If you use a termination condition that has to do with convergence of iterates instead of a number of iterations (often the case), then you generally don't know beforehand the length of the finite sequences. Maybe you know a bound, but in general you might not even have that. In an important sense, it only becomes a finite algorithm. It isn't one. You cannot write the finite sequence of instructions down. It's got loops. To your point about approximations vs not, if you have an algorithm that, for any desired approximation accuracy can compute the square root to that accuracy in a finite number of steps, then that process is as much "the square root" as anything involving the real numbers.
    - yakubin 6y ago
      > To your point about approximations vs not, if you have an algorithm that, for any desired approximation accuracy can compute the square root to that accuracy in a finite number of steps, then that process is as much "the square root" as anything involving the real numbers. Not really, since approximations, no matter how accurate, don't preserve algebraic properties. You only get to know what it's bigger/smaller than.
      - gugagore 6y ago
bopbeepboop 6y ago
Algorithms aren’t necessarily finite, eg “while True, print 1”. Also, an irrational exponent is the product of component factors. b = Prod(0,inf) a^[x_i * 10^(-i)] = a^x So even with irrational numbers, operations can be decomposed - such as exponentiation into multiplication of integer exponents and roots. Which makes sense, because in the sequence definition of reals you need a way to generate the resulting sequence from the two original sequences. I think you’re trying to claim more than is true.
eru 6y ago
> There will be infinite addition involved, and algorithms are finite. People are just bit sloppy, and say algorithm when they mean something slightly different. See https://stackoverflow.com/questions/28841260/what-is-the-difference-between-codata-and-data https://stackoverflow.com/questions/28841260/what-is-the-dif... and https://en.wikipedia.org/wiki/Corecursion https://en.wikipedia.org/wiki/Corecursion Basically, you don't want an 'algorithm' here to produce the whole number. All you need is some scheme that will produce the next digit in finite time (and the next one and the next one etc).
- alisonkisk 6y ago
  Which is a technical way of saying "in real life people use finite rational or algebraic approximations for reals, so uncountability of reals and infinite precision aren't a problem".
  - eru 6y ago
    Not quite. Consider the following real number made of binary digits: Enumerate all Turing machines and all possible inputs, iff the i-th machine/input combination holds, the i-th binary digit in our number is 0, otherwise 1. This number is well-defined (once you fix your enumeration scheme). But there's no finite algorithm to produce approximations in your sense. What I was after were what's also called Computable numbers (https://en.wikipedia.org/wiki/Computable_number https://en.wikipedia.org/wiki/Computable_number). But I used the more general term of co-recursion, that also applies to arbitrary other data-structures like infinite lists, or with some generalization, infinite event-loops where the important condition is that each run through the body of the loop only takes finite time.

qsort 6y ago

Well, no, not really. The standard definition of the reals is as the unique nontrivial totally-ordered, Dedekind-complete, Archimedean field up to isomorphism. So what you would really need is a uniqueness proof, with addition and multiplications "provided" by the hypothesis.

howling 6y ago
And how do you prove that a totally-ordered, Dedekind-complete, Archimedean field does not lead to contradiction besides constructing it explicitly by bootstrapping from natural numbers?
- qsort 6y ago
  Nothing in the construction requires you to show an algorithm that given x, y \in R allows you to compute x+y and xy. You would make the usual Dedekind construction and show it satisfies the axioms of such a field. (as a matter of fact, no such algorithm exists in full generality!) It's probably a tomato/tomato kind of thing, but I'm only objecting to the 'algorithm' part of parent's comment.