Algebra Seminar talk
Choiceless Ramsey Theory for Linear Orders
Using an idea of Sierpiński one can show that the Axiom of Choice implies that every linear order admits a colouring of its pairs in black and white such that every descending sequence contains a black pair and every ascending sequence a white one. In 1971 Erdős, Milner and Rado showed that---again using the Axiom of Choice---every linear order admits a colouring of its triples in black and white such that every copy of the integers contains a black triple and every quadruple a white one.
It turns out that even without using the Axiom of Choice there are analogous (yet still weaker) results as long as there is an ordinal alpha such that the linear order considered is embeddable into the lexicographically ordered sequences of zeroes and ones of length alpha.
On the other hand some partition properties that have been shown to fail for all linear orders according to ZFC are derivable for the continuum in---for example---the system ZF + "All sets of reals have the property of Baire.". The following statement is an example:
"There is no colouring of quadruples in black and white such that
- every set of order-type $ \omega^* + \omega$ (the integers) contains a black quadruple and
- every set of order-type $\omega + \omega^*$ contains a black quadruple and
- every quintuple contains a white quadruple.
According to ZF the statement resulting from replacing "quintuple" by "septuple" fails for any linear order embeddable into a lexicographically ordered sequences of zeroes and ones.
The obvious question is hitherto unanswered.