4 ms·

> But you could at least prove the validity of the ratio test for any computably enumerable sequence of computable real numbers, or such things. You could carry

> But you could at least prove the validity of the ratio test for any computably enumerable sequence of computable real numbers, or such things. You could carry out the full argument of the ratio test, except for the tiny part at the beginning where it says "Let us quantify over the set of all sequences of reals...". I don't actually think so. I'd have to retrace the arguments again, but I believe the ratio test is beyond ACA0 which puts it beyond PA and therefore impossible to prove in a much more fundamental way than just the inability to quantify over the reals. (also, as I'm sure you know, but for the benefit of other readers, you can "morally" quantify over the reals in the same manner I described for "moral" existential quantification of a real, but even with that trick, I don't believe you can prove the transformed version of the ratio test).

Chinjut 4y ago
How could the ratio test possibly be beyond ACA0? The ratio test is just a straightforward special case of the comparison test. For convenience, let us suppose we are dealing with series of positive terms (since the ratio test is about magnitudes and absolute convergence anyway). Given a series S with limiting value L for ratio of terms to previous terms, and considering a geometric series G for which the same ratio is any value strictly between L and 1, then when L < 1, we have that S is eventually upper-bounded by G and G is convergent, while for L > 1, we have that S is eventually lower-bounded by G and G is divergent.
- dwohnitmok 4y ago
  I have no idea why I wrote ACA0. I was totally wrong (ACA0 is enough for Dedekind-completeness...). But the ratio test is actually subtly difficult. > But you could at least prove the validity of the ratio test for any computably enumerable sequence of computable real numbers, or such things. This still actually isn't quite true, the emphasis on "computable" being essential here. In particular the ratio test is (unless I've yet again made a catastrophic mistake) not provable in RCA0. The tricky problem with your proof sketch is the word "eventually." In general you can't find the N that validates your usage of the word "eventually" in a computable fashion. This is fundamentally different than superficially similar tests such as the alternating series test because those don't lean on "eventually" in the same way. So the ratio test is actually still uniquely difficult for (computable) finitism.
  - Chinjut 4y ago
    RCA_0 is a much stronger restriction than just negating the Axiom of Infinity, though. Your original post claimed the ratio test could not be proven in Peano Arithmetic, which was what I objected to. Peano Arithmetic is basically equivalent in strength to ACA_0.
    - dwohnitmok 4y ago
      Yes you're correct. But computably enumerable sequences of computable reals is also too strong of a restriction.

Chinjut 4y ago

How could the ratio test possibly be beyond ACA0? The ratio test is just a straightforward special case of the comparison test. For convenience, let us suppose we are dealing with series of positive terms (since the ratio test is about magnitudes and absolute convergence anyway). Given a series S with limiting value L for ratio of terms to previous terms, and considering a geometric series G for which the same ratio is any value strictly between L and 1, then when L < 1, we have that S is eventually upper-bounded by G and G is convergent, while for L > 1, we have that S is eventually lower-bounded by G and G is divergent.

dwohnitmok 4y ago
I have no idea why I wrote ACA0. I was totally wrong (ACA0 is enough for Dedekind-completeness...). But the ratio test is actually subtly difficult. > But you could at least prove the validity of the ratio test for any computably enumerable sequence of computable real numbers, or such things. This still actually isn't quite true, the emphasis on "computable" being essential here. In particular the ratio test is (unless I've yet again made a catastrophic mistake) not provable in RCA0. The tricky problem with your proof sketch is the word "eventually." In general you can't find the N that validates your usage of the word "eventually" in a computable fashion. This is fundamentally different than superficially similar tests such as the alternating series test because those don't lean on "eventually" in the same way. So the ratio test is actually still uniquely difficult for (computable) finitism.
- Chinjut 4y ago
  RCA_0 is a much stronger restriction than just negating the Axiom of Infinity, though. Your original post claimed the ratio test could not be proven in Peano Arithmetic, which was what I objected to. Peano Arithmetic is basically equivalent in strength to ACA_0.
  - dwohnitmok 4y ago
    Yes you're correct. But computably enumerable sequences of computable reals is also too strong of a restriction.