# Prove existence of an infinite set which intersects each subset of a set of countably infinite sets finitely many times

Assume that $\mathcal{A}$ is a countable infinite set of infinite subsets of $\mathbb{N}$ such that $A \cap B$ is finite for all $A \neq B \in \mathcal{A}$. Prove that there is an infinite set $X \subset \mathbb{N}$ such that $X \cap A$ is finite for all $A \in \mathcal{A}$.

I want to construct the set $X$ in the following way,

$\forall n$, $x_n \in X$, is such that $x_n=min \left ( (A_n \setminus \bigcup_{i <n} A_i) \setminus \{x_0,x_1, \dots, x_{n-1} \} \right )$.

Example, $x_0=min(A_0)$

$x_1= min(A_1 \setminus A_0)\setminus \{x_0\}$

Then $X= \bigcup \{ x_i | i \in \omega \}$. I think this will work but I am having a difficult time with the details.

How can I construct the $x_i$ using recursion?

• You mean $X=\bigcup\{x_i\mid i\in\omega\}$, right? – Asaf Karagila May 7 '14 at 18:48
• @Asaf, Correct! I will edit momentarily. – user7090 May 7 '14 at 18:49
• Ugh, no. That's the same thing. I got confused! I meant to ask if you meant $X=\bigcup\{x_i\}$. – Asaf Karagila May 7 '14 at 18:59
• $X=\{x_0,x_1, \dots, x_n, \dots \}$ where each $x_i$ is constructed as above. – user7090 May 7 '14 at 19:02
• Yes, and $\bigcup x_i$ or alternatively $\bigcup\{x_i\mid i\in\omega\}$ are both the union of the sets $x_i$, which in turn is easily shown to be $\omega$ itself. On the other hand, $\{x_i\mid i\in\omega\}$ is a whole other thing. – Asaf Karagila May 7 '14 at 19:09

HINT: Suppose that $x_k\in X\cap A_n$, then it is impossible that $k>n$ because $x_n$ was taken from which set?