Mathematicians Bridge Finite-Infinite Divide
quantamagazine.org
quantamagazine.org
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.
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.
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.
"How To Count Past Infinity" https://www.youtube.com/watch?v=SrU9YDoXE88
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 ;-)
[1]: https://www.patrickstevens.co.uk/finitistic-reducibility/
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).
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.
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.
Because it's not an axiom? I feel like I'm not understanding your question completely
Color the pair blue if its elements are 1 and 0. Color the pair red otherwise.
Color the triplet blue if its elements are 1, -1, and 0. Color the triplet red otherwise.
> 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?
> 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...
You may enjoy "Meta Math" by Gregory Chaitin (jump to Chapter 5 for the impatient):
http://arxiv.org/abs/math/0404335
"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:
"Set Theory: Should You Believe?"
web.maths.unsw.edu.au/~norman/papers/SetTheory.pdf
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.
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".
It seems like the theorem would be interesting if it said something about the "magnitude" of the subset, not just that it's infinite.
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.
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?
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.
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).
Could you elaborate on this?
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".
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.
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.
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.
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.
[ * *] https://youtu.be/LJR24_Povzw
"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."
Either way, glad it exists!
Simons Foundations --> James Simons, who is a hedge fund mananger worth ~ $14billion.
Excellent interview with Numberphile here:
[0] http://www.bloomberg.com/news/articles/2011-11-01/harvard-gr...