Spencinar #6: The Galvin-Prikry Theorem

Today Zach Norwood talked about the Galvin-Prikry Theorem.

Prerequisites: basic topology, notions of category, familiarity with Ramsey theory is helpful for motivation. Last week's Spencinar post will be referenced occasionally but only in inessential remarks.

The Galvin-Prikry Theorem is a Ramsey result that is perhaps surprising because it is an example of an "infinite exponent" partition property. This means it deals with colorings of infinite subsets of the underlying space. With the Axiom of Choice, none of the usual partition relations hold with infinite exponents.

The Galvin-Prikry Theorem gets around this by only worrying about definable partitions of $[\omega^\omega]$. In order to state the theorem, let's make some definitions:

Definition: $Y\subseteq [\omega]^\omega$ is Ramsey if there is $A\in [\omega]^\omega$ with $[A]^\omega\subseteq Y$ or $A^\omega\subseteq Y^c$. (Here $Y^c$ is the complement of $Y$.) I'll informally say that $A$ in the first case is $Y$-homogeneous and $A$ in the second case is $Y^c$-homogeneous.

$Y$ can also be thought of as a coloring $[\omega]^\omega\rightarrow 2$. As in last week's post, we think of $[X]^\omega$ as the set of all increasing infinite sequences of $X$, or sometimes in a slight abuse of notation as the set of infinite subsets of $X$.

Galvin-Prikry Theorem: If $Y$ is Borel, then $Y$ is Ramsey.

Here the topology on $Y$ is generated by sets of the form $\{X: x \textrm{ is an initial segment of }X\}$. The proof, originally due to Ellentuck, will actually go through a finer topology which is more suited to the situation at hand. Notice the similarity with the Mathias forcing from last week. 

Definition: The Ellentuck topology is generated by sets of the form 

$$[s,B]^\omega:=\{X\in [\omega]^\omega: s \textrm{ is an initial segment of } X, x\setminus s\subseteq B\},$$

where $s\in [\omega]^{<\omega}$ and $B\in [\omega]^\omega$.

We will use "$\ast$-" to indicate the use of the Ellentuck topology over the usual one. Notice that all Borel sets are $\ast$-Borel.

Fix $Y\subseteq [\omega]^\omega$. We say $B\in[\omega]^\omega$ accepts $s$ (into $Y$) if $[s,B]^\omega\subseteq Y$. We say $B$ rejects $s$ if no infinite subset of $B$ accepts $s$. Informally, $B$ accepts $s$ if $s$ is long enough and $B$ is thin enough so that every subset of $B-\max(s)$ compatible with $s$ is in $Y$. $B$ rejects $s$ if $s$ is too short or $B$ concentrates on the wrong place for acceptance to occur. Although perhaps its best to think just in terms of the Ellentuck topology.

Some easy remarks:

• if $B$ accepts $s$, then so do all infinite subsets of $B$.
• if $B$ rejects $s$, then so do all infinite subsets of $B$ and all supersets of $B$.

The main part of the proof is the following lemma, which clarifies the relationship between acceptance and rejection.

Galvin-Prikry Lemma: For $Y\subseteq [\omega]^\omega$, exactly one of the following holds:

1. There is $B\in[\omega]^\omega$ that accepts $\emptyset$, or
2. there is $B \in [\omega]^\omega$ which rejects all of its finite subsets.

A $B$ that accepts $\emptyset$ is just one that is $Y$-homogeneous, and a $B$ which rejects all of its finite subsets is exactly one for which no $\ast$-open subset of $[B]^\omega$ is $Y$-homogeneous. For those familiar with forcing and last week's seminar, this is a special version of the Prikry lemma for the empty condition in Mathias forcing. Not having read the original source, I wonder if Prikry noticed the analogy with Prikry forcing?

Proof: Assume that no $B$ accepts $\emptyset$, so $\omega$ rejects $\emptyset$. We will construct recursively

• infinite subsets of $\omega$: $B_0\supseteq B_1\subseteq B_2\supseteq\cdots$, and
• natural numbers $a_1<a_2<\cdots$

so that $a_i\in B_i$ and $B_i$ rejects all subsets of $\{a_1,\ldots,a_{i-1}\}$. If this can be done, then $\{a_1,a_2,\ldots\}$ rejects all of its finite subsets. This kind of construction is typical in Ramsey theory.

By our assumption, $B_0=\omega$ works. At the $k$th stage of the construction, suppose that $B_0,\ldots, B_k$ and $a_1,\ldots,a_{k-1}$ have already been constructed. We want to define $a_k>a_{k-1}$ in $B_k$ and $B_{k+1}\subseteq B_k$ so that $B_{k+1}$ rejects all subsets of $\{a_1,\ldots,a_k\}$. 

If such $a_k, B_{k+1}$ did not exist, then we will define a sequence $C_1\supseteq C_2\supseteq\ldots$ of subsets of $B_k$, $b_1<b_2<\ldots$ with $b_{i+1}\in C_i$ and a finite subset $\bar{s}$ of $B_k$ so that $\{b_1,b_2,\ldots\}$ accepts $\bar{s}$. But this contradicts the inductive assumption on $B_k$. (This auxiliary construction is another version of the "typical" Ramsey construction building a kind of homogeneous object in the other direction.)

Choose $b_1>a_{k-1}$ in $B_k$. $B_k$ doesn't reject all subsets of $\{a_1,\ldots,a_{k-1},b_1\}$ (otherwise we could pick $b_1$ to be $a_k$ and $B_k$ to be $B_{k+1}$), so we can take $C_1\in [B_k]^{\omega}$ and $S_1\subseteq\{a_1,\ldots,a_{k-1},b_1\}$ so that $C_1$ accepts $s_1$. We must have $b_1\in s_1$ since we assumed that $B_k$ rejects all subsets of $\{a_1,\ldots,a_{k-1}\}$. Put $\bar{s}_1=s_1-\{b_1\}$. 

Continuing the construction, at stage $i+1$ pick $b_{i+1}>b_k$ in $C_i$, $C_{i+1}\in[C_i]^\omega$, and $s_{i+1}\subseteq \{a_1,\ldots,a_{k-1},b_{i+1}\}$ so that $C_{i+1}$ accepts $s_{i+1}$. Let $\bar{s}_{i+1}=s_{i+1}-\{b_{i+1}\}$.

Now the $\bar{s}_i$ must be constant for infinitely many $i$, and let this constant value be $\bar{s}$. Then $\{b_1,b_2,\ldots\}$ accepts $\bar{s}$. $\Box$

After this proof, we stopped using the language of acceptance and rejection, which made it easier for me to follow since I don't think that "rejection" is that easy to grasp in the flow of things.

As a first application of the Galvin-Prikry lemma,

Lemma 1: $\ast$-open sets are Ramsey.

Proof: Let $Y\subseteq [\omega]^\omega$, and take $B$ satisfying the conclusion of the Galvin-Prikry lemma. In the first case, $B$ accepts $\emptyset$, so we're done. In the second case, $B$ rejects all of its finite subsets. We'll show that $B$ is $Y^c$-homogeneous. Otherwise, there is $A$ an infinite subset of $B$ so that $A\in Y$. Using that $Y$ is $\ast$-open, it follows that there is a $\ast$-neighborhood of $A$, say $[s,A]^\omega$, with $[s,A]^\omega\subseteq Y$. But this means that $A$ accepts $s$, contradicting that $B$ rejects $s$. $\Box$

Now we introduce a strengthening of the Ramsey property:

Definition: A set $Y\subseteq [\omega]^\omega$ is completely Ramsey if for every $s\in[\omega]^<\omega$ and every $B\in[\omega]^\omega$, there exists $C\in [B]^\omega$ so that either $[s,C]^\omega\subseteq Y$ or $[s,C]^\omega\subseteq Y^c$. If the second possibility holds for all $s,B$, then $Y$ is called Ramsey null.

Thus, completely Ramsey means that a local Ramsey property holds on any $\ast$-open set. This is useful because topological properties are local in this sense; a key idea of this proof will be to show that certain Ramsey properties are equivalent to topological properties in the Ellentuck topology.

Lemma 2: $\ast$-open sets are completely Ramsey. As a corollary, $\ast$-closed sets are completely Ramsey.

Proof:  Let $s\in [\omega]^{<\omega}$ and $B\in [\omega]^\omega$ be arbitrary. The idea of the proof is to use a homeomorphism from $[\omega]^\omega$ to $[s,B]^\omega$ to transfer the result of Lemma 1. Enumerate $B=b_1<b_2<b_2<\cdots$. Then we define $f:[\omega]^\omega\rightarrow [s,B]^\omega$ by $X\mapsto s\cup \{b_i:i\in X\}$ (let's make the harmless assumption that $\min(B)>\max(s)$). It is easy to see that $f$ is $\ast$-continuous, so $f^{-1}Y$ is $\ast$-open, so Ramsey by Lemma 1. Now there is a $C'\in [\omega]^\omega$ so that $[C']^\omega\subseteq Y$ or $Y^c$. We can take $C=f(C')$ to witness completely Ramsey at $[s,B]^\omega$. $\Box$

We begin to realize the "key idea" mentioned above.

Lemma 3: $Y\in[\omega]^\omega$ is Ramsey null iff it is $\ast$-nowhere dense. (Reminder: a set is nowhere dense iff its closure has empty interior.)

Proof: The forward direction follows easily from the definitions: $\ast$-nowhere dense just means that for any basic $\ast$-open set $[s,B]^\omega$, there is a basic $\ast$-open subset $[t,C]^\omega$ disjoint from $Y$. Ramsey null is the prima facie stronger assertion where we cannot change the "stem" part $s$.

Conversely, take $[s,B]^\omega$ a basic $\ast$-open set. The $\ast$-closure $\bar{Y}$ of $Y$ is completely Ramsey by Lemma 2. If there were $C\in [B]^\omega$ with $[s,C]^\omega\subseteq \bar{Y}$, then $[s,C]^\omega$ would be a subset of the $\ast$-interior of $\bar{Y}$, contradicting $\ast$-nowhere dense. $\Box$

Let's recall some of the basic notions of category, the topological notion of largeness. The meager sets are countable unions of nowhere dense sets. It's a basic result (the Baire category theorem) that under some flexible hypotheses, a space is nonmeager in its own topology, so the category notions are nontrivial.

It turns out that Lemma 3 can be improved to $\ast$-meager sets:

Lemma 4: If $Y$ is $\ast$-meager, then it is Ramsey null.

Proof: Set $Y=\bigcup_{n=0}^\infty Y_n$, $Y_n$ is $\ast$-nowhere dense. The proof is roughly a diagonal argument, similar to some of the earlier ones. Let $s,B$ be arbitrary. We use several applications of Lemma 3 to construct $B_0\supseteq B_1\supseteq B_2\supseteq \cdots$ subsets of $B$ and an increasing sequence of $x_i\in B_i$ so that for each $n$,

$[s\cup F,B_n]^\omega\subseteq Y_n^c$ for all $F\subseteq\{x_0,\ldots,x_{n-1}\}$.

So at the $n$th stage, we use Lemma 3 successively to shrink $B_{n-1}$ so that the statement above holds for each $F\subseteq\{x_0,\ldots,x_{n-1}\}$ (one application of Lemma 3 for each $F$).

Then the sequence of $\{x_0,x_1,\ldots\}$ witnesses completely Ramsey for $s,B$. $\Box$

So $\ast$-nowhere dense, $\ast$-meager, and Ramsey null are all the same thing.

We can finally put it all together to get the main theorem of this talk, which implies the Galvin-Prikry Theorem as a corollary (since Borel sets in the usual topology are easily $\ast$-Baire, being in the $\sigma$-ideal generated by the $\ast$-open sets.). Recall that a set $Y$ is Baire (or has the property of Baire) iff there is a meager set $W$ and an open set $Z$ so that $Y= Z\triangle W$ is open (these are the "measurable" sets in terms of category).

Theorem: $Y$ is $\ast$-Baire iff it is completely Ramsey.

Proof: For the forward direction, suppose $Y$ is $\ast$-Baire, so there is a $\ast$-meager set $W$ and $\ast$-open $Z$ with $Y=Z\triangle W$. Take $s\in[\omega]^{<\omega}$ and $B\in [\omega]^\omega$ arbitrary. By Lemma 5, there is $C\in [B]^\omega$ so that $[s,C]^\omega\subseteq W^c$.  By Lemma 1, there is $D\in[C]^\omega$ so that $[s,D]^\omega\subseteq Z$ or $Z^c$. By choice of $C$, this means that $[s,D]^\omega\subseteq Z-W\subseteq Y$ or $[s,D]^\omega\subseteq Z^c-W\subseteq Y^c$.

Conversely, assume $Y$ is completely Ramsey. We will show that $Y-\rm{int}(Y)$ is $\ast$-meager. It suffices to show that it's Ramsey null. Take $s\in[\omega]^{<\omega}$ and $B\in [\omega]^\omega$ arbitrary. There is $C\in [B]^\omega$ so that $[s,C]^\omega\subseteq Y$ or $Y^c$. In the first case, $[s,C]^\omega$ is contained in the interior of $Y$, and in the second case, $[s,C]^\omega$ is disjoint from $Y$, so in either case $[s,C]\subseteq Y-\rm{int}(Y)$. $\Box$

Zach ended by giving an open question. Mathias proved that if it is consistent that an inaccessible cardinal exists, then it is consistent that projective sets are Ramsey (this statement holds in Solovay's model, obtained by collapsing an inaccessible). But is the inaccessible necessary? Does the statement that projective sets are Ramsey have consistency strength above just ZFC?