# Problem on ultrafilters

I have to solve this problem: suppose to have an ultrafilter $\mathcal{U}$. Suppose that (1) holds, I want to prove (2):

1) for every partition $\mathbb{N}=\bigsqcup A_k$ $|A_k|=\aleph_0$ there exists $X\in\mathcal{U}$ such that $|X\cap A_k|=1$ for all $k$.

2) $f:\mathbb{N}\rightarrow\mathbb{N}$ not $\mathcal{U}$-eq. to a constant, then it is $\mathcal{U}$-eq to an injective function.

Here what I have done:

We have $f:\mathbb{N}\rightarrow\mathbb{N}$, and we define $A_k:=f^{-1}(k)$, $f$ not $\mathcal{U}$-eq. to a constant implies $A_k\not\in\mathcal{U}$. So for (1) we have that there exists $X\in\mathcal{U}$ such that $|X\cap A_k|=1$. Take $x_k\in X\cap A_k$ then $\{x_k:k\in\mathbb{N}\}=X\in\mathcal{U}$ and $f(x_k)=k$. Define $g:\mathbb{N}\rightarrow\mathbb{N}$ in this way $k\mapsto x_k$, it is injective, but I can't prove that $\{k:f(k)=g(k)\}=\{k:f(k)=x_k\}$ is in the ultrafilter $\mathcal{U}$.

-
This is Lemma I.1.5 from Argyros, Todorcevic: Ramsey Methods in Analysis. – Martin Sleziak Apr 24 '11 at 4:44
I can't find this book, on google booke the page where is that proof is missing. Could you write a proof please? – Jacob Fox Apr 24 '11 at 10:35
Jacob: What is wrong with the proof I gave? – Asaf Karagila Apr 24 '11 at 12:05
@Asaf: The reason I mentioned this book was not that I would think that there is something wrong with your proof. Another lemma from the same chapter of this book was related to another Jacob's question on Ramsey filters, so I though it would be worth mentioning. – Martin Sleziak Apr 24 '11 at 16:20
@Martin: my comment was directed at Jacob, not at you. – Asaf Karagila Apr 24 '11 at 18:04

Firstly, if the requirement in (1) is not that $A_k\notin\mathcal U$ then it is simply not true if $\mathcal U$ is free.

Proof: Suppose $\mathcal U$ is free, then there is some $A\in\mathcal U$ which is infinite and not co-finite. Take partition of $\mathbb N\setminus A$ to infinitely many infinite sets, $A_n$ for $n>0$, set $A_0=A$.

This is a partition to infinite sets, however if such $X\in\mathcal U$ exists then $X\cap A\in\mathcal U$ is a singleton, contradiction the fact the ultrafilter is free.

Now, for your actual question, suppose $f\colon\mathbb N\to\mathbb N$ and $A_k=f^{-1}(k)$, since $f$ is indeed not $\mathcal U$-constant we know that $A_k\notin\mathcal U$ for all $k$.

By property (1) there exists some $X\in\mathcal U$ such that $X\cap A_k = \{x_k\}$ for all $k\in\mathbb N$, therefore $X=X\cap\mathbb N = X\cap\bigcup_k A_k = \bigcup_k X\cap A_k = \bigcup_k\{x_k\}$.

Define $g\colon\mathbb N\to\mathbb N$ as follows:

$g(x) = k$ for $x=x_k\in X$ and $g(x)=0$ otherwise.

As Martin enlightened me in the comments, it seems $g$ is not injective, and easy to see it is surjective and therefore cannot be made injective like that. Instead we will change slightly the playing sets:

Since $\mathcal U$ is an ultrafilter either $2\mathbb N$ or $2\mathbb N+1$ are in it (i.e. even numbers and odd numbers). Without the loss of generality assume the even numbers are there, and let $X'=X\cap\{2k\mid k\in\mathbb N\}$.

Since $X'$ is not co-finite. Enumerate the following sets:

1. $\mathbb N\setminus X' = \{y_k\mid k\in\mathbb N\}$,
2. $\{k\mid x_k\notin X'\}=\{y'_k\mid k\in\mathbb N\}$.

Now we can define $g$ as follows:

1. $g(x) = k$ if $x=x_k\in X'$ for some $k$;
2. $g(x) = y'_k$ if $x=y_k\notin X'$ for some $k$.

This can probably be cleaned up a little bit, but for the needs of the proof it works.

If $g(a)=g(b)$ then clearly either $a,b\in X'$ or $a,b\notin X'$ (otherwise the range of $g$ goes into disjoint sets), and the definition of each part is obviously injective.

Now suppose $\{n\mid f(n)=g(n)\}\notin\mathcal U$, then we have $Y=\{n\mid f(n)\neq g(n)\}\in\mathcal U$.

Since ultrafilters are closed under finite intersections we have some $k\in X'\cap Y$ however $f(x_k)=k=g(x_k)$ which is a contradiction. Therefore $Y\notin\mathcal U$ and $X'$ is, and so $f$ is $\mathcal U$-equivalent to an injective function.

-
why $g(x_k)=k$? I defined $g$ so that $g(k)=x_k$. If we define $g$ such that $g(x_k)=k$ and extend it to $\mathbb{N}$ it won't be injective. – Jacob Fox Apr 24 '11 at 0:26
@Jacob: Sorry, too much bookkeeping for me ;-) I corrected it. – Asaf Karagila Apr 24 '11 at 8:50
@Asaf: Excuse me but I still don't understand :p. Why $f(k)=x_k$ and why $g(k)=X_k$, do you mean $g(k)=x_k$? – Jacob Fox Apr 24 '11 at 10:47
@Jacob: My shift key was pressed. – Asaf Karagila Apr 24 '11 at 10:50
I am a little confused by your proof too. The function $g$ is not injective. Perhaps it could be modified using $A_k=f^{-1}(2k,2k+1)$? – Martin Sleziak Apr 24 '11 at 21:27

This is the proof of (Ramsey) $\Rightarrow$ (2) from from Argyros, Todorcevic: Ramsey Methods in Analysis; Lemma I.1.5. The claim of this lemma is in fact equivalence of the two conditions. The converse implication has, however, longer proof and it was not asked for.

We use a condition different from (1), but you already know various characterizations of Ramsey (selective) ultrafilters from another your question Help on a proof

Given $f$, define a coloring $c: \mathbb N^{[2]} \to \{0, 1\}$ by letting $c(i, j) = 0$ iff $f(i) = f(j)$. Find $M \in \mathcal U$ with monochromatic $M^{[2]}$. Then $f$ is either constant or one-to-one on $M$.

Basically the same proof is in the book Problems and theorems in classical set theory By Péter Komjáth, V. Totik; p. 343, Exercise 12.

-