# Cardinality of intersection with set belongs to set for all sets in a family

Consider $X=\{2,3,4\}$. This set has some interesting properties:

• The number of even numbers in $X$ is 2, an even number
• The number of odd numbers in $X$ is 1, an odd number
• The number of primes in $X$ is 2, a prime
• The number of squares in $X$ is 1, a square

We might wonder if this example can be extended to any number of such similar "properties." Hence:

Question:

Suppose $\mathcal{A} = \{A_1,A_2,\ldots,A_k\} \subseteq 2^{\mathbb{N}}$ is a finite family of infinite subsets of nonnegative integers (that is, each $A_i$ is infinite). Does there exist $X \subseteq \mathbb{N}$ such that $|A_i \cap X| \in A_i$ for all $i=1,\ldots,k$?

Note that it is not necessarily the case that such an $X$ exists if the $A_i$ are allowed to be finite, even if $\mathcal{A}$ satisfies the following obvious necessary condition:

• $\mathrm{min}(A) \leq |A|$ for all $A \in \mathcal{A}$ (where $\mathrm{min}(\emptyset):=\infty$);

consider the example $\mathcal{A}=\{\{1\},\{2,4\},\{1,2,4\}\}$.

Also note that there is not necessarily such an $X$ if $\mathcal{A}$ itself is allowed to be infinite, as in the example $\mathcal{A}=\{A_1,A_2,\ldots\}$ where $A_i =\{i,i+1,i+2,\ldots\}$.

• I don't understand the proof of the theorem; for instance, in the first case, where we replace $A_i$ and $A_j$ by $A_i \cap A_j$, and we get $X$ working for $\mathcal{A}'$, why should $X$ work for $\mathcal{A}$? We get that $|X \cap A_i \cap A_j| \in A_i \cap A_j$, but there could be elements of $X$ in $A_i \backslash A_j$ and so we don't know that $|X \cap A_i| \in A_i$. – Douglas Ulrich Mar 27 '17 at 23:04
• @DouglasUlrich: Thanks for pointing out my sloppiness. I have now edited the question to instead ask if what I originally claimed was a "theorem" is in fact true. – Sam Hopkins Mar 27 '17 at 23:57

## 1 Answer

Just take $A_1=\{2^n : n \in \mathbb N\}$, $A_2=\{2^n : n \textrm{ even}\}$, and $A_3=\{2^n : n \textrm{ odd}\}$. If $|A_2 \cap X| \in A_2$ and $|A_3 \cap X| \in A_3$, then $|A_1 \cap X|$ is a sum of two distinct powers of $2$, and hence is not in $A_1$.

• Thanks for the very simple answer to my too naive question! – Sam Hopkins Mar 28 '17 at 0:18