Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
1  
What's your definition of Ramsey ultrafilter? –  azarel Jul 20 '12 at 0:06
    
Typo, it should be there is $X\subseteq \omega$. –  André Nicolas Jul 20 '12 at 0:25
add comment

2 Answers 2

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.

share|improve this answer
add comment

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?

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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