Extracting a subsequence common to infinitely many sets from an uncountable collection with uniform positive upper density

Question

Let $\{a_n\},\{b_n\}$ be strictly increasing sequence of positive integers satisfying $a_1<b_1<a_2<b_2<a_3<b_3<\ldots$ and $(b_n-a_n) \to \infty$. Define $I_n:= [a_n,b_n]$, meaning the set of all consecutive integers from $a_n$ to $b_n$. Let $A_{\alpha},\alpha \in \mathcal{A}$ be an uncountable family of infinite subsets of $\mathbb{N}$ that satisfies the following:

There exists some $c \in (0,1)$ so that for all $\alpha \in \mathcal{A}$ there exists some $n(\alpha) \in \mathbb{N}$ so that $|A_{\alpha} \cap I_n|\geq c(b_n-a_n)$ for all $n\geq n(\alpha)$. (Here $|B|$ is the number of elements of a finite subset $B \subset \mathbb{N}$)

Then my question is the following:

Does there exist a strictly increasing sequence of positive integers $\{l_n\} \to \infty$ for which there exists an infinite subset $\mathcal{B}\subset \mathcal{A}$ so that $l_n \in A_{\alpha}$ for all $n \in \mathbb{N}$, $\alpha \in \mathcal{B}$?

Answer 1

Fix a free ultrafilter $\mathcal{U}$ on $\omega$ and define a finitely additive measure $m:\mathcal{P}(\omega) \to [0, 1]$ via the ultralimit $$m(A) = \lim_{\mathcal{U}} \frac{|A \cap I_n|}{|I_n|}.$$ Now try to construct $\langle \mathcal{A}_k, N_k, B_k, n_k: k < \omega \rangle$ satisfying the following for every $k$.

(1) Each $\mathcal{A}_k$ is uncountable family of sets of measure $\geq 1/N_k$ and $\mathcal{A}_0 \subseteq \mathcal{A}$.

(2) $B_k \in \mathcal{A}_{k}$.

(3) $\mathcal{A}_{k+1} \subseteq \{B_k \cap B: B \in \mathcal{A}_{k}\}$.

(4) $n_k \in B_k$ and $n_k < n_{k+1}$.

To do the inductive step, argue as follows. Suppose $N \geq 1$ and $\mathcal{F}$ is an uncountable family of sets of measure $\geq 1/N$. A simple calculation shows that we can find an $L \geq 1$ (depending only on $N$) such that whenever $A_1, \cdots, A_L$ are distinct sets of measure $\geq 1/N$, there must exist $i < j \leq L$ such that $m(A_i \cap A_j) \geq 1/L$. Consider the coloring $c:[\mathcal{F}]^2 \to \{0, 1\}$ defined by $c(A, B) = 0$ iff $m(A \cap B) < 1/L$. Apply Erdos-Dushnik-Miller theorem to $c$ to get an uncountable subfamily $\mathcal{F}' \subseteq \mathcal{F}$ such that for every distinct $A, B \in \mathcal{F}'$, $m(A \cap B) \geq 1/L$. Fix $B_{\star} \in \mathcal{F}'$. Finally observe that there are arbitrarily large $n$ for which $\mathcal{F}'' = \{B \in \mathcal{F}': n \in B \cap B_{\star}\}$ is uncountable.

Answer 2

The answer is yes. The following proof is much less elegant than Jaguar's but has the minor virtue of being self-contained, in that it doesn't refer to the Erdős–Dushnik–Miller theorem. Mainly, though, I'm posting it because I lay awake in bed most of last night working it out and I hate to see that misery go to waste.

Theorem. Let $A$ be an index set, $|A|=\aleph_1$. Let $I_n$ ($n\in\mathbb N$) be disjoint countable sets with $I=\bigcup_{n\in\mathbb N}I_n$, and let $\mu$ be a nonnegative finitely additive measure on $I$ such that $\mu(I_n)\lt\infty$ for all $n\in\mathbb N$. Let $\mathcal U$ be a free ultrafilter on $\mathbb N$ and let $\varepsilon\gt0$. For each $\alpha\in A$ let $S_\alpha$ be a set such that $$\{n\in\mathbb N:\mu(S_\alpha\cap I_n)\gt\varepsilon\mu(I_n)\}\in\mathcal U$$ (so in particular $|S_\alpha\cap I|=\aleph_0$).
Then there is an infinite set $M\subseteq A$ such that $(\bigcap_{\alpha\in M}S_\alpha)\cap I_n\ne\varnothing$ for infinitely many $n\in\mathbb N$.

Proof.

Claim 1. There exist $n_0\in\mathbb N$, $x_0\in I_{n_0}$, $B\subseteq A$, $J_n\subseteq I_n$ ($n\in\mathbb N$), and $J\subseteq I$ such that $|B|=\aleph_1$, $J=\bigcup_{n\in\mathbb N}J_n$, $$\forall\alpha\in B,\ \{n\in\mathbb N:\mu(S_\alpha\cap J_n)\gt\varepsilon\mu(J_n)\}\in\mathcal U,$$ $x_0\in S_\alpha$ for all $\alpha\in B$, and $I_{n_0}\cap J=\varnothing.$

Proof of Claim 1. Choose $x_0\in I$ so that $\{\alpha\in A:x_0\in S_\alpha\}$ is uncountable. (If there were no such $x_0$ then, since $I$ is countable and $A$ is uncountable, there would be some $\alpha\in A$ with $S_\alpha\cap I=\varnothing$.) Then $x_0\in I_{n_0}$ for some $n_0\in\mathbb N$. Let $B=\{\alpha\in A:x_0\in S_\alpha\}$, let $J_n=I_n\setminus I_{n_0}$ for $n\in\mathbb N$, and let $J=I\setminus I_{n_0}$.

Claim 2. There exist $\alpha_0\in A$, $B\subseteq A\setminus\{\alpha_0\}$, $J_n\subseteq I_n$ ($n\in\mathbb N$), $J\subseteq I$, and $\delta\gt0$ such that $|B|=\aleph_1$, $J=\bigcup_{n\in\mathbb N}J_n\subseteq S_{\alpha_0}$, and $$\forall\beta\in B,\ \{n\in\mathbb N:\mu(S_\beta\cap J_n)\gt\delta\mu(J_n)\}\in\mathcal U.$$

Proof of Claim 2. Choose $k\in\mathbb N$ so that $k\varepsilon\gt1$ and choose $\delta\gt0$ so that $k\varepsilon-\binom k2\delta\gt1$. Let's call $S_\alpha$ and $S_\beta$ "almost disjoint" if $\{n\in\mathbb N:\mu(S_\alpha\cap S_\beta\cap I_n)\le\delta\mu(I_n)\}\in\mathcal U$. Then any pairwise almost disjoint subfamily of $\{S_\alpha:\alpha\in A\}$ has fewer than $k$ elements, so there is a maximal pairwise almost disjoint subfamily $\{S_\alpha:\alpha\in A_0\}$ where $A_0$ is a finite subset of $A$. Then for each $\beta\in A\setminus A_0$ there is some $\alpha\in A_0$ such that $\{n\in\mathbb N:\mu(S_\beta\cap S_\alpha\cap I_n)\gt\delta\mu(I_n)\}\in\mathcal U$. Choose $\alpha_0\in A_0$ and $B\subseteq A\setminus A_0$ so that $|B|=\aleph_1$ and $$\forall\beta\in B,\ \{n\in\mathbb N:\mu(S_\beta\cap S_{\alpha_0}\cap I_n)\gt\delta\mu(I_n)\ge\delta\mu(S_{\alpha_0}\cap I_n)\}\in\mathcal U.$$ Let $J_n=S_{\alpha_0}\cap I_n$ ($n\in\mathbb N$), and let $J=S_{\alpha_0}\cap I$.

Applying Claims 1 and 2 infinitely many times, we get infinitely many distinct elements $\alpha_0,\alpha_1,\dots\in A$ and $x_0,x_1,\dots\in I$ and $n_0,n_1,\dots\in\mathbb N$ such that $x_k\in S_j\cap I_{n_k}$ for all $j,k\in\mathbb N$.

P.S. The following is a partial answer to a question raised in a comment.

Theorem. Let $(I_n:n\in\mathbb N)$ be a sequence of disjoint nonempty sets with $|I_n|\le2^{\aleph_0}$. Assuming the continuum hypothesis $2^{\aleph_0}=\aleph_1$, there is a family of sets $(A_t:t\in\mathbb R)$ such that:
(i) $|I_n\setminus A_t|=1$ for all $t\in\mathbb R$ and all $n\in\mathbb N$;
(ii) there is no set $X$ such that $\{n\in\mathbb N:X\cap I_n\ne\varnothing\}$ is infinite and $\{t\in\mathbb R:X\subseteq A_t\}$ is uncountable.

Proof. Let $\{X_s:s\in\mathbb R\}$ be the collection of all countable sets $X\subseteq\bigcup_{n\in\mathbb N}I_n$ such that $\{n\in\mathbb N:X\cap I_n\ne\varnothing\}$ is infinite.

By the continuum hypothesis, there is a well-ordering $\prec$ of $\mathbb R$ such that, for each $t\in\mathbb R$, the set $\{s\in\mathbb R:s\prec t\}$ is countable.

By transfinite recursion we can define $A_t\subseteq\bigcup_{n\in\mathbb N}I_n$ for $t\in\mathbb R$ so that $|I_n\setminus A_t|=1$ for each $n\in\mathbb N$ while $X_s\not\subseteq A_t$ for all $s\prec t$.