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