4 ms·

>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 incl

>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'?

foota 10y ago
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.
- Smaug123 10y ago
  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.
  - tnecniv 10y ago
    How do these finitists handle things like the real numbers? Do they just not consider questions that require the notion of infinity?
    - roywiggins 10y ago
      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-were-finite-how-could-the-real-numbers-be-defined https://math.stackexchange.com/questions/501/if-all-sets-wer...
      - Smaug123 10y ago
        This is correct: given a computation, you're allowed to execute it as far as you like. You're just not allowed to consider it "after executing infinitely many steps". So you're allowed to consider a real number expanded to n decimal places, for any n.
    - mcherm 10y ago
      In high-school calculus (if you've taken that), you apply things like "d/dx" which LOOKS like it is just a fraction, dividing "d" by "d times x". The notation was first dreamed up by mathematicians who were thinking "but if we keep making the d-slices really REALLY small we would move from the discrete approximation to the formula for the correct continuous answer". Unfortunately, while SOME such formulas worked (the ones you learned in calculus - stuff like the chain rule), other formulas generated using the same kind of reasoning ("just imagine that d becomes infinitely small") come up with answers that are nonsensical or just wrong. How can we know when it's OK to just say "let things get infinitely small" and when it gives bogus answers? The solution, which is taught in high-school calculus, was the "epsilon-delta" formulation. Instead of saying "let d become infinitely small" (a statement that may just be nonsense), say "I will prove that for ANY small epsilon (greater than 0) I can find a delta > 0 such that for values of x closer than delta, the error will be less than epsilon". That statement doesn't require an infinity to exist anywhere -- it is just a statement about particular finite numbers. And we can build calculus on such principles. This isn't an EXACT analogy to your question about real numbers, but it uses the same type of reasoning, and I'm hoping the analogy is in terms of mathematical reasoning you are already familiar with.
thaumasiotes 10y ago
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).
- sxyuan 10y ago
  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_five_subsystems_of_second_order_arithmetic https://en.wikipedia.org/wiki/Reverse_mathematics#The_big_fi...

foota 10y ago

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.

Smaug123 10y ago
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.
- tnecniv 10y ago
  How do these finitists handle things like the real numbers? Do they just not consider questions that require the notion of infinity?
  - roywiggins 10y ago
    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-were-finite-how-could-the-real-numbers-be-defined https://math.stackexchange.com/questions/501/if-all-sets-wer...
    - Smaug123 10y ago
      This is correct: given a computation, you're allowed to execute it as far as you like. You're just not allowed to consider it "after executing infinitely many steps". So you're allowed to consider a real number expanded to n decimal places, for any n.
  - mcherm 10y ago
    In high-school calculus (if you've taken that), you apply things like "d/dx" which LOOKS like it is just a fraction, dividing "d" by "d times x". The notation was first dreamed up by mathematicians who were thinking "but if we keep making the d-slices really REALLY small we would move from the discrete approximation to the formula for the correct continuous answer". Unfortunately, while SOME such formulas worked (the ones you learned in calculus - stuff like the chain rule), other formulas generated using the same kind of reasoning ("just imagine that d becomes infinitely small") come up with answers that are nonsensical or just wrong. How can we know when it's OK to just say "let things get infinitely small" and when it gives bogus answers? The solution, which is taught in high-school calculus, was the "epsilon-delta" formulation. Instead of saying "let d become infinitely small" (a statement that may just be nonsense), say "I will prove that for ANY small epsilon (greater than 0) I can find a delta > 0 such that for values of x closer than delta, the error will be less than epsilon". That statement doesn't require an infinity to exist anywhere -- it is just a statement about particular finite numbers. And we can build calculus on such principles. This isn't an EXACT analogy to your question about real numbers, but it uses the same type of reasoning, and I'm hoping the analogy is in terms of mathematical reasoning you are already familiar with.

thaumasiotes 10y ago

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).

sxyuan 10y ago
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_five_subsystems_of_second_order_arithmetic https://en.wikipedia.org/wiki/Reverse_mathematics#The_big_fi...