• Foundation
  • About 13 min
  • 5 practice questions

Subsets, power sets and the universal set

Decide when one set is a subset of another, count all subsets and proper subsets with 2^n, build a power set and write intervals as subsets of R.

If something looks wrong, please tell us.

Once you can write a set, the next question is how sets sit inside each other. The idea of a subset leads straight to one of the most used counting results in the chapter: a set with n elements has 2^n subsets. This lesson builds that result from a small example so that you can see where the formula comes from, and shows the difference between 'belongs to' and 'is a subset of', which causes many careless errors.

Subsets

A set A is a subset of a set B, written A ⊆ B, if every element of A is also an element of B. For example {2, 4} ⊆ {1, 2, 3, 4}. If even one element of A is missing from B, then A is not a subset, written A ⊄ B. Two facts follow directly from the definition. Every set is a subset of itself, A ⊆ A, because each of its elements is certainly in it. The empty set is a subset of every set, because it has no element that could fail the test.

If A ⊆ B and A ≠ B, then A is a proper subset of B, written A ⊂ B. So {2, 4} is a proper subset of {1, 2, 3, 4}, while {1, 2, 3, 4} is a subset of itself but not a proper one. Finally, A = B exactly when A ⊆ B and B ⊆ A; this is the standard way to prove two sets equal.

Belongs to versus subset of

The symbol ∈ links an element to a set; the symbol ⊆ links a set to a set. If A = {1, 2, {3}}, then 1 ∈ A and {3} ∈ A, because {3} is itself listed as an element. But 3 ∉ A, since the number 3 is not listed on its own, and so {3} is not a subset of A. On the other hand {1, 2} ⊆ A and {{3}} ⊆ A. When an element is itself a set, read the brackets slowly.

Power set and the 2^n rule

The power set of A, written P(A), is the set of all subsets of A. Count them by thinking about each element separately: when you build a subset, every element either goes in or stays out. That is two choices per element, and the choices are independent, so a set with n elements has 2 × 2 × ... × 2 = 2^n subsets. These 2^n subsets include both the empty set and the whole set.

  • Number of subsets (including ∅ and A itself): 2^n.
  • Number of proper subsets (including ∅, excluding A): 2^n − 1.
  • Number of non-empty proper subsets (excluding both ∅ and A): 2^n − 2.
  • n(P(∅)) = 2^0 = 1, since the only subset of ∅ is ∅ itself.

Worked example 1: listing every subset

List the subsets of A = {a, b, c}. Group them by size. Size 0: ∅. Size 1: {a}, {b}, {c}. Size 2: {a, b}, {a, c}, {b, c}. Size 3: {a, b, c}. That is 1 + 3 + 3 + 1 = 8 subsets, and 2^3 = 8 agrees. So P(A) has 8 members. Of these, 7 are proper subsets (all except A) and 6 are non-empty proper subsets.

Worked example 2: counting without listing

A set has 4 elements. How many subsets, proper subsets and non-empty proper subsets does it have? Subsets: 2^4 = 16. Proper subsets: 16 − 1 = 15. Non-empty proper subsets: 16 − 2 = 14. Working backwards also helps: if a power set has 64 members, then 2^n = 64 gives n = 6.

The universal set and intervals

In any discussion we fix a large set that contains all the sets being talked about. It is called the universal set U. When studying numbers on the real line, U is often R, and certain subsets of R are written as intervals. For real numbers a < b, the open interval (a, b) = {x ∈ R : a < x < b} leaves out both ends, the closed interval [a, b] = {x ∈ R : a ≤ x ≤ b} keeps both, and the half-open intervals [a, b) and (a, b] keep one end each. A square bracket means the end point is included; a round bracket means it is not.

A set with n elements has 2^n subsets, counting both ∅ and the set itself. Remove the set itself for proper subsets (2^n − 1); remove ∅ as well for non-empty proper subsets (2^n − 2).

— Rule to remember

Key takeaways

A ⊆ B means every element of A is in B; ∅ and A itself are always subsets of A. Use ∈ for an element and ⊆ for a set. Each element has two choices, in or out, which gives 2^n subsets. Read every subset question for what it includes: all subsets, proper subsets or non-empty proper subsets give three different answers.

Check your understanding

  1. 1. How many subsets does {1, 2, 3, 4, 5} have, counting both the empty set and the set itself?

    1. 25
    2. 32
    3. 31
    4. 10
    Show answer

    Answer: B. Each of the 5 elements is either in or out of a subset, so there are 2^5 = 32 subsets.

  2. 2. A set has 3 elements. How many proper subsets does it have (counting the empty set but not the set itself)?

    1. 7
    2. 8
    3. 6
    4. 3
    Show answer

    Answer: A. Total subsets 2^3 = 8. Leaving out the set itself gives 8 − 1 = 7 proper subsets.

  3. 3. Let A = {1, 2, {3}}. Which statement is true?

    1. {3} ∈ A
    2. 3 ∈ A
    3. {3} ⊆ A
    4. {1, 2} ∈ A
    Show answer

    Answer: A. {3} is listed as an element, so {3} ∈ A. The number 3 is not an element, so 3 ∉ A and {3} ⊄ A. {1, 2} is a subset of A, not an element of it.

  4. 4. The power set of A has 64 members. How many elements does A have?

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

    Answer: C. n(P(A)) = 2^n = 64 = 2^6, so n = 6.

  5. 5. Which describes the interval [2, 5)?

    1. {x ∈ R : 2 ≤ x < 5}
    2. {x ∈ R : 2 < x ≤ 5}
    3. {x ∈ R : 2 < x < 5}
    4. {x ∈ R : 2 ≤ x ≤ 5}
    Show answer

    Answer: A. A square bracket includes the end point and a round bracket excludes it, so 2 is included and 5 is not.

Privacy · Terms · Refunds · Delivery