Sets (Advanced)

Sets collect objects; counting formulas and Venn diagrams turn survey problems into simple arithmetic on the regions of the diagram.

Key ideas

φ is a subset of every set, and every set is a subset of itself. A proper subset leaves out at least one element.
The power set P(A) is the set of all subsets of A. Its elements are sets: {a} ∈ P(A), but a is not.
A − B is in A but not in B; A′ = U − A is everything in U outside A.
Fill a Venn diagram from the inside out: the region in all three sets first, then the "only two" regions, then the "only one" regions.
The overlap n(A ∩ B) is smallest when n(A ∪ B) is as big as U allows, and largest when the smaller set lies inside the larger.
Each element of a set is either in a subset or out of it, which is why the number of subsets is a power of 2.

Remember

Subsets of a set with n elements	n[P(A)] = 2ⁿ; proper subsets 2ⁿ − 1
Two sets	n(A ∪ B) = n(A) + n(B) − n(A ∩ B)
Only A	n(A − B) = n(A) − n(A ∩ B)
Exactly one of A, B	n(A) + n(B) − 2n(A ∩ B)
Neither	n(A′ ∩ B′) = n(U) − n(A ∪ B)
Three sets	n(A ∪ B ∪ C) = n(A) + n(B) + n(C) − n(A ∩ B) − n(B ∩ C) − n(C ∩ A) + n(A ∩ B ∩ C)
Exactly two (everyone in at least one)	n(A) + n(B) + n(C) − n(A ∪ B ∪ C) − 2n(A ∩ B ∩ C)

Watch out

Adding n(A) and n(B) without taking away the common part, so it is counted twice.
Using the number in A ∩ B as the number in "A and B only": in three-set problems, take away the region in all three first.
Forgetting φ, or the set itself, when listing a power set.

Worked example

Every one of 73 customers chose at least one of shampoo A, shampoo B and shampoo C: 35 chose shampoo A, 32 shampoo B, 46 shampoo C; 11 chose shampoo A and shampoo B, 17 chose shampoo B and shampoo C, 21 chose shampoo C and shampoo A. Find (a) how many chose all three (b) how many chose exactly one.

Working: (a) 73 = 113 − 49 + n(all three); (b) only shampoo A = 35 − 11 − 21 + 9 = 12, and so on: 12 + 13 + 17

Answer: (a) 9; (b) 42