Book of Proof, third edition
Richard Hammack · Free textbook
Read §§1.1 and 1.3–1.5; use printed p.13 / PDF p.25 for the subset decision tree.
Open the sourceSets: the grammar of selection
Learn the notation until it becomes ordinary language.
Prerequisites: 01 · What is a number?
Understand
Objectives
- Translate membership, subset, union and intersection into words.
- Calculate a union and intersection without double-counting.
- List all subsets of a three-member set, including the empty set.
Start with something you can see
Label buttons red or round. Predict whether a red, round button belongs to the selection “red or round.” It does: mathematical “or” here includes both. A list [a,b,a] remembers order and repeats; turning it into the set {a,b} forgets both. Name the information needed before choosing a representation. The MIT set-operations passage begins at 17:14. [1]
Give the idea a precise name
A set records membership. The symbol x∈A says x is a member of A; A⊆B says every member of A is a member of B. A∪B keeps members in A or B, A∩B keeps members in both, and A∖B keeps members in A but not B. The empty set ∅ has no members. For a fixed universe E, the complement E∖A contains members of E outside A; the power set 𝒫(E) contains every subset of E.
|A∪B| = |A| + |B| − |A∩B|
Vertical bars count finite members. Union and intersection name the inclusive selection and its overlap; subtraction removes one extra count of each shared member. A complement is undefined until its universe is named.
Work one small world
With E={1,2,3,4}, A={1,2} and B={2,3}, the overlap is {2}, the union is {1,2,3}, A∖B={1}, and E∖(A∪B)={4}. The formula reads 3=2+2−1. For {a,b,c}, each of three members can be in or out, yielding 2³=8 subsets including ∅.
| Member of E | In A? | In B? | In A∪B? | In A∩B? |
|---|---|---|---|---|
| 1 | yes | no | yes | no |
| 2 | yes | yes | yes | yes |
| 3 | no | yes | yes | no |
| 4 | no | no | no | no |
Counterexample to “union means exactly one”: member 2 is in both A and B and still belongs to A∪B. Excluding it would be symmetric difference, a different operation. Also ∅ and {∅} differ: their sizes are zero and one.
THE BRIDGEA matroid will specify a family of allowed subsets of a ground set. Its elements and its subsets are different levels of description.
WHERE THIS IDEA STOPSUnion is inclusive, and complement requires a stated universe. Repetitions in lists do not become extra set members.
Experiment
Before filling the membership table for E={1,2,3,4}, predict the row for 2, which belongs to both A and B. Then test the counting formula.
Is the empty set a subset of every set? What would a counterexample have to contain?
Check & explain
For A={a,b,c} and B={c,d}, how many members are in A∪B?
With E={1,2,3,4} and A={1,2}, which is E∖A?
- {3,4}
- {2,3,4}
- {1,2}
Teach back
Give the union, intersection and difference for two overlapping button sets. Then list the eight subsets of a three-button universe.
- Include the overlap in union.
- Distinguish membership from subset containment.
- Include ∅ in the power set.
Read deeper
Lecture 1: Sets, Set Operations and Mathematical Induction
MIT OpenCourseWare · Lecture · 74 min
Start at 17:14. Watch the short core 17:14–20:00; then the longer passage 17:14–34:00. The full 74-minute lecture is available from the same link.
Open the source