Mathematicians Bridge Finite-Infinite Divide
quantamagazine.org
Mathematicians Bridge Finite-Infinite Divide
1–10 of 63 posts
Re: Mathematicians Bridge Finite-Infinite Divide
#2Related (a bit of Cantor and Hilbert, no direct relation to Ramsey’s theorem):
"How To Count Past Infinity" https://www.youtube.com/watch?v=SrU9YDoXE88
Re: Mathematicians Bridge Finite-Infinite Divide
#3>Whereas almost all theorems can be shown to be equivalent to one of a handful of major systems of logic — sets of starting assumptions that may or may not include infinity, and which span the finite-infinite divide — RT22 falls between these lines.
Could anyone explain this statement? I feel like it's key for understanding the rest! How exactly does RT22 fall between 'these lines'?
Re: Mathematicians Bridge Finite-Infinite Divide
#4>Whereas almost all theorems can be shown to be equivalent to one of a handful of major systems of logic — sets of starting assumptions that may or may not include infinity, and which span the finite-infinite divide — RT22 falls between these lines. Could anyone explain this statement? I feel like it's key for understanding the rest! How exactly does RT22 fall between 'these lines'?
I'm not entirely sure that I'm hitting the pin on the head with this, but it seems that it is saying that RT_2^2 is inherently an infinite concept but can be proven under a set of axioms that do not require acknowledging that infinite things exist? Ie, that the case for finite things implies the case for infinite things. And that this can then be used to say construct the natural numbers.
Re: Mathematicians Bridge Finite-Infinite Divide
#5>Whereas almost all theorems can be shown to be equivalent to one of a handful of major systems of logic — sets of starting assumptions that may or may not include infinity, and which span the finite-infinite divide — RT22 falls between these lines. Could anyone explain this statement? I feel like it's key for understanding the rest! How exactly does RT22 fall between 'these lines'?
From later in the article:
> Almost all of the thousands of theorems studied by Simpson and his followers over the past four decades have turned out (somewhat mysteriously) to be reducible to one of five systems of logic spanning both sides of the finite-infinite divide. For instance, Ramsey’s theorem for triples (and all ordered sets with more than three elements) was shown in 1972 to belong at the third level up in the hierarchy, which is infinitistic.
> A breakthrough came in 1995, when the British logician David Seetapun, working with Slaman at Berkeley, proved that RT^2_2 is logically weaker than RT^3_2 and thus below the third level in the hierarchy.
> “Since then, many seminal papers regarding RT^2_2 have been published,” said Weiermann — most importantly, a 2012 result by Jiayi Liu (paired with a result by Carl Jockusch from the 1960s) showed that RT^2_2 cannot prove, nor be proved by, the logical system located at the second level in the hierarchy, one rung below RT^3_2.
So: there are five nested axiomatic systems that have been in common use to classify how much a theorem relies on infinite concepts. RT^2_2 is weaker than the third of those, and hard-to-compare with the second of them. (The second system can't prove it, but it also can't prove the second system.)
The new result says that RT^2_2 is reducible to primitive recursive arithmetic, which should mean that PRA is capable of proving anything RT^2_2 can prove. The article mentions that Mysterious Classification Level 2 is also reducible to primitive recursive arithmetic, so, as far as I understand things, PRA was already a system that fell "between the lines" of the five Mysterious Classification Levels (since Mysterious Level 3 is infinitistic and PRA is not).
Re: Mathematicians Bridge Finite-Infinite Divide
#6>Whereas almost all theorems can be shown to be equivalent to one of a handful of major systems of logic — sets of starting assumptions that may or may not include infinity, and which span the finite-infinite divide — RT22 falls between these lines. Could anyone explain this statement? I feel like it's key for understanding the rest! How exactly does RT22 fall between 'these lines'?
I'm not entirely sure that I'm hitting the pin on the head with this, but it seems that it is saying that RT_2^2 is inherently an infinite concept but can be proven under a set of axioms that do not require acknowledging that infinite things exist? Ie, that the case for finite things implies the case for infinite things. And that this can then be used to say construct the natural numbers.
Not quite, I think, although I haven't read the original paper.
There are some mathematicians who doubt that there is an infinite object (we call such mathematicians "finitist"). For such mathematicians, there is a large chunk of the mathematical literature they just can't use, because it relies inherently on the existence of an infinite set. Ramsey's theorem for pairs looks like it relies on the existence of an infinite set; the surprising result described in this article is that while RT_2^2 talks about infinite objects, its proof doesn't actually rely on them. So finitists are free to use it.
Even more, according to that article, the introduction of R_2^2 into a proof apparently doesn't break the property that "there is an algorithm to compute the construction the proof is doing". Previously it was thought that introducing R_2^2 to an otherwise "computable" proof (that is, one which carries out some computable operation) might stop it from being computable (that is, would make it so that no computer program corresponded to what the proof was doing: basically making it less constructive). It is now known that that is not the case.
Re: Mathematicians Bridge Finite-Infinite Divide
#7>Whereas almost all theorems can be shown to be equivalent to one of a handful of major systems of logic — sets of starting assumptions that may or may not include infinity, and which span the finite-infinite divide — RT22 falls between these lines. Could anyone explain this statement? I feel like it's key for understanding the rest! How exactly does RT22 fall between 'these lines'?
From later in the article: > Almost all of the thousands of theorems studied by Simpson and his followers over the past four decades have turned out (somewhat mysteriously) to be reducible to one of five systems of logic spanning both sides of the finite-infinite divide. For instance, Ramsey’s theorem for triples (and all ordered sets with more than three elements) was shown in 1972 to belong at the third level up in…
In case you're curious, the five systems in the article are mentioned by the original paper, and correspond to the ones described here: https://en.wikipedia.org/wiki/Reverse_mathematics#The_big_fi...
Re: Mathematicians Bridge Finite-Infinite Divide
#8I love the fact there's a long popular article devoted to the proof “that RT^2_2 is Π^0_3 conservative over IΣ^0_1”, as the abstract of the paper summarises it. Reverse mathematics is a fairly niche area even within mathematical logic. Kudos to Natalie Wolchover for taking it on.
Re: Mathematicians Bridge Finite-Infinite Divide
#9Earlier quoted context omitted.
I'm not entirely sure that I'm hitting the pin on the head with this, but it seems that it is saying that RT_2^2 is inherently an infinite concept but can be proven under a set of axioms that do not require acknowledging that infinite things exist? Ie, that the case for finite things implies the case for infinite things. And that this can then be used to say construct the natural numbers.
Not quite, I think, although I haven't read the original paper. There are some mathematicians who doubt that there is an infinite object (we call such mathematicians "finitist"). For such mathematicians, there is a large chunk of the mathematical literature they just can't use, because it relies inherently on the existence of an infinite set. Ramsey's theorem for pairs looks like it relies on the existence of an infi…
How do these finitists handle things like the real numbers? Do they just not consider questions that require the notion of infinity?
Re: Mathematicians Bridge Finite-Infinite Divide
#10Earlier quoted context omitted.
Not quite, I think, although I haven't read the original paper. There are some mathematicians who doubt that there is an infinite object (we call such mathematicians "finitist"). For such mathematicians, there is a large chunk of the mathematical literature they just can't use, because it relies inherently on the existence of an infinite set. Ramsey's theorem for pairs looks like it relies on the existence of an infi…
How do these finitists handle things like the real numbers? Do they just not consider questions that require the notion of infinity?
I gave it a google, and per Math StackOverflow:
> One can make statements about π or any other explicitly defined real number, as theorems about a specific sequence of rational approximations
https://math.stackexchange.com/questions/501/if-all-sets-wer...