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." In fact, we have the following:

Theorem Let $\mathcal{A}=\{A_1,A_2,\ldots,A_k\}$ be a finite family, where each $A_i \subseteq \mathbb{N}$ is an infinite subset of nonnegative numbers. Then there exists $X\subseteq \mathbb{N}$ such that $|X\cap A_i| \in A_i$ for all $i=1,\ldots,k$.

Proof: We claim that in fact we can find $X\subseteq \mathbb{N}$ such that

• $|X\cap A_i| \in X\cap A_i$ for all $i=1,\ldots,k$;
• $X \subseteq \cup_{i=1}^{k}A_i$ (and hence $X$ is finite).

The proof is by induction on the number of pairs $i \neq j$ with $A_i \cap A_j \neq \emptyset$. In the base case of zero such pairs, i.e., if all the sets are pairwise disjoint, it is easy to find such an $X$: we start by putting the smallest $\mathrm{min}(A_1)$ elements of $A_1$ into $X$, then we put the smallest $\mathrm{min}(A_2)$ elements of $A_2$ into $X$, and so on.

So suppose there is $i \neq j$ with $A_i \cap A_j \neq \emptyset$. First suppose $|A_i \cap A_j| = \infty$. Then consider the new family $\mathcal{A}'$ obtained from $\mathcal{A}$ by removing $A_i$ and $A_j$ and adding $A_i \cap A_j$. This family has fewer pairs with nontrivial intersection and any $X$ that works for $\mathcal{A}'$ works for $\mathcal{A}$ as well. Next suppose that $|A_i \cap A_j| < \infty$. Then consider the new family $\mathcal{A}'$ obtained from $\mathcal{A}$ by replacing $A_i$ with $A_i \setminus A_j$ and $A_j$ with $A_j \setminus A_i$. Again, this family has fewer pairs with nontrivial intersection and any $X$ that works for $\mathcal{A}'$ works for $\mathcal{A}$ as well. So we are done by induction $\square$

Question:

Now consider the "general case." That is, suppose $\mathcal{A} \subseteq 2^{\mathbb{N}}$ is a arbitrary (i.e., finite or infinite) family of arbitrary (i.e., finite or infinite) subsets of nonnegative integers. When does there exist $X \subseteq \mathbb{N}$ such that $|A \cap X| \in A$ for all $A \in \mathcal{A}$?

I am looking for interesting necessary and/or sufficient conditions.

For example, the following is obviously a necessary condition:

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

A sufficient condition is the above obviously necessary condition plus the sets in $\mathcal{A}$ being pairwise disjoint.

But the above theorem gives a different sufficient condition: $\mathcal{A}$ is finite while all the sets in it are infinite.

Note that, even if $\mathcal{A}$ is finite, the above obvious necessary condition is not sufficient: consider the example $\mathcal{A}=\{\{1\},\{2,4\},\{1,2,4\}\}$.

Also note that all sets in $\mathcal{A}$ being infinite is not sufficient 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\}$.

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\}$.

Questions:

1. Suppose $\mathcal{A}=\{A_1,A_2,\ldots\}$ is a countably infinite family where again each $A_i \subseteq \mathbb{N}$ is an infinite subset of nonnegative integers. Then we cannot in general conclude that there is an $X$ as in the theorem above: consider the case where $A_i :=\{i,i+1,i+2,\ldots\}$. Are there some nontrivial necessary and/or sufficient conditions for having an $X \subseteq \mathbb{N}$ with $|X \cap A_i| \in A_i$ for all $i=1,2,\ldots$ in this case?

2. Now suppose $\mathcal{A}=\{A_1,A_2,\ldots,A_k\}$ is again a finite family, but where each $A_i \subseteq \mathbb{N}$ is an arbitrary (i.e., possibly finite) subset of nonnegative integers. An obvious necessary condition for the existence of an $X$ as in the theorem above is that $\mathrm{min}(A_i) \leq |A_i|$ for all $i=1,\ldots,k$ (where $\mathrm{min}(\emptyset):=\infty$). But this obvious necessary condition is not sufficient: consider $\mathcal{A}=\{\{1\},\{2,4\},\{1,2,4\}\}$. Are there some nontrivial necessary and/or sufficient conditions for having an $X \subseteq \mathbb{N}$ with $|X \cap A_i| \in A_i$ for all $i=1,\ldots,k$ in this case?

In either case, a sufficient condition (although far from necessary) is that the sets be pairwise disjoint.

Question:

Now consider the "general case." That is, suppose $\mathcal{A} \subseteq 2^{\mathbb{N}}$ is a arbitrary (i.e., finite or infinite) family of arbitrary (i.e., finite or infinite) subsets of nonnegative integers. When does there exist $X \subseteq \mathbb{N}$ such that $|A \cap X| \in A$ for all $A \in \mathcal{A}$?

I am looking for interesting necessary and/or sufficient conditions.

For example, the following is obviously a necessary condition:

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

A sufficient condition is the above obviously necessary condition plus the sets in $\mathcal{A}$ being pairwise disjoint.

But the above theorem gives a different sufficient condition: $\mathcal{A}$ is finite while all the sets in it are infinite.

Note that, even if $\mathcal{A}$ is finite, the above obvious necessary condition is not sufficient: consider the example $\mathcal{A}=\{\{1\},\{2,4\},\{1,2,4\}\}$.

Also note that all sets in $\mathcal{A}$ being infinite is not sufficient 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\}$.