Suppose we are given three finite, non-empty sets $A, B, C$ such that $|C|\leq |A| \leq |B|$. Is it always true that $\frac{|A\cap C|}{|A|} + \frac{|B\cap C|}{|B|} \leq 1 + \frac{|A\cap B|}{|B|}$?

I have tried countless examples for days and I haven't found any counterexample so far... This is just a curious question. But if it's true, there has to be a proof, right?

  • $\begingroup$ Since these cardinals are necessarily finite (otherwise the division has no meaning), the question is not a set theory question, but rather a combinatorial question. $\endgroup$ – Asaf Karagila Sep 11 at 17:52
  • $\begingroup$ "But if it's true, there has to be a proof, right?" Not necessarily. Gödel's theorems guarantee the existence of statements that are true but not provable. But in this simple case, I think it is safe to say that yes, if it's true then there has to be a proof. I'm working on it:-) $\endgroup$ – TonyK Sep 11 at 18:10

As Asaf Karagila already noted, this is not a set theory question (nor a combinatorial one, I'd say), since it basically follows from an algebraic approach.

Define $|A|=a, \ |B|=b, \ |C|=c$ and $|A\cap B\cap C|=x.$ Also, let $|(A\cap B)\setminus C|=r,$ $|(A\cap C)\setminus B|=s$ and $|(B\cap C)\setminus A|=t.$ We can now rewrite the given inequality as $$\frac{s+x}{a}+\frac{t+x}{b}\leq 1+\frac{r+x}{b}\implies \frac{s+x}{a}+\frac{t-r}{b}\leq 1\implies b(s+x)+a(t-r)\leq ab.$$ Since all the variables are non-negative and $c\leq a\leq b,$ we have that $$b(s+x)+a(t-r)\leq b(s+x)+at\leq b(s+x)+bt=b(s+t+x).$$ However, notice that $s+t+x\leq c$ since $(A\cap C)\setminus B, \ (B\cap C)\setminus A$ and $A\cap B\cap C$ are disjoint subsets of $C,$ thus $b(s+t+x)\leq bc\leq ab,$ as desired.

  • $\begingroup$ This is beautiful! It never occurred to me to consider those extra cardinals. You have ended my frustration, sir. $\endgroup$ – Castor Sep 11 at 18:38

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.