4 ms·

(Somewhat OT, but...) Constructive logic accepts the truth of every integer is either even or odd, but only because we have an effective means of determining w

(Somewhat OT, but...) Constructive logic accepts the truth of every integer is either even or odd, but only because we have an effective means of determining which alternative holds for any integer. It does not accept the statement every real number is either rational or irrational; given a real number, say as a convergent series, we have no effective means of determining whether or not it is rational. I don't understand this. Consider the smallest number N so that any N points in the coordinate plane in general position contain a subset of 7 points that form the vertices of a convex polygon (taken from [0], recently discussed here on HN): is this number, which is definitely an integer, even or odd? We don't know, because we don't know what the number is. Isn't that the same situation we are in with regard to the convergent series? What's the difference? If we actually computed the decimal expansion of the value of the convergent series, we would be able to look at it and see whether it was rational or irrational. There is the minor difficulty that the expansion is in most cases going to be infinite, but so what? We're talking about mathematics here, not computation. [0] https://liorpachter.wordpress.com/2015/09/20/unsolved-problems-with-the-common-core/ https://liorpachter.wordpress.com/2015/09/20/unsolved-proble..., "Fifth grade" section

spdionis 11y ago
I don't think that the expansion being sometimes infinite is a minor difficulty. In fact it sounds pretty major, similiar to the halting problem. Unless you can prove if it's infinite or not a priori. I'm not knowledgeable about this topic but the quote suggests you can't prove that.
- dllthomas 11y ago
  "In fact it sounds pretty major, similiar to the halting problem." I think it's identical to the halting problem. The issue is that, for irrational numbers, there is never a point at which you can stop and say "okay, we know it is irrational now". In fact, if we had an algorithm that could always tell us whether a sequence converged to a rational number, we could solve the Halting Problem: For any Turing Machine you wish to check for halting-ness, produce a sequence S by successively appending a full encoding (any will do) of the Turing Machine state at every step to the decimal expansion of the previous value in S. Apply your algorithm to S. If S is irrational, then we know it never halts. If S is rational, then we know it halts or repeats after a finite number of digits - so we can simply run it until it does one or the other (this may take arbitrarily long, and an arbitrarily large amount of storage, but finitely in both cases).
  - ScottBurson 11y ago
    Everyone has gotten distracted by the infinite expansion and has missed the point of my question. Let me try again, with no infinite expansion. The constructivist position is to refuse to accept the statement "every real number is either rational or irrational" because they're not in possession of proofs, for each possible real-valued expression, that its value is rational or, alternatively, a proof that its value is irrational. And yet, according to the quoted paragraph, they accept the statement "every integer is either even or odd", quote, "because we have an effective means of determining which alternative holds for any integer". My argument is that they should reject this statement on the same grounds: I named an integer whose value is not known, and therefore it is not known whether it is even or odd. There is not, in fact, an effective procedure for determining the evenness or oddness of the value of an arbitrary integer-valued expression. It's only after one actually knows the value that answering the question becomes easy.
    - dllthomas 11y ago
      IANAM, but I think the difference comes down to the fact that we know the integer you are producing is one we possess a proof for. We do not know that for reals.
    - plonh 11y ago
      Constructivists reject the notion of an integer whose value is not known (more precisely, whose value cannot be computed in finite time) so there is no room to even ask of "it" is odd. Infinite vs finite is an important distinction. A fact that takes infinite time to prove is not constructive and is likewise not computable.
    - pavpanchekha 11y ago
      Constructivists don't accept that you've named an integer. They would say: an integer is any member of the smallest constructive set that contains 0 and one more than any member of that set. Since the set is a constructive set, if you have anything you claim to be an integer, you must be able to either prove that it is 0 or one more than an integer. The number you named isn't zero, so presumably it must be more than some integer ("one less than the number you named"). But if I then ask you whether that number is one more than an integer, and then the same about that one, and so on, at some point you will be unable to answer me. Since you can't provide the evidence that qualifies something as an integer, there's no reason for me to think it is an integer.
tgb 11y ago
A convergent sequence doesn't have to be a digit expansion and so might not have the nice property that "if it's just repeating, it's rational, otherwise irrational." Furthermore, it wasn't proven until the 18th century that Pi was irrational (https://en.wikipedia.org/wiki/Proof_that_%CF%80_is_irrational https://en.wikipedia.org/wiki/Proof_that_%CF%80_is_irrationa...). To this day, it is unproven that pi+e is irrational, yet the decimal expansion is easy to compute (and you'd be a fool to bet on it being rational).

spdionis 11y ago

I don't think that the expansion being sometimes infinite is a minor difficulty. In fact it sounds pretty major, similiar to the halting problem. Unless you can prove if it's infinite or not a priori. I'm not knowledgeable about this topic but the quote suggests you can't prove that.

dllthomas 11y ago
"In fact it sounds pretty major, similiar to the halting problem." I think it's identical to the halting problem. The issue is that, for irrational numbers, there is never a point at which you can stop and say "okay, we know it is irrational now". In fact, if we had an algorithm that could always tell us whether a sequence converged to a rational number, we could solve the Halting Problem: For any Turing Machine you wish to check for halting-ness, produce a sequence S by successively appending a full encoding (any will do) of the Turing Machine state at every step to the decimal expansion of the previous value in S. Apply your algorithm to S. If S is irrational, then we know it never halts. If S is rational, then we know it halts or repeats after a finite number of digits - so we can simply run it until it does one or the other (this may take arbitrarily long, and an arbitrarily large amount of storage, but finitely in both cases).
- ScottBurson 11y ago
  Everyone has gotten distracted by the infinite expansion and has missed the point of my question. Let me try again, with no infinite expansion. The constructivist position is to refuse to accept the statement "every real number is either rational or irrational" because they're not in possession of proofs, for each possible real-valued expression, that its value is rational or, alternatively, a proof that its value is irrational. And yet, according to the quoted paragraph, they accept the statement "every integer is either even or odd", quote, "because we have an effective means of determining which alternative holds for any integer". My argument is that they should reject this statement on the same grounds: I named an integer whose value is not known, and therefore it is not known whether it is even or odd. There is not, in fact, an effective procedure for determining the evenness or oddness of the value of an arbitrary integer-valued expression. It's only after one actually knows the value that answering the question becomes easy.
  - dllthomas 11y ago
    IANAM, but I think the difference comes down to the fact that we know the integer you are producing is one we possess a proof for. We do not know that for reals.
  - plonh 11y ago
    Constructivists reject the notion of an integer whose value is not known (more precisely, whose value cannot be computed in finite time) so there is no room to even ask of "it" is odd. Infinite vs finite is an important distinction. A fact that takes infinite time to prove is not constructive and is likewise not computable.
  - pavpanchekha 11y ago
    Constructivists don't accept that you've named an integer. They would say: an integer is any member of the smallest constructive set that contains 0 and one more than any member of that set. Since the set is a constructive set, if you have anything you claim to be an integer, you must be able to either prove that it is 0 or one more than an integer. The number you named isn't zero, so presumably it must be more than some integer ("one less than the number you named"). But if I then ask you whether that number is one more than an integer, and then the same about that one, and so on, at some point you will be unable to answer me. Since you can't provide the evidence that qualifies something as an integer, there's no reason for me to think it is an integer.

tgb 11y ago

A convergent sequence doesn't have to be a digit expansion and so might not have the nice property that "if it's just repeating, it's rational, otherwise irrational." Furthermore, it wasn't proven until the 18th century that Pi was irrational (https://en.wikipedia.org/wiki/Proof_that_%CF%80_is_irrational https://en.wikipedia.org/wiki/Proof_that_%CF%80_is_irrationa...). To this day, it is unproven that pi+e is irrational, yet the decimal expansion is easy to compute (and you'd be a fool to bet on it being rational).