The shift graph and the Ramsey degree of ℕ ω

Abstract

We address several questions related to the Ramsey degree of the class of infinite structures isomorphic to the positive integers with the usual ordering. In particular we study the strength of stating that this class has finite Ramsey degree in the absence of the axiom of choice. We show that if the shift graph has finite chromatic number then this class has infinite Ramsey degree.