Sets are the language the rest of mathematics is written in: relations, functions, sequences, probability, and the formal models of computation are all built from them. Chapter 6 does two things at once. It gives you the vocabulary (subset, union, intersection, complement, power set, product, partition), and it teaches the element method, the single proof technique that settles almost every set fact by reducing it to the logic of Chapters 2 and 3.
The thread that runs through it. A set identity such as (A ∪ B)ᶜ = Aᶜ ∩ Bᶜ is the logical equivalence ¬(p ∨ q) ≡ ¬p ∧ ¬q wearing different clothes. By 6.4 this is made precise: logic, sets, and bits are all the same algebraic structure, a Boolean algebra. That is why the chapter ends where digital hardware begins.
Three facts that the notation hides. (1) Order does not matter: {a, b, c} = {c, a, b}. (2) Repetition does not matter: {a, a, b} = {a, b}, a set has no multiplicities. (3) A set may be an element of another set: {1, {1}} has two elements, 1 and the set {1}. In particular a one-element set is not the same as its element: {a} ≠ a.
A set-builder can be empty: {x ∈ ℝ | 3 < x < 2} = ∅, since no real number is both greater than 3 and less than 2.
(a) C ⊆ D is true. Suppose x ∈ C, so x = 6r − 5 for some integer r. Then x = 6r − 6 + 1 = 3(2r − 2) + 1. Let s = 2r − 2, an integer; then x = 3s + 1, so x ∈ D. Hence C ⊆ D.
(b) D ⊆ C is false. Take x = 4 (from s = 1: 3·1 + 1 = 4), so 4 ∈ D. If 4 ∈ C then 4 = 6r − 5, forcing r = 3/2, not an integer. So 4 ∉ C, and this one witness disproves the universal claim.
ℙ(∅) = {∅}: the empty set has exactly one subset, itself. Size 1 = 2⁰. (Note this is not the empty set; it has one element.)
ℙ({∅}) = {∅, {∅}}: the set {∅} has one element, so two subsets. Size 2 = 2¹.
ℙ({a, b}) = {∅, {a}, {b}, {a, b}}. Size 4 = 2².
The goal of 6.2 is to prove set facts rigorously, not by shading a Venn diagram. A Venn picture is a guide; the proof is the element argument. The engine is a small set of procedural definitions, the rules that turn membership in a compound set into a logical sentence.
(⊆) Suppose x ∈ A ∩ (B ∪ C). Then x ∈ A, and x ∈ B ∪ C, i.e. x ∈ B or x ∈ C.
Case x ∈ B: then x ∈ A and x ∈ B, so x ∈ A ∩ B. Case x ∈ C: then x ∈ A ∩ C. Either way x ∈ (A ∩ B) ∪ (A ∩ C).
(⊇) Suppose x ∈ (A ∩ B) ∪ (A ∩ C). Then x ∈ A ∩ B or x ∈ A ∩ C; in both cases x ∈ A, and x ∈ B or x ∈ C, so x ∈ A and x ∈ B ∪ C, i.e. x ∈ A ∩ (B ∪ C).
Both containments hold, so the two sets are equal. ■
The mistake. A ⊆ B is a universal conditional, ∀x, (x ∈ A → x ∈ B), not the existential “there is an x with x ∈ A and x ∈ B.” The flawed proof misreads both subset relations as existential and silently reuses the same x for two unrelated ones. Even a genuine x ∈ A ∩ C would not establish the universal A ⊆ C.
Correct proof. Suppose A ⊆ B and B ⊆ C, and let x be a particular but arbitrarily chosen element of A. Since A ⊆ B, x ∈ B; since B ⊆ C, x ∈ C. As x was arbitrary, every element of A is in C, so A ⊆ C. ■
Two new skills. First, disproving a proposed set property: a claim “for all sets A, B, C…” is universal, so one counterexample kills it. Second, the algebraic method: instead of arguing element by element, transform one side into the other using the identities of Theorem 6.2.2, citing one law per step.
| (A ∩ B) ∪ (A ∩ Bᶜ) | |
| = A ∩ (B ∪ Bᶜ) | distributive law |
| = A ∩ U | complement law |
| = A | identity law |
So (A ∩ B) ∪ (A ∩ Bᶜ) = A: splitting A by whether an element is in B and rejoining recovers all of A.
Logic, sets, and bits keep obeying the same laws: commutative, associative, distributive, identity, complement, De Morgan. Boolean algebra is the abstract structure that captures exactly those laws once, so a theorem proved for the abstract structure holds for all three at once.
| Axiom | for + | for · |
|---|---|---|
| Commutative | a + b = b + a | a · b = b · a |
| Associative | (a + b) + c = a + (b + c) | (a · b) · c = a · (b · c) |
| Distributive | a + (b · c) = (a + b) · (a + c) | a · (b + c) = (a · b) + (a · c) |
| Identity | a + 0 = a | a · 1 = a |
| Complement | a + a̅ = 1 | a · a̅ = 0 |
The point is not three separate theories but one structure with three readings. Read the table across a row to translate any statement between logic, sets, and digital circuits; a law proved once from the axioms holds in all three at once. This is why De Morgan and the distributive law keep reappearing.
| Boolean algebra | Logic (Ch 2–3) | Sets (this chapter) | Bits / gates |
|---|---|---|---|
| a + b | p ∨ q (or) | A ∪ B (union) | OR |
| a · b | p ∧ q (and) | A ∩ B (intersection) | AND |
| a̅ | ¬p (not) | Aᶜ (complement) | NOT |
| 0 | F (false) | ∅ (empty set) | 0 |
| 1 | T (true) | U (universe) | 1 |
So “De Morgan” is the same fact three times: ¬(p ∨ q) ≡ ¬p ∧ ¬q, (A ∪ B)ᶜ = Aᶜ ∩ Bᶜ, and the rule for combining NOR gates. Telling the three apart is just a matter of which symbols are in front of you; the algebra underneath is identical.
| a + 1 | |
| = (a + 1) · 1 | identity for · |
| = (a + 1) · (a + a̅) | complement for + |
| = a + (1 · a̅) | distributive |
| = a + (a̅ · 1) | commutative for · |
| = a + a̅ | identity for · |
| = 1 | complement for + |
Its dual, a · 0 = 0, follows by swapping + ↔ · and 0 ↔ 1.
Russell's paradox. Let S = {A | A is a set and A ∉ A}, the set of all sets that are not members of themselves. Ask: is S ∈ S? If S ∈ S, then by its defining property S ∉ S; if S ∉ S, then it satisfies the property, so S ∈ S. Both lead to contradiction. The lesson: “the set of all sets satisfying any property” is not always a set, naive set theory needs axioms (ZFC) to forbid such self-membership.
The halting problem. The same self-reference defeats any supposed program H(p, x) that decides whether program p halts on input x. Build D(p) that loops forever if H(p, p) says “halts” and halts otherwise; then D(D) halts iff it does not. No such H can exist. Russell's set and Turing's program are the same trick, applied to sets and to computation.
A selection of the exercises recommended on the slides, solved in full. Several are the textbook's own worked examples re-taught at exam depth; the rest are representative problems of the recommended type. Each cites its Epp section and the recommended item range. Attempt on paper before revealing.
Statements follow Epp, Discrete Mathematics with Applications (4th ed.). Where a single textbook problem number is not reproduced verbatim, the exercise is marked “cf.” and matches the type and difficulty of the recommended range.
Read each operation straight off the definitions.
Note: A ∩ C = ∅ says A and C are disjoint.
A round bracket excludes the endpoint (open); a square bracket includes it (closed).
First: yes. The blocks are non-empty, pairwise disjoint ({1,2}∩{3}=∅, etc.), and their union is {1,2,3,4,5}. Both partition conditions hold.
Second: no. The blocks are not disjoint: {1,2,3} ∩ {3,4,5} = {3} ≠ ∅. The element 3 lies in two blocks, which a partition forbids.
(⊆) Suppose x ∈ A ∪ (B ∩ C), so x ∈ A, or x ∈ B ∩ C.
If x ∈ A: then x ∈ A ∪ B and x ∈ A ∪ C, so x is in their intersection. If x ∈ B ∩ C: then x ∈ B (so x ∈ A ∪ B) and x ∈ C (so x ∈ A ∪ C), again in the intersection. So the left side is contained in (A ∪ B) ∩ (A ∪ C).
(⊇) Suppose x ∈ (A ∪ B) ∩ (A ∪ C), so x ∈ A ∪ B and x ∈ A ∪ C. If x ∈ A we are done (x ∈ left side). Otherwise x ∉ A; then from x ∈ A ∪ B we get x ∈ B, and from x ∈ A ∪ C we get x ∈ C, so x ∈ B ∩ C, hence x ∈ A ∪ (B ∩ C).
Both containments hold, so the sets are equal. ■ This is the set form of the logical equivalence p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r).
Suppose, for contradiction, that A ∩ (B − A) has an element x.
By the definition of intersection, x ∈ A and x ∈ B − A. By the definition of difference, x ∈ B − A means x ∈ B and x ∉ A.
So x ∈ A and x ∉ A, a contradiction. Therefore A ∩ (B − A) has no element, hence equals ∅. ■
The claim is universal, so a single counterexample disproves it.
Let A = {1}, B = ∅, C = {2}. Then:
Since {2} ≠ ∅, the two sides differ. The identity fails because ∪ and ∩ do not re-bracket freely; it would hold only when C ⊆ A.
| (A ∪ B) − C | |
| = (A ∪ B) ∩ Cᶜ | set difference law |
| = Cᶜ ∩ (A ∪ B) | commutative for ∩ |
| = (Cᶜ ∩ A) ∪ (Cᶜ ∩ B) | distributive law |
| = (A ∩ Cᶜ) ∪ (B ∩ Cᶜ) | commutative for ∩ |
| = (A − C) ∪ (B − C) | set difference law |
Every step is an equality of sets justified by a single named identity, the hallmark of an algebraic proof. ■
| a + (a · b) | |
| = (a · 1) + (a · b) | identity for · |
| = a · (1 + b) | distributive for · |
| = a · (b + 1) | commutative for + |
| = a · 1 | universal bound b + 1 = 1 (Exercise 6.4.A) |
| = a | identity for · |
By duality, a · (a + b) = a holds as well. ■