Discrete Math · Undergraduate
Sets, Set Operations and Inclusion–Exclusion
Quick answer
A set is a collection of distinct objects. The union A ∪ B holds everything in either set, the intersection A ∩ B what they share, the difference A − B what is in A but not B, and the complement everything outside A. A set with n elements has 2ⁿ subsets. To count a union without double-counting the overlap, use inclusion–exclusion: |A ∪ B| = |A| + |B| − |A ∩ B|, with alternating corrections for three or more sets.
What you'll learn
- Use set notation and the four basic operations
- Count subsets and describe the power set
- Apply inclusion–exclusion to two and three sets
- Connect set operations to logical connectives
Collections and their operations
A set is a collection of distinct objects, its elements. We write , and means is an element of . Order and repetition do not matter: . The number of elements is .
For and :
| Operation | Meaning | Result |
|---|---|---|
| in or (or both) | ||
| in both | ||
| in but not | ||
| not in (within a universe ) | depends on |
These mirror the logical connectives: means ” or ”, is and, and the complement is not. De Morgan’s laws carry over: .
Subsets and the power set
is a subset of , written , when every element of is in . The power set of is the set of all its subsets. For it has members: , three one-element sets, three two-element sets and itself. In general a set with elements has subsets: build a subset by deciding, element by element, in or out, two choices each time.
Why inclusion–exclusion subtracts the overlap
To count , adding counts every element of the overlap twice, once in each set. Subtracting once leaves every element counted exactly once:
For three sets, subtracting the three pairwise overlaps removes the triple overlap once too often, so it is added back:
Each element ends up counted exactly once, however many of the sets it lies in.
Worked examples
Common mistakes
Practice problems
-
For and , find , and .
Answer
; ;
Full solution
The union combines both lists without repeats; the intersection keeps what is in both.
-
How many subsets does a -element set have?
Answer
Full solution
.
-
, and . Find .
Answer
Full solution
.
-
How many of the numbers to are divisible by or ?
Answer
Full solution
multiples of , of and of : .
-
Use De Morgan’s law to describe the numbers from to divisible by none of , , , and count them.
Answer
The complement of the union;
Full solution
. Example 2 counted the union.
-
In a class, take French, Spanish, German; take French and Spanish, French and German, Spanish and German, and all three. How many take at least one?
Answer
Full solution
.
-
Is ? Is ?
Answer
Yes; no
Full solution
Both elements of are in the larger set, but the set is not itself one of its elements.
-
A student counts the soccer-or-chess players in Example 1 as . What went wrong?
Answer
The students in both clubs were counted twice. The answer is .
Full solution
Inclusion–exclusion subtracts the overlap once: .
Frequently asked questions
What is the difference between union and intersection?
The union A ∪ B contains every element in A or in B. The intersection A ∩ B contains only the elements in both.
How many subsets does a set have?
A set with n elements has 2ⁿ subsets, since each element is either in a subset or not. These subsets form the power set.
What is the inclusion–exclusion principle?
For two sets, |A ∪ B| = |A| + |B| − |A ∩ B|. Adding the sizes counts the overlap twice, so it is subtracted once.
What is inclusion–exclusion for three sets?
|A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|.
How do set operations relate to logic?
Union corresponds to or, intersection to and, and complement to not. De Morgan's laws hold for sets too: the complement of A ∪ B is the intersection of the complements.