5 ms·

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

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

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