I came across this problem in my study of set theory and am not quite sure how to approach it. A solution or starting point would be welcome.

Prove that if $\mathcal U$ is a nonprincipal ultrafilter over over $\omega$, then the following are equivalent:

(a) $\mathcal U$ is a Ramsey ultrafilter.

(b) For all $f: \omega \to \omega$ there exists $X \in \omega$ such that $f\restriction X$ is either an injective function or a constant function.

As a note, by a Ramsey ultrafilter, I mean a nonprincipal ultrafilter $\mathcal U$ on $\omega$ such that for every $\mathcal X: ( \omega )^{2} \to 2$ there exists a $\mathcal X$-monochromatic $A \in \mathcal U$.

  • 1
    $\begingroup$ What's your definition of Ramsey ultrafilter? $\endgroup$ – azarel Jul 20 '12 at 0:06
  • $\begingroup$ Typo, it should be there is $X\subseteq \omega$. $\endgroup$ – André Nicolas Jul 20 '12 at 0:25

We do one direction. The other direction goes along very similar lines.

Suppose the ultrafilter $\mathcal{U}$ is Ramsey. Then (by definition) for any partition of $\omega$ into pairwise disjoint subsets non-empty $S_n$ such that $S_n$ is not in $\mathcal{U}$, there is a set $X\in \mathcal{U}$ that meets each $S_n$ in exactly one point.

Now let $f$ be a function from $\omega$ to $\omega$. Say that the natural number $a$ is equivalent to $b$ if $f(a)=f(b)$. This is an equivalence relation that partitions $\omega$ into sets $S_n$.

If one of the $S_n$, say $S_{i}$, is in $\mathcal{U}$, let $X=S_{i}$. Then $f$ restricted to $X$ is constant.

If none of the $S_n$ is in $\mathcal{U}$, then by the Ramsey property there is an $X\in \mathcal{U}$ such that $X\cap S_n$ is a singleton for every $n$. Then $f$ restricted to $X$ is injective.


André’s answer actually shows that every selective ultrafilter on $\omega$ has property (b), and as he says, the converse is proved similarly. To complete the argument, you need to show that an ultrafilter is selective iff it’s Ramsey.

Suppose that $\mathscr{U}$ is selective; i.e., if $\{S_n:n\in\omega\}$ is a partition of $\omega$, either $S_n\in\mathscr{U}$ for some $n\in\omega$, or there is a set $A\subseteq\omega$ such that $|S_n\cap A|=1$ for each $n\in\omega$. (The set $A$ is a selector for the partition, hence the name selective.) Suppose further that $\chi:[\omega]^2\to 2$ is a $2$-coloring of $[\omega]^2$. For $n\in\omega$ and $i\in 2$ let $A_i(n)=\big\{m\in\omega:\chi\big(\{m,n\}\big)=i\big\}$; for each $n$ exactly one of $A_0(n)$ and $A_1(n)$ belongs to $\mathscr{U}$. For $i\in 2$ let $B_i=\{n\in\omega:A_i(n)\in\mathscr{U}\}$; exactly one of $B_0$ and $B_1$ belongs to $\mathscr{U}$. Without loss of generality assume that $B_0\in\mathscr{U}$, and let $\mathscr{C}=\{B_0\}\cup\{A_0(n):n\in B_0\}\subseteq\mathscr{U}$. Suppose that $C=\bigcap\mathscr{C}\in\mathscr{U}$. If $\{m,n\}\in[C]^2$, then $m\in B_0$, so $A_0(m)\in\mathscr{C}$ and therefore $n\in C\subseteq A_0(m)$, so $\chi\big(\{m,n\}\big)=0$, and $[C]^2$ is monochromatic with $C\in\mathscr{U}$.

If $C\notin\mathscr{U}$, let $B_0=\{n_k:k\in\Bbb Z^+\}$ be an increasing enumeration. Let $D_0=B_0$, and for $k\in\Bbb Z^+$ let $D_k=D_{k-1}\cap A_0(n_k)\in\mathscr{U}$. For $k\in\omega$ let $S_k=D_k\setminus D_{k+1}\notin\mathscr{U}$. Then

$$\{C,\omega\setminus D_0\}\cup\{S_k:k\in\omega\}$$

is a partition of $\omega$ into sets not in $\mathscr{U}$, so it has a selector $U\in\mathscr{U}$. For $k\in\omega$ let $n_k$ be the unique element of $U\cap S_k$. If $j\ge k$, then $n_j\in S_j\subseteq D_j\subseteq D_k$, so $D_k\supseteq\{n_j:j\ge k\}$. Now let $A=\{n_k:k\in\Bbb Z^+\}\in\mathscr{U}$. Suppose that $\{n_j,n_k\}\in[A]^2$ with $j<k$. Then $n_k\in D_j\subseteq A_0(n_j)$, and $n_j\in D_0=B_0$, so $\chi\big\{n_j,n_k\}\big)=0$, and $[A]^2$ is monochromatic with $A\in\mathscr{U}$. Thus, $\mathscr{U}$ is Ramsey.

Now suppose that $\mathscr{U}$ is Ramsey, and let $\mathscr{S}=\{S_n:n\in\omega\}$ be a partition of $\omega$ into sets not in $\mathscr{U}$. For $\{m,n\}\in[\omega]^2$ let $\chi\big(\{m,n\}\big)=1$ if $m$ and $n$ belong to the same member of $\mathscr{S}$; otherwise let $\chi\big(\{m,n\}\big)=0$. There is a $U\in\mathscr{U}$ such that $[U]^2$ is monochromatic. If $[U]^2$ were monochromatic for $1$, there would be an $n\in\omega$ such that $U\subseteq S_n$ (why?), contradicting the fact that $U\in\mathscr{U}$, so $U$ must be monochromatic for $0$. Clearly $|U\cap S_n|\le 1$ for each $n\in\omega$ (why?). $U$ may not quite be a selector for $\mathscr{S}$, but it can be extended to a selector $V\in\mathscr{U}$; how?

  • $\begingroup$ Your proof that a selective ultrafilter is Ramsey seems flawed to me. I couldn't manage to understand why $A$ is monochromatic and I am not sure it is. Probably the error arises from the double definition of $n_k$. A proof of that implication is at page 20 of Ultrafilters on a Countable Set -- David Booth. In the book (IV)=Selective, (I)=Ramsey and (V) is one more equivalent property. The implication we are interested in is (IV)->(V) (as (V) -> (I) is rather easy) and the proof is very similar to yours, but it ends in a diffe $\endgroup$ – dario2994 Apr 4 '15 at 15:46
  • $\begingroup$ (adding the remainder of Dario's comment, JL) a different and more subtle way. It uses again the selective property in order to find a subset of A (in your notation) that is monochromatic. $\endgroup$ – Jyrki Lahtonen Apr 4 '15 at 18:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.