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:


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

  • 1
    $\begingroup$ 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$. $\endgroup$ – Douglas Ulrich Mar 27 '17 at 23:04
  • $\begingroup$ @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. $\endgroup$ – Sam Hopkins Mar 27 '17 at 23:57

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

| cite | improve this answer | |
  • $\begingroup$ Thanks for the very simple answer to my too naive question! $\endgroup$ – Sam Hopkins Mar 28 '17 at 0:18

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.