3
$\begingroup$

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$.

  • 0
    Typo, it should be there is $X\subseteq \omega$.2012-07-20

2 Answers 2

1

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.

1

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. 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?

  • 0
    (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.2015-04-04