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 A={1,2,3,4}A = \{1, 2, 3, 4\}, and 3∈A3 \in A means 33 is an element of AA. Order and repetition do not matter: {1,2}={2,1,1}\{1, 2\} = \{2, 1, 1\}. The number of elements is ∣A∣|A|.

For A={1,2,3,4}A = \{1, 2, 3, 4\} and B={3,4,5}B = \{3, 4, 5\}:

OperationMeaningResult
A∪BA \cup Bin AA or BB (or both){1,2,3,4,5}\{1, 2, 3, 4, 5\}
A∩BA \cap Bin both{3,4}\{3, 4\}
A−BA - Bin AA but not BB{1,2}\{1, 2\}
AcA^cnot in AA (within a universe UU)depends on UU

These mirror the logical connectives: x∈A∪Bx \in A \cup B means ”x∈Ax \in A or x∈Bx \in B”, ∩\cap is and, and the complement is not. De Morgan’s laws carry over: (A∪B)c=Ac∩Bc(A \cup B)^c = A^c \cap B^c.

Subsets and the power set

AA is a subset of BB, written A⊆BA \subseteq B, when every element of AA is in BB. The power set of AA is the set of all its subsets. For {a,b,c}\{a, b, c\} it has 88 members: ∅\varnothing, three one-element sets, three two-element sets and {a,b,c}\{a, b, c\} itself. In general a set with nn elements has 2n2^n subsets: build a subset by deciding, element by element, in or out, two choices each time.

Why inclusion–exclusion subtracts the overlap

To count A∪BA \cup B, adding ∣A∣+∣B∣|A| + |B| counts every element of the overlap A∩BA \cap B twice, once in each set. Subtracting ∣A∩B∣|A \cap B| once leaves every element counted exactly once:

∣A∪B∣=∣A∣+∣B∣−∣A∩B∣|A \cup B| = |A| + |B| - |A \cap B|

For three sets, subtracting the three pairwise overlaps removes the triple overlap once too often, so it is added back:

∣A∪B∪C∣=∣A∣+∣B∣+∣C∣−∣A∩B∣−∣A∩C∣−∣B∩C∣+∣A∩B∩C∣|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|

Each element ends up counted exactly once, however many of the sets it lies in.

Worked examples

Common mistakes

Practice problems

  1. For A={2,4,6,8}A = \{2, 4, 6, 8\} and B={1,2,3,4}B = \{1, 2, 3, 4\}, find A∪BA \cup B, A∩BA \cap B and A−BA - B.

    Answer

    {1,2,3,4,6,8}\{1, 2, 3, 4, 6, 8\}; {2,4}\{2, 4\}; {6,8}\{6, 8\}

    Full solution

    The union combines both lists without repeats; the intersection keeps what is in both.

  2. How many subsets does a 44-element set have?

    Answer

    1616

    Full solution

    242^4.

  3. ∣A∣=40|A| = 40, ∣B∣=25|B| = 25 and ∣A∩B∣=10|A \cap B| = 10. Find ∣A∪B∣|A \cup B|.

    Answer

    5555

    Full solution

    40+25−1040 + 25 - 10.

  4. How many of the numbers 11 to 6060 are divisible by 33 or 44?

    Answer

    3030

    Full solution

    2020 multiples of 33, 1515 of 44 and 55 of 1212: 20+15−520 + 15 - 5.

  5. Use De Morgan’s law to describe the numbers from 11 to 100100 divisible by none of 22, 33, 55, and count them.

    Answer

    The complement of the union; 100−74=26100 - 74 = 26

    Full solution

    (A∪B∪C)c=Ac∩Bc∩Cc(A \cup B \cup C)^c = A^c \cap B^c \cap C^c. Example 2 counted the union.

  6. In a class, 2020 take French, 1515 Spanish, 1010 German; 66 take French and Spanish, 44 French and German, 33 Spanish and German, and 22 all three. How many take at least one?

    Answer

    3434

    Full solution

    20+15+10−6−4−3+2=3420 + 15 + 10 - 6 - 4 - 3 + 2 = 34.

  7. Is {1,2}⊆{1,2,3}\{1, 2\} \subseteq \{1, 2, 3\}? Is {1,2}∈{1,2,3}\{1, 2\} \in \{1, 2, 3\}?

    Answer

    Yes; no

    Full solution

    Both elements of {1,2}\{1, 2\} are in the larger set, but the set {1,2}\{1, 2\} is not itself one of its elements.

  8. A student counts the soccer-or-chess players in Example 1 as 3030. What went wrong?

    Answer

    The 55 students in both clubs were counted twice. The answer is 2525.

    Full solution

    Inclusion–exclusion subtracts the overlap once: 18+12−518 + 12 - 5.

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.

What to learn next