News for hackers. Stuff that matters.
Re:The Axiom of Infinity by dwohnitmok on Tuesday December 06, 2022 @08:44PM (#33889738)
> Practically speaking, what results obtained with the Axiom of Infinity cannot be achieved without it?

There's a surprising amount you can achieve without the Axiom of Infinity, but the way you have to "talk" about things gets very awkward very quickly.

First off, what you end up with at the end of the day if you take the negation of the Axiom of Infinity but keep the rest of ZF (this is also known as the theory of hereditarily finite sets, i.e. finite sets whose members must also be finite sets all the way down) are the (first-order) Peano Axioms. To explain an intuition for why in a very hand-wavy sense, if you only have finite sets, you can encode any finite set as a single natural number and vice versa .As witness of this in programming, note that that an array ultimately is a single binary number consisting of 0s and 1s and likewise a single natural number ultimately is just a single binary number consisting of 0s and 1s. To also very hand-wavingly describe why the Peano Axioms are in fact excluding the notion of infinity, note that the Peano Axioms have no way to talk about the natural numbers as a single entity, only a way of talking about each individual number.

So to answer your question directly, any theorem about the natural numbers that cannot be proved with the Peano Axioms cannot be proved without the Axiom of Infinity in ZF. For example, the Paris-Harrington Theorem cannot be proved without the Axiom of Infinity in ZF. These are potentially philosophically interesting examples since they are theorems about finite numbers that cannot be proved without the Axiom of Infinity (although the ultrafinitist would object to the careless use of "for all natural numbers" that shows up in these statements).

On the flip side, a surprising amount of theorems ostensibly about infinite structures can be proved purely with Peano Arithmetic alone. Let's talk about the real numbers for example. The general trick is that while you obviously cannot talk directly about a "real number," you can talk about all the finite structures which approximate a real number and their finite consequences. So instead of saying statements of the form "there exists a real number r such that X" you end up saying "for all natural numbers n, there exists another natural number m_n with property A such that each number satisfies X'" where n forms the indices of a series of approximations m_n whose property A ensures that they are correctly approximating r and X' is the property X translated to be a property on each individual approximation.

Now I personally find this a very awkward way to talk about the real numbers. In particular the theory itself cannot recognize that it's trying to approximate something, as the theory has no concept of that "something." Only you as an external observer can look at the theory and "realize" that a given theorem is "really" talking about the real numbers. Within the theory it just looks like you're proving really weird things about really weird sequences.

But with this in hand you can prove some parts of analysis, but not others. E.g. the validity of using the ratio test from calculus cannot be proven even within this framework.

Re:The Axiom of Infinity by Chinjut on Tuesday December 06, 2022 @11:20PM (#33890588)
You can't prove the validity of the ratio test for all sequences of real numbers, because you can't talk about all sequences of real numbers. 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...".
Re:The Axiom of Infinity by dwohnitmok on Wednesday December 07, 2022 @12:43AM (#33891023)
> 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).

Re:The Axiom of Infinity by Chinjut on Wednesday December 07, 2022 @02:18AM (#33891585)
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.

Re:The Axiom of Infinity by dwohnitmok on Thursday December 08, 2022 @05:12PM (#33914412)
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.

Re:The Axiom of Infinity by Chinjut on Friday December 09, 2022 @02:24AM (#33918618)
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.
Re:The Axiom of Infinity by dwohnitmok on Friday December 09, 2022 @11:45AM (#33923392)
Yes you're correct. But computably enumerable sequences of computable reals is also too strong of a restriction.