Exercise 245Combinatorics › Inclusion-exclusionHigh schoolAdded 3 Nov 2026

Proof of the two-set formula

#IE#two sets#proof

Statement

Prove that $|A\cup B|=|A|+|B|-|A\cap B|$ .

Hint

Partition $A\cup B$ into three disjoint parts: $A\setminus B$ , $A\cap B$ , $B\setminus A$ .

Show solutionHide solution

Partition. $A\cup B=(A\setminus B)\cup(A\cap B)\cup(B\setminus A)$ (disjoint).

Sizes. $|A|=|A\setminus B|+|A\cap B|$ , $|B|=|B\setminus A|+|A\cap B|$ .

Sum. $|A|+|B|=|A\setminus B|+|B\setminus A|+2|A\cap B|=|A\cup B|+|A\cap B|$ .

Conclusion. $|A\cup B|=|A|+|B|-|A\cap B|$ .