Prove the existence of a subset of N\mathbb{N} with the following property.

Suppose ⟨An : n∈N⟩\left \langle A_n\ :\ n\in\mathbb{N} \right \rangle is a sequence of infinite subsets of N\mathbb{N}.
Prove that there exist an infinite set of A⊆NA\subseteq\mathbb{N} such that

∀n∈N\forall n\in\mathbb{N} [A ∩ AnA\ \cap\ A_n is infinite and (N∖A) ∩An(\mathbb{N}\backslash A) \ \cap A_n is infinite]

I really wanted to do induction here, but I cant clear the base case n=0n=0, so I was wondering if there are other ways to prove such existence.

Any help or insights is deeply appreciated.



2 Answers


In technical terms, you want to construct an A⊆NA\subseteq\Bbb N that splits each AnA_n. Note that AA splits AnA_n iff N∖A\Bbb N\setminus A splits AnA_n, so the idea is to construct disjoint subsets of N\Bbb N that have infinite intersection with each AnA_n. You can do this recursively, picking one member of each subset at each stage.

Suppose that for some n∈Nn\in\Bbb N we’ve chosen sk,tk∈Aks_k,t_k\in A_k for each k0n>0.
– Brian M. Scott

You can construct AA step by step as follows:

Put the smallest element of A_1A_1 into A, put the second-smallest element of A_1A_1 not into AA. Remove all elements smaller or equal to these from all sets A_iA_i.

Repeat this with A_2A_2. Then A_1A_1 again, then A_2A_2, then A_3A_3. Then A_1A_1 again, then A_2A_2 again , then A_3A_3 again, then A_4A_4 and so on. This is a common “diagonal” argument, which hits every A_iA_i infinitely many times.

(there is probably a more elegant formulation, but I hope the idea is understandable)