Thread: Inclusion/Exclusion

I've been working on this problem for a while. Could someone show me how to connect the last part?

Let A, B, and C be finite sets. Prove:
If
then A, B, and C must be pairwise disjoint.

Here is what I have:

Suppose A, B, and C are finite sets with .

By inclusion/exclusion, we know that



By cancellation, we have:



I'm just not sure how to connect that to "Thus A, B, and C must be pairwise disjoint."

Originally Posted by absvalue

I've been working on this problem for a while. Could someone show me how to connect the last part?

Let A, B, and C be finite sets. Prove:
If
then A, B, and C must be pairwise disjoint.

Here is what I have:

Suppose A, B, and C are finite sets with .

By inclusion/exclusion, we know that



By cancellation, we have:



I'm just not sure how to connect that to "Thus A, B, and C must be pairwise disjoint."

Well, , so rearranging



since the LHS must be non negative we have so both of those terms must be 0. You can do a similar thing with to get proving the result.