Prove the existence of a subset of $\mathbb{N}$ with the following property. Suppose $\left \langle A_n\ :\ n\in\mathbb{N} \right \rangle$ is a sequence of infinite subsets of $\mathbb{N}$. 
Prove that there exist an infinite set of $A\subseteq\mathbb{N}$ such that
$\forall n\in\mathbb{N}$ [$A\ \cap\ A_n$ is infinite and $(\mathbb{N}\backslash A) \ \cap A_n$ is infinite]
I really wanted to do induction here, but I cant clear the base case $n=0$, so I was wondering if there are other ways to prove such existence.
Any help or insights is deeply appreciated.
 A: In technical terms, you want to construct an $A\subseteq\Bbb N$ that splits each $A_n$. Note that $A$ splits $A_n$ iff $\Bbb N\setminus A$ splits $A_n$, so the idea is to construct disjoint subsets of $\Bbb N$ that have infinite intersection with each $A_n$. You can do this recursively, picking one member of each subset at each stage.
Suppose that for some $n\in\Bbb N$ we’ve chosen $s_k,t_k\in A_k$ for each $k<n$ in such a way that the $n$ natural numbers $s_k$ and $t_k$ are all distinct. Let $S_n=\{s_k:k<n\}$ and $T_n=\{t_k:k<n\}$ and $F_n=S_n\cup T_n$. $F_n$ is finite, so $A_n\setminus F_n$ is infinite, and we can let 
$$s_n=\min(A_n\setminus F_n)$$
and
$$t_n=\min\big(A_n\setminus(F_n\cup\{s_n\})\big)\;.$$
Clearly $s_n,t_n\notin F_n$, so the recursion hypothesis for the next step is satisfied, and the recursion goes through to yield disjoint infinite subsets $S=\{s_n:n\in\Bbb N\}$ and $T=\{t_n:n\in\Bbb N\}$ of $\Bbb N$, either of which will serve for $A$.
A: You can construct $A$ step by step as follows:
Put the smallest element of $A_1$ into A, put the second-smallest element of $A_1$ not into $A$. Remove all elements smaller or equal to these from all sets $A_i$.
Repeat this with $A_2$. Then $A_1$ again, then $A_2$, then $A_3$. Then $A_1$ again, then $A_2$ again , then $A_3$ again, then $A_4$ and so on. This is a common "diagonal" argument, which hits every $A_i$ infinitely many times.
(there is probably a more elegant formulation, but I hope the idea is understandable)
