1
Subset is a conditional, quantified
A ⊆ B says every member of A is a member of B. Logic and Proof's rules for ∀ and → apply unchanged.
Lesson · Sets, Relations, and Functions · Sets
Subsets and Power Sets
A ⊆ B is a universally quantified conditional, which is why the empty set is a subset of everything. The power set collects all subsets, and there are exactly 2ⁿ of them.
A ⊆ B ⟺ ∀x (x ∈ A → x ∈ B)
∅ ⊆ A for every A (vacuously)
A = B ⟺ A ⊆ B and B ⊆ A the double-inclusion proof
|P(A)| = 2^|A|
Containment and its consequences
Core ideas
What this lesson establishes
Subset is defined by a conditional, and every surprising fact in this lesson comes from that conditional being vacuously true.
2
The empty set is a subset of everything
∀x (x ∈ ∅ → x ∈ B) is vacuously true, since nothing is in ∅. This is not a special case; it is the definition applied honestly.
3
Double inclusion is how set equality is proved
To show A = B, show A ⊆ B and B ⊆ A. Two conditional proofs, one in each direction — exactly like a biconditional.
The material
Containment and the power set
The definition, the proof technique it gives you, and the counting result.
Definition · Subset
A ⊆ B ("A is a subset of B") means ∀x (x ∈ A → x ∈ B). A ⊂ B or A ⊊ B means A ⊆ B and A ≠ B — a proper subset.
∈ and ⊆ are different relations and mixing them is the standard error. 1 ∈ {1, 2} and {1} ⊆ {1, 2} are both true; 1 ⊆ {1, 2} and {1} ∈ {1, 2} are both false. The first because 1 is not a set, the second because the members of {1, 2} are 1 and 2, not {1}.
Theorem · Every set contains the empty set
∅ ⊆ A for every set A.
The claim is ∀x (x ∈ ∅ → x ∈ A). The hypothesis x ∈ ∅ is false for every x, so each conditional is vacuously true, and the universal statement holds. There is nothing to check, which is exactly why it holds.
□
Theorem · Set equality by double inclusion
A = B if and only if A ⊆ B and B ⊆ A.
This is the workhorse. To prove two sets equal, take an arbitrary element of one and show it belongs to the other, then do the same in reverse. Each half is a direct proof of a conditional, which is exactly what “Direct Proof” in Logic and Proof taught.
Definition · Power set
The power set P(A) is the set of all subsets of A: P(A) = {S : S ⊆ A}. Its members are sets.
Example · Power sets of small sets
P(∅) = {∅} — one member. P({a}) = {∅, {a}} — two. P({a, b}) = {∅, {a}, {b}, {a, b}} — four. P({a, b, c}) has eight.
Theorem · The power set doubles
If |A| = n then |P(A)| = 2ⁿ.
A subset of A is determined by an independent yes/no decision for each of the n elements: is it in, or out? Two choices, made n times independently, give 2ⁿ distinct subsets, and distinct choice patterns give distinct subsets because a set is determined by its members.
Combinatorics and Counting formalises this as the product rule; Induction and Recursion proves it again by induction on n.
□
The doubling is why power sets are not something to enumerate casually. A ten-element set has 1024 subsets; a thirty-element set has over a billion. This is the same 2ⁿ as the truth table row count, and for the same reason: a subset is a truth assignment to the membership question.
Interactive
The four counting rules
Enumerated while enumeration is possible
Method
Proving a containment or an equality
One arbitrary element, followed all the way through.
1
To prove A ⊆ B, take an arbitrary x ∈ A
Then show x ∈ B, using nothing about x beyond its membership in A.
2
Unfold the definitions of both sets
If A = {x : P(x)}, then x ∈ A means P(x). The proof is then a propositional argument from P(x) to Q(x).
3
To prove A = B, do it twice
Both inclusions, each written out. Proving one and asserting the other is the incomplete answer this technique exists to prevent.
4
To disprove A ⊆ B, exhibit one element
One x with x ∈ A and x ∉ B settles it, exactly as one counterexample refutes any universal claim.
Subsets
Score 0 / 0Choose the answer you can justify.
One set, two descriptions: prove them equal
“Sets and Membership”'s set A = {x ∈ ℤ : x = 3k + 1 for some k ∈ ℤ} against B = {x ∈ ℤ : x = 3m − 2 for some m ∈ ℤ}. Two inclusions, one arbitrary element each.
(⊆) Let x ∈ A be arbitrary. Then x = 3k + 1 for some integer k.
x = 3k + 1 = 3k + 3 − 2 = 3(k + 1) − 2, and k + 1 ∈ ℤ.
So x = 3m − 2 with m = k + 1, which is the condition for x ∈ B.
(⊇) Let x ∈ B be arbitrary. Then x = 3m − 2 for some integer m.
x = 3m − 2 = 3m − 3 + 1 = 3(m − 1) + 1, and m − 1 ∈ ℤ.
So x ∈ A.
Both inclusions hold, so A = B. ∎
A containment that goes one way only:
{x ∈ ℤ : 6 | x} ⊆ {x ∈ ℤ : 3 | x} since x = 6k = 3(2k).
The reverse is FALSE: 3 is a multiple of 3 and not of 6.
Each inclusion took an arbitrary element, unfolded the set-builder condition, and rewrote until the other condition appeared — step 2 of the method, and Logic and Proof's direct proof with x ∈ A as the hypothesis. The last two lines are the other half of the technique. Having proved one inclusion it is tempting to assume the reverse; one element, 3, shows it fails, and one element is all a refutation ever needs.
Common mistakes
1
Writing ∈ where ⊆ is meant{1} ∈ {1, 2} is false and {1} ⊆ {1, 2} is true. The two symbols relate different kinds of thing, and no context makes them interchangeable.
2
Proving one inclusion and claiming equalityA ⊆ B is half of A = B. The other half needs its own argument, and is often the half that fails.
3
Forgetting A ⊆ AEvery set is a subset of itself, so ⊆ is reflexive while ⊂ is not. That difference is what makes ⊆ a partial order in “Partial Orders”.
Check your understanding
✓
Finish when double inclusion is your reflex for any set equality.
Prove {n ∈ ℤ : n = 2k + 1 for some k ∈ ℤ} = {n ∈ ℤ : n = 2m − 1 for some m ∈ ℤ} by double inclusion. Both directions are three lines in the shape of the worked example, and writing them is what makes “Set Identities and Proofs”'s chain of laws safe to use as a shortcut.
Note: |P(A)| = 2^|A| holds for infinite sets too, in the sense that P(A) is always strictly larger than A — Cantor's theorem, which “Cardinality and Countability” proves in four lines.