Here is a little anecdote: I met Ludovic Patey at the École normale supérieure that we both entered in 2009. Among our classmates, Ludovic was easily the best programmer and mastered a lot of different technologies (from advanced web stuff down to assembly languages), so we were all quite surprised when he chose to turn to pure mathematics… But then during his PhD he has been immensely successful (invited as keynote speaker to conferences, praised by peers, and an impressive list of journal publications). A few weeks ago, he has been ranked first in the CNRS 2016 recruitment competition, which is internationally competitive. When that competition started he hadn't even graduated from his PhD yet! Which means he (deservedly) bypassed the cumbersome post-doc phase by which virtually all young researchers must go through these days. This time, none of us were surprised :) !
Great 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 foundations? Doesn't even thinking about what that statement means involve reasoning about infinities? Let's just accept that nothing ever is really unshakable and let's use the tools that will get the job at hand done.
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.
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.
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.
I think you're on to something here. We often assume a playing field of finite, seperate, individual objects interacting with other finite, seperate, individual objects, but I feel this is more a relic of how our brains break down reality than what reality actually is.
How do people produce videos like that? It must be very expensive: shooting, pictures, music, all these animations, montage. It can't be done a hobbyist?
Vsauce is a hobbyist. As he got more popular and ad revenue came in, he could afford better cameras, mics, and props. Hes actually the most successful of the VsauceX (X=1,2,3,4) channels but still keeps them as a network because they are all friends. Honestly, YouTubing like anything else, takes effort more than anything. Some of the most successful channels used a smartphone camera for well past a million subscribers. And part of the rub is that there are a ton of good channels with very little success. Good art and entertainment is borne out of desire to share, not desire to bear. At least in my opinion. Because there will always be garbage to cater to garbage.
I should mention, most of the editing can be easily done in After Effects with a couple weeks of training. Its really amazing how accessible having your own syndication is these days. I am not interesting enough or entertaining enough so I leave it to those who are. Sticking to HN threads so I can hide my ugly mug ;-)
I 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].
>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'?
> 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).
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.
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.
Question: Isn't there an axiom that says "for any real number, there's always a bigger number"? What stopped Patey and Yokoyama from proving Ramsey's Theorem For Pairs/Triples by saying "for any pair which satisfies some relation X, there exists another pair which also satisfies relation X"?
> What stopped Patey and Yokoyama from proving Ramsey's Theorem For Pairs/Triples by saying "for any pair which satisfies some relation X, there exists another pair which also satisfies relation X"?
Because it's not an axiom? I feel like I'm not understanding your question completely
> When this is done, RT22 states that there will exist an infinite monochromatic subset: a set consisting of infinitely many numbers, such that all the pairs they make with all other numbers are the same color.
I read this as saying "There exists and infinite number of x's which satisfy the relation f(x, y) = blue for all values of y over some arbitrary function f()". What am I missing?
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.
"Finally, and perhaps even more devastatingly, it turns out that the set of all reals that can be individually named or specified or even defined or referred to—constructively or not—within a formal language or within an individual FAS, has probability zero. Summary: reals are unnameable with probability one.
So the set of real numbers, while natural—indeed, immediately given—geometrically, nevertheless remains quite elusive:
Why should I believe in a real number if I can’t calculate it, if I can’t prove what its bits are, and if I can’t even refer to it? And each of these things happens with probability one!"
You might also want to take a look at some of Norman Wildbergers work, like:
I'll try to summarize my finitist position, which I seem stuck with despite years of trying to accept the mainstream / Cantorian view. One criticism is that the mainstream treatment of infinity is more invented, and less grounded in nature, relative to other areas of math. Another is that it is rife with equivocation, especially between the notion of infinity, and the notions of number and quantity.
It's commonly debated whether math is discovered, or invented. I think it depends on which part of math you're talking about. I think 1 + 1 = 2 is way over on the "discovered" end of the spectrum. It's very strongly grounded in nature, reality, everyday experience, etc. The mainstream treatment of infinity, including infinite sets, "different sized" infinities, bijections, etc., rely more on definitions and consensus about what passes as an acceptable "proof". For example, the tangent function is cited as a mapping between [-pi/2, pi/2] and [-inf, +inf], which is supposed to show that a subset of the reals is the same "size" as the whole set. But this requires defining division by zero as infinity in this context, whereas that's commonly considered undefined. I also have a big argument with the use of bijections (mappings) to compare the supposed "sizes" of infinities, but I can't fit it in a comment. The summary is that I think the ideas of cardinality and infinity are inherently contradictory, and putting them together creates nonsense. The idea of different sized infinities is actually created by (rather than proved by) the conventional restrictions on the style of bijections / mappings that are proposed and considered. But that's just another way of saying I think this area of math is a lot more on the "invented by definitions" end of the spectrum, and that whole philosophical question is another area on which people are going to differ in their attitudes.
On equivocation: Infinity is neither a number nor a quantity. It's not a number, because you can't get there by counting. It's not a quantity, because it can't be measured. But in the mainstream treatment of infinity, all the common intuitions about number and quantity get mixed in, for example the idea of different sized infinities. Infinity means "in this place where a number belongs, the value is unlimited". It's not itself an unlimited number, because as soon as it becomes unlimited, it no longer refers to any number. Similarly, I believe a more reasonable treatment of sets would say that "infinite" and "set" are incompatible, and attempting to force the concept of infiniteness onto a set makes it no longer a set, but rather something else like an abstract category. I think it was a mistake to generalize sets to include infinite sets.
As to how I treat infinity, it simply means something is boundless, inexhaustible, unlimited. I have no problem saying there are infinite reals, while minding that "infinity" is not a "count" of the reals. There are also infinite natural numbers. It doesn't make any sense to say there are more reals than naturals, in spite of "bijection theory". Reals, integers, natural numbers, etc. can all be considered different ways of naming items plucked from an infinite bag. When laid on a number line, reals and integers acquire one difference - integers can be adjacent, and reals can't.
One last note: I'm fully aware that my whole argument can be easily refuted by saying that math is made of definitions. That's fine. My position is simply that when people say things like "Hey, did you know there are actually different sized infinities? Isn't that cool?" they should be mindful that they're talking about a convention within a theory based on conventions, and not a natural or logical fact.
> Infinity is neither a number nor a quantity. It's not a number, because you can't get there by counting.
That's an oddly narrow implied definition of "number" which, as well as infinity, would exclude everything other than the natural numbers. Maybe it extends to the integers, if you use an unusually generous definition of "counting". But it certainly excludes non-integral rationals, and, a fortiori, all irrationals from the set of "numbers".
Maybe "count" is too restrictive depending on how you think of counting. Substitute "reached" or "located" if you like. As another comment here says (paraphrasing) if a real can't be named, is it even a thing? I'd say any real that can be named can be "counted to" from another real that's arbitrarily close to it. If that's still too restrictive, then for any real that can be named, I can point to a segment of the number line and say "It's roughly, round about... there." Can't do that for infinity, again, because it's not a number.
As 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 just that it's infinite.
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.
It's hard to know what you're finding uninteresting/confusing from your description. Perhaps it would help to note that every possible pairing is given a colour, and in your infinite subset every possible pairing within that subset has the same colour. To me this is quite counter-intuitive.
There is a somewhat enlightening comparison to be made between Ramsey on pairs and the result that every real sequence x_n has a monotonic subsequence. You get this result as a corollary by colouring a pair of natural numbers a<b red if x_a <= x_b and blue otherwise.
Interestingly, the Ramsey theorem can be extended to three, four or any number of colours. I believe you can use this to show that any real sequence has either a convex or concave subsequence, but I'll omit the details :p
There's also a delicate balance between the infinite and finite going on. Clearly, with an infinite number of colours you could get a colouring without a monochromatic subset. More surprisingly perhaps, if you colour the infinite subsets of the natural numbers red or blue, then there exist colourings for which there is no monochromatic subset.
I have the same confusion as the GP, so let me try to ask a clarifying question:
Is the challenge to partition the pairs (of natural numbers) such that both partitions are infinite and monochromatic? Is that the hard thing that was proved here?
If so, how about "color red if a = b-1, blue otherwise"? Then the infinite subset (0, 1), (1, 2), (2, 3), ... is monochromatic.
What criterion did my partition there fail to satisfy?
The hard part is to show that for any coloring, there's some infinite subset without relying on "well, we can just pick one for each of these infinitely many numbers".
I'm pretty sure that the challenge is to prove that you can for any coloring construct a finitely defined rule for picking the members of the subset which is guaranteed to give you a monochromatic subset.
The question is more about if you can always find such a (finite) rule to partition the set, rather than if you can in a few easily constructed examples.
Wouldn't the subset {(a, b) | a,b > 20} be monochromatic?
Ed:
Perhaps I phrased it poorly, but I think the point was to show that you can always construct a predicate, P over a and b, such that P(a, b) is finitely defined (such as "a > 20 and b > 20"), but {(a, b) | P(a, b) is true} is infinite and monochromatic.
Instead of having some cases of colorings where your only option is to construct things of the form "(a = 5 and b = 17) or (a = 3 and b = 47) or ..." where you just list out every pair that matches (in an infinite subset).
> More surprisingly perhaps, if you colour the infinite subsets of the natural numbers red or blue, then there exist colourings for which there is no monochromatic subset.
Yes, a little, although it's on the fringes of my knowledge on the subject. Suppose, instead of colouring all the pairs of natural numbers like {2,3} or {100, 1056}, you colour all the infinite sets of natural numbers like the set of all odd numbers {1, 3, 5, ...} or the set of powers of two {2, 4, 8, ... }. Every possible infinite set must be coloured either red or blue.
Now, if the Ramsey theorem were to extend to this scenario, then for every possible red/blue colouring there would be some (necessarily infinite) subset A of natural numbers which is "monochromatic", i.e. every infinite subset of A receives the same colour. However, this isn't the case. It's possible to show there exists a very clever colouring which excludes the possibility of having an infinite monochromatic subset. I've only seen proofs of this which use the axiom of choice and are not constructive (although I don't know if this is always necessarily so), but the top reply to this question is one of the nicer proofs: http://math.stackexchange.com/questions/282827/does-a-red-bl...
This is surprising partly because if you take an arbitrarily large number n and colour all sets of natural numbers with cardinality n, then you will still get an infinite monochromatic subset.
Edit: the second response in the above link argues that the Axiom of Choice is a necessary assumption in the proof. This is probably one of those unsatisfying results which says "we know this thing exists, but we also know that we'll never be able to construct or define it explicitly".
> 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 has to be one of the most insidious defects in reasoning. Even to acknowledge the defect by dismissing it is almost like saying things could have turned out that way when they _never_ could.
Finite means limited or bounded or quantifiable. Infinite means unlimited or unbounded or unquantifiable. They are two wholly separate classes of things. Another way to say this is discrete versus continuous (in nature).
Imagine I said that I could bridge the coloured/non-coloured divide. What could I possibly mean by that. It would mean that I have found a way to talk about both coloured things and non-coloured things that applies to both class of things.
Put another way. Imagine I separate coloured things into green ones and not green ones. Both subclasses belong to the class of coloured things. What class then do the subclasses of finite things and non-finite things belong to? Negation constructs the distinction, negation _is_ the bridge in a way and all the could be said of both subclasses of things is that they are both things. (Which, to be clear, is not saying very much at all, is it?) If those things are numbers then all we are saying is that both things are numbers, if both things are procedures then all we are saying is that both things are procedures. And so on.
If I'm thinking about this properly then the paper is trying to more precisely define the term "countably". That's as most as it can do. To say otherwise is not just vastly overstating what the paper is about but outright misleading.
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 reasoning about a certain infinite object, in fact remain true if you're restricted only to reasoning about finite objects.
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.
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.
The 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.
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?
I'm having trouble imagining what finitism actually is, based on what I remember from set theory. Is it equivalent to Zermelo-Frankel set theory without the axiom of infinity?
"The main idea of finitistic mathematics is not accepting the existence of infinite objects such as infinite sets. While all natural numbers are accepted as existing, the set of all natural numbers is not considered to exist as a mathematical object. Therefore quantification over infinite domains is not considered meaningful."
I 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.
It makes me curious how Quanta is funded. The journal is very high quality and in a niche market: pure science journalism. I can't imagine they make enough subscription revenue; maybe it's funded mostly through the Simons Foundation?
In addition, James Simons was a mathematician prior to his work in the finance industry, hence his partiality toward funding a magazine that often writes about pure mathematics.
To be fair, he was a successful researcher who became professor and later chair of the Mathematics department at Stony Brook before starting Renaissance, so he got past all that the normal way.
