Question

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?

Answer 1

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

Answer 2

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