Live data from Hacker News

Mathematicians Bridge Finite-Infinite Divide

quantamagazine.org

51–60 of 63 posts

Re: Mathematicians Bridge Finite-Infinite Divide

#51
post #19

Earlier quoted context omitted.

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…

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

Because there doesn't have to be another pair that satisfies that relation. Counterexamples are trivial:

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.

Re: Mathematicians Bridge Finite-Infinite Divide

#52
post #49
post #20

Earlier quoted context omitted.

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…

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 s…

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.

Re: Mathematicians Bridge Finite-Infinite Divide

#53
post #49

Earlier quoted context omitted.

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 s…

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 fi…

But it's not true for any coloring, e.g. "red if a and b < 20, blue otherwise".

Re: Mathematicians Bridge Finite-Infinite Divide

#54
post #20
post #18

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…

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…

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

Could you elaborate on this?

Re: Mathematicians Bridge Finite-Infinite Divide

#55
post #53

Earlier quoted context omitted.

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 fi…

But it's not true for any coloring, e.g. "red if a and b < 20, blue otherwise".

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

Re: Mathematicians Bridge Finite-Infinite Divide

#57
post #20

Earlier quoted context omitted.

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…

> 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. Could you elaborate on this?

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

Re: Mathematicians Bridge Finite-Infinite Divide

#58
post #9
post #6

Earlier 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'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.

Re: Mathematicians Bridge Finite-Infinite Divide

#59
post #9

Earlier quoted context omitted.

How do these finitists handle things like the real numbers? Do they just not consider questions that require the notion of infinity?

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 deb…

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

Re: Mathematicians Bridge Finite-Infinite Divide

#60
post #51

Earlier quoted context omitted.

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

Because there doesn't have to be another pair that satisfies that relation. Counterexamples are trivial: 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.

Then I misunderstood the article when it said

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

Post reply on HN