So if I get the gist of this correctly, this makes proofs that are applicable to finite sets/structures/objects easier to translate to a proof that's applicable to infinite sets?
Mathematicians Bridge Finite-Infinite Divide
21–30 of 63 posts
Re: Mathematicians Bridge Finite-Infinite Divide
#22> The boundary does not pass between some huge finite number and the next, infinitely large one. Rather, it separates two kinds of mathematical statements: “finitistic” ones, which can be proved without invoking the concept of infinity, and “infinitistic” ones, which rest on the assumption — not evident in nature — that infinite objects exist. Let Y = some ridiculously huge finite number. The notion that ∞ = Y + 1 ha…
You're not thinking about this properly. There are some facts about finite objects which simply cannot be proved without reasoning about infinite objects - for example, the well-definedness of the TREE function. These facts are true if you have access to infinite objects, but not necessarily if you don't. This paper shows that a certain class of statements about finite objects, which we knew were true by virtue of re…
I tried to give my reasons by using only appeals to objects of our common understanding. You have countered my claim by appealing to "the well-definedness of the TREE function". Do you expect me (and everyone else) to know what that is? In order for us to be able to follow your argument you would need to spell that out in a bit more detail.
If I'm not thinking about this properly, which of the assertions I made was incorrect? Where is the error in my reasoning? Is there an error in how I am conceiving things?
> This paper shows that a certain class of statements about finite objects
From what I can gather, it's not that simple. For a start, the initial set is the set of natural numbers. This is not finite. The procedure for generating/enumerating them is. The paper deals with pairs of inequalities based on the natural numbers and sub-sequences to be found therein. This set of pairs is also non-finite (but I'm happy with the assertion that in some sense it is a different order of infinity from the natural numbers). We are now trying to reason about the nature of the sequencing of these sub-sequences.
Are you saying that sometimes the sub-sequences are finite? If so, their complement would be infinite. And it is the partitioning that makes this so.
Re: Mathematicians Bridge Finite-Infinite Divide
#23[deleted]
Re: Mathematicians Bridge Finite-Infinite Divide
#24Earlier quoted context omitted.
You're not thinking about this properly. There are some facts about finite objects which simply cannot be proved without reasoning about infinite objects - for example, the well-definedness of the TREE function. These facts are true if you have access to infinite objects, but not necessarily if you don't. This paper shows that a certain class of statements about finite objects, which we knew were true by virtue of re…
I tried to give my reasons by using only appeals to objects of our common understanding. You have countered my claim by appealing to "the well-definedness of the TREE function". Do you expect me (and everyone else) to know what that is? In order for us to be able to follow your argument you would need to spell that out in a bit more detail. If I'm not thinking about this properly, which of the assertions I made was i…
Your understanding of the point of the theorem is very different to mine, and I'm moderately sure my understanding is pretty close to correct.
It is a fact of mathematics that there are some statements which are solely about finite objects, but to prove them requires reasoning about an infinite object. For a more accessible example than TREE, I think the Ackermann function falls into this category. The Ackermann function A(n+1, m+1) = A(n, A(n+1, m)) is well-defined for all n and m (we prove this by induction over NxN), but the proof relies on considering the lexicographic order on NxN which is inherently infinite. (I'm not totally certain that all proofs of Ackermann's well-definedness rely on an infinite object, but the only proof known to me does.) Ackermann's function itself is in some sense a "finite" object, but the proof of its well-definedness is in some sense "infinite". Whatever the status of my conjecture that "you can't prove that Ackermann's function is well-defined without considering an infinite object", it is certainly a fact that Ackermann is not primitive-recursive, and "primitive-recursive functions" corresponds to the lowest level of the five "mysterious levels" the article talks about.
So the analogy is as follows. Imagine that we knew of this "infinitary" proof that Ackermann is well-defined, but we hadn't proved that no "finitary" proof exists. (So finitists are not happy to use Ackermann, because it might not actually be well-defined according to them: any known proof requires dealing with an infinite object.) Now, this paper comes along and proves that actually a finitary proof exists. Suddenly the finitists are happy to use the Ackermann function.
The actual definition of TREE is a bit too long for me to explain here, but it is an example of a function like Ackermann, which is well-defined, but in fact if you're not allowed to consider infinite objects during the proof then it is provably impossible to prove that TREE is well-defined. So the statement "TREE is well-defined" is, in some sense, "less constructive" or "more infinitary" than R_2^2.
Re: Mathematicians Bridge Finite-Infinite Divide
#25I wrote a short note [1] to try and clear up some of the misconceptions in this thread. Feedback welcome; Hacker News thread for the short note at [2].
[1]: https://www.patrickstevens.co.uk/finitistic-reducibility/
Re: Mathematicians Bridge Finite-Infinite Divide
#26As a noob, I'm having a hard time grasping why the Ramsey pairing is interesting: If you pair up every member of an infinite set with every member of that same infinite set, of course you'll get an infinite subset for almost every predicate about a pairing, just by virtue of starting from an infinite superset. It seems like the theorem would be interesting if it said something about the "magnitude" of the subset, not…
It's not the infinity of the subset of Ramsey pairings that's the central point of interest in this proof. What is mainly interesting is that their proof can show this, using only finitistic methods. Their proof shows this without explicitly using any concepts of infinity, for example, without assuming an infinite superset.
Re: Mathematicians Bridge Finite-Infinite Divide
#27Great article, very well written and actually understandable without hunting down mathematical definitions. I think it is quite cool that people are still hunting down the various different incarnations of infinity and are able to prove deep results like this. On the other hand, I don't think that these questions are as essential as they are made out to be. How do we know that everything finite is on unshakable found…
But we can be more sure of things that are less shakeable. Additionally, these techniques sometimes give us more effective proofs: for example, if we know that A is true, that is less useful than knowing that A is true and that we can find a finite certificate of its truth. We can make computers verify finite certificates, for instance.
A useful distinction to have in mind is: I know that the number 91 must have prime factors, because I can prove that all numbers have prime factors. But that's much less useful than knowing that its prime factors are 7 and 13. Similarly, if I could prove A using infinitistic methods, that's in some sense "a bit less useful" than a proof which uses finitistic and/or constructive methods.
Re: Mathematicians Bridge Finite-Infinite Divide
#28The book Where Mathematics Comes From demonstrates that the concept of infinity itself is finitistically reducible via conceptual metaphor. This really isn't that surprising though, is it? Our experience is grounded in the interaction of concrete, finite objects.
Re: Mathematicians Bridge Finite-Infinite Divide
#29Great article, very well written and actually understandable without hunting down mathematical definitions. I think it is quite cool that people are still hunting down the various different incarnations of infinity and are able to prove deep results like this. On the other hand, I don't think that these questions are as essential as they are made out to be. How do we know that everything finite is on unshakable found…
But we can be more sure of things that are less shakeable. Additionally, these techniques sometimes give us more effective proofs: for example, if we know that A is true, that is less useful than knowing that A is true and that we can find a finite certificate of its truth . We can make computers verify finite certificates, for instance. A useful distinction to have in mind is: I know that the number 91 must have pri…
My point is that if you prove that 91 has as its prime factors 7 and 13, I don't care if you did that proof using infinite methods or not.
In general, I am only proving theorems that are useful to me, so "a bit less useful" doesn't apply to these situations. If I needed that "bit more usefulness", I would go ahead and prove it (if I could).
Your reasoning mostly only applies if you prove theorems for their own sake, and not because you already know what you want them for.
Re: Mathematicians Bridge Finite-Infinite Divide
#30Earlier quoted context omitted.
But we can be more sure of things that are less shakeable. Additionally, these techniques sometimes give us more effective proofs: for example, if we know that A is true, that is less useful than knowing that A is true and that we can find a finite certificate of its truth . We can make computers verify finite certificates, for instance. A useful distinction to have in mind is: I know that the number 91 must have pri…
My point is that if you prove that 91 has as its prime factors 7 and 13, I don't care if you did that proof using infinite methods or not. In general, I am only proving theorems that are useful to me, so "a bit less useful" doesn't apply to these situations. If I needed that "bit more usefulness", I would go ahead and prove it (if I could). Your reasoning mostly only applies if you prove theorems for their own sake,…
It's only an analogy. The analogy is meant to be "prove that 91 has prime factors" using infinitistic methods, and "prove that 91's prime factors are 7 and 13" using finitistic ones.