5 ms·

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

by scribu 10y ago

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.

n4r9 10y ago
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.
- SilasX 10y ago
  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?
  - NotAPerson 10y ago
    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.
    - SilasX 10y ago
      But it's not true for any coloring, e.g. "red if a and b < 20, blue otherwise".
      - NotAPerson 10y ago
        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).
- NotAPerson 10y ago
  > 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?
  - n4r9 10y ago
    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-blue-coloring-of-the-infinite-subsets-of-mathbbn-necessarily-giv 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".
get2zpointer 10y ago
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.

by scribu 10y ago

n4r9 10y ago

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.

SilasX 10y ago
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?
- NotAPerson 10y ago
  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.
  - SilasX 10y ago
    But it's not true for any coloring, e.g. "red if a and b < 20, blue otherwise".
    - NotAPerson 10y ago
      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).
NotAPerson 10y ago
> 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?
- n4r9 10y ago
  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-blue-coloring-of-the-infinite-subsets-of-mathbbn-necessarily-giv 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".

get2zpointer 10y ago

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.