3
$\begingroup$

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

  • 0
    @Martin: my comment was directed at Jacob, not at you.2011-04-24

2 Answers 2

3

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.

  • 0
    @Martin: You are, as before, correct. The point is that it doesn't matter what $g(x)$ on a null set (which is why I did not give it any thought). I will change $g$ to be completely injective, anyway. **Added:** As defined right now $g$ is surjective and cannot be modified, I will modify $X$ as well, if so.2011-04-24
1

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 about Ramsey ultrafilters

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.