Chapter recap
Sets collect objects; ∈ is for elements, ⊆ for subsets; |P(A)| = 2^|A|; A − B = A ∩ B̅; complement depends on the universe. Functions give exactly one output per input (|B|^|A| of them); partial functions may skip inputs. Equivalence relations (reflexive, symmetric, transitive) cut a set into classes; the number of classes is the index. Proofs: contrapositive is equivalent; converse is not; contradiction proves impossibility; induction proves “for all n”. Pigeonhole: more objects than boxes ⇒ a shared box; an n-mode machine reading ≥ n symbols repeats a mode. Graphs: paths spell words, reachability by BFS, infinitely many paths iff a cycle lies on the route.
Merged rule card
From 0.2.1 Sets
- x ∈ A (element) vs X ⊆ A (subset). ∅ ⊆ every set. A = B ⇔ A ⊆ B and B ⊆ A.
- A ∪ B, A ∩ B, A − B = A ∩ B̅, A̅ = U − A. De Morgan: (A∪B)̅ = A̅∩B̅, (A∩B)̅ = A̅∪B̅.
- |A ∪ B| = |A| + |B| − |A ∩ B|. |A × B| = |A|·|B|. |P(A)| = 2^|A|.
- |∅| = 0, |{∅}| = 1, P(∅) = {∅}.
From 0.2.2 Functions, relations and equivalence classes
- Relation ⊆ A × B. Function: every input exactly one output. Partial function: some inputs have none.
- #functions A→B = |B|^|A|. #one-to-one (|A| ≤ |B|) = |B|·(|B|−1)···. #relations on n-set = 2^(n²).
- Equivalence = reflexive + symmetric + transitive. Classes partition the set; number of classes = index.
- Finer relation (refinement) ⇒ more classes; every fine class sits inside a coarse class.
From 0.2.3 Proof techniques
- P ⇒ Q false only when P true, Q false. Contrapositive ¬Q ⇒ ¬P ≡ original. Converse/inverse are NOT.
- Contradiction: assume ¬S, derive the impossible. Used for “no machine can…” proofs.
- Induction: base S(n₀) + step S(k) ⇒ S(k+1). Strong induction assumes all S(≤k).
- One counterexample kills a “for all”. Examples never prove it.
From 0.2.4 Pigeonhole principle
- n + 1 objects in n boxes ⇒ some box has ≥ 2.
- N objects in k boxes ⇒ some box has ≥ ⌈N/k⌉. To force m in a box: (m−1)k + 1 objects.
- Machine with n modes, input length ≥ n ⇒ some mode repeats ⇒ a loop in the input.
From 0.2.5 Directed graphs
- Directed graph (V, E ⊆ V×V); self-loop; in/out-degree; labelled edges spell words along paths.
- Path length = #edges. Cycle = path returning to start. Self-loop = cycle of length 1.
- Reachable set: grow from u until nothing new (BFS). Shortest path in n-node graph ≤ n−1 edges.
- Infinitely many u→v paths ⇔ some cycle lies on a u→v route.
Practice questions
- NAT
|P(A × B)| where |A| = 2, |B| = 2?
Write your answer before opening the key.
- MCQ
Which relation on {1,2,3} is an equivalence relation?
- {(1,1),(2,2)}
- {(1,1),(2,2),(3,3),(1,3)}
- {(1,1),(2,2),(3,3),(1,3),(3,1)}
- {(1,2),(2,1)}
- MSQ
Which are always true?
- ∅ ⊆ A
- ∅ ∈ A
- A ⊆ A
- A ∩ A̅ = ∅
- NAT
A 4-mode machine reads an input. What is the smallest input length that guarantees a repeated mode?
Write your answer before opening the key.
- MCQ
“If a graph has a cycle on a u→v route then there are infinitely many u→v paths.” The contrapositive is:
- If there are infinitely many u→v paths then a cycle lies on a route
- If there are finitely many u→v paths then no cycle lies on any u→v route
- If no cycle lies on a route then paths are finite
- If there is no u→v path then there is no cycle
- NAT
Number of one-to-one functions from a 2-element set to a 5-element set?
Write your answer before opening the key.
- MCQ
Relation “x − y divisible by 6” on integers has index:
- 2
- 3
- 6
- infinite
- MSQ
Directed graph edges: (a,b),(b,c),(c,a),(c,d). Which hold?
- d reachable from a
- a reachable from d
- Cycle a→b→c→a exists
- Infinitely many paths from a to d
Answer key
Reveal answers when you’re ready
- 16 — |A×B| = 4 ⇒ 2⁴.
- C — Reflexive, symmetric, transitive; classes {1,3},{2}.
- A: Missing (3,3).
- B: Not symmetric.
- D: Not reflexive.
- ACD — B holds only if ∅ is listed as an element of A.
- B: Only sometimes.
- 4 — 4 symbols ⇒ 5 moments > 4 modes.
- B — Negate both and swap.
- A: Converse.
- C: Inverse.
- D: Unrelated.
- 20 — 5 · 4.
- C — Remainders 0..5.
- A: That is mod 2.
- B: That is mod 3.
- D: Finitely many remainders.
- ACD — The cycle lies on the route to d.
- B: d has no outgoing edges.