How can I Prove or disprove that every uncountable collection of subsets of a countably infinite set must have two members whose intersection has at least 2010 elements?

  • $\begingroup$ Hint: How many sets of $2010$ natural numbers are there? $\endgroup$ – aschepler May 25 '14 at 18:53

This is true.

Let $A$ be this countable set and let $\binom{A}{2010}$ be the set of subsets of $A$ of size $2010$. Let $F$ be an uncountable collection of subsets of $A$.

Let $f: F\rightarrow P(\binom{A}{2010})$ be the function $f(B)=\binom{B}{2010}$ (sends a subset of $A$ to the set of subsets of size $2010$).
Assume by contrary that $f(B) \cap f(C)=\varnothing$ for every different $B, C\in F$.
Now consider the disjoint union of $f(B)$ for $B\in F$.
There is a countable number of $B$ such that $f(B)=\varnothing$ (why?) and therefore the disjoint union is uncountable. But it is a subset of $\binom{A}{2010}$ which is countable, contradiction.


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.