7 ms·

Mathematicians Bridge Finite-Infinite Divide

157 points by lolptdr 9y ago

vanderZwan 9y ago
> The colorable, divisible infinite sets in RT22 are abstractions that have no analogue in the real world. And yet, Yokoyama and Patey’s proof shows that mathematicians are free to use this infinite apparatus to prove statements in finitistic mathematics — including the rules of numbers and arithmetic, which arguably underlie all the math that is required in science — without fear that the resulting theorems rest upon the logically shaky notion of infinity. That’s because all the finitistic consequences of RT22 are “true” with or without infinity; they are guaranteed to be provable in some other, purely finitistic way. RT22’s infinite structures “may make the proof easier to find,” explained Slaman, “but in the end you didn’t need them. You could give a kind of native proof — a [finitistic] proof.” I'm not a mathematician, but this sounds a lot like proof by induction VS proof by anything except induction.
- vanderZwan 9y ago
  Maybe I should have clarified. I recall being taught induction in my first year of physics, but the maths professor told us that it is generally frowned upon as a proof because it does not give any insight. So if there is a choice between two proofs, the other option is almost always more useful. This last sentence sounds a lot like that: > RT22’s infinite structures “may make the proof easier to find,” explained Slaman, “but in the end you didn’t need them. You could give a kind of native proof — a [finitistic] proof.”
xamuel 9y ago
A genuine breakthrough in the narrow realm of reverse mathematics. (The article exagerates that into a breakthrough in general, par for the course for science journalism.) Here's the actual paper: https://arxiv.org/pdf/1601.00050.pdf https://arxiv.org/pdf/1601.00050.pdf The quantamagazine article puts a lot of emphasis on the youth (34 and 27) of the researchers. I guess the journalist overlooked a more surprising age. Lu "Jiayi" Liu (whom the article briefly mentions for a preliminary result) was I think 20 years old when he made his discovery in 2012 which was a tentative step toward the stronger result in this article. I saw Liu give a talk and it was remarkable. It was in a conference where all the other speakers were very well-established logicians with many decades in the field, and then this Chinese undergrad who was probably the youngest person in the whole building... and all these well-established logicians were humbled by him.
- Sniffnoy 9y ago
  A note -- if you're linking to arXiv, it's better to link to the abstract (https://arxiv.org/abs/1601.00050 https://arxiv.org/abs/1601.00050) rather than directly to the PDF. From the abstract, one can easily click through to the PDF; not so the reverse. And the abstract allows one to do things like see different versions of the paper, search for other things by the same authors, etc. Thank you!
  - throwawayjava 9y ago
    > not so the reverse That big grey text on the right of each arxiv paper is actually a link you can click form the pdf. Took make like N->\inf years to figure that out... I used to complain about how heavy pdf docs are and therefore preferred websites that contained some metadata with a link to actual content, but websites these days... and at least the .pdf honestly downloads on anroid/iPhone, which are the only two platforms where I honestly care about bandwidth (and even then...)
lngnmn 9y ago
There is no such thing as Infinite outside your heads. This is actually a pattern - a false dichotomy with a pure abstraction produced as an abstract opposite or an abstract result of negation of some other concept or a named entity. Applied Hegelian nonsense if you wish. Infinity is a pure abstraction, like zero, but ill-defined (zero is an symbol for a concept of an empty slot, absence or nothing, while infinite is mere a negation of finite). Like many other concepts it might be useful, but usability does not imply existence.
- colordrops 9y ago
  An orthogonal issue is that most if not all humans have a hard time distinguishing which aspects (all of them?) of their reality are just abstractions.
- deleted 9y ago
  [deleted]
- umanwizard 9y ago
  How is "zero" more of an abstraction than "five" ?
  - gizmo686 9y ago
    Zero was invented long after the rest of the natural numbers (to my knowledge this is the case in every culture that independently invented zero). At least in the case of the Greeks, its status was somewhat controversial; I am not sure how other societies viewed it once it was invented.
    - johncolanduoni 9y ago
      If we find out some alien race started using positive numbers and zero at the same time, do they then become the same level of abstraction?
  - smhost 9y ago
    It would go something like: > Zero is offensive and ungodly. With "five", at least there's something there to abstract. With zero, there's not even anything! How can nothing be something? Cue angry biting of thumbs
nthcolumn 9y ago
Where is this divide? It is some concept I am unaware of?
- gfody 9y ago
  [the divide] 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.
  - johncolanduoni 9y ago
    The article stated this in a very silly way. Infinite objects existing in nature has nothing to do with whether reasoning about certain infinite objects (e.g. The real numbers) is sound, any more than thinking about counterfactuals is impossible because they differ from the real world.
    - gfody 9y ago
      further in she cites Aristotle potential vs. actual which I guess is more philosophy than math but it covers the point you're making now.
- danharaj 9y ago
  In principle a statement that involves only finite sets of natural numbers can be proved by exhaustive calculation. A statement involving infinity in an essential way cannot. This means there is a gap in certitude between finite and infinite mathematics. There's many ways to describe this divide. For example, an arithmetic statement involving unbounded quantifiers. You can measure how much such a statement fails to be finite by counting the alternation of universal and existential unbounded quantifiers. This is a measurement of the naive logical complexity of a statement. Godels incompleteness theorems can be seen as a statement about the gap between finite and infinite mathematics. Decidability, semidecidability and undecidability can be seen as the relationship between boundedly quantified arithmetic statements, statements with one unbounded existential quantifier, and statements with one unbounded universal quantifier. Another avenue of exploring the gap between finite and infinite mathematics is via linear logic. There the thesis is that contraction, the logical reuse of variables, is where infinity creeps into logical reasoning. Indeed logic without contraction is quite tame. Logic with unlimited contraction is wild. Surprisingly there are logics with an intermediate strength of contraction: so-called light linear logics. These can classify reasoning that embodies polynomial time computation or elementary time computation. So in another sense infinity can be measured by algorithmic complexity.
graycat 9y ago
Ah, foundations of math, start with applied math for making money, descend to applied math that doesn't make money, descend to pure math, descend to foundations, and, there, down in the dark basement try to make some sense. I've been there, done that, never made even 10 cents there! So, get to Zermelo-Fraenkel set theory, the axiom of choice, the work of Kurt Gödel and Paul Cohen (I still have the copy of Cohen's paper Max Zorn gave me!), etc. A friend worked in forcing arguments, Ramsey theory, etc. and never made even 10 cents there either. I climbed out of that dark basement and don't want to go back!
- fizixer 9y ago
  I'm on my way down but haven't seen the darkness yet :) Maybe because I didn't start out with money making in mind (not to say I don't want to make money. I do. I do.) Also how long did the whole process take for you? ... If you make up your mind in advance, as I have, that you're going to be in there for 10 years give or take, (in 8-hour days; so 20 calendar years if you spend 4 hours a day), and try to make a living on the side, does it still feel as dark?
  - graycat 9y ago
    One way and another, starting in my senior year in college, I spent a year or so in that dark basement. The most intense time was in a course in axiomatic set theory in an NSF summer math program at Vanderbilt. The next fall, I was in a course in real analysis, and the prof started with foundations. After the first test he wanted to "see me". The exercises on the test were all trivial except one, and I got it only in the last minute or so so wrote quickly. I used little omega for the ordinal of the natural numbers without defining it. I told him that from the course I'd taken the previous summer I thought that that was standard notation. Apparently he didn't know that. After my explanation, he saw that my solution was correct and one step shorter than his. Then I asked him what he wanted to "see me" about, and he said "Now, nothing.". Gads. I got my Ph.D. later from a better program at another university. Occasionally later I touched on that material. That was all. No way did I spend or want to spend 10 years in that basement. And no way did I want to do original research with that material. Some of the pure math I studied I liked and still like a lot, and some of it is a crucial pillar of the crucial applied math core of my startup.
hzhou321 9y ago
The paper is too abstract for me but it seems to mean that we don't really need the concept of infinity (for theorems in finite domain). I like that.
robinhouston 9y ago
The previous discussion of this article was interesting too: https://news.ycombinator.com/item?id=11763080 https://news.ycombinator.com/item?id=11763080
gweinberg 9y ago
I took a course in combinatorics as an undergrad, so I know what Ramsey's theorem is. But our professor didn't go over the proof of Ramsey's theorem, our professor said he couldn't expect us to understand the proof because he didn't understand it himself. I might have gotten more out the article if there was some explanation as to what a "finitistic" proof is, and how it differs from the "infinitistc" proof. Maybe the concept is too complicated to explain in a short article.
snissn 9y ago
Good.

157 points by lolptdr 9y ago

> The colorable, divisible infinite sets in RT22 are abstractions that have no analogue in the real world. And yet, Yokoyama and Patey’s proof shows that mathematicians are free to use this infinite apparatus to prove statements in finitistic mathematics — including the rules of numbers and arithmetic, which arguably underlie all the math that is required in science — without fear that the resulting theorems rest upon the logically shaky notion of infinity. That’s because all the finitistic consequences of RT22 are “true” with or without infinity; they are guaranteed to be provable in some other, purely finitistic way. RT22’s infinite structures “may make the proof easier to find,” explained Slaman, “but in the end you didn’t need them. You could give a kind of native proof — a [finitistic] proof.” I'm not a mathematician, but this sounds a lot like proof by induction VS proof by anything except induction.

vanderZwan 9y ago
Maybe I should have clarified. I recall being taught induction in my first year of physics, but the maths professor told us that it is generally frowned upon as a proof because it does not give any insight. So if there is a choice between two proofs, the other option is almost always more useful. This last sentence sounds a lot like that: > RT22’s infinite structures “may make the proof easier to find,” explained Slaman, “but in the end you didn’t need them. You could give a kind of native proof — a [finitistic] proof.”

xamuel 9y ago

A genuine breakthrough in the narrow realm of reverse mathematics. (The article exagerates that into a breakthrough in general, par for the course for science journalism.) Here's the actual paper: https://arxiv.org/pdf/1601.00050.pdf https://arxiv.org/pdf/1601.00050.pdf The quantamagazine article puts a lot of emphasis on the youth (34 and 27) of the researchers. I guess the journalist overlooked a more surprising age. Lu "Jiayi" Liu (whom the article briefly mentions for a preliminary result) was I think 20 years old when he made his discovery in 2012 which was a tentative step toward the stronger result in this article. I saw Liu give a talk and it was remarkable. It was in a conference where all the other speakers were very well-established logicians with many decades in the field, and then this Chinese undergrad who was probably the youngest person in the whole building... and all these well-established logicians were humbled by him.

Sniffnoy 9y ago
A note -- if you're linking to arXiv, it's better to link to the abstract (https://arxiv.org/abs/1601.00050 https://arxiv.org/abs/1601.00050) rather than directly to the PDF. From the abstract, one can easily click through to the PDF; not so the reverse. And the abstract allows one to do things like see different versions of the paper, search for other things by the same authors, etc. Thank you!
- throwawayjava 9y ago
  > not so the reverse That big grey text on the right of each arxiv paper is actually a link you can click form the pdf. Took make like N->\inf years to figure that out... I used to complain about how heavy pdf docs are and therefore preferred websites that contained some metadata with a link to actual content, but websites these days... and at least the .pdf honestly downloads on anroid/iPhone, which are the only two platforms where I honestly care about bandwidth (and even then...)

lngnmn 9y ago

There is no such thing as Infinite outside your heads. This is actually a pattern - a false dichotomy with a pure abstraction produced as an abstract opposite or an abstract result of negation of some other concept or a named entity. Applied Hegelian nonsense if you wish. Infinity is a pure abstraction, like zero, but ill-defined (zero is an symbol for a concept of an empty slot, absence or nothing, while infinite is mere a negation of finite). Like many other concepts it might be useful, but usability does not imply existence.

colordrops 9y ago
An orthogonal issue is that most if not all humans have a hard time distinguishing which aspects (all of them?) of their reality are just abstractions.
deleted 9y ago
[deleted]
umanwizard 9y ago
How is "zero" more of an abstraction than "five" ?
- gizmo686 9y ago
  Zero was invented long after the rest of the natural numbers (to my knowledge this is the case in every culture that independently invented zero). At least in the case of the Greeks, its status was somewhat controversial; I am not sure how other societies viewed it once it was invented.
  - johncolanduoni 9y ago
    If we find out some alien race started using positive numbers and zero at the same time, do they then become the same level of abstraction?
- smhost 9y ago
  It would go something like: > Zero is offensive and ungodly. With "five", at least there's something there to abstract. With zero, there's not even anything! How can nothing be something? Cue angry biting of thumbs

nthcolumn 9y ago

Where is this divide? It is some concept I am unaware of?

gfody 9y ago
[the divide] 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.
- johncolanduoni 9y ago
  The article stated this in a very silly way. Infinite objects existing in nature has nothing to do with whether reasoning about certain infinite objects (e.g. The real numbers) is sound, any more than thinking about counterfactuals is impossible because they differ from the real world.
  - gfody 9y ago
    further in she cites Aristotle potential vs. actual which I guess is more philosophy than math but it covers the point you're making now.
danharaj 9y ago
In principle a statement that involves only finite sets of natural numbers can be proved by exhaustive calculation. A statement involving infinity in an essential way cannot. This means there is a gap in certitude between finite and infinite mathematics. There's many ways to describe this divide. For example, an arithmetic statement involving unbounded quantifiers. You can measure how much such a statement fails to be finite by counting the alternation of universal and existential unbounded quantifiers. This is a measurement of the naive logical complexity of a statement. Godels incompleteness theorems can be seen as a statement about the gap between finite and infinite mathematics. Decidability, semidecidability and undecidability can be seen as the relationship between boundedly quantified arithmetic statements, statements with one unbounded existential quantifier, and statements with one unbounded universal quantifier. Another avenue of exploring the gap between finite and infinite mathematics is via linear logic. There the thesis is that contraction, the logical reuse of variables, is where infinity creeps into logical reasoning. Indeed logic without contraction is quite tame. Logic with unlimited contraction is wild. Surprisingly there are logics with an intermediate strength of contraction: so-called light linear logics. These can classify reasoning that embodies polynomial time computation or elementary time computation. So in another sense infinity can be measured by algorithmic complexity.

graycat 9y ago

Ah, foundations of math, start with applied math for making money, descend to applied math that doesn't make money, descend to pure math, descend to foundations, and, there, down in the dark basement try to make some sense. I've been there, done that, never made even 10 cents there! So, get to Zermelo-Fraenkel set theory, the axiom of choice, the work of Kurt Gödel and Paul Cohen (I still have the copy of Cohen's paper Max Zorn gave me!), etc. A friend worked in forcing arguments, Ramsey theory, etc. and never made even 10 cents there either. I climbed out of that dark basement and don't want to go back!

fizixer 9y ago
I'm on my way down but haven't seen the darkness yet :) Maybe because I didn't start out with money making in mind (not to say I don't want to make money. I do. I do.) Also how long did the whole process take for you? ... If you make up your mind in advance, as I have, that you're going to be in there for 10 years give or take, (in 8-hour days; so 20 calendar years if you spend 4 hours a day), and try to make a living on the side, does it still feel as dark?
- graycat 9y ago
  One way and another, starting in my senior year in college, I spent a year or so in that dark basement. The most intense time was in a course in axiomatic set theory in an NSF summer math program at Vanderbilt. The next fall, I was in a course in real analysis, and the prof started with foundations. After the first test he wanted to "see me". The exercises on the test were all trivial except one, and I got it only in the last minute or so so wrote quickly. I used little omega for the ordinal of the natural numbers without defining it. I told him that from the course I'd taken the previous summer I thought that that was standard notation. Apparently he didn't know that. After my explanation, he saw that my solution was correct and one step shorter than his. Then I asked him what he wanted to "see me" about, and he said "Now, nothing.". Gads. I got my Ph.D. later from a better program at another university. Occasionally later I touched on that material. That was all. No way did I spend or want to spend 10 years in that basement. And no way did I want to do original research with that material. Some of the pure math I studied I liked and still like a lot, and some of it is a crucial pillar of the crucial applied math core of my startup.

hzhou321 9y ago

The paper is too abstract for me but it seems to mean that we don't really need the concept of infinity (for theorems in finite domain). I like that.

robinhouston 9y ago

The previous discussion of this article was interesting too: https://news.ycombinator.com/item?id=11763080 https://news.ycombinator.com/item?id=11763080

gweinberg 9y ago

I took a course in combinatorics as an undergrad, so I know what Ramsey's theorem is. But our professor didn't go over the proof of Ramsey's theorem, our professor said he couldn't expect us to understand the proof because he didn't understand it himself. I might have gotten more out the article if there was some explanation as to what a "finitistic" proof is, and how it differs from the "infinitistc" proof. Maybe the concept is too complicated to explain in a short article.

snissn 9y ago

Good.