Subsets - When One Set Lives Inside Another

A subset is a set whose every element also belongs to another set. If every member of set A is also a member of set B, then A is a subset of B. Understanding subsets is essential for describing relationships between groups and forms the backbone of set operations.

The idea that a set could have exponentially many subsets was proved rigorously by Georg Cantor in 1891, in what is now called Cantor's theorem: for any set A, the power set P(A) always has strictly more elements than A itself, even when A is infinite. This surprising result – that there is no biggest infinity – used a technique called diagonalisation that later became central to computer science, underpinning Alan Turing's 1936 proof that some computing problems can never be solved by any algorithm. Around the same period, the British logician John Venn introduced diagrams (in an 1880 paper) that made subset relationships visually intuitive, drawing one circle entirely inside another whenever every element of the smaller set belonged to the larger one – the same picture you will use throughout this course.

Notation

A ⊆ B means “A is a subset of B” (every element of A is in B).
A ⊂ B means “A is a proper subset of B” (A ⊆ B and A ≠ B, i.e. B has at least one element not in A).
A ⊈ B means “A is not a subset of B” (at least one element of A is not in B).

Key Facts About Subsets

Every set is a subset of itself: A ⊆ A.
The empty set is a subset of every set: ∅ ⊆ A for any set A.
If A ⊆ B and B ⊆ A, then A = B.
A set with n elements has exactly 2ⁿ subsets (including ∅ and the set itself).

Listing All Subsets

To list every subset of a set, work systematically: start with ∅, then all single-element subsets, then all two-element subsets, and so on up to the full set.

Worked Examples

A = {1, 2, 3}. List all subsets of A and count them.

Subsets with 0 elements: ∅
Subsets with 1 element: {1}, {2}, {3}
Subsets with 2 elements: {1,2}, {1,3}, {2,3}
Subsets with 3 elements: {1,2,3}
Total: 8 subsets = 2³ ✓

B = {2, 4, 6, 8, 10}. Is {2, 6} ⊆ B? Is {2, 5} ⊆ B? Is B ⊂ B?

{2, 6} ⊆ B: True – both 2 and 6 are in B.
{2, 5} ⊆ B: False – 5 is not in B.
B ⊂ B: False – B ⊆ B is true, but B ⊂ B (proper subset) requires B ≠ B, which is never true.

How many subsets does the set {a, b, c, d} have? How many are proper subsets?

n = 4 elements. Total subsets = 2⁴ = 16.
Proper subsets (excluding the set itself) = 16 − 1 = 15.

P = {even numbers}, Q = {multiples of 4}. Is Q ⊆ P? Is P ⊆ Q?

Every multiple of 4 (4, 8, 12, …) is even, so Q ⊆ P (in fact Q ⊂ P).
P ⊆ Q: False – 2 is even but not a multiple of 4.

Power Set

The power set of A, written P(A), is the set of all subsets of A.
If |A| = n, then |P(A)| = 2ⁿ.

Example: A = {x, y}. P(A) = {∅, {x}, {y}, {x,y}}. |P(A)| = 4 = 2².

Key Takeaways

A ⊆ B: every element of A is also in B.
A ⊂ B (proper subset): A ⊆ B and A ≠ B.
∅ is a subset of every set; every set is a subset of itself.
A set with n elements has 2ⁿ subsets total and 2ⁿ − 1 proper subsets.

Practice: Counting and Checking Subsets

Counting Subsets