Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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
up vote 3 down vote accepted

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.

share|cite|improve this answer
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.

share|cite|improve this answer

Your Answer


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.