Read through concept notes with worked explanations and diagrams, chapter by chapter.
Tip: use←→to switch concepts
Concept 02 / 10Sets, Relations and Functions
Set Operations, De Morgan's Laws and the Inclusion-Exclusion Principle
Union, intersection, difference, complement and symmetric difference, the algebra of sets and element-chasing proofs, and the inclusion-exclusion formulas for two and three sets, including 'exactly one', maximum and minimum overlap problems.
Figure 1
Once sets exist, we combine them. Work inside a universal set U that contains everything under discussion. The basic operations are defined by what they do to a single element x, and this element-wise view is the key to every proof in the topic.
Union: A∪B={x:x∈A or x∈B}, where 'or' is inclusive. Intersection: A∩B={x:x∈A and x∈B}. If A∩B=ϕ the sets are disjoint. Difference: A−B={x:x∈A,x∈/B}, which equals A∩B′. Complement: A′=U−A. Symmetric difference: AΔB=(A−B)∪(B−A), the elements in exactly one of the two sets.
The algebra of sets mirrors the algebra of logic, with ∪ as 'or', ∩ as 'and' and complement as 'not'. Commutative laws: A∪B=B∪A and A∩B=B∩A. Associative laws: (A∪B)∪C=A∪(B∪C) and likewise for ∩. Distributive laws, which go both ways (unlike ordinary arithmetic): A∩(B∪C)=(A∩B)∪(A∩C) and A∪(B∩C)=(A∪B)∩(A∪C). Identity and domination: A∪ϕ=A, A∩U=A, A∩ϕ=ϕ, A∪U=U. Complement laws: A∪A′=U, A∩A′=ϕ, (A′)′=A.
De Morgan's laws are the most tested identities: (A∪B)′=A′∩B′ and (A∩B)′=A′∪B′. In words, the complement turns unions into intersections and vice versa. Proof of the first by element chasing: x∈(A∪B)′⟺x∈/A∪B⟺ it is not true that (x∈A or x∈B) ⟺x∈/A and x∈/B⟺x∈A′∩B′. Every step is reversible, so the sets are equal. Relative versions hold too: A−(B∪C)=(A−B)∩(A−C) and A−(B∩C)=(A−B)∪(A−C).
Counting: inclusion-exclusion. For finite sets, adding n(A) and n(B) counts every element of A∩B twice, so we subtract it once:
n(A∪B)=n(A)+n(B)−n(A∩B). The Venn diagram shows the three disjoint regions A−B, A∩B and B−A whose sizes add up to n(A∪B). For three sets the same logic gives
n(A∪B∪C)=n(A)+n(B)+n(C)−n(A∩B)−n(B∩C)−n(C∩A)+n(A∩B∩C).
Why add the triple intersection back? An element in all three sets is counted 3 times in the first group, subtracted 3 times in the second group, so it has been counted 0 times; adding n(A∩B∩C) restores it to exactly once. The general principle alternates signs over intersections of 1,2,3,… sets, and it underlies the formulas for derangements and onto functions later in the course.
Region formulas that follow directly: n(A−B)=n(A)−n(A∩B); the number in exactly one of A,B is n(AΔB)=n(A)+n(B)−2n(A∩B); the number in neither is n(U)−n(A∪B), which equals n(A′∩B′) by De Morgan. For three sets, the number in exactly one set is ∑n(A)−2∑n(A∩B)+3n(A∩B∩C), and the number in exactly two sets is ∑n(A∩B)−3n(A∩B∩C).
Bounds on overlaps. Since n(A∪B)≤n(U), we get n(A∩B)≥n(A)+n(B)−n(U), and trivially n(A∩B)≥0. Since A∩B sits inside both sets, n(A∩B)≤min(n(A),n(B)). So
max(0,n(A)+n(B)−n(U))≤n(A∩B)≤min(n(A),n(B)).
The minimum is reached when the two sets are spread out as much as possible, the maximum when the smaller set sits entirely inside the larger.
Key Takeaways:
- A−B=A∩B′; AΔB=(A∪B)−(A∩B).
- De Morgan: (A∪B)′=A′∩B′ and (A∩B)′=A′∪B′.
- Both distributive laws hold: ∩ over ∪ and ∪ over ∩.
- n(A∪B)=n(A)+n(B)−n(A∩B); the three-set version adds back n(A∩B∩C).
- Exactly one of A,B: n(A)+n(B)−2n(A∩B).
- max(0,n(A)+n(B)−n(U))≤n(A∩B)≤min(n(A),n(B)).
- To prove an identity, either chase an element through both sides or reduce both sides to the same expression using the laws. A Venn diagram illustrates an identity but does not prove it.
- Pitfall: A−B=B−A in general, and (A−B)∪B=A∪B, not A.
Brain-Teaser 1: In a class of 100 students, 60 like Mathematics and 50 like Physics. What are the least and greatest possible numbers who like both? If every student likes at least one of the two, what is the answer?
Solution: With n(U)=100, n(M)=60 and n(P)=50, the lower bound is n(M∩P)≥60+50−100=10, reached when nobody dislikes both. The upper bound is min(60,50)=50, reached when every Physics lover also likes Mathematics. So the overlap lies between 10 and 50. If every student likes at least one subject, then n(M∪P)=100 is forced, and n(M∩P)=60+50−100=10 exactly. The extra condition collapses the range to a single value.
Brain-Teaser 2: Prove that A−(B∪C)=(A−B)∩(A−C) without drawing a diagram.
Solution: Rewrite differences as intersections with complements and apply De Morgan. A−(B∪C)=A∩(B∪C)′=A∩(B′∩C′). Because ∩ is associative, commutative and idempotent (A=A∩A), this equals (A∩B′)∩(A∩C′)=(A−B)∩(A−C). The logic behind it: to be outside 'B or C', an element must be outside B and outside C. Converting '−' into '∩ complement' is the single most useful move in set algebra, because it turns every difference into something the standard laws can act on.
Brain-Teaser 3: How many integers from 1 to 1000 are divisible by at least one of 2, 3, 5? How many are divisible by none?
Solution: Let Ak be the multiples of k in 1 to 1000, so n(Ak)=⌊1000/k⌋. A number is divisible by both 2 and 3 exactly when it is divisible by 6, so the intersections are multiples of the least common multiples. Then n(A2)=500, n(A3)=333, n(A5)=200, n(A6)=166, n(A10)=100, n(A15)=66 and n(A30)=33. Inclusion-exclusion gives 500+333+200−166−100−66+33=734. So 734 are divisible by at least one, and 1000−734=266 by none. As a sanity check, the density of integers coprime to 30 is (1−21)(1−31)(1−51)=154, and 154×1000≈266.7, which agrees.
