What is a set?
A set is a well-defined collection of distinct objects. "Well-defined" means we can always decide whether a given object belongs to it.
"The vowels of the English alphabet" is a set.
"The five best cricketers in India" is not a set, because "best" is a matter of opinion.
If a belongs to set A we write a ∈ A. If not, a ∉ A.
Representing sets
Roster (tabular) form: list the elements in braces. A = {a, e, i, o, u}. The order does not matter and repeated elements are written only once.
Set-builder form: describe the property the elements share. A = {x : x is a vowel of the English alphabet}.
Standard sets: N (natural numbers), Z (integers), Q (rationals), R (reals).
Types of sets
Type | Meaning | Example |
|---|---|---|
Empty (null) set ∅ | no elements | {x : x ∈ N, x < 1} |
Singleton | exactly one element | {0} |
Finite | a countable number of elements | {1, 2, 3} |
Infinite | not finite | N |
Equal sets | exactly the same elements | {1, 2} = {2, 1} |
Equivalent sets | the same number of elements | {a, b} and {1, 2} |
Careful: {0} is not the empty set. It has one element, 0.
Subsets and power sets
A is a subset of B (A ⊆ B) if every element of A is also in B.
Every set is a subset of itself, and ∅ is a subset of every set.
If A ⊆ B and A ≠ B, then A is a proper subset of B (A ⊂ B).
The power set P(A) is the set of all subsets of A. If A has n elements, P(A) has 2ⁿ elements.
For A = {1, 2}: P(A) = {∅, {1}, {2}, {1, 2}}, which has 2² = 4 elements.
Intervals are subsets of R: (a, b) = {x : a < x < b} excludes the endpoints, and [a, b] includes them.
Operations on sets
Let U be the universal set, the set containing everything under discussion.
Operation | Notation | Contains |
|---|---|---|
Union | A ∪ B | elements in A or B (or both) |
Intersection | A ∩ B | elements in both A and B |
Difference | A − B | elements in A but not in B |
Complement | A′ | elements of U not in A |
If A ∩ B = ∅, the sets are disjoint.
Example. U = {1, 2, …, 10}, A = {2, 4, 6, 8}, B = {1, 2, 3, 4, 5}.
A ∪ B = {1, 2, 3, 4, 5, 6, 8}
A ∩ B = {2, 4}
A − B = {6, 8}
A′ = {1, 3, 5, 7, 9, 10}
Laws of set algebra
Commutative: A ∪ B = B ∪ A, and A ∩ B = B ∩ A.
Associative: (A ∪ B) ∪ C = A ∪ (B ∪ C), and the same for ∩.
Distributive: A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C).
De Morgan's laws: (A ∪ B)′ = A′ ∩ B′ and (A ∩ B)′ = A′ ∪ B′.
Counting with Venn diagrams
For finite sets A and B, with n(·) meaning "number of elements":
n(A ∪ B) = n(A) + n(B) − n(A ∩ B)
The overlap is subtracted because it would otherwise be counted twice.
Example. In a class of 40 students, 25 like cricket, 18 like football and 7 like both. How many like neither?
n(C ∪ F) = 25 + 18 − 7 = 36. So 40 − 36 = 4 students like neither.
How many like only cricket? 25 − 7 = 18.
For three sets:
n(A ∪ B ∪ C) = n(A) + n(B) + n(C) − n(A ∩ B) − n(B ∩ C) − n(A ∩ C) + n(A ∩ B ∩ C)