2
$\begingroup$

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?

$\endgroup$
5
  • $\begingroup$ You mean $X=\bigcup\{x_i\mid i\in\omega\}$, right? $\endgroup$
    – Asaf Karagila ♦
    May 7, 2014 at 18:48
  • $\begingroup$ @Asaf, Correct! I will edit momentarily. $\endgroup$
    – user7090
    May 7, 2014 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, 2014 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, 2014 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, 2014 at 19:09

1 Answer 1

Reset to default
2
$\begingroup$

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?

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .