Proof
Theorem:
| Let A and B be finite sets. | ||
| n(A ∪ B) | = | n(A – B) + n(A ∩ B) + n(B – A) |
| Adding and subtracting n(A ∩ B), we have | ||
| n(A ∪ B) | = | n(A – B) + n(A ∩ B) + n(B – A) + n(A ∩ B) – n(A ∩ B) |
| But n(A – B) + n(A ∩ B) | = | n(A) |
| And n(B – A) + n(A ∩ B) | = | n(B) |
| So, we have | ||
| n(A ∪ B) | = | n(A) + n(B) – n(A ∩ B) ----- (i) |
| If A, B and C are finite sets, then | ||
| n(A ∪ B ∪ C) | = | n(A) + n(B) + n(C) – n(A ∩ B) – n(B ∩ C) – n(A ∩ C) + n(A ∩ B ∩ C) |
Proof:
| Applying (i) to n(A ∪ B ∪ C), we have | ||
| n(A ∪ B ∪ C) | = | n(A) + n(B ∪ C) – n[A ∩ (B ∪ C)] |
| Again applying (i) to n(B ∪ C), we have | ||
| n(A ∪ B ∪ C) | = | n(A) + n(B) + n(C) – n(B ∩ C) – n[A ∩ (B ∪ C)] |
| Since A ∩ (B ∪ C) | = | (A ∩ B) ∪ (A ∩ C), we have |
| n[A ∩ (B ∪ C)] | = | n(A ∩ B) + n(A ∩ C) – n[(A ∩ B) ∩ (A ∩ C)] |
| = | n (A ∩ B) + n(A ∩ C) – n(A ∩ B ∩ C) | |
| ∴ n(A ∪ B ∪ C) | = | n(A) + n(B) + n(C) – n(A ∩ B) – n(B ∩ C) – n(A ∩ C) + n(A ∩ B ∩ C) |