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?

  • $\begingroup$ You mean $X=\bigcup\{x_i\mid i\in\omega\}$, right? $\endgroup$ – Asaf Karagila May 7 '14 at 18:48
  • $\begingroup$ @Asaf, Correct! I will edit momentarily. $\endgroup$ – user7090 May 7 '14 at 18:49
  • $\begingroup$ Ugh, no. That's the same thing. I got confused! I meant to ask if you meant $X=\bigcup\{x_i\}$. $\endgroup$ – Asaf Karagila May 7 '14 at 18:59
  • $\begingroup$ $X=\{x_0,x_1, \dots, x_n, \dots \}$ where each $x_i$ is constructed as above. $\endgroup$ – user7090 May 7 '14 at 19:02
  • $\begingroup$ 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. $\endgroup$ – 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?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.