Every analytic set is Ramsey

Abstract

If X is a set, [ Χ ] ω will denote the set of countably infinite subsets of X . ω is the set of natural numbers. If S is a subset of [ ω ] ω , we shall say that S is Ramsey if there is some infinite subset X of ω such that either [ Χ ] ω ⊆ S or [ Χ ] ω ∩ S = 0. Dana Scott (unpublished) has asked which sets, in terms of logical complexity, are Ramsey. The principal theorem of this paper is: Every Σ 1 1 (i.e., analytic) subset of [ ω ] ω is Ramsey (for the Σ, Π notations, see Addison [1]). This improves a result of Galvin-Prikry [2] to the effect that every Borel set is Ramsey. Our theorem is essentially optimal because, if the axiom of constructibility is true, then Gödel's Σ 2 1 Π 2 1 well-ordering of the set of reals [3], having the convenient property that the set of ω -sequences of reals enumerating initial segments is also Σ 2 1 ∩ Π 2 1 , rather directly gives a Σ 2 1 ∩ Π 2 1 set which is not Ramsey. On the other hand, from the assumption that there is a measurable cardinal we shall derive the conclusion that every Σ 2 1 (i.e., PCA) is Ramsey. Also, we shall explore the connection between Martin's axiom and the Ramsey property.