• Advanced
  • About 15 min
  • 5 practice questions

Set algebra: identities, symmetric difference and power sets

Use set identities, De Morgan's laws, symmetric difference and power-set counting to simplify expressions and count subsets quickly.

If something looks wrong, please tell us.

At the advanced level, set questions are rarely about listing elements. They ask you to simplify a long expression, to find a count from a few given numbers, or to count subsets with a condition attached. All three become fast once a small toolkit of identities is automatic. This lesson builds that toolkit and shows the counting trick that turns many subset questions into a single power of 2 or 3.

The identities that do most of the work

Write A' for the complement of A and A − B for the elements of A that are not in B, so A − B = A ∩ B'. With that one translation, almost every identity follows from De Morgan's laws: (A ∪ B)' = A' ∩ B' and (A ∩ B)' = A' ∪ B'. Applied inside a difference, they give the two forms examiners love: A − (B ∪ C) = (A − B) ∩ (A − C) and A − (B ∩ C) = (A − B) ∪ (A − C). Notice that the union and the intersection swap when they come out of the bracket.

  • A ⊆ B is equivalent to each of: A ∪ B = B, A ∩ B = A, A − B = ∅, B' ⊆ A'.
  • Distributive laws: A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) and A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C).
  • Symmetric difference: A Δ B = (A − B) ∪ (B − A) = (A ∪ B) − (A ∩ B).
  • Count: n(A Δ B) = n(A) + n(B) − 2 n(A ∩ B).

Power sets and the choice-per-element method

If n(A) = n, the power set P(A) has 2^n members, because each element independently chooses 'in' or 'out'. The same idea counts conditional subsets. Subsets that must contain one fixed element: that element has no choice, the other n − 1 have two choices, giving 2^(n−1). Subsets that contain x but not y: 2^(n−2). Proper subsets: 2^n − 1. Non-empty proper subsets: 2^n − 2.

The method extends to pairs of subsets. To count ordered pairs (X, Y) with X ⊆ Y ⊆ A, give each element three choices: in neither, in Y only, or in both X and Y. The answer is 3^n. Ordered pairs of disjoint subsets (X ∩ Y = ∅) also number 3^n: each element is in X only, in Y only, or in neither. Two more facts about power sets: P(A) ∩ P(B) = P(A ∩ B) always, but P(A) ∪ P(B) equals P(A ∪ B) only when one of A, B contains the other.

Worked example 1: verify a difference identity

Let A = {1, 2, 3, 4, 5, 6}, B = {2, 4, 6, 8} and C = {3, 6, 9}. Left side: B ∪ C = {2, 3, 4, 6, 8, 9}, so A − (B ∪ C) = {1, 5}. Right side: A − B = {1, 3, 5} and A − C = {1, 2, 4, 5}; their intersection is {1, 5}. Both sides agree, confirming that the union inside becomes an intersection outside. If you had wrongly used a union on the right you would get {1, 2, 3, 4, 5}, a typical wrong option.

Worked example 2: counting from the symmetric difference

Given n(A) = 8, n(B) = 6 and n(A Δ B) = 8, find n(A ∪ B). From n(A Δ B) = n(A) + n(B) − 2 n(A ∩ B): 8 = 14 − 2 n(A ∩ B), so n(A ∩ B) = 3. Then n(A ∪ B) = 8 + 6 − 3 = 11. Check: the union minus the intersection is 11 − 3 = 8, which matches the symmetric difference.

Worked example 3: subsets with a size condition

How many subsets of a 6-element set have at least 2 elements? Count the complement: there is 1 empty subset and 6 one-element subsets. The total is 2^6 = 64, so the answer is 64 − 1 − 6 = 57. Subtracting what you do not want is almost always faster than adding what you do.

Inside a difference, De Morgan swaps the operation: A − (B ∪ C) = (A − B) ∩ (A − C). For subset counts, give each element its choices and multiply: 2 choices give 2^n, 3 choices give 3^n.

— Rule to remember

Key takeaways

Translate every difference into an intersection with a complement and De Morgan's laws do the rest. Use n(A Δ B) = n(A) + n(B) − 2 n(A ∩ B) to move between counts. For any subset-counting question, ask how many independent choices each element has; fixed elements contribute a factor of 1, and the complement count is often the quickest route.

Check your understanding

  1. 1. A has 5 elements, and x and y are two of them. How many subsets of A contain x but not y?

    1. 16
    2. 8
    3. 32
    4. 4
    Show answer

    Answer: B. x must be in and y must be out, so they have no choice. The remaining 3 elements each have 2 choices: 2^3 = 8.

  2. 2. Which expression is always equal to A − (B ∩ C)?

    1. (A − B) ∩ (A − C)
    2. (A ∪ B) − C
    3. (A − B) ∪ (A − C)
    4. A ∩ B ∩ C'
    Show answer

    Answer: C. A − (B ∩ C) = A ∩ (B ∩ C)' = A ∩ (B' ∪ C') = (A ∩ B') ∪ (A ∩ C') = (A − B) ∪ (A − C). The intersection inside becomes a union outside.

  3. 3. n(A) = 10, n(B) = 7 and n(A ∪ B) = 13. Find n(A Δ B).

    1. 13
    2. 5
    3. 17
    4. 9
    Show answer

    Answer: D. n(A ∩ B) = 10 + 7 − 13 = 4. Then n(A Δ B) = n(A ∪ B) − n(A ∩ B) = 13 − 4 = 9. Check: 10 + 7 − 2 × 4 = 9.

  4. 4. For sets A and B, when is P(A) ∪ P(B) = P(A ∪ B)?

    1. Exactly when A ⊆ B or B ⊆ A
    2. Exactly when A and B are disjoint
    3. Only when A = B
    4. Always
    Show answer

    Answer: A. If neither contains the other, pick a in A − B and b in B − A. The set {a, b} is in P(A ∪ B) but in neither P(A) nor P(B). If A ⊆ B, then A ∪ B = B and P(A) ⊆ P(B), so the union is P(B) = P(A ∪ B).

  5. 5. A has 4 elements. How many ordered pairs (X, Y) of subsets of A satisfy X ⊆ Y?

    1. 16
    2. 64
    3. 81
    4. 256
    Show answer

    Answer: C. Each element has 3 choices: in neither set, in Y only, or in both X and Y (it cannot be in X only). So the count is 3^4 = 81.

Privacy · Terms · Refunds · Delivery