MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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 was trying to construct some element with specific properties in an ultraproduct and it boils down to a question which seems relatively natural but leaves me perfectly clueless.

$\textbf{Question:}$ Pick some $\alpha \in (0,1)$. Let $\phi:\mathcal{P} _{fin}(\mathbb{N}) \to \mathcal{P} _{fin}(\mathbb{N})$ be any function between finite sets which does not reduce cardinality too much, $\textit{i.e.}$ such that $|\phi(S)| \geq \alpha |S|$ and $\phi(S) \subset S$. Does there exists a non-principal ultrafilter $\mathcal{U}$ on $\mathbb{N}$ and a sequence of finite sets $S_i \subset \mathbb{N}$ such that $\forall s \in \mathbb{N}, \lbrace i \in \mathbb{N} \mid s \in \phi(S_i) \rbrace =: F_s \in \mathcal{U}$.

As far as I know, the value of $\alpha$ may be irrelevant, but this does not help me much: if $\alpha =1$ then the answer is obviously "yes" ($\phi$ must be the identity, so any increasing sequence of sets will do) and if $\alpha=0$ it's obviously "no" ($\phi$ may send every set to the empty set).

Also, does the requirement that $\phi$ is increasing ($\textit{i.e. } S \subset S' \Rightarrow \phi(S) \subset \phi(S')$ change anything?

share|cite|improve this question
As stated, the answer is no: take $\phi(S)$ to be $\{0\}$ if $S=\{0\}$ and $S\setminus\{0\}$ otherwise. The, no matter what ultrafilter you use, the only way to have 0 present in almost every $\phi(S_i)$ is to have them all be $\{0\}$, in which case no other number can be. One can make $\alpha$ smaller and still have a counterexample by only removing anything from sufficiently large sets; if the size of the $S_i$ is bounded almost everywhere, only a few $F_s$ can be large, and if the $S_i$ grow to be unbounded, 0 is almost always removed. – Henry Towsner May 8 '12 at 12:56
up vote 3 down vote accepted

The answer to the original question (without the "increasing" requirement) is no, for any $\alpha<1$. Given $\alpha<1$, fix a positive integer $n$ so large that $\alpha+(1/n)<1$. Then, for each finite set $S\subseteq\mathbb N$, define $\phi(S)\subseteq S$ with $|\phi(S)|\geq\alpha|S|$ in such a way that $\phi(S)$ avoids one of the $n$ congruence classes modulo $n$ (say the smallest); that is, there is some $a(S)\in\{0,1,\dots,n-1\}$ such that no element of $\phi(S)$ is congruent mod $n$ to $a(S)$. Now suppose, toward a contradiction, that you had a sequence of sets $S_i$ and an ultrafilter $\mathcal U$ as in your question. $a(S_i)$ would be the same $a$ for $\mathcal U$-almost all $i$ (because $\mathcal U$ is an ultrafilter and $a(S)$ ranges over a finite set). So the desired conclusion fails for $s=a$.

share|cite|improve this answer

This fails if $\alpha = 1/2$ and $\phi(x)$ is the top half of $x$ --- in other words the elements of $x$ that greater than at least half of the other elements of $x$. Given a non-principal ultrafilter $\mathcal U$ and a sequence $S_i$ suppose first that there is no element of $A$ of $\mathcal U$ such that the $S_i$ with $i\in A$ are bounded. It is clear that then that it is impossible for any $F_s$ to belong to $\mathcal U$ because each element of $F_s$ has cardinality no greater than $2s$.

On the other hand, if $A\in \mathcal U$ is such that $|S_i|<2k$ for each $ i\in A$ then $\bigcap_{s\leq k}F_s\cap A$ must be empty. In fact, not even infinitely many $F_s$ can belong to $\mathcal U$.

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.