News for hackers. Stuff that matters.
Re:The Axiom of Infinity by andrewla on Tuesday December 06, 2022 @06:56PM (#33888843)
I'm generally aligned with constructivism and intuitionism, but I don't quite get finitism. To me it seems that even without this axiom, it's clear that there are infinite objects in the sense of an unbounded set.

Practically speaking, what results obtained with the Axiom of Infinity cannot be achieved without it?

Re:The Axiom of Infinity by naasking on Tuesday December 06, 2022 @07:32PM (#33889143)
Any discussion of finitism warrants a citation of Bendegem's paper:

A Defense of Strict Finitism, https://www.researchgate.net/publication/288354797_A_Defense...

Re:The Axiom of Infinity by vintermann on Wednesday December 07, 2022 @04:21AM (#33892329)
Thank you, that seems really interesting, and it touches tantalizingly onto some ideas I've wondered if anyone has formalized.

There's the old joke that

1. Not all numbers are interesting 2. If not all numbers are interesting, then there's a smallest number that's not interesting 3. But that's interesting in itself! Ha! Contradiction!

But it seems to me all you need to resolve that contradiction is to be a bit tough and say that no, it being the smallest boring number isn't interesting. Who cares.

What I would like to know is if there is a formalization of "we don't care about that". Obviously we use the idea sometimes (Karnaugh maps come to mind).

Re:The Axiom of Infinity by yamrzou on Tuesday December 06, 2022 @09:14PM (#33889925)
Re:The Axiom of Infinity by naasking on Tuesday December 06, 2022 @09:31PM (#33890011)
Nice list! I'll add one more I enjoyed:

Struggles with the Continuum, by John Baez, https://arxiv.org/abs/1609.01421

Re:The Axiom of Infinity by qsort on Tuesday December 06, 2022 @07:03PM (#33888896)
Without the axiom of infinity you can't show that there exists an infinite set in ZF.

i.e. you can't use anything infinite, including natural numbers. It's actually extremely restrictive to get rid of it.

Re:The Axiom of Infinity by Chinjut on Tuesday December 06, 2022 @08:27PM (#33889601)
Well, you can't create the infinite set of all natural numbers without the Axiom of Infinity. You can still reason about natural numbers themselves without the Axiom of Infinity (and if you are inclined to speak in such terms, the natural numbers will still comprise a "class", just a proper class rather than a set, when the Axiom of Infinity is negated).

ZF(C) with the Axiom of Infinity replaced by its negation is essentially equivalent to Peano Arithmetic, and you can do an awful lot of math just fine in Peano Arithmetic.

Re:The Axiom of Infinity by Kranar on Wednesday December 07, 2022 @02:14AM (#33891571)
You can't create the set of natural numbers even with the axiom of infinity either, at least not in any first order logic. No first order logic is sufficient to strictly define the set of all natural numbers.

You can technically construct natural numbers in second order logic, at least syntactically, but then the semantics of natural numbers in second order logic does not end up corresponding to what is actually meant by natural numbers.

A good article on this is linked here:

https://www.lesswrong.com/posts/MLqhJ8eDy5smbtGrf/completene...

Re:The Axiom of Infinity by dwohnitmok on Thursday December 08, 2022 @05:29PM (#33914642)
> You can't create the set of natural numbers even with the axiom of infinity either, at least not in any first order logic. No first order logic is sufficient to strictly define the set of all natural numbers.

Eh that's a fundamentally different problem though, although that is part of the reason why finitism and ultra-finitism are attractive.

You can define a set that is the natural numbers for all intents and purposes from the viewpoint of your theory. If you were willing accept that something like PA is enough to do large parts of real analysis (and also believed in the usefulness of real analysis), then philosophically you should be totally fine with using theories that have models with nonstandard natural numbers, since "you can't observe any of the consequences from your theory" is the same bar in both cases (in the case of finitistic approaches to analysis it's even trickier because often you can only deal with encodings of objects rather than objects themselves and must rely on your metatheory to do the association of the encoding to the object).

Re:The Axiom of Infinity by Kranar on Thursday December 08, 2022 @07:38PM (#33915916)
I don't agree it's a different problem, as OP pointed out, ZF with the axiom of infinity replaced by its negation is equal to first order Peano Arithmetic, sometimes referred to as the theory of hereditarily finite sets.

Said theory is also sufficient for all intents and purposes of doing real analysis.

Re:The Axiom of Infinity by dwohnitmok on Thursday December 08, 2022 @08:51PM (#33916383)
> I don't agree it's a different problem, as OP pointed out, ZF with the axiom of infinity replaced by its negation is equal to first order Peano Arithmetic, sometimes referred to as the theory of hereditarily finite sets.

Being unable to talk about the set of natural numbers except through encodings (which is how you do infinitary math without infinity) is different than having a symbol for the set of natural numbers which may or may not have additional properties which cannot be discerned within the theory itself (e.g. Lowenheim-Skolem).

> Said theory is also sufficient for all intents and purposes of doing real analysis.

Large chunks of real analysis can indeed be carried out, but significant amounts cannot. Many theorems in analysis concerning perfect sets are not provable in that theory (usually stated as ACA0).

Re:The Axiom of Infinity by skulk on Tuesday December 06, 2022 @08:32PM (#33889642)
> you can't use anything infinite, including natural numbers.

This is false, you don't need the axiom of infinity to prove theorems about all natural numbers.

https://math.stackexchange.com/questions/2850064/does-counta...

Particularly:

> Notice here, we are just treating the natural numbers as a class, not necessarily a set. In fact we can prove from ZF minus infinity that any of the (translations of the) axioms of PA, including all the induction axioms, hold in this class.

Re:The Axiom of Infinity by andrewla on Tuesday December 06, 2022 @07:22PM (#33889057)
I need more elucidation on that. Why can't you use the natural numbers? You can construct them even within the constraints of ZF. Is it just that you can't use it the same way as a set in all cases? It seems like you could define a new class, call them seits, that include both the set as axiomatically defined as well as these sorts of unbounded objects, and then prove that you can define similar operations as exist for sets on seits, and then go on and live your life.

When you say you can't "use" anything infinite, what's an example of a theorem that cannot be proven without the Axiom of Infinity?

Re:The Axiom of Infinity by qsort on Tuesday December 06, 2022 @07:29PM (#33889114)
> Why can't you use the natural numbers?

Because the rest of the axioms of ZF aren't sufficient to construct them.

> what's an example of a theorem that cannot be proven without the Axiom of Infinity?

That there exists a set equal to the natural numbers up to isomorphism, that there exist well-defined operations "+", "-", "*", "/" with usual semantics, that there exist the usual sets of rational, real, complex numbers.

Re:The Axiom of Infinity by klodolph on Tuesday December 06, 2022 @10:13PM (#33890229)
You can construct any natural number without the axiom of infinity, but you cannot construct the set of natural numbers itself.

> It seems like you could define a new class, call them seits, that include both the set as axiomatically defined as well as these sorts of unbounded objects, and then prove that you can define similar operations as exist for sets on seits, and then go on and live your life.

Imagine you’re at a vegan restaurant. Your food arrives, you pull a fistful of ground beef out of your pocket and stick it on top. You’re “still eating vegan food”, you’ve just added beef to it.

Finitism is a lot like a dietary restriction. It’s asking “What can you do WITHOUT these axioms?” The question is whether you still have a balanced diet afterwards, whether you’re satisfied, whether you prefer a vegan or omnivorous diet, etc. If you add infinities to your finite sets but call them classes instead you’re just cheating on your diet. (Or you’re talking about models of finitism.)

I suspect that there are a ton of results that can’t be proven without the axiom of infinity, but I don’t keep track of them.

Re:The Axiom of Infinity by amelius on Tuesday December 06, 2022 @07:11PM (#33888977)
Not a mathematician, but can't you parameterize e.g. the natural numbers by its largest element, then write whatever you want to do with the set and put lim n->inf around it? That way, you keep the objects finite, but you still allow them to become arbitrarily large.
Re:The Axiom of Infinity by qsort on Tuesday December 06, 2022 @07:34PM (#33889167)
That "lim n->inf" is doing a lot of work there.

How would you even define "limit"?

You can certainly work with bounded integers, but now suddenly your arithmetic has undefined behavior.

Re:The Axiom of Infinity by Ferrotin on Tuesday December 06, 2022 @07:14PM (#33888999)
That parameterization, as you describe it, would be a an infinite set.
Re:The Axiom of Infinity by naasking on Tuesday December 06, 2022 @07:30PM (#33889120)
I don't see why. A parameter provides an upper bound but there's no need to also assume that that upper bound must go to infinity.
Re:The Axiom of Infinity by Ferrotin on Tuesday December 06, 2022 @10:03PM (#33890165)
Define lim without infinite sets. Define how you quantify over all values of n without infinite sets. The parameterization you describe would be a function mapping an infinite set of sets of natural numbers to their maximum elements, that function itself being (or containing) an infinite set of ordered pairs.

You might be able to pull it off without creating something equivalent to the axiom of infinity — I wouldn’t know if it’s possible. But the naïve implementation of your ideas involves the construction of infinite sets.

I think you can do this rigorously outside the theory, talking about it, but not inside.

Re:The Axiom of Infinity by rfergie on Tuesday December 06, 2022 @07:43PM (#33889241)
One construction of the natural numbers that I've seen is

1. There exists an element 0 that is a natural number

2. For every natural number there is a "sucessor" that is also a natural number. (i.e. if n is a natural number then n+1 is a natural number)

This construction means there can't be an upper bound N because then step 2 couldn't be applied to N.

Maybe there are other constructions that could workaround this? I'm guessing not because you'd still struggle to define the usual rules of addition for all numbers in a bounded set

Re:The Axiom of Infinity by naasking on Tuesday December 06, 2022 @08:55PM (#33889819)
> This construction means there can't be an upper bound N because then step 2 couldn't be applied to N.

Bendegem discusses this problem at length in his paper [1]. As programming-heavy site, I assume we're all aware that computers have finite resources. The universe too has finite resources so no matter how big a computer you build, it too will be finite. Therefore the infinity that is so pervasive in math is unphysical in a very real sense. So what would math look like and how would theorems change if this finiteness were formalized? That's what various flavours of finitism aim to achieve.

So to get back to your question as to the nature of the naturals, it seems evident that yes, at some point, you literally can fail construct the natural number N+1 if you are given N, because you will run out of particles in the universe. What implications this will have for various theorems will be interesting for sure, but it isn't clear yet because finitism isn't given much funding.

Edit: however, it's clear that some very unintuitive results follow from the infinities embedded in mathematics, and that a finitist approach resolves some of them. For instance, the argument that "0.9999... = 1" is true in classical mathematics while this equality is arguably not true under strict finitism because "0.999..." does not exist, because infinite objects do not exist, and so it will never equal 1.

[1] See the section on continuous counting, https://www.researchgate.net/publication/288354797_A_Defense...

Re:The Axiom of Infinity by Ferrotin on Tuesday December 06, 2022 @11:22PM (#33890602)
Calling “0.999… = 1” very unintuitive is a very strange thing to say, because that makes perfect sense to most children. I’d like to see a result that truly is unintuitive, like what we get with the axiom of choice.
Re:The Axiom of Infinity by naasking on Wednesday December 07, 2022 @12:22AM (#33890890)
> Calling “0.999… = 1” very unintuitive is a very strange thing to say, because that makes perfect sense to most children.

Gotta call bullshit on that. First I don't think you have any robust empirical data on that question.

Second what's convincing to children that don't have enough knowledge of math to have formed any intuitions about it is not a compelling argument.

Re:The Axiom of Infinity by Ferrotin on Wednesday December 07, 2022 @12:31AM (#33890946)
I remember being a kid and having this discussion in elementary school. Kids have enough intuition to know that operations with fractions should get the same result as with decimal numbers. Or that 1-0.999… = 0.000…. Or that different lengths have a length in between them. All are legitimate and compelling arguments.
Re:The Axiom of Infinity by amelius on Wednesday December 07, 2022 @06:20AM (#33893118)
I think lots of students get lost with different orders of infinity (countable, uncountable, etc.), so I think there is definitely a point beyond which you can't push the intuition behind infinite objects.
Re:The Axiom of Infinity by naasking on Wednesday December 07, 2022 @10:11AM (#33895195)
> Or that different lengths have a length in between them. All are legitimate and compelling arguments.

Except that's wrong, not all lengths do have a length between them.

Re:The Axiom of Infinity by rfergie on Wednesday December 07, 2022 @06:09PM (#33901719)
Thank you for the link to the paper; very interesting!
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.