Every chain of subsets of $\mathbb{N}$ has a countable subchain with equal intersection

Question

Let $ (C_i)_{i \in I} $ be a chain of subsets of $ \mathbb{N} $ where $ I $ is an arbitrary indexing set. Does there always exist a countable subchain $ (C_{i_n})_{n \in \mathbb{N}} $ such that $ \bigcap_{i \in I} C_i = \bigcap_{n \in \mathbb{N}} C_{i_n} $?

This seems like a fairly basic result, but I haven't found it anywhere.

I have a proof in mind using choice. Let $ J = \bigcap_{i \in I} C_i $. We can enumerate $ J^c = \{a_1, a_2, \dots \} $. Then, well-order $ I $. We proceed recursively as follows. For the base case, let $ i_1 $ be the minimal index in the well-order such that $ a_1 \not \in C_{i_1} $. Then, assume $ i_1, \dots, i_n $ have been defined so that $ C_{i_k} \supset C_{i_{k + 1}} $ and $ a_k \not \in C_{i_k} $ for $ 1 \leq k \leq n $. We choose $ i_{n + 1} $ to be the minimal index such that $ C_{i_n} \supset C_{i_{n + 1}} $ and $ a_{n + 1} \not \in C_{i_{n + 1}} $.

As $ (C_{i_n})_{n \in \mathbb{N}} $ is a subchain of $ (C_i)_{i \in I} $, $ \bigcap_{n \in \mathbb{n}} C_{i_n} \supseteq \bigcap_{i \in I} C_i $. Moreover, for any $ a \not \in \bigcap_{i \in I} C_i $, $ a \not \in \bigcap_{n \in \mathbb{n}} C_{i_n} $ by construction, so we have equality.

Is this correct? If so, can it be done without choice?

Answer 1

Your argument looks correct!

---

As to your second question, yes, choice is in fact necessary. To see this I think it's helpful to switch from chains of subsets of $\mathbb{N}$ to chains of subsets of $\mathbb{Q}$ (since there is a bijection between those two sets, this is a benign modification). We can now associate, to each set $A$ of real numbers, a chain $\mathcal{C}_A$ of sets of rational numbers via Dedekind cuts: $$\mathcal{C}_A=\{\{q\in\mathbb{Q}: q<a\}: a\in A\}.$$ Now it turns out that it is consistent with $\mathsf{ZF}$ (= set theory without choice) that there is an uncountable set of reals $X$ with no countably infinite subset. In particular, this means that $\mathcal{C}_X$ has no countably infinite chains at all, let alone countably infinite chains with the same intersection as $\bigcap \mathcal{C}_X$, and so we're done. (OK fine technically we also need that $X$ have no least element, but this is easy to ensure: if $X$ is as above then the set of elements of $X$ with only finitely many predecessors in $X$ is itself finite, and we can WLOG remove this finite set from $X$.)

However, this $\mathcal{C}_X$ does "almost" have a countable subchain with the same intersection: there is a countable set of reals $Y$ such that $$\bigcap \mathcal{C}_{X\cup Y}=\bigcap \mathcal{C}_X=\bigcap \mathcal{C}_Y.$$ Just take $Y$ to consist of the countably many rationals greater than some element of $X$. Now most of the elements of $\mathcal{C}_Y$ won't be elements of $\mathcal{C}_X$, but in a sense adding them doesn't disrupt things too much.

This raises the question of whether choice is needed for the following seemingly-weaker result:

Suppose $\mathcal{C}$ is a chain of subsets of $\mathbb{N}$. Let $$\mathcal{C}^+=\{\bigcup \mathcal{B}: \mathcal{B}\subseteq \mathcal{C}, \mathcal{B}\not=\emptyset\}$$ (think of $\mathcal{C}^+$ as the "completion" of $\mathcal{C}$, and note that $\mathcal{C}^+$ is a chain with $\bigcap \mathcal{C}^+=\bigcap \mathcal{C}$). Then there is a countable $\mathcal{D}\subseteq \mathcal{C}^+$ such that $\bigcap \mathcal{D}=\bigcap \mathcal{C}^+$.

In fact choice is not needed here since we can modify your argument to apply choicelessly to $\mathcal{C}^+$ as follows:

HINT: for $n\in \mathbb{N}\setminus \bigcap \mathcal{C}$ consider $$A_n=\bigcup\{U\in \mathcal{C}: n\not\in U\}.$$