Prove the claim

Question

Prove the following Claim:

"Claim: Suppose sets $A$ and $B$ are finite subsets of a finite set $U$

Then $|A| \cap |B| \ge |A| + |B| - |U|$"

By subtracting $|A| \cap |B|$ from both sides and adding $|U|$ to both sides I get

$|U| \ge |A| + |B| - |A \cap B|$

which results in (by the inclusion-exclusion principle)

$|U| \ge |A \cup B|$

Am I going about this correctly? Is my result enough to prove the claim?

That's how I would have done it. What do you mean is it enough? Can the size of $A\cup B$ be bigger than the size of $U$? — user2345215, Apr 08 '14 at 00:17

André Nicolas · Accepted Answer · 2014-04-08T00:39:35.980

0

In principle the argument is not correct. You have shown correctly that if what you hope is true is indeed true, then we reach an assertion that is definitely true. But you need to check that the steps you took are reversible. This can be done. A correct writeup might go as follows.
We have $$|A\cup B|=|A|+|B|-|A\cap B|.$$ Clearly $|U|\ge |A\cup B|$. It follows that $$|U|\ge |A|+|B|-|A\cap B|.$$ Now manipulation gives the desired result.

edited Apr 08 '14 at 00:39

answered Apr 08 '14 at 00:28

André Nicolas

507,029

Thank you very much. I didn't think of it that way. – WhatsAGuitar Apr 08 '14 at 13:09
You are welcome. Note that the ingredients were exactly the same as yours. Yours could have also been made correct by observing that your implications (steps) are reversible. – André Nicolas Apr 08 '14 at 14:38

Prove the claim

1 Answers1