Filter for fast review: “Definitions” turns the page into a flashcard list; “Check yourself” shows only the practice questions.
From the Lecture 9 review: exams are closed notes, no devices. You do not need to memorize the names of rules of inference or write formal numbered arguments. You do need to: make truth tables, translate English ↔ logic, negate quantified statements, and write proofs. When you prove something by contraposition or by contradiction, you must say so in the first line. Know the definitions of odd, even, rational, irrational and absolute value cold, and be able to write them from memory.
◎The whole course in 2 minutes
Read this first. Each part builds on the ones above it.
| Part | What it's about | Picture it |
|---|---|---|
| I · Logic | How mathematical statements are built (and, or, if-then, for all, there exists) and how to negate them. | The grammar you need before you can write an essay. |
| II · Proofs | How to argue that a statement is always true: direct, contraposition, contradiction, cases, examples and counterexamples. | A lawyer's case: every step must follow from evidence or earlier steps. |
| III · Sets & functions | The objects math talks about (collections and rules that match inputs to outputs) and how to compare infinite sizes. | Bags of items, and pairing items up one to one. |
| IV · Number theory | Divisibility, remainders, primes, gcd, solving equations mod m, and how it all powers RSA encryption. | Clock arithmetic: numbers that wrap around. |
| V · Induction | Proving infinitely many cases at once, and defining things step by step. | Dominoes: knock over the first one, and each one knocks over the next. |
| VI · Counting | Counting outcomes without listing them: multiply, add, pigeonhole, permutations, combinations. | Ordering from a menu: an appetizer and a main multiplies; soup or salad adds. |
Logic is the language every proof is written in. Proofs (Part II) are the method used everywhere after. Number theory leans on sets and proofs, and the induction of Part V is what proves the division algorithm and prime factorization from Part IV. Counting uses sets (a set of size n has 2ⁿ subsets) and the binomial coefficients that showed up in Fermat's little theorem.
Part I
Logic
§1Propositions & connectives
Lecture 1 · Rosen §1.1 · HW 1.1–1.3
A proposition is a sentence that's either true or false. The connectives (not, and, or, if-then, iff) glue propositions together, and each one is defined by its truth table.
A proposition is a statement that is either true or false (not both).
Propositions: “1 + 1 = 4” (false, still a proposition), “There are infinitely many primes” (true), “Today is Monday.”
Not propositions: “x + 1 = 2” (depends on x; that's a predicate, §3), “Close the door” (a command), “What time is it?” (a question).
We use letters p, q, r, s as propositional variables, and write T for true, F for false.
The six connectives
Connectives build bigger propositions out of smaller ones. Each one is defined by its truth table, so memorize this table:
| p | q | ¬p | p ∧ q | p ∨ q | p ⊕ q | p → q | p ↔ q |
|---|---|---|---|---|---|---|---|
| T | T | F | T | T | F | T | T |
| T | F | F | F | T | T | F | F |
| F | T | T | F | T | T | T | F |
| F | F | T | F | F | F | T | T |
- Negation ¬p: “it is not the case that p.” Opposite truth value.
- Conjunction p ∧ q (“p and q”): true when both are true, false otherwise. In logic, “but” also means ∧.
- Disjunction p ∨ q (“p or q”): false when both are false, true otherwise. This is the inclusive or.
- Exclusive or p ⊕ q: true when exactly one of p, q is true.
In everyday English “or” often means “one or the other but not both.” In math, ∨ always allows both. The lecture joke: a logician's spouse says “you may have cake or you may have pie,” and the logician replies “Excellent! I'll have both.”
The conditional (or implication) p → q is the proposition “if p, then q.” It is false only when p is true and q is false, and true otherwise. p is the hypothesis (premise, antecedent); q is the conclusion (consequence).
Think of p → q as a promise: “If you get an A on the final, then you get an A in the class.” The only way the promise is broken is if you ace the final and still don't get the A (T → F). If you don't ace the final, the promise hasn't been broken no matter what happens, so the statement counts as true. That's why the bottom two rows are T. We call this vacuously true.
In English, “if p then q” suggests p causes q. In math there's no causation needed: “If 1 + 1 = 2, then 2 + 2 = 4” is true; “If 1 + 1 = 3, then Santa is real” is also true (false hypothesis).
A false proposition implies any proposition. This isn't just a quirk of the truth table: the rules of proof let you derive anything from a false assumption.
Claim: if 1 + 1 = 3 then 1 + 1 = 4. Suppose 1 + 1 = 3. Then 2 = 3, so 2 − 1 = 3 − 1, so 1 = 2. So 1 + 1 = 2 + 2 = 4.
All the ways to say “p → q”
| English | English |
|---|---|
| if p, then q | p implies q |
| q if p | p is sufficient for q |
| p only if q | q is necessary for p |
| q whenever p | q follows from p |
| q provided that p | q unless ¬p |
“p only if q” means p → q, not q → p. “You can vote only if you're 18” means vote → 18. Being 18 doesn't force you to vote; it's a requirement.
“p unless q” means ¬q → p. Lecture example: “You will not pass the class unless you take the final.” With p = pass, q = take final: ¬q → ¬p, equivalently p → q.
“You will see the movie only if you are an adult or have permission.” Let m = see movie, a = adult, p = permission. Answer: m → (a ∨ p).
“We will picnic if it is sunny and we are not tired.” (p = picnic, q = sunny, r = tired) Answer: (q ∧ ¬r) → p. The “if” clause is the hypothesis even though it comes second.
Converse, contrapositive, inverse
Starting from p → q:
- converse: q → p
- contrapositive: ¬q → ¬p ← always equivalent to p → q
- inverse: ¬p → ¬q (equivalent to the converse, not the original)
S a shape. “If S is a square, then S has 4 sides”: true. Converse “If S has 4 sides, then S is a square”: false (rectangles). Contrapositive “If S doesn't have 4 sides, it's not a square”: true, same as the original.
The biconditional p ↔ q (“p if and only if q”, abbreviated iff) is true when p and q have the same truth value and false otherwise. It means (p → q) ∧ (q → p).
Order of operations
Precedence, highest to lowest: ¬, ∧, ∨, →, ↔. (Like PEMDAS: ¬ is like a minus sign, ∧ like ×, ∨ like +.)
p ∨ q ∧ r means p ∨ (q ∧ r). With p = T, q = F, r = F this is T, but (p ∨ q) ∧ r is F, so order matters.
¬p ∧ q ∨ p → p ∧ r means ((¬p ∧ q) ∨ p) → (p ∧ r).
Truth tables for compound propositions
With n variables, a truth table has 2n rows. Make a column for each sub-piece, working from the inside out.
| p | q | p ∧ q | ¬p | (p ∧ q) ∨ ¬p | p → q |
|---|---|---|---|---|---|
| T | T | T | F | T | T |
| T | F | F | F | F | F |
| F | T | F | T | T | T |
| F | F | F | T | T | T |
The last two columns match, so (p ∧ q) ∨ ¬p ≡ p → q. This is the method HW 1.1 asks for: build the table, then read off a simpler formula with the same column.
Is “x + 2 = 5” a proposition?
Hint
Does it have a definite truth value on its own?Answer
No. Its truth depends on x, so it's a predicate (§3).When exactly is p → q false?
Answer
Only when p is true and q is false.Translate “You get dessert only if you eat your vegetables” (d, v).
Hint
“Only if” points at the requirement.Answer
d → v.
§2Equivalences & tautologies
Lecture 1 · Rosen §1.3 · HW 1.4–1.6
Two formulas are equivalent when they always have the same truth value. A short list of equivalences lets you simplify formulas like algebra.
A compound proposition that is always true, whatever the truth values of its variables, is a tautology. One that is always false is a contradiction. One that is neither is a contingency.
Examples: p ∨ ¬p is a tautology, p ∧ ¬p is a contradiction, p → q is a contingency.
Propositions p and q are logically equivalent, written p ≡ q, if p ↔ q is a tautology. Equivalently: they have identical truth-table columns.
≡ is not a connective. p ≡ q is a statement about two formulas, not a new formula.
The equivalences to know
| Name | Equivalence |
|---|---|
| Conditional as “or” | p → q ≡ ¬p ∨ q |
| Contrapositive | p → q ≡ ¬q → ¬p |
| Negated conditional | ¬(p → q) ≡ p ∧ ¬q |
| Biconditional | p ↔ q ≡ (p → q) ∧ (q → p) |
| De Morgan | ¬(p ∧ q) ≡ ¬p ∨ ¬q ¬(p ∨ q) ≡ ¬p ∧ ¬q |
| Double negation | ¬(¬p) ≡ p |
| Identity | p ∧ T ≡ p p ∨ F ≡ p |
| Domination | p ∨ T ≡ T p ∧ F ≡ F |
| Negation | p ∨ ¬p ≡ T p ∧ ¬p ≡ F |
| Idempotent | p ∨ p ≡ p p ∧ p ≡ p |
| Commutative | p ∨ q ≡ q ∨ p p ∧ q ≡ q ∧ p |
| Associative | (p ∨ q) ∨ r ≡ p ∨ (q ∨ r) (p ∧ q) ∧ r ≡ p ∧ (q ∧ r) |
| Distributive | p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r) p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r) |
| Absorption | p ∨ (p ∧ q) ≡ p p ∧ (p ∨ q) ≡ p |
| Same hypothesis | (p → q) ∧ (p → r) ≡ p → (q ∧ r) |
| Same conclusion | (p → r) ∧ (q → r) ≡ (p ∨ q) → r |
| Exportation | p → (q → r) ≡ (p ∧ q) → r |
| Contradiction | (¬p → F) ≡ p |
De Morgan: “Not (rich and famous)” means “not rich, or not famous.” To negate, flip every ∧ ↔ ∨ and push the ¬ inside. The same move works for quantifiers (§3): ∀ ↔ ∃.
¬(p → q) ≡ p ∧ ¬q: the only way a promise is broken is if p happened and q didn't. This one shows up constantly when setting up proofs by contradiction.
Show ¬(p ∨ (¬p ∧ q)) ≡ ¬p ∧ ¬q without a truth table.
Lecture's point: truth tables (like the 8-row one for the distributive law) are “horrible and error-prone”; chaining known equivalences is cleaner. Label each step.
Is p ∨ (q → ¬p) a tautology? Cases: if p is true, the whole “or” is true. If p is false, ¬p is true so q → ¬p is true. Either way: true. Algebra: p ∨ (¬q ∨ ¬p) ≡ (p ∨ ¬p) ∨ ¬q ≡ T ∨ ¬q ≡ T.
Is q ∧ (q → p) a tautology? No: one false row is enough, and q = F makes it false.
Same idea (Lecture 9 review): (p → q) ∨ p is a tautology. If p is true the right side is true; if p is false then p → q is true.
Checking a tautology by truth table takes 2n rows. With 400 variables that's more rows than atoms in the universe. Is there a fast (polynomial-time) program to decide whether a formula is a tautology? That's essentially the P = NP question, a $1 million Millennium Prize problem. It matters for computer science because propositional formulas are basically logic circuits.
Simplify ¬(p ∧ ¬q).
Hint
De Morgan, then double negation.Answer
¬p ∨ q, which is the same as p → q.Is (p → q) ∨ (q → p) a tautology?
Hint
Split on whether q is true.Answer
Yes. If q is true, p → q is true. If q is false, q → p is true.Write ¬(p → q) without using →.
Answer
p ∧ ¬q.
§3Predicates & quantifiers
Lecture 2 · Rosen §1.4 · HW 1.7, 1.9
A predicate is a sentence with a blank, like “x > 3.” ∀ means every x works; ∃ means at least one does. To negate, swap ∀ ↔ ∃ and negate what's inside.
A predicate is a statement involving variables which becomes true or false once the values of those variables are specified.
Let P(x) be “x² ≥ x”. Then P(2) is true (4 ≥ 2), P(1) is true (1 ≥ 1), and P(½) is false (¼ ≥ ½ is false). We write predicates with capital letters: P(x), Q(x), L(x, y).
∀x P(x) (the universal quantification) is the proposition “P(x) is true for every x in the domain.” An x where P(x) is false is a counterexample.
∃x P(x) (the existential quantification) is the proposition “there exists an x in the domain such that P(x).”
A quantified statement means nothing until you fix the domain (the allowed values of x). With P(x) = “x² ≥ x”:
- Domain ℝ: ∀x P(x) is false (x = ½).
- Domain ℤ: ∀x P(x) is true. If x ≥ 1 then x·x ≥ x·1; if x ≤ 0 then x² ≥ 0 ≥ x.
Over a finite domain {a₁, …, aₙ}, quantifiers are just long and/or chains:
∀x P(x) ≡ P(a₁) ∧ P(a₂) ∧ … ∧ P(aₙ) and ∃x P(x) ≡ P(a₁) ∨ P(a₂) ∨ … ∨ P(aₙ).
So negating a quantifier is just De Morgan's law on a long chain.
¬∀x P(x) ≡ ∃x ¬P(x) ¬∃x P(x) ≡ ∀x ¬P(x)
“Not everyone passed” = “someone didn't pass.” “Nobody cheated” = “everyone didn't cheat.”
Rewrite ¬∀x [P(x) → Q(x)] so every ¬ sits right in front of a predicate.
Read it: “not every P is a Q” = “some P is not a Q.” Shortcut: ¬(p → q) ≡ p ∧ ¬q.
Translating English: the four patterns
| English | Logic |
|---|---|
| Every P is a Q | ∀x (P(x) → Q(x)) |
| Some P is a Q | ∃x (P(x) ∧ Q(x)) |
| No P is a Q | ∀x (¬P(x) ∨ ¬Q(x)) ≡ ∀x (P(x) → ¬Q(x)) ≡ ¬∃x (P(x) ∧ Q(x)) |
| Some P is not a Q | ∃x (P(x) ∧ ¬Q(x)) |
Rule of thumb: ∀ goes with →, ∃ goes with ∧.
Domain: all Berkeley students. E(x): x is in Math 55. B(x): x owns the textbook.
“Every Math 55 student owns the book” is not ∀x (E(x) ∧ B(x)). That says every Berkeley student is in Math 55 and owns the book; it's false as soon as one student isn't enrolled. Correct: ∀x (E(x) → B(x)).
“Some Math 55 student owns the book” is not ∃x (E(x) → B(x)). That's true as soon as one student isn't enrolled, because F → anything is true. Correct: ∃x (E(x) ∧ B(x)).
When do quantifiers distribute?
∀x (P(x) ∧ Q(x)) ≡ ∀x P(x) ∧ ∀x Q(x)
∃x (P(x) ∨ Q(x)) ≡ ∃x P(x) ∨ ∃x Q(x)
∀x (P ∨ Q) ≢ ∀x P ∨ ∀x Q. Over ℤ: ∀x (x ≥ 0 ∨ x ≤ 0) is true but ∀x (x ≥ 0) ∨ ∀x (x ≤ 0) is false.
∃x (P ∧ Q) ≢ ∃x P ∧ ∃x Q. ∃x (x = 1 ∧ x = 2) is false but ∃x (x = 1) ∧ ∃x (x = 2) is true.
Memory trick: ∀ is a big ∧, so it plays nicely with ∧. ∃ is a big ∨, so it plays nicely with ∨.
English words for ∀ and ∃
| ∃x P(x) | ∀x P(x) |
|---|---|
| there exists x such that P(x) | for all x, P(x) |
| some x satisfies P(x) | every / each x satisfies P(x) |
| at least one x satisfies P(x) | given an arbitrary x, P(x) is true |
| we can find x with P(x) | suppose x is in the domain; then P(x) |
Avoid “any” and “some” in your own writing. “Any” can mean ∀ (“any integer squared is ≥ 0”) or ∃ (“is there any solution?”). The lecture's advice: just say “there exists” and “for all.”
Quantifying over a set
(∀x ∈ A) P(x) abbreviates ∀x (x ∈ A → P(x)). (∃x ∈ A) P(x) abbreviates ∃x (x ∈ A ∧ P(x)).
Examples: (∀x ∈ ℝ)(x > 0) false; (∀x ∈ ℝ)(x² ≥ 0) true; (∀x ∈ ℕ)(x > 0) false (x = 0); (∃x ∈ ℕ)(x − 1 = 0) true.
Over the empty set: (∀x ∈ ∅) P(x) is always true (vacuously: there is no x to break it), and (∃x ∈ ∅) P(x) is always false (there's nothing to be the witness).
Domain ℤ: true or false, ∃x (x² = 2)?
Answer
False. √2 isn't an integer.Negate “Every student passed.”
Answer
“Some student didn't pass”: ∃x ¬P(x).Translate “Some dog is not friendly” using D(x), F(x).
Hint
∃ goes with ∧.Answer
∃x (D(x) ∧ ¬F(x)).
§4Nested quantifiers
Lecture 2 · Rosen §1.5 · HW 1.8–1.9
With two quantifiers, order matters. ∀x ∃y lets y depend on x; ∃y ∀x needs a single y that works for every x.
- ∀x ∃y L(x, y): everyone loves someone.
- ∃x ∀y L(x, y): someone loves everyone.
- ∃x ∃y L(x, y): someone loves someone.
- ∃y ∀x L(x, y): there's one person loved by everyone (the lecture's answer: Dolly Parton).
Swapping two quantifiers of the same kind is fine: ∀x ∀y P ≡ ∀y ∀x P and ∃x ∃y P ≡ ∃y ∃x P.
Swapping a ∀ and an ∃ changes the meaning: ∀x ∃y P(x, y) ≢ ∃y ∀x P(x, y).
One direction does hold: ∃y ∀x P(x, y) implies ∀x ∃y P(x, y), but not the reverse.
∀x ∃y: “every lock has a key.” Each lock may need a different key, and y is allowed to depend on x.
∃y ∀x: “there's a master key.” One fixed y works for every x at once.
A master key gives every lock a key, but every lock having a key doesn't give you a master key. Another way to see it: read the quantifiers left to right as a game. For ∀x ∃y, an opponent picks x first and then you get to respond with y.
∀x ∃y (y > x): “every integer has a bigger integer.” True (take y = x + 1).
∃y ∀x (y > x): “some integer is bigger than all integers.” False (it would have to be bigger than itself).
Domain {1, 2, 3} instead: ∃y ∀x (y ≥ x) is true, with y = 3.
Lecture 9 review: a predicate on ℝ where ∀x ∃y P(x, y) is true but ∃y ∀x P(x, y) is false is P(x, y): x < y.
Flip each quantifier as the ¬ passes through it, then negate what's inside:
¬∀x ∃y P(x, y) ≡ ∃x ∀y ¬P(x, y)
¬∀x ∀y (P(x, y) → Q(x, y)) ≡ ∃x ∃y (P(x, y) ∧ ¬Q(x, y))
“There is a unique x”
∃!x P(x) (the uniqueness quantifier) means “there is exactly one x with P(x).” In ordinary quantifiers:
∃!x P(x) ≡ ∃x [ P(x) ∧ ∀y (y ≠ x → ¬P(y)) ]
“There is an x with P(x), and every other y fails P.” (Equivalently ∃x [P(x) ∧ ∀y (P(y) → y = x)].)
Meaning: every x either fails P or has a different y that also satisfies P. So there are zero solutions, or at least two.
Domain ℝ. Is ∀x ∃y (x + y = 0) true? Is ∃y ∀x (x + y = 0)?
Hint
In the second, one fixed y has to work for every x.Answer
First: true (take y = −x). Second: false (no single y cancels every x).Negate ∀x ∃y (y > x²).
Hint
Flip each quantifier, then negate the inside.Answer
∃x ∀y (y ≤ x²).
§5Rules of inference
Lecture 2 · Rosen §1.6 · HW 1.10–1.11
Rules of inference are the legal moves for getting new facts from ones you have. A proof is a chain of legal moves.
A (propositional) rule of inference is a tautology of the form (q₁ ∧ … ∧ qₙ) → p, expressing that if q₁, …, qₙ are all true then p is true. It's often written with premises stacked above a line and the conclusion after “∴”.
A propositional argument is a list of propositions where each line is a premise or follows from earlier lines by a rule of inference.
Rosen §1.6 Def 1: an argument is a sequence of propositions; all but the last are premises, the last is the conclusion. It is valid if the truth of all the premises implies the conclusion is true.
| Rule | From | Conclude | Tautology |
|---|---|---|---|
| Modus ponens | p, p → q | q | (p ∧ (p → q)) → q |
| Modus tollens | ¬q, p → q | ¬p | (¬q ∧ (p → q)) → ¬p |
| Hypothetical syllogism | p → q, q → r | p → r | ((p → q) ∧ (q → r)) → (p → r) |
| Disjunctive syllogism | p ∨ q, ¬p | q | ((p ∨ q) ∧ ¬p) → q |
| Simplification | p ∧ q | p | (p ∧ q) → p |
| Addition | p | p ∨ q | p → (p ∨ q) |
| Conjunction | p, q | p ∧ q | ((p) ∧ (q)) → (p ∧ q) |
| Resolution | p ∨ q, ¬p ∨ r | q ∨ r | ((p ∨ q) ∧ (¬p ∨ r)) → (q ∨ r) |
Lecture: you don't need these names for exams or quizzes. (HW 1.10 still asks for them.)
Modus ponens (“affirming”): if it rains the ground is wet; it rains; so the ground is wet.
Modus tollens (“denying”): if it rains the ground is wet; the ground is not wet; so it didn't rain. (This is the contrapositive in action.)
Disjunctive syllogism: the cookie is in the jar or on the plate; it's not in the jar; so it's on the plate.
Affirming the conclusion: from p → q and q, concluding p. “If it rained, the grass is wet. The grass is wet. So it rained.” Wrong: maybe the sprinklers ran. ((p → q) ∧ q) → p is not a tautology.
Denying the hypothesis: from p → q and ¬p, concluding ¬q. “It didn't rain, so the grass isn't wet.” Also invalid.
Both mistakes amount to treating p → q as if it were its converse.
Premises: ¬p ∧ q, r → p, ¬r → s, s → t. Show t.
| # | Statement | Reason |
|---|---|---|
| 1 | ¬p ∧ q | premise |
| 2 | ¬p | simplification (1) |
| 3 | r → p | premise |
| 4 | ¬r | modus tollens (2, 3) |
| 5 | ¬r → s | premise |
| 6 | s | modus ponens (4, 5) |
| 7 | s → t | premise |
| 8 | t | modus ponens (6, 7) |
Strategy for English versions (like HW 1.11): name each simple sentence with a letter, translate every hypothesis, then chain rules.
Rules for quantifiers
| Rule | From | Conclude |
|---|---|---|
| Universal instantiation | ∀x P(x) | P(c) for any c in the domain |
| Universal generalization | P(c) for an arbitrary c | ∀x P(x) |
| Existential instantiation | ∃x P(x) | P(c) for some c (a new name, nothing else assumed about it) |
| Existential generalization | P(c) for some particular c | ∃x P(x) |
Universal generalization needs c to be truly arbitrary: you may not assume anything special about it. Checking P(2), P(3) and P(10) proves nothing about ∀x P(x). This is why proofs start with “Let n be an arbitrary integer.”
If ∀x (P(x) ∧ Q(x)) then ∀x P(x) ∧ ∀x Q(x).
- ∀x (P(x) ∧ Q(x)) — premise
- P(c) ∧ Q(c), c arbitrary — universal instantiation
- P(c) — simplification
- ∀x P(x) — universal generalization
- Q(c) — simplification (2)
- ∀x Q(x) — universal generalization
- ∀x P(x) ∧ ∀x Q(x) — conjunction
All of mathematics = valid propositional rules of inference + the four quantifier rules + an axiom system (usually ZFC set theory). Russell and Whitehead's Principia Mathematica (1910) tried to do math fully formally this way, and needed hundreds of pages to reach 1 + 1 = 2.
“If it's a weekday, I have class. I don't have class.” What follows?
Answer
It isn't a weekday (modus tollens).Valid? “If I study, I pass. I passed. So I studied.”
Answer
Invalid: that's affirming the conclusion. You could have passed without studying.
Part II
Proofs
§6Vocabulary & direct proof
Lecture 3 · Rosen §1.7 · HW 2.1
A proof is an argument built from definitions. A direct proof assumes the “if” part and works forward to the “then” part.
| Word | Meaning |
|---|---|
| Theorem | A proposition we can prove is true; usually signals importance. (“Thm”) |
| Lemma | A proven helper result used to prove a bigger theorem. |
| Corollary | Something that follows easily from a theorem just proved. (“Cor”) |
| Proposition | Also (confusingly) used for a less important theorem. The lecture doesn't use it this way. |
| Conjecture | Believed true but not yet proved (e.g. the Twin Prime Conjecture). |
| Proof | The argument for why it's true; often ends with □ (the “Halmos” tombstone). |
| Axiom | A statement assumed true without proof (Rosen). |
The most common theorem shape is ∀x (P(x) → Q(x)): “every object of type P has property Q.” The Pythagorean theorem (every right triangle satisfies a² + b² = c²), Fermat's Last Theorem, and the Four Color Theorem all have this form.
An integer n is even if there exists an integer k such that n = 2k, and odd if there exists an integer k such that n = 2k + 1.
Two integers have the same parity if both are even or both are odd, and opposite parity otherwise. Every integer is even or odd, and none is both. (Lecture: we'll prove that later by induction.)
A real number r is rational if there exist integers p and q with q ≠ 0 such that r = p/q. A real number that is not rational is irrational.
A direct proof of p → q: assume p is true, then use definitions, known facts and logic to show q must be true.
To prove ∀x (P(x) → Q(x)) directly: let x be an arbitrary element of the domain satisfying P(x), then prove Q(x).
- Write down what you're assuming, unpacked with the definition: “n is odd, so n = 2k + 1 for some integer k.”
- Write down what you want, also unpacked: “I need n² = 2(something) + 1.”
- Do algebra until the thing you have looks like the thing you want.
Most Math 55 proofs at this stage are just “plug in the definition and simplify.”
Thm. For all integers n, if n is even then n² is even.
Assume n is even, so n = 2k for some integer k. Then n² = (2k)² = 4k² = 2(2k²). Since 2k² is an integer, n² is even.
Thm. If n is odd, then n² is odd.
Assume n is odd, so n = 2k + 1 for some integer k. Then n² = 4k² + 4k + 1 = 2(2k² + 2k) + 1, so n² is odd.
Thm. If a, b, c are odd integers, then a + b + c is odd.
Assume a, b, c are odd. By definition a = 2k + 1, b = 2m + 1, c = 2n + 1 for some integers k, m, n. So a + b + c = 2(k + m + n) + 3 = 2(k + m + n + 1) + 1, which is odd.
Notice the last proof uses three different letters k, m, n. If you wrote a = 2k + 1 and b = 2k + 1 with the same k, you'd be secretly assuming a = b. Each number gets its own fresh variable.
Thm. If r and s are rational, then r + s is rational.
Assume r, s are rational. By definition r = p/q and s = n/m for integers p, q, m, n with q ≠ 0 and m ≠ 0. Then r + s = mp/(mq) + nq/(mq) = (mp + nq)/(mq). Since mp + nq and mq are integers and mq ≠ 0, r + s is rational by definition.
Two degenerate kinds of proof
From Rosen §1.7. A vacuous proof shows p → q by showing p is false (e.g. “if n > 1 then n² > n” is vacuously true for n = 0). A trivial proof shows p → q by showing q is true, without using p.
Proving “if and only if”
To prove p ↔ q, prove both p → q and q → p, usually as two labeled parts “(⇒)” and “(⇐)”. Each direction can use a different technique.
Prove the sum of two even integers is even.
Hint
Call them 2a and 2b, using two different letters.Answer
2a + 2b = 2(a + b), and a + b is an integer.Prove: if n is odd, then 3n + 1 is even.
Answer
n = 2k + 1, so 3n + 1 = 6k + 4 = 2(3k + 2).
§7Contraposition & contradiction
Lecture 3 · Rosen §1.7 · HW 2.2–2.5
Two indirect strategies: prove the contrapositive (¬q → ¬p), or assume the statement is false and reach something impossible.
Since p → q ≡ ¬q → ¬p, to prove p implies q we can instead prove ¬q implies ¬p. This is proof by contraposition.
Start the proof with “By contraposition.” and state the contrapositive you're proving.
Use contraposition when the hypothesis is hard to unpack but the negated conclusion is easy. “n² is even” gives you nothing about n directly. “n is not even,” i.e. “n is odd,” gives you n = 2k + 1, which you can work with.
Thm. If n² is even, then n is even.
By contraposition. We show: if n is not even, then n² is not even. Assume n is not even, so n is odd. By the earlier theorem, n² is odd, so n² is not even.
Thm. If a, b are reals and ab ≠ 0, then a ≠ 0 and b ≠ 0.
By contraposition. We need: if it's not the case that (a ≠ 0 and b ≠ 0), then ab = 0. By De Morgan, that hypothesis is “a = 0 or b = 0.” If a = 0 then ab = 0, and if b = 0 then ab = 0. So a = 0 or b = 0 implies ab = 0.
Thm (Lecture 9 review). If n, m are integers and n² + 2m is odd, then n is odd.
By contraposition. We show: if n is even then n² + 2m is even. If n = 2k, then n² + 2m = 4k² + 2m = 2(2k² + m), which is even.
To prove p, assume ¬p and derive something false (a contradiction). This works because (¬p → F) ≡ p.
Begin with “Assume for a contradiction that …” and end with “Contradiction!” plus a sentence saying what the contradiction is.
The negation of p → q is p ∧ ¬q, not “¬p → ¬q.” So you assume p is true and q is false.
Lecture 9: to prove “if x + y is irrational, then x is irrational or y is irrational” by contradiction, assume x + y is irrational and x is rational and y is rational. (De Morgan turned “not (x irrational or y irrational)” into “x rational and y rational.”)
Thm. If a, b, c are integers, then at least one of a + b, a + c, b + c is even.
Assume for a contradiction that a, b, c are integers and a + b, a + c, b + c are all odd. A sum of three odd integers is odd, so (a + b) + (a + c) + (b + c) is odd. But it equals 2a + 2b + 2c = 2(a + b + c), which is even. Contradiction! It can't be both even and odd.
Suppose for a contradiction that √2 is rational. Then we can write √2 = p/q as a fraction in lowest terms, so p and q share no common factors; in particular p and q are not both even. Squaring, 2 = p²/q², so p² = 2q², so p² is even. Since p² is even, p is even (theorem above), so p = 2k for some k. Then (2k)² = 2q², so 4k² = 2q², so q² = 2k², so q² is even, so q is even. Contradiction! p and q are both even.
Legend has it that Hippasus, a Pythagorean, first proved √2 is irrational. The others believed every number was rational, so they took him “fishing” and threw him overboard.
Fermat's Last Theorem (claimed 1637, proved by Andrew Wiles 1995): for an integer n > 2, xⁿ + yⁿ = zⁿ has no solutions in positive integers. Lecture shows ∛2 irrational as a corollary: if ∛2 = p/q then 2q³ = p³, i.e. q³ + q³ = p³, violating FLT. (HW 2.5 asks for a proof that avoids FLT.)
| Contraposition | Contradiction | |
|---|---|---|
| Proves | an implication p → q | any statement p |
| You assume | ¬q | ¬p (for p → q: assume p ∧ ¬q) |
| You must reach | specifically ¬p | anything false |
| First words | “By contraposition, …” | “Assume for a contradiction that …” |
- Direct proof of ∀x (P(x) → Q(x)): start with “Assume x is such that P(x) is true” and end with “so Q(x) is true.”
- By contraposition: say so (“We prove this by contraposition”).
- By contradiction: start “Assume for a contradiction that …” and end “Contradiction!” with an explanation.
- Don't prove the converse by accident. Assuming the conclusion and deriving the hypothesis proves q → p, not p → q.
What's the contrapositive of “if n² is odd then n is odd”?
Answer
If n is even, then n² is even.Prove by contradiction that there's no largest integer.
Hint
Suppose N is the largest. Look at N + 1.Answer
N + 1 is an integer bigger than N. Contradiction!Proving p → q by contradiction: what's your first line?
Answer
“Assume for a contradiction that p is true and q is false.”
§8Cases, existence, uniqueness, counterexamples
Lecture 4 · Rosen §1.8 · HW 2.6–2.9
Split into cases that cover everything. To show something exists, find it (or show it must exist). One counterexample kills a “for all.”
Proof by cases
To prove (p₁ ∨ p₂ ∨ … ∨ pₙ) → q, use [(p₁ ∨ … ∨ pₙ) → q] ≡ [(p₁ → q) ∧ … ∧ (pₙ → q)]: show each case separately implies q.
Often the hypothesis isn't an “or” yet. Then first split it into cases that cover every possibility (n even / n odd; x ≥ 0 / x < 0; n mod 3 = 0, 1, 2), and handle each.
Thm. If n is even or m is even, then nm is even.
Case 1: n is even, so n = 2k and nm = 2(km), even. Case 2: m is even, so m = 2k and nm = 2(nk), even.
Thm. For every integer n, n(n + 1) is even.
By cases on n's parity. Case 1: n = 2k. Then n(n + 1) = 2k(2k + 1) = 2(2k² + k), even. Case 2: n = 2k + 1. Then n(n + 1) = (2k + 1)(2k + 2) = 4k² + 6k + 2 = 2(2k² + 3k + 1), even.
Thm (Lecture 9). n² + n + 1 is odd for every integer n.
Case n = 2k: n² + n + 1 = 4k² + 2k + 1 = 2(2k² + k) + 1. Case n = 2k + 1: 4k² + 4k + 1 + 2k + 1 + 1 = 4k² + 6k + 3 = 2(2k² + 3k + 1) + 1. Odd either way.
The absolute value of a real number x is |x| = x if x ≥ 0, and |x| = −x if x < 0.
For all real x: −|x| ≤ x ≤ |x|.
Case 1: x ≥ 0. Then |x| = x, so x ≤ |x|, and −|x| = −x ≤ 0 ≤ x. Case 2: x < 0. Then |x| = −x > 0, so x < 0 < |x|, and −|x| = x.
Triangle inequality. For all real x, y: |x + y| ≤ |x| + |y|.
Case 1: x + y ≥ 0. Then |x + y| = x + y ≤ |x| + |y|, since x ≤ |x| and y ≤ |y|. Case 2: x + y < 0. Then |x + y| = −x − y. By the previous theorem −x ≤ |x| and −y ≤ |y|, so |x + y| ≤ |x| + |y|.
Thm. If 3 | ab, then 3 | a or 3 | b.
By contraposition: assume 3 ∤ a and 3 ∤ b, i.e. a, b ≢ 0 (mod 3). Four cases: (a, b) ≡ (1, 1) gives ab ≡ 1; (1, 2) gives 2; (2, 1) gives 2; (2, 2) gives 4 ≡ 1 (mod 3). In every case ab ≢ 0 (mod 3), so 3 ∤ ab.
Existence proofs
To prove ∃x P(x): a constructive proof exhibits a specific x and checks P(x). A nonconstructive proof shows some x must exist without saying which one (often by contradiction or by cases).
There are irrational x, y with x + y rational: x = √2, y = −√2, so x + y = 0. Lecture 9: the same pair makes both x + y = 0 and xy = −2 rational.
There's an irrational y and a rational x with xʸ rational: x = 1, y = √2 gives 1^√2 = 1.
Mersenne claimed in 1644 that 2⁶⁷ − 1 is prime. In 1903 Frank Nelson Cole silently wrote 2⁶⁷ − 1 = 147,573,952,589,676,412,927 = 193,707,721 × 761,838,257,287 on the board, multiplied it out, and sat down to a standing ovation. A constructive disproof by one example.
There exist irrational numbers x, y such that xʸ is rational.
Case 1: √2^√2 is rational. Take x = y = √2. Case 2: √2^√2 is irrational. Take x = √2^√2 and y = √2. Then xʸ = (√2^√2)^√2 = √2^(√2·√2) = (√2)² = 2, rational.
We never learn which case holds; that's what makes it nonconstructive. (In fact √2^√2 is irrational, by the Gelfond–Schneider theorem.)
Counterexamples
If ∀x P(x) is false, there must be some x with ¬P(x): a counterexample. One counterexample disproves a “for all.”
“If x, y are irrational then x + y is irrational”? False: counterexample x = √2, y = −√2.
When asked to disprove, give the specific counterexample and verify it satisfies the hypotheses but not the conclusion.
Every 2-D convex shape has at least two stable and two unstable equilibrium points. Mathematicians expected the same in 3-D, but in 2006 Gábor Domokos and Péter Várkonyi built a counterexample, the Gömböc: a convex solid of uniform density with exactly one stable and one unstable equilibrium. It looks a lot like an Indian star tortoise shell, since tortoises benefit from being able to right themselves.
Uniqueness proofs
To prove “there is a unique x with P(x)”, do two steps:
- Existence: show ∃x P(x).
- Uniqueness: show that if P(x) and P(y), then x = y.
Thm. If n, m are integers and n ≠ 0, there is a unique rational r with nr + m = 0.
Existence: let r = −m/n (rational since n ≠ 0). Then nr + m = −m + m = 0. Uniqueness: suppose nr + m = 0 and ns + m = 0. Then nr = −m = ns, so r = s since n ≠ 0.
Rosen §1.8 also uses “without loss of generality” (WLOG): when two cases are symmetric (e.g. x ≤ y vs y ≤ x), prove one and say the other is the same with the roles swapped.
Prove n² + n is even for every integer n.
Hint
Cases: n even, n odd. (Or notice n² + n = n(n + 1).)Answer
n = 2k: 4k² + 2k = 2(2k² + k). n = 2k + 1: 4k² + 6k + 2 = 2(2k² + 3k + 1).Disprove: “every prime is odd.”
Answer
2 is prime and even. One counterexample is enough.Is the √2^√2 proof constructive?
Answer
No. It shows x, y exist without telling you which case is true.
§9Games & strategy stealing
Lecture 4 · HW 2.10–2.11 · (no game problems on Midterm 1)
In finite two-player games with no draws, someone has a winning strategy. In Chomp, player 1 wins by “stealing” player 2's strategy.
Suppose two players alternate moves m₁, n₁, m₂, n₂, …, m_k, n_k, each sees all earlier moves, and after k rounds exactly one player is declared the winner (no draws). Then either player I or player II has a winning strategy: a rule that says how to move on each turn, depending on the opponent's moves, that guarantees a win.
Examples: Armageddon chess (draws count as wins for Black), Go with a half-point komi.
Let W(m₁, n₁, …, m_k, n_k) mean “player I wins.” Player I has a winning strategy iff
∃m₁ ∀n₁ ∃m₂ ∀n₂ … ∃m_k ∀n_k W(…)
Negate it: ∀m₁ ∃n₁ … ∀m_k ∃n_k ¬W(…), which says exactly that player II has a winning strategy. A statement or its negation is true, so one of them has a winning strategy. Quantifiers really are a game: ∃ is your move, ∀ is your opponent's.
Chomp: a grid of cookies whose top-left cookie is poisoned. On each turn a player picks a remaining cookie and eats it along with every cookie below and/or to the right of it. Whoever eats the poisoned cookie loses.
The first player has a winning strategy on every n × m board except 1 × 1.
By contradiction. Suppose player I has no winning strategy. By Zermelo, player II has one. Player I imagines opening by eating only the bottom-right cookie, and looks up the bite X that II's winning strategy answers with. Every bite eats the bottom-right cookie too, so the board after “bottom-right, then X” is the same as the board after X alone. So player I really opens with X, and from then on follows II's strategy. Player I is now sitting in II's winning seat, so player I has a winning strategy. Contradiction: both players can't have winning strategies.
This strategy-stealing proof is nonconstructive. It's an open problem to describe the winning strategy explicitly for all board sizes (there was progress on 3 × n boards in 2026).
Chomp on a 1×2 board (the poisoned cookie plus one more). Who wins?
Answer
Player 1: eat the safe cookie, and player 2 is left with the poison.Why is the strategy-stealing argument nonconstructive?
Answer
It proves player 1 has a winning strategy without saying what it is.
Part III
Sets, functions & infinity
§10Sets
Lecture 5 · Rosen §2.1 · HW 3.1–3.2, 3.4
A set is a bag of distinct items; order and repeats don't matter. Know ∈ (“is an item in”) versus ⊆ (“every item is also in”).
A set is an unordered collection of distinct objects, called its elements or members. a ∈ A means a is an element of A; a ∉ A means it isn't. Sets get uppercase letters, elements lowercase.
A set is a bag. All that matters is what's in the bag. The order you list things in doesn't matter, and putting the same thing in twice doesn't add anything: {1, 2} = {2, 1} = {1, 1, 2}.
Describing sets
- Roster: list elements in braces: {1, 13, 20}, {Alice, Bob, Charlie, Eve}. Use “…” only when the pattern is obvious: {1, 2, …, 100}, {2, 4, 6, 8, …}.
- Set-builder: {x | P(x)} is the set of all x satisfying P(x). E.g. {x | x is even and x > 0} = {2, 4, 6, …}.
| Symbol | Set |
|---|---|
| ℕ = {0, 1, 2, 3, …} | natural numbers (includes 0 in this course and Rosen) |
| ℤ = {…, −2, −1, 0, 1, 2, …} | integers |
| ℤ⁺ = {1, 2, 3, …} | positive integers |
| ℚ = {p/q | p, q ∈ ℤ, q ≠ 0} | rational numbers |
| ℝ | real numbers (anything you can write as a decimal) |
| ℂ = {x + iy | x, y ∈ ℝ} | complex numbers |
| Duplicates? | Ordered? | Labels? | |
|---|---|---|---|
| Set | No | No | No |
| Multiset | Yes | No | No |
| Sequence | Yes | Yes | No |
| Injective sequence | No | Yes | No |
| Indexed family | Yes | No | Yes |
A is a subset of B, written A ⊆ B (and B is a superset of A, B ⊇ A), if every element of A is also an element of B:
A ⊆ B ⟺ ∀x (x ∈ A → x ∈ B)
A is a proper subset, A ⊊ B (Rosen: A ⊂ B), if A ⊆ B and A ≠ B.
Two sets are equal if they have exactly the same elements: A = B ⟺ ∀x (x ∈ A ↔ x ∈ B). Equivalently A ⊆ B and B ⊆ A.
The empty set, written ∅ or {}, is the set with no elements.
For every set S: ∅ ⊆ S and S ⊆ S.
∅ ⊆ S means ∀x (x ∈ ∅ → x ∈ S). Since x ∈ ∅ is always false, each implication is vacuously true. S ⊆ S because x ∈ S → x ∈ S is always true.
True/false checks: {1, 3} ⊆ {1, 2, 3} T; {1, 2, 3} ⊆ {1, 2, 3} T; {1, 3} ⊆ {1, 2} F; {1, 2} = {2, 1} T; {1, 2, 3} = {1, 2} F; {1, 1, 2} = {1, 2} T.
Sets inside sets: ∈ vs ⊆
x ∈ A: “x is one of the items in bag A.”
X ⊆ A: “every item in bag X is also an item in bag A.”
A bag can contain another bag as a single item. The items inside the inner bag are not items of the outer bag.
Let B = {1, {1, 2}, {{3}}}. It has exactly 3 elements.
| Statement | Why | |
|---|---|---|
| 1 ∈ B | T | listed |
| 2 ∈ B | F | 2 is inside {1, 2}, which is an element, but 2 itself isn't |
| {1, 2} ∈ B | T | listed as an element |
| {1, 2} ⊆ B | F | would need 2 ∈ B |
| {1} ⊆ B | T | 1 ∈ B |
| {3} ∈ B | F | the element is {{3}}, not {3} |
| ∅ ⊆ B | T | always |
| ∅ ∈ B | F | ∅ isn't listed |
Note 2 ∈ {1, 2} and {1, 2} ∈ B, but 2 ∉ B: ∈ is not transitive (⊆ is).
With C = {∅}: ∅ ∈ C (T), ∅ ⊆ C (T), and C ≠ ∅ (C has one element). With D = {∅, {∅}}: {∅} ∈ D and {∅} ⊆ D are both true.
∅ ≠ {∅}. The first is an empty bag; the second is a bag holding one empty bag.
If S has exactly n distinct elements (n a nonnegative integer), S is finite with cardinality |S| = n. A set that is not finite is infinite. (|∅| = 0, |{∅}| = 1.)
The power set of A, 𝒫(A), is the set of all subsets of A: 𝒫(A) = {B | B ⊆ A}.
𝒫({1, 2}) = {∅, {1}, {2}, {1, 2}}. 𝒫(∅) = {∅}. 𝒫({∅}) = {∅, {∅}}.
If |A| = n then |𝒫(A)| = 2ⁿ (each element is either in or out of a subset). Always ∅ ∈ 𝒫(A) and A ∈ 𝒫(A).
Thm. If A ⊆ B then 𝒫(A) ⊆ 𝒫(B).
Assume A ⊆ B. We need: if C ∈ 𝒫(A) then C ∈ 𝒫(B). Suppose C ∈ 𝒫(A), so C ⊆ A by definition. Since A ⊆ B, C ⊆ B (⊆ is transitive). So C ∈ 𝒫(B).
Tuples and Cartesian products
An ordered n-tuple (a₁, …, aₙ) has a first element, a second element, …, an nth element. Two tuples are equal iff corresponding entries are equal. A 2-tuple is an ordered pair: (a, b) = (c, d) iff a = c and b = d. So (1, 3) ≠ (3, 1), unlike sets.
The Cartesian product A × B = {(a, b) | a ∈ A ∧ b ∈ B}. More generally A₁ × ⋯ × Aₙ = {(a₁, …, aₙ) | aᵢ ∈ Aᵢ}.
{1, 2} × {x, y} = {(1, x), (1, y), (2, x), (2, y)}. ℝ × ℝ = ℝ² is the plane. In general A × B ≠ B × A, and |A × B| = |A|·|B|.
A = {1, {2}, {1, 2}}. Is 2 ∈ A? {2} ∈ A? {1} ⊆ A? {1, 2} ⊆ A?
Hint
∈: is it listed? ⊆: is every item listed?Answer
No · yes · yes · no (that would need 2 ∈ A).How big is 𝒫({a, b, c})? List its 2-element subsets.
Answer
2³ = 8. The 2-element subsets are {a, b}, {a, c}, {b, c}.Is ∅ ∈ {1, 2}? Is ∅ ⊆ {1, 2}?
Answer
No (it isn't listed). Yes (∅ is a subset of everything).
§11Set operations
Lecture 5 · Rosen §2.2 · HW 3.3–3.4
Union, intersection, difference and complement are “or,” “and,” “and not” and “not” for sets. Prove two sets are equal by chasing an element.
- Union: A ∪ B = {x | x ∈ A ∨ x ∈ B}, elements in A or B or both.
- Intersection: A ∩ B = {x | x ∈ A ∧ x ∈ B}, elements in both.
- A and B are disjoint if A ∩ B = ∅.
- Difference: A − B = {x | x ∈ A ∧ x ∉ B} (also written A \ B), elements of A not in B.
- Complement (relative to a universal set U): A = U − A = {x ∈ U | x ∉ A}.
{1, 2} ∪ {2, 5} = {1, 2, 5} {1, 2} ∩ {2, 5} = {2} {1, 2} − {2, 5} = {1}. With U = ℤ, the complement of the evens is the odds.
Counting: |A ∪ B| = |A| + |B| − |A ∩ B| (don't double count the overlap).
Set operations are logic in disguise: ∪ is ∨, ∩ is ∧, complement is ¬, and ⊆ is →. Every logical equivalence from §2 gives a set identity.
| Set identity | Name |
|---|---|
| A ∪ ∅ = A, A ∩ U = A | Identity |
| A ∪ U = U, A ∩ ∅ = ∅ | Domination |
| A ∪ A = A, A ∩ A = A | Idempotent |
| complement of A = A | Complementation |
| A ∪ B = B ∪ A, A ∩ B = B ∩ A | Commutative |
| A ∪ (B ∪ C) = (A ∪ B) ∪ C, same for ∩ | Associative |
| A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C), A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) | Distributive |
| A ∪ B = A ∩ B, A ∩ B = A ∪ B | De Morgan |
| A ∪ (A ∩ B) = A, A ∩ (A ∪ B) = A | Absorption |
| A ∪ A = U, A ∩ A = ∅ | Complement |
To prove A = B you must show ∀x (x ∈ A ↔ x ∈ B). Two standard ways:
- Chain of iffs (“element chasing”): x ∈ A ⟺ … ⟺ x ∈ B, using the definitions of the operations at each step.
- Double inclusion: show A ⊆ B (“let x ∈ A … so x ∈ B”) and B ⊆ A separately.
To show not equal, give one element in one set but not the other (a concrete counterexample with small sets).
Show A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C). For any x:
For a collection of sets, A₁ ∪ ⋯ ∪ Aₙ = ⋃ᵢ Aᵢ contains elements in at least one Aᵢ; A₁ ∩ ⋯ ∩ Aₙ = ⋂ᵢ Aᵢ contains elements in all of them.
A = {1, 2, 3, 4}, B = {3, 4, 5}. Find A ∪ B, A ∩ B, A − B, B − A.
Answer
{1, 2, 3, 4, 5} · {3, 4} · {1, 2} · {5}.U = {1, …, 6}. What's the complement of {2, 4, 6}?
Answer
{1, 3, 5}.State De Morgan's law for sets.
Answer
The complement of A ∪ B is Ā ∩ B̄, and the complement of A ∩ B is Ā ∪ B̄.
§12Functions
Lecture 6 · Rosen §2.3 · HW 3.5–3.10
A function gives every input exactly one output. Injective: no two inputs share an output. Surjective: every possible output is hit. Bijective: both.
A function f from A to B, written f : A → B, assigns exactly one element f(a) ∈ B to each element a ∈ A. Functions are also called mappings.
A is the domain, B is the codomain. If f(a) = b, then b is the image of a and a is a preimage of b.
The graph of f is {(a, b) ∈ A × B | f(a) = b}. In set theory a function is its graph: a subset f ⊆ A × B such that for every a ∈ A there is a unique b ∈ B with (a, b) ∈ f.
Domain = buttons, codomain = all snacks the machine could stock. A function means every button gives exactly one snack. Two buttons may give the same snack (not injective). Some snacks may not be on any button (not surjective). A button that gives nothing, or a random one of two snacks, means it isn't a function at all: f(x) = 1/x on ℝ (0 gets nothing) and “f(x) = ±√x” (two outputs) aren't functions.
Injective (one-to-one)
f is one-to-one (injective, an injection) if different inputs give different outputs:
∀a ∀b (a ≠ b → f(a) ≠ f(b)) ≡ ∀a ∀b (f(a) = f(b) → a = b)
To prove injective: assume f(a) = f(b) and show a = b. To disprove: give two different inputs with the same output.
- f : ℤ → ℤ, f(x) = x + 1: injective. If a + 1 = b + 1 then a = b.
- f : ℤ → ℤ, f(x) = x²: not injective. f(−2) = f(2) = 4.
- f : ℕ → ℕ, f(x) = x²: injective. If a² = b² then a = b, since both are ≥ 0 (no negative roots in the domain). Same formula, different domain, different answer.
For f with domain and codomain ⊆ ℝ, and all x, y in the domain with x < y, f is:
- increasing if f(x) ≤ f(y); strictly increasing if f(x) < f(y);
- decreasing if f(x) ≥ f(y); strictly decreasing if f(x) > f(y).
Examples: eˣ is strictly increasing. The constant f(x) = 0 is both increasing and decreasing (not strictly). x² on ℤ is neither (−1 < 0 but f(−1) > f(0); 0 < 1 but f(0) < f(1)). −x is strictly decreasing.
If f : A → B (A, B ⊆ ℝ) is strictly increasing, then f is injective.
Let a, b ∈ A with a ≠ b. Case 1: a < b, so f(a) < f(b), so f(a) ≠ f(b). Case 2: b < a, so f(b) < f(a), so f(a) ≠ f(b).
Image and range
For S ⊆ A, the image of S is f(S) = {f(s) | s ∈ S}. The range of f is ran(f) = f(A) = {f(a) | a ∈ A}, the set of outputs actually hit.
Range ≠ codomain. The codomain is where outputs are allowed to land; the range is where they actually land.
- f : ℤ → ℤ, f(x) = 2x. f({−1, 2, 3}) = {−2, 4, 6}. ran(f) = all even integers.
- f : ℝ → ℝ, f(x) = x³. ran(f) = ℝ, since for any y, f(∛y) = y.
- f : ℝ → ℤ, f(x) = ⌊x⌋ (floor: the greatest integer ≤ x). ran(f) = ℤ, since ⌊n⌋ = n.
For f : A → B and S₁, S₂ ⊆ A: f(S₁ ∪ S₂) = f(S₁) ∪ f(S₂) and f(S₁ ∩ S₂) ⊆ f(S₁) ∩ f(S₂).
(∪) y ∈ f(S₁ ∪ S₂) ⟺ y = f(a) for some a ∈ S₁ ∪ S₂ ⟺ y = f(a) for some a ∈ S₁, or y = f(a) for some a ∈ S₂ ⟺ y ∈ f(S₁) or y ∈ f(S₂) ⟺ y ∈ f(S₁) ∪ f(S₂).
(∩) Suppose y ∈ f(S₁ ∩ S₂), so y = f(x) for some x ∈ S₁ ∩ S₂. Then x ∈ S₁, so y ∈ f(S₁), and x ∈ S₂, so y ∈ f(S₂). So y ∈ f(S₁) ∩ f(S₂).
The ∩ version is only ⊆: equality can fail when f isn't injective (HW 3.9).
Surjective, bijective, inverse
f is onto (surjective, a surjection) if every element of the codomain is hit: ∀b ∈ B ∃a ∈ A (f(a) = b), i.e. ran(f) = B.
f is a bijection (one-to-one correspondence) if it is both injective and surjective. A bijection pairs up the elements of A and B exactly.
To prove surjective: let b ∈ B be arbitrary; solve for an a with f(a) = b and check a really is in A. To disprove: name one b in the codomain that's never hit.
- f : ℤ → ℤ, f(x) = 2x: injective (2x = 2y ⇒ x = y) but not onto (1 is never hit, since 2x is even). Lecture 9 review.
- f : ℝ → ℝ, f(x) = x³: onto (ran = ℝ) and injective, so a bijection.
- ⌊x⌋ : ℝ → ℤ: onto, not injective (⌊0.2⌋ = ⌊0.7⌋ = 0).
- f : ℝ → ℝ, f(x) = x² is not onto (−1 isn't hit), but f : ℝ → [0, ∞) with the same formula is onto. Changing the codomain changes surjectivity.
If f : A → B is a bijection, its inverse f⁻¹ : B → A sends b to the unique a with f(a) = b: f⁻¹(b) = a ⟺ f(a) = b. (Lecture also defines it for any injective f as a function ran(f) → A.)
Example: f(x) = x³ on ℝ is a bijection with f⁻¹(y) = ∛y, since y = x³ ⟺ ∛y = x.
Facts: f⁻¹(f(a)) = a for all a ∈ A, and f(f⁻¹(b)) = b for all b ∈ B.
f⁻¹ is the inverse function, not 1/f. Only bijections (or injections, onto their range) have inverses.
Composition
If g : A → B and f : B → C, the composition f ∘ g : A → C is (f ∘ g)(a) = f(g(a)). Apply g first (read right to left).
Example: f(x) = 2x + 3, g(x) = x² on ℝ. (f ∘ g)(x) = 2x² + 3 but (g ∘ f)(x) = (2x + 3)². Composition isn't commutative.
Let g : A → B and f : B → C. (1) If f and g are injective, so is f ∘ g. (2) If f and g are surjective, so is f ∘ g. (So compositions of bijections are bijections.)
(1) Suppose a ≠ b in A. Since g is injective, g(a) ≠ g(b). Since f is injective, f(g(a)) ≠ f(g(b)). (2) Let z ∈ C. Since f is onto, z = f(b) for some b ∈ B. Since g is onto, b = g(a) for some a ∈ A. So z = f(g(a)).
Floor ⌊x⌋ = the largest integer ≤ x. Ceiling ⌈x⌉ = the smallest integer ≥ x. E.g. ⌊3.7⌋ = 3, ⌈3.2⌉ = 4, ⌊−1.5⌋ = −2.
f : ℤ → ℤ, f(x) = 3x + 1. Injective? Surjective?
Hint
Can f(x) ever equal 0?Answer
Injective (3a + 1 = 3b + 1 ⇒ a = b). Not surjective: 3x + 1 = 0 has no integer solution.Same formula on ℝ → ℝ: is it a bijection? What's the inverse?
Answer
Yes. f⁻¹(y) = (y − 1)/3.f(x) = x + 1, g(x) = 2x. Find (f ∘ g)(3) and (g ∘ f)(3).
Hint
f ∘ g means do g first.Answer
f(g(3)) = f(6) = 7, and g(f(3)) = g(4) = 8.
§13Cardinality & infinity
Lectures 6–7 · Rosen §2.5 · HW 3.10–3.12
Two sets are the same size if you can pair them up perfectly. ℕ, ℤ and ℚ are all the same size (countable), but ℝ is strictly bigger.
Sets A and B have the same cardinality, |A| = |B|, if there is a bijection from A to B.
|A| ≤ |B| if there is an injection from A to B. |A| < |B| if |A| ≤ |B| and |A| ≠ |B| (an injection exists but no bijection does).
Before you could count, you could still tell if you had as many sheep as pebbles: pair them off one to one. That's a bijection. Same cardinality means the sets are relabelings of each other. Cantor (late 1800s) noticed this matches “size” for finite sets and proposed it as the definition for infinite sets too.
- Positive ↔ negative integers: f(x) = −x.
- Odd ↔ even positive integers: f(x) = x + 1.
- ℕ = {0, 1, 2, …} ↔ ℤ⁺ = {1, 2, 3, …}: f(x) = x + 1. An infinite set can have the same size as a proper subset of itself.
- ℤ is countable: list it as 0, 1, −1, 2, −2, 3, −3, … (Rosen §2.5).
A hotel with rooms 0, 1, 2, … is full. One new guest: everyone moves from room n to n + 1, and room 0 is free. An infinite bus with seats 0, 1, 2, …: everyone in the hotel moves from n to 2n (freeing all odd rooms) and the passenger in seat n takes room 2n + 1.
Write ℕ × ℕ as an infinite grid of pairs (a, b) and walk the diagonals in a zigzag: (0,0), (1,0), (0,1), (2,0), (1,1), (0,2), … Every pair appears exactly once, which gives a bijection ℕ → ℕ × ℕ. The same idea shows ℚ is countable (list fractions p/q along diagonals, skipping repeats).
(Lecture) A is finite if it has the same cardinality as {0, 1, …, n − 1} for some n ∈ ℕ; then |A| = n. Otherwise A is infinite.
(Lecture) A set is countable if it has the same cardinality as a subset of ℕ. Equivalently, it's finite or has the same cardinality as ℕ (countably infinite). Intuitively: you can list its elements as a₀, a₁, a₂, …
Rosen §2.5 Def 3: a set is countable if it is finite or has the same cardinality as ℤ⁺; otherwise uncountable. A countably infinite S has |S| = ℵ₀ (“aleph null”). Same notion as the lecture's.
Every set A is either finite, or |ℕ| ≤ |A|.
Idea: pick distinct elements a₀, a₁, a₂, … of A one by one. Either you run out at some step n (then i ↦ aᵢ is a bijection {0, …, n−1} → A), or you never do (then i ↦ aᵢ is an injection ℕ → A). Making infinitely many choices at once quietly uses the axiom of choice, which is why this is only a proof idea.
- A subset of a countable set is countable.
- If A and B are countable, so is A ∪ B (Rosen §2.5 Thm 1; HW 3.11).
- Schröder–Bernstein (Rosen §2.5 Thm 2): if |A| ≤ |B| and |B| ≤ |A|, then |A| = |B|. So two injections, one each way, give a bijection.
- ℕ × ℕ, ℤ, ℚ are countable. ℝ, [0, 1], and the irrationals are uncountable.
The interval [0, 1] = {x ∈ ℝ | 0 ≤ x ≤ 1} is uncountable. Hence ℝ is uncountable and |ℕ| < |ℝ|.
Suppose for a contradiction there were a bijection f : ℕ → [0, 1]. List the decimal expansions of f(0), f(1), f(2), … in a table. Build y = 0.d₀d₁d₂… by going down the diagonal: choose digit dₙ different from the nth digit of f(n) (and avoid 0 and 9; e.g. use 5 unless that digit is 5, then use 4). Then y ≠ f(0) since they differ in the 1st digit, y ≠ f(1) since they differ in the 2nd digit, and in general y ≠ f(n) for every n. So y ∈ [0, 1] is not in the range of f, so f isn't onto. Contradiction!
Some reals have two decimal expansions: 0.4999… = 0.5000… That's why the proof avoids digits 0 and 9, so y has only one expansion and really differs from every f(n).
Why 0.999… = 1: let x = 0.999…; then 10x = 9.999…, so 10x − x = 9, so 9x = 9 and x = 1. (Or: the geometric series Σ 0.9·(0.1)ⁿ = 0.9 / (1 − 0.1) = 1.) The underlying reason is there are no infinitely small nonzero real numbers.
For every set X, |X| < |𝒫(X)|. There's always a bigger infinity: |ℕ| < |𝒫(ℕ)| < |𝒫(𝒫(ℕ))| < …
A real number is algebraic if it solves a nontrivial integer polynomial equation (√2 solves x² = 2; √(13/7) solves 7x² = 13). Cantor showed there are only countably many integer polynomials, so only countably many algebraic numbers. But ℝ is uncountable, so most real numbers are not algebraic (they're transcendental), and Cantor proved this without exhibiting a single one.
Poincaré: “Later generations will regard set theory as a disease from which one has recovered.”
Cantor (1878) asked: is there a cardinality strictly between |ℕ| and |ℝ|? Gödel (1938) and Cohen (1963) showed the standard axioms (ZFC) can't prove or disprove it. There are “universes” of set theory where |ℝ| is the next infinity after |ℕ|, and others with many sizes in between.
Von Neumann: each number is the set of all smaller numbers. 0 = ∅, 1 = {0} = {∅}, 2 = {0, 1} = {∅, {∅}}, 3 = {0, 1, 2}. The first infinite ordinal is ω = {0, 1, 2, …}, and counting continues: ω + 1 = {0, 1, 2, …, ω}.
Let A = {x | x ∉ x}. Is A ∈ A? If A ∉ A, then A satisfies the rule, so A ∈ A. If A ∈ A, then A breaks the rule, so A ∉ A. Contradiction either way, so Cantor's original (“naive”) set theory was inconsistent. (Analogy: the barber who shaves exactly those who don't shave themselves.)
The fix, after about 30 years: modern set theory (ZFC) only lets you use set-builder notation to carve a subset out of an existing set, {x ∈ S | P(x)}, and has other axioms to build sets (e.g. every set has a power set). Take Math 135 for more.
Show ℕ and the even naturals have the same cardinality.
Answer
f(n) = 2n is a bijection between them.Countable or uncountable: ℤ × ℤ? the interval (0, 1)? all finite strings of letters?
Answer
Countable · uncountable · countable.In the diagonal argument, why can't the new number y be on the list?
Answer
For every n, y differs from the n-th number in its n-th digit.
Part IV
Number theory
§14Divisibility & modular arithmetic
Lecture 7 · Rosen §4.1 · HW 4.1–4.6
a | b means b is a multiple of a. a mod m is the remainder. a ≡ b (mod m) means same remainder, and congruences can be added and multiplied like equations.
If a and b are integers with a ≠ 0, then a divides b, written a | b, if there is an integer c such that b = ac. Then a is a factor (divisor) of b and b is a multiple of a. a ∤ b means a does not divide b.
3 | 12 T (12 = 3·4). 2 | 7 F (7 ≠ 2c for any integer c). 6 | 2 F. 2 | 0 T (0 = 2·0). 2 | −6 T (−6 = 2·(−3)).
a | b is a statement (true or false), not a number. Don't write “3 | 12 = 4.” The number is 12/3 = 4.
Let a, b, c be integers with a ≠ 0.
- If a | b and a | c, then a | (b + c).
- If a | b, then a | bc for every integer c.
- If a | b and b | c, then a | c.
Corollary (used constantly): if a | b and a | c, then a | (mb + nc) for all integers m, n.
(1) If b = sa and c = ta, then b + c = (s + t)a. (2) If b = sa then bc = (sc)a. (3) If b = sa and c = tb then c = (ts)a. Corollary: a | mb and a | nc by (2), so a | mb + nc by (1).
Claim: if 3 | x and 3 | y, then 3 | 5x − 2y.
- Unpack the definition: x = 3s and y = 3t for some integers s, t.
- Substitute: 5x − 2y = 15s − 6t.
- Factor the 3 back out: = 3(5s − 2t). Since 5s − 2t is an integer, 3 | 5x − 2y. □
Turn “divides” into “= a·(integer)”, do algebra, then factor a out.
Let a be an integer and d a positive integer. Then there are unique integers q and r with 0 ≤ r < d such that a = dq + r.
q is the quotient and r the remainder: q = a div d, r = a mod d. (Proof comes later, with induction.)
The remainder is never negative: 0 ≤ r < d. For negative a, round the quotient down. −11 = (−1)·10 − 1 is not the division algorithm because r = −1 < 0.
a mod d is where you land on a clock with d hours (labeled 0 to d − 1) after moving a steps from 0. Negative a means walking backwards: 11 steps back on a 10-hour clock lands on 9.
If a, b are integers and m is a positive integer, then a is congruent to b modulo m, written a ≡ b (mod m), if m | (a − b). m is the modulus.
a ≡ b (mod m) ⟺ a mod m = b mod m (same remainder; HW 4.5) ⟺ a = b + km for some integer k.
5 ≡ 3 (mod 2) since 2 | 2. 7 ≡ 11 (mod 4) since 4 | −4. 7 ≡ −1 (mod 4) since 4 | 8.
a mod m is a function that outputs a number in {0, …, m − 1}. a ≡ b (mod m) is a statement that's true or false. “17 mod 5 = 2” and “17 ≡ 2 (mod 5)” and “17 ≡ −3 (mod 5)” are all true, but “17 mod 5 = −3” is false.
If a ≡ b (mod m) and c ≡ d (mod m), then a + c ≡ b + d (mod m) and ac ≡ bd (mod m).
Also: a ≡ a; if a ≡ b then b ≡ a; if a ≡ b and b ≡ c then a ≡ c (mod m).
m | (a − b) and m | (c − d), so m | (a − b) + (c − d) = (a + c) − (b + d). For products: ac − bd = c(a − b) + b(c − d), and m divides both terms, so m divides the sum. Transitivity: a − c = (a − b) + (b − c).
Upshot: you can add, multiply, reorder and chain congruences just like equations. Rosen Cor 2: (a + b) mod m = ((a mod m) + (b mod m)) mod m and ab mod m = ((a mod m)(b mod m)) mod m.
(101 · 47) mod 9: 101 ≡ 2 and 47 ≡ 2 (mod 9), so the product ≡ 4. No need to compute 4747. (Check: 4747 = 527·9 + 4.)
Parity in mod language: n even ⟺ n ≡ 0 (mod 2), n odd ⟺ n ≡ 1 (mod 2). If n ≡ 1 then n² ≡ 1·1 = 1 (mod 2), so odd squares are odd, in one line.
ac ≡ bc (mod m) does not imply a ≡ b (mod m), even if c ≢ 0. Example: 2·3 ≡ 4·3 (mod 6) (6 ≡ 12) but 2 ≢ 4 (mod 6). Cancellation works when gcd(c, m) = 1 (§18).
(a + b)² ≡ a² + b² (mod 2), since (a + b)² = a² + 2ab + b² and 2ab ≡ 0. False over the integers, true mod 2. Later (§20): (a + b)ᵖ ≡ aᵖ + bᵖ (mod p) for every prime p (the Frobenius identity), which matters for cryptography and primality testing.
Find 45 div 7 and 45 mod 7. Then find −45 mod 7.
Hint
For the negative one, round the quotient down.Answer
45 = 7·6 + 3, so 6 and 3. −45 = 7(−7) + 4, so 4.True or false: 23 ≡ −5 (mod 7)?
Hint
Is 23 − (−5) divisible by 7?Answer
True: 28 = 4·7.Compute (123·456) mod 5 without multiplying.
Answer
123 ≡ 3 and 456 ≡ 1, so the answer is 3.If 4 | a and 4 | b, must 4 | 3a − 2b?
Answer
Yes. a = 4s and b = 4t, so 3a − 2b = 4(3s − 2t).
§15Base-b expansions & fast modular powers
Lecture 7 · Rosen §4.2 · HW 4.7–4.9
Base b writes numbers using powers of b. Repeated squaring computes huge powers mod m in a handful of steps.
Let b be an integer greater than 1. Every positive integer n can be written uniquely as
n = a_k b^k + a_{k−1} b^{k−1} + ⋯ + a₁ b + a₀
where each digit satisfies 0 ≤ aᵢ < b and the leading digit a_k ≠ 0. This is the base b expansion of n, written (a_k … a₁a₀)_b. (Proved later by induction.)
Decimal: 3978 = 3·10³ + 9·10² + 7·10 + 8. Hexadecimal uses digits 0–9, A–F (A = 10, …, F = 15).
Dividing by 10 peels off the last digit: 3978 = 397·10 + 8. The remainder is the last digit and the quotient is everything else. The same works in any base, so repeatedly divide by b; the remainders are the digits, last digit first.
Another: 200 in base 3. 200 = 66·3 + 2, 66 = 22·3 + 0, 22 = 7·3 + 1, 7 = 2·3 + 1, 2 = 0·3 + 2. Reading remainders bottom-up: 200 = (21102)₃. Check: 2·81 + 1·27 + 1·9 + 0·3 + 2 = 200.
Fast modular exponentiation (repeated squaring)
- Square repeatedly, reducing mod m each time: a, a², a⁴, a⁸, a¹⁶, … (each is the previous one squared).
- Write the exponent in binary, i.e. as a sum of powers of 2.
- Multiply together the matching powers, reducing mod m as you go.
This takes about 2·log₂(n) multiplications instead of n, and numbers never get bigger than m². Lecture: “very important for many modern computer algorithms.”
Sanity check with Fermat (§20): 5¹⁰ ≡ 1, so 5⁴³ ≡ 5³ = 125 ≡ 4. ✓
Convert (10110)₂ to decimal.
Answer
16 + 4 + 2 = 22.Convert 50 to binary.
Hint
Divide by 2 repeatedly; read the remainders bottom-up.Answer
(110010)₂ = 32 + 16 + 2.Compute 3¹⁰ mod 11 by repeated squaring.
Hint
10 = 8 + 2.Answer
3² = 9, 3⁴ ≡ 81 ≡ 4, 3⁸ ≡ 16 ≡ 5, so 3¹⁰ ≡ 5·9 = 45 ≡ 1.
§16Primes
Lecture 8 · Rosen §4.3 · HW 4.11
Primes are the building blocks: every integer above 1 factors into primes in exactly one way, and there are infinitely many primes.
An integer p > 1 is prime if its only positive factors are 1 and p. An integer greater than 1 that is not prime is composite.
2, 3, 5 are prime; 4 (factors 1, 2, 4) and 6 (factors 1, 2, 3, 6) are composite. 1 is neither (it has only one positive factor). n is composite ⟺ some a with 1 < a < n divides n.
Every integer greater than 1 can be written uniquely as a prime or a product of primes, up to the order of the factors. Grouping repeated primes: n = p₁^{a₁} p₂^{a₂} ⋯ p_k^{a_k}.
Example: 360 = 2³ · 3² · 5; lecture's example: 6,061,496 = 2³ · 7³ · 47², and that is the only way.
(Uniqueness is proved using “if p | ab then p | a or p | b,” §18.)
Pad both factorizations with zero exponents so they use the same primes: a = p₁^{a₁}⋯pₙ^{aₙ}, b = p₁^{b₁}⋯pₙ^{bₙ}.
- Multiplying adds exponents: ab = p₁^{a₁+b₁} ⋯ pₙ^{aₙ+bₙ}. E.g. (2²·3·5)(2·3³·7) = 2³·3⁴·5·7.
- a | b ⟺ aᵢ ≤ bᵢ for every i. (⇒: if b = ad, uniqueness of factorization gives bᵢ = aᵢ + dᵢ ≥ aᵢ.)
If n is composite, then n has a prime divisor ≤ √n. (If n = ab with 1 < a ≤ b, then a² ≤ ab = n.)
So to test n, try dividing by primes up to √n. Example: 101 isn't divisible by 2, 3, 5, 7, and √101 < 11, so 101 is prime.
List 2, 3, …, N. Circle the first number not crossed out (it's prime) and cross out all its multiples. Repeat. Up to 30 the survivors are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29. You can stop once the next prime exceeds √N.
There are infinitely many primes.
Suppose for a contradiction there were only finitely many primes p₁, p₂, …, pₙ. Let Q = p₁p₂⋯pₙ + 1. Each pᵢ leaves remainder 1 when divided into Q, so no pᵢ divides Q, so no pᵢ appears in Q's prime factorization. But Q > 1 has a prime factorization, so it contains a prime not on our list. Contradiction!
E.g. from 2, 3, 5: 2·3·5 + 1 = 31 must have a prime factor other than 2, 3, 5.
The proof does not say p₁⋯pₙ + 1 is prime. 2·3·5·7·11·13 + 1 = 30031 = 59 · 509. It only says Q has a prime factor that's not on the list. (HW 4.11 adapts this argument to primes ≡ 3 mod 4.)
- Prime Number Theorem (Hadamard and de la Vallée Poussin, 1896): π(x), the number of primes ≤ x, satisfies π(x) / (x / ln x) → 1 as x → ∞. Originally proved with complex analysis. An even better estimate is the logarithmic integral Li(x). The Riemann Hypothesis is equivalent to the error |π(x) − Li(x)| being O(√x log x).
- Bertrand's postulate (a theorem): for every n ≥ 2 there is a prime p with n < p < 2n.
- Twin Prime Conjecture (open): infinitely many p with p and p + 2 both prime. Heuristic: treat n as “prime with probability 1/ln n.” Then the expected number of twin primes is about Σ 1/(ln n)², which diverges.
Is 91 prime?
Hint
Test primes up to √91 ≈ 9.5.Answer
No: 91 = 7·13.Prime-factor 360.
Answer
2³·3²·5.Why isn't 1 prime?
Answer
A prime needs exactly two positive divisors, and 1 has only one. (This also keeps factorizations unique.)
§17gcd, lcm & the Euclidean algorithm
Lecture 8 · Rosen §4.3 · HW 4.3–4.4, 4.10
gcd is the biggest shared divisor and lcm the smallest shared multiple. The Euclidean algorithm finds the gcd fast by repeated division.
Let a, b be integers, not both zero. The greatest common divisor gcd(a, b) is the largest integer d with d | a and d | b.
a and b are relatively prime if gcd(a, b) = 1. Integers a₁, …, aₙ are pairwise relatively prime if gcd(aᵢ, aⱼ) = 1 for all i ≠ j.
The least common multiple lcm(a, b) of positive integers a, b is the smallest positive integer divisible by both.
gcd(6, 10) = 2, gcd(0, 11) = 11 (everything divides 0), gcd(−12, 18) = 6, lcm(6, 10) = 30, lcm(12, 60) = 60.
10, 17, 21 are pairwise relatively prime. 10, 19, 24 are not, since gcd(10, 24) = 2 (even though gcd(10, 19) = gcd(19, 24) = 1).
If a = p₁^{a₁}⋯pₙ^{aₙ} and b = p₁^{b₁}⋯pₙ^{bₙ}, then
gcd(a, b) = p₁^{min(a₁,b₁)} ⋯ pₙ^{min(aₙ,bₙ)} lcm(a, b) = p₁^{max(a₁,b₁)} ⋯ pₙ^{max(aₙ,bₙ)}
and therefore gcd(a, b) · lcm(a, b) = ab (Rosen §4.3 Thm 5), because min(x, y) + max(x, y) = x + y.
(gcd) g = ∏ p^{min} divides a and b since min(aᵢ, bᵢ) ≤ aᵢ, bᵢ. If d = ∏ p^{dᵢ} divides both, then dᵢ ≤ aᵢ and dᵢ ≤ bᵢ, so dᵢ ≤ min(aᵢ, bᵢ), so d | g and d ≤ g. (min + max lemma) If x ≤ y, min + max = x + y; if x > y, min + max = y + x.
a = 2³·3²·5 = 360, b = 2·3⁴·7 = 1134. gcd = 2¹·3² = 18. lcm = 2³·3⁴·5·7 = 22680. Check: 18 · 22680 = 408240 = 360 · 1134.
Lecture 9: a = 7²·11⁴·13, b = 5³·11·13²: gcd = 11·13, lcm = 5³·7²·11⁴·13², and a ∤ b (b has no factor of 7).
If a = bq + r (all integers), then gcd(a, b) = gcd(b, r).
It suffices to show a, b and b, r have the same common divisors. If d | a and d | b, then d | a − bq = r. If d | b and d | r, then d | bq + r = a.
To find gcd(a, b) with a ≥ b > 0: divide, then replace (a, b) by (b, remainder). Repeat until the remainder is 0. The last nonzero remainder is the gcd.
r₀ = a, r₁ = b; rᵢ₋₁ = rᵢ qᵢ + rᵢ₊₁ ⇒ gcd(rᵢ₋₁, rᵢ) = gcd(rᵢ, rᵢ₊₁); … gcd(rₙ, 0) = rₙ.
Lecture 9: gcd(126, 108): 126 = 108·1 + 18, 108 = 18·6 + 0, so the gcd is 18.
If 2ⁿ > a > b, the algorithm takes at most 2n steps, because every two steps the remainder at least halves: rᵢ₊₂ < rᵢ / 2.
Case 1: rᵢ₊₁ ≤ rᵢ/2. Then rᵢ₊₂ < rᵢ₊₁ ≤ rᵢ/2. Case 2: rᵢ₊₁ > rᵢ/2. Then the quotient is 1, so rᵢ₊₂ = rᵢ − rᵢ₊₁ < rᵢ − rᵢ/2 = rᵢ/2.
Factoring is slow (much of modern cryptography would break if it weren't), so computing gcds by factoring is inefficient. Euclid's way avoids factoring entirely.
Use factorizations to find gcd(48, 180) and lcm(48, 180).
Hint
48 = 2⁴·3, 180 = 2²·3²·5.Answer
gcd = 2²·3 = 12, lcm = 2⁴·3²·5 = 720. Check: 12·720 = 48·180 = 8640.Use Euclid to find gcd(91, 35).
Answer
91 = 2·35 + 21, 35 = 1·21 + 14, 21 = 1·14 + 7, 14 = 2·7 + 0. So the gcd is 7.
§18Bézout & solving congruences
Lecture 10 · Rosen §4.3–4.4 · HW 5.1–5.6
Run Euclid backwards to write gcd = sa + tb. That gives inverses mod m, which let you solve ax ≡ b (mod m).
If a and b are positive integers, there exist integers s and t such that gcd(a, b) = sa + tb. That is, the gcd is an integer linear combination of a and b.
s, t are Bézout coefficients, and gcd(a, b) = sa + tb is Bézout's identity. They aren't unique. The extended Euclidean algorithm computes them.
Run Euclid forwards. Then start from the second-to-last equation, solved for the gcd, and substitute backwards, each time replacing the smaller remainder by its formula from the line above, until only a and b remain. Simplify (collect terms) after every substitution.
So gcd(72, 26) = 2 = 4·72 − 11·26. Check: 288 − 286 = 2.
So 1 = −15·49 + 23·32. Check: −735 + 736 = 1.
Write gcd(84, 33) as s·84 + t·33.
Each step replaces the smallest remaining remainder using the line above it. Stop when only 84 and 33 are left. Check: 168 − 165 = 3 ✓.
Table method (same answer, fewer slips): keep columns r, s, t where each row means r = s·84 + t·33. Start with rows (84, 1, 0) and (33, 0, 1). Each new row = (row two up) − q × (row above), where q is Euclid's quotient.
If gcd(a, b) = 1 and a | bc, then a | c.
By Bézout, 1 = sa + tb. Multiply by c: c = csa + ctb. Now a | csa obviously, and a | ctb since a | bc. So a divides the sum, c.
If p is prime and p | ab, then p | a or p | b. More generally, if p | a₁a₂⋯aₙ then p | aᵢ for some i.
Assume p | ab. If p | a we're done. Otherwise p ∤ a, and since p's only positive divisors are 1 and p, gcd(a, p) = 1. By the corollary, p | b.
This is the key ingredient in the uniqueness part of the Fundamental Theorem of Arithmetic.
Fails for composite numbers: 6 | 30 = 10·3, but 6 ∤ 10 and 6 ∤ 3.
Solving ax ≡ b (mod m)
A linear congruence is ax ≡ b (mod m) with unknown x. If x is a solution, so is anything ≡ x (mod m), so you only need to search 0, 1, …, m − 1. But there's a much faster way.
2x ≡ 3 (mod 12): no solution. 2x − 3 is odd, and 12 can't divide an odd number.
3x ≡ 1 (mod 7): x = 5, since 15 = 2·7 + 1.
Let d = gcd(a, m). If d ∤ b, then ax ≡ b (mod m) has no solution.
By contraposition. Suppose ax ≡ b (mod m), so ax − b = km for some integer k. Then b = ax − km. Since d | a and d | m, d divides ax − km = b.
If d = gcd(a, m) divides b, write d = sa + tm (extended Euclid) and b = cd. Then x = cs is a solution.
a(cs) = c(sa) = c(d − tm) = cd − ctm ≡ cd = b (mod m), since m ≡ 0.
- Compute d = gcd(a, m) with Euclid.
- If d ∤ b: no solution. Stop.
- Otherwise use extended Euclid to write d = sa + tm. Then x₀ = (b/d)·s is a solution.
- All solutions: x = x₀ + k·(m/d) for integers k. So there are exactly d solutions mod m (HW 5.3 proves this).
From before, gcd(26, 72) = 2 = 4·72 − 11·26, so 26·(−11) ≡ 2 (mod 72).
- 26x ≡ 2: x = −11 ≡ 61 works.
- 26x ≡ 3: no solution, since 2 ∤ 3.
- 26x ≡ 6: 6 = 3·2, so x = 3·(−11) = −33 ≡ 39. Since m/d = 36, all solutions are x ≡ 39 (mod 36), i.e. x ≡ 3 or 39 (mod 72). Check: 26·3 = 78 ≡ 6 and 26·39 = 1014 = 14·72 + 6.
d = 3 and 3 | 9, so solvable. s = 3, b/d = 3, so x₀ = 9. Check: 15·9 = 135 = 6·21 + 9. m/d = 7, so all solutions are x ≡ 2 (mod 7): x = 2, 9, 16 in {0, …, 20}.
7x ≡ 3 (mod 10). gcd(7, 10) = 1, so 7 has an inverse. Try multiples: 7·3 = 21 ≡ 1, so the inverse is 3. Multiply both sides by 3: x ≡ 9 (mod 10). Check: 7·9 = 63 ≡ 3 ✓.
12x ≡ 8 (mod 20). d = gcd(12, 20) = 4, and 4 | 8, so it's solvable with 4 solutions. Euclid gives 4 = 2·12 − 20, so s = 2 and x₀ = (8/4)·2 = 4. Step size m/d = 5: x = 4, 9, 14, 19.
Inverses mod m
An integer ā with āa ≡ 1 (mod m) is an inverse of a modulo m. It's the mod-m version of 1/a.
If gcd(a, m) = 1 and m > 1, then a has an inverse mod m, and it is unique mod m. (Conversely, if gcd(a, m) > 1 there's no inverse; HW 5.5.)
How to find it: Bézout gives 1 = sa + tm, so sa ≡ 1 (mod m), and s is the inverse.
5·3 = 15 ≡ 1 (mod 7), so 3 is an inverse of 5 mod 7. To solve 5y ≡ 4 (mod 7), multiply both sides by 3: y ≡ 12 ≡ 5. Check: 25 ≡ 4.
From 1 = −15·49 + 23·32: 23 is the inverse of 32 mod 49 (32·23 = 736 = 15·49 + 1), and −15 ≡ 17 is the inverse of 49 mod 32.
General trick: once you have ā, the solution of ay ≡ b is y ≡ āb, because a(āb) = (aā)b ≡ b.
If ac ≡ bc (mod m) and gcd(c, m) = 1, then a ≡ b (mod m).
Since gcd(c, m) = 1, c has an inverse c̄. Multiply both sides by c̄: a(cc̄) ≡ b(cc̄), so a·1 ≡ b·1 (mod m).
Write gcd(91, 35) = 7 as s·91 + t·35.
Hint
Start from 7 = 21 − 14 and work upward.Answer
7 = 21 − (35 − 21) = 2·21 − 35 = 2(91 − 2·35) − 35 = 2·91 − 5·35.Find the inverse of 3 mod 11.
Answer
4, since 3·4 = 12 ≡ 1.Solve 3x ≡ 5 (mod 11).
Hint
Multiply both sides by the inverse of 3.Answer
x ≡ 4·5 = 20 ≡ 9. Check: 27 ≡ 5.Does 6x ≡ 4 (mod 9) have a solution?
Answer
No. gcd(6, 9) = 3 doesn't divide 4.
§19Chinese remainder theorem
Lectures 10–11 · Rosen §4.4 · HW 5.7–5.8
If you know a number's remainders for several coprime moduli, you know the number itself, up to their product.
Let m₁, …, mₙ be pairwise relatively prime positive integers greater than 1, and a₁, …, aₙ any integers. Then the system
x ≡ a₁ (mod m₁), x ≡ a₂ (mod m₂), …, x ≡ aₙ (mod mₙ)
has a unique solution modulo M = m₁m₂⋯mₙ: there's a solution with 0 ≤ x < M, and every other solution is congruent to it mod M. (Existence: lecture. Uniqueness: HW 5.8.)
Think of a combination lock with several dials, of sizes 3, 7 and 10, that all click forward together. After x clicks, the dials read x mod 3, x mod 7, x mod 10. CRT says that when the dial sizes share no common factor, the readings determine x exactly, up to a full cycle of 3·7·10 = 210 clicks.
- M = m₁⋯mₙ, and for each i, Mᵢ = M / mᵢ (the product of all the other moduli).
- Find yᵢ = an inverse of Mᵢ mod mᵢ: Mᵢyᵢ ≡ 1 (mod mᵢ). It exists because gcd(Mᵢ, mᵢ) = 1.
- x = a₁M₁y₁ + a₂M₂y₂ + ⋯ + aₙMₙyₙ, then reduce mod M.
Why it works: mod mᵢ, every term except the i-th has a factor of mᵢ inside Mⱼ (j ≠ i), so it's ≡ 0. The i-th term is aᵢ·(Mᵢyᵢ) ≡ aᵢ·1. So x ≡ aᵢ (mod mᵢ) for every i. Each term is a “switch” that is 1 on its own dial and 0 on all the others.
Solve x ≡ 2 (mod 3), x ≡ 5 (mod 7), x ≡ 3 (mod 10).
Check: 173 = 57·3 + 2 ✓, 173 = 24·7 + 5 ✓, 173 ends in 3 ✓.
Lecture 10's smaller one: x ≡ 1 (mod 2), x ≡ 2 (mod 3), x ≡ 4 (mod 5) has M = 30, and the solution is x = 29 (search 0–29 or construct).
x ≡ 2 (mod 5), x ≡ 3 (mod 7). The first says x = 2 + 5t. Plug in: 2 + 5t ≡ 3 (mod 7), so 5t ≡ 1, so t ≡ 3 (5·3 = 15 ≡ 1). So t = 3 + 7u and x = 2 + 5(3 + 7u) = 17 + 35u, i.e. x ≡ 17 (mod 35).
The moduli must be pairwise relatively prime. x ≡ 0 (mod 2) and x ≡ 1 (mod 4) has no solution: the first makes x even, the second makes x odd.
Solve x ≡ 2 (mod 3), x ≡ 3 (mod 4).
Hint
List the numbers ≡ 3 (mod 4): 3, 7, 11, …Answer
x ≡ 11 (mod 12).Why doesn't the CRT apply to x ≡ 1 (mod 4), x ≡ 2 (mod 6)?
Answer
4 and 6 aren't coprime. In fact there's no solution: the first makes x odd, the second makes it even.
§20Fermat's little theorem
Lecture 11 · Rosen §4.4 · HW 5.9–5.10
Mod a prime p, ap−1 ≡ 1 (when p ∤ a). So exponents can be shrunk mod p − 1.
(x + y)ⁿ = Σₖ C(n, k) xⁿ⁻ᵏyᵏ where C(n, k) = n! / (k!(n − k)!), the rows of Pascal's triangle.
E.g. (x + y)⁷ = x⁷ + 7x⁶y + 21x⁵y² + 35x⁴y³ + 35x³y⁴ + 21x²y⁵ + 7xy⁶ + y⁷. Notice 7 divides every middle coefficient.
If p is prime and 1 ≤ k ≤ p − 1, then p | C(p, k): p appears in the factorization of p! but not of k! or (p − k)!. Hence
(x + y)ᵖ ≡ xᵖ + yᵖ (mod p) for p prime.
If p is prime and a is an integer not divisible by p, then aᵖ⁻¹ ≡ 1 (mod p). Furthermore, for every integer a, aᵖ ≡ a (mod p).
(Lecture, for a ≥ 1.) Write a = 1 + 1 + ⋯ + 1 (a ones) and apply the Freshman's dream over and over: aᵖ = (1 + (a − 1))ᵖ ≡ 1ᵖ + (a − 1)ᵖ ≡ 1ᵖ + 1ᵖ + (a − 2)ᵖ ≡ ⋯ ≡ 1ᵖ + ⋯ + 1ᵖ = a (mod p). So aᵖ ≡ a. If p ∤ a, then gcd(a, p) = 1, so we can cancel one a (cancellation law): aᵖ⁻¹ ≡ 1 (mod p).
Mod a prime p (and p ∤ a), exponents only matter mod p − 1. Write the exponent as q(p − 1) + r; then aⁿ = (aᵖ⁻¹)^q · aʳ ≡ 1^q · aʳ = aʳ.
3¹⁰⁰ mod 7: 3⁶ ≡ 1 (mod 7), and 100 = 16·6 + 4, so 3¹⁰⁰ ≡ 3⁴ = 81 ≡ 4.
2¹⁰⁰⁰ mod 11: 2¹⁰ ≡ 1 (mod 11), and 1000 = 100·10, so 2¹⁰⁰⁰ ≡ 1.
Reduce the exponent mod p − 1, not mod p. And it needs p prime and p ∤ a.
Primality testing
Given n, pick a with 0 < a < n. If aⁿ⁻¹ ≢ 1 (mod n), then n is definitely not prime (contrapositive of Fermat). If aⁿ⁻¹ ≡ 1, n may or may not be prime.
Example: 2¹⁴ mod 15 = 4 ≠ 1 (since 2⁴ ≡ 1, 2¹⁴ ≡ 2² = 4), so 15 is composite, without finding a factor.
Modern primality tests (e.g. Miller–Rabin, used to find huge primes for cryptography) are built on this: pass many such tests and the probability n is prime is provably very high.
A composite n with bⁿ⁻¹ ≡ 1 (mod n) is a pseudoprime to the base b. A composite n that is a pseudoprime to every base b with gcd(b, n) = 1 is a Carmichael number; the smallest is 561 = 3·11·17. So the Fermat test alone can be fooled.
If p is prime and gcd(e, p − 1) = 1, then f(m) = mᵉ mod p is a one-to-one function on {0, …, p − 1}. Its inverse is g(c) = cᵈ mod p, where de − k(p − 1) = 1 (Bézout).
g(f(m)) ≡ mᵈᵉ = m^{1 + k(p−1)} = m·(mᵖ⁻¹)ᵏ ≡ m·1ᵏ = m (mod p) by Fermat, for p ∤ m; and if m = 0 both sides are 0. So g undoes f, which forces f to be injective.
Example: p = 7, e = 5 (gcd(5, 6) = 1). 5·5 = 25 = 4·6 + 1, so d = 5. Then f(3) = 3⁵ mod 7 = 5 and g(5) = 5⁵ mod 7 = 3. ✓ Modular powers otherwise behave “randomly” enough to be used in pseudorandom number generators.
Compute 2¹⁰⁰ mod 7.
Hint
2⁶ ≡ 1, so reduce 100 mod 6.Answer
100 = 16·6 + 4, so 2¹⁰⁰ ≡ 2⁴ = 16 ≡ 2.Why can't you use Fermat to compute 3¹⁰⁰ mod 9?
Answer
9 isn't prime (and 3 divides 9 anyway).2¹⁴ mod 15 = 4. What does that prove?
Answer
15 is composite. A prime p would give 2^(p−1) ≡ 1.
§21RSA public-key cryptography
Lecture 11 · Rosen §4.6 · HW 5.11–5.12
Anyone can encrypt with the public key (n, e). Only someone who knows how n factors can compute d and decrypt.
Alice hands out open padlocks to everyone (the public encryption function f) but keeps the only key (the secret decryption function g, with g(f(m)) = m). Anyone can snap a message shut, but only Alice can open it. Knowing how to compute f and seeing f(m) should not let an eavesdropper (Eve) recover m. Scary fact from lecture: nobody has proved this is actually hard. It's a very important open problem.
- Alice privately picks two large primes p, q and sets n = pq.
- She chooses e with gcd(e, (p − 1)(q − 1)) = 1.
- Public key: (n, e). Encryption: c = f(m) = mᵉ mod n.
- Private: using Bézout, she finds d with de ≡ 1 (mod (p − 1)(q − 1)), i.e. de − k(p − 1)(q − 1) = 1. Decryption: m = g(c) = cᵈ mod n.
- She keeps p, q, d (and (p − 1)(q − 1)) secret.
Encrypting and decrypting both use fast modular exponentiation (§15).
With p, q, n, e, d, k as above, g(f(m)) = m for all 0 ≤ m < n.
(Case gcd(m, p) = gcd(m, q) = 1; the general case is HW 5.12.) g(f(m)) ≡ (mᵉ)ᵈ = m^{1 + k(p−1)(q−1)} = m · x, where x = m^{k(p−1)(q−1)}. By Fermat, mᵖ⁻¹ ≡ 1 (mod p), so x = (mᵖ⁻¹)^{k(q−1)} ≡ 1 (mod p). Likewise x ≡ 1 (mod q). Since 1 also solves both congruences, uniqueness in the CRT gives x ≡ 1 (mod pq = n). So g(f(m)) ≡ m (mod n), and both are in {0, …, n − 1}, so they're equal.
Anyone who could factor n into p·q could compute (p − 1)(q − 1), then d, and decrypt. RSA's security rests on factoring huge n being infeasible. RSA keys use primes with hundreds of digits each; the lecture mentioned RSA-896 had just been factored. A quantum computer running Shor's algorithm would break RSA, which motivates post-quantum cryptography.
How browser trust works (simplified): your computer ships with public keys of certificate authorities (e.g. GlobalSign, DigiCert). A site like pets.com presents a certificate, signed by such an authority, binding its domain to its own public key. Your browser checks the signature, then uses the site's public key.
The related problem of recovering m from mᵉ mod n (with e, n known) has no known fast general method when n is composite, short of trying every m.
p = 3, q = 11, e = 7. Find n, (p − 1)(q − 1), and d.
Hint
d is the inverse of e mod (p − 1)(q − 1).Answer
n = 33, (p − 1)(q − 1) = 20, and d = 3 since 7·3 = 21 ≡ 1 (mod 20).Encrypt m = 2 with the public key (33, 7).
Answer
2⁷ = 128 = 3·33 + 29, so c = 29. (Decrypt check: 29³ ≡ (−4)³ = −64 ≡ 2.)What would Eve need in order to find d?
Answer
(p − 1)(q − 1), which means factoring n.
Part V · recent lectures
Induction & recursion
The lecture notes after Oct 6 aren't in your folder, so Parts V and VI follow Rosen Chapters 5–6, which is what the syllabus lists for these weeks. If your lecture notes differ, trust them.
§22Mathematical induction
Rosen §5.1 · syllabus: Oct 8
To prove something for every n, prove it for the first n, then prove that being true for one n forces it to be true for the next.
A line of dominoes, one for each n. If (1) you knock over the first one and (2) every domino that falls knocks over the next, then every domino falls. You never have to check them one at a time.
To prove P(n) for all positive integers n:
- Basis step: show P(1) is true.
- Inductive step: show that for every k ≥ 1, if P(k) is true then P(k + 1) is true. Assuming P(k) here is called the inductive hypothesis (IH).
In logic: [P(1) ∧ ∀k (P(k) → P(k + 1))] → ∀n P(n). The start can be any integer b instead of 1 (then you get P(n) for all n ≥ b).
Basis: “P(1) says … , which is true because …”
Inductive step: “Let k ≥ 1 and assume P(k): [write it out]. We show P(k + 1): [write out the goal].” Start from the k + 1 side, find the P(k) piece inside it, replace it using the IH, and simplify until you reach the goal.
Conclusion: “By induction, P(n) holds for all n ≥ 1.”
Claim: 1 + 2 + ⋯ + n = n(n + 1)/2.
Basis: n = 1: the left side is 1 and the right side is 1·2/2 = 1 ✓.
Step: assume 1 + ⋯ + k = k(k + 1)/2. Then
The key move in sum proofs: the sum up to k + 1 is the sum up to k plus one more term.
Claim: 1 + 3 + 5 + ⋯ + (2n − 1) = n². (Check: 1 = 1, 1 + 3 = 4, 1 + 3 + 5 = 9.)
Basis: 1 = 1² ✓. Step: assume the sum up to (2k − 1) is k². Add the next odd number, 2(k + 1) − 1 = 2k + 1: the total is k² + 2k + 1 = (k + 1)² ✓.
Claim: 3 | n³ − n for every n ≥ 1.
Basis: 1 − 1 = 0, and 3 | 0 ✓.
Step: assume 3 | k³ − k. Expand: (k + 1)³ − (k + 1) = k³ + 3k² + 3k + 1 − k − 1 = (k³ − k) + 3(k² + k). The first part is divisible by 3 by the IH, and the second part has a factor of 3. A sum of multiples of 3 is a multiple of 3 ✓.
The key move in divisibility proofs: rearrange the k + 1 expression so the k expression appears inside it.
Claim: 2ⁿ < n! for all n ≥ 4. (It's false for n = 1, 2, 3, so the basis is n = 4.)
Basis: 2⁴ = 16 < 24 = 4! ✓. Step: assume 2ᵏ < k! with k ≥ 4. Then 2ᵏ⁺¹ = 2·2ᵏ < 2·k! < (k + 1)·k! = (k + 1)!, using 2 < k + 1 ✓.
- Don't assume P(k + 1). You assume P(k) and prove P(k + 1).
- You must actually use the inductive hypothesis. If you didn't, it wasn't an induction proof.
- Don't skip the basis. Without a first domino, nothing falls.
- Check that the step works for the smallest k. The famous fake proof that “all horses are the same color” breaks exactly at k = 1 → 2.
Prove 2 + 4 + ⋯ + 2n = n(n + 1) by induction.
Hint
In the step, add the next term 2(k + 1) to k(k + 1).Answer
Basis: 2 = 1·2. Step: k(k + 1) + 2(k + 1) = (k + 1)(k + 2).Prove 5 | 6ⁿ − 1 for all n ≥ 1.
Hint
6ᵏ⁺¹ − 1 = 6(6ᵏ − 1) + 5.Answer
Basis: 5 | 5. Step: by the IH 5 | 6ᵏ − 1, so 5 divides 6(6ᵏ − 1) + 5.What's wrong with starting the inductive step with “Assume P(k + 1)”?
Answer
That assumes what you're trying to prove. Assume P(k), then prove P(k + 1).
§23Strong induction & well-ordering
Rosen §5.2 · syllabus: Oct 8
Strong induction lets you assume all the earlier cases, not just the one before. Well-ordering says every nonempty set of natural numbers has a smallest element.
To prove P(n) for all n ≥ 1: Basis: P(1). Inductive step: for k ≥ 1, assume P(1), P(2), …, P(k) are all true, and prove P(k + 1).
It's just as valid as ordinary induction. Use it when the k + 1 case breaks into pieces that are smaller, but not necessarily equal to k.
Ordinary induction: “if I can reach rung k, I can reach rung k + 1.” Strong induction: “if I can reach every rung up to k, I can reach rung k + 1.” Sometimes you need to step up from a rung further down.
Claim: every integer n ≥ 2 is a product of primes. (This is the existence half of the Fundamental Theorem of Arithmetic, §16.)
Basis: 2 is prime, so it's a product of one prime ✓.
Step: assume every integer from 2 to k is a product of primes. Look at k + 1. If it's prime, done. If not, k + 1 = ab with 2 ≤ a, b ≤ k. By the strong IH, a and b are both products of primes, so ab is too ✓.
Ordinary induction wouldn't help here: knowing about k says nothing about k + 1's factors a and b.
Claim: every amount n ≥ 12 cents can be made from 4¢ and 5¢ stamps.
Basis (four cases): 12 = 4+4+4, 13 = 4+4+5, 14 = 4+5+5, 15 = 5+5+5.
Step: for k ≥ 15, to make k + 1 cents, make (k + 1) − 4 = k − 3 cents (possible by the IH, since 12 ≤ k − 3 ≤ k) and add a 4¢ stamp ✓.
Why four basis cases? The step jumps back 4, so it needs four starting values to cover 12, 13, 14, 15 before it takes over.
Every nonempty set of nonnegative integers has a least element.
It's equivalent to induction, and gives the “smallest counterexample” proof style: suppose the claim fails, take the smallest n where it fails, and show an even smaller failure exists. Contradiction.
Given a and d > 0, look at the set S = {a − dq : q an integer, a − dq ≥ 0}. It's nonempty (take q very negative). By well-ordering, it has a least element r = a − dq, so a = dq + r and r ≥ 0.
If r ≥ d, then r − d = a − d(q + 1) would be a smaller element of S. Contradiction. So 0 ≤ r < d ✓.
Why does the postage-stamp proof need four basis cases?
Answer
The step reaches back 4 (it uses k − 3), so 12 through 15 must be checked directly.What's the least element of {n ∈ ℕ : n² > 50}?
Answer
8 (7² = 49 isn't enough, 8² = 64 is).
§24Recursive definitions & structural induction
Rosen §5.3 · syllabus: Oct 13
Define something by giving a starting value and a rule that builds each new value from earlier ones. Then prove things about it by induction, which follows the same structure.
Basis step: give the value at the start (e.g. f(0)). Recursive step: give a rule for f(n + 1) in terms of earlier values.
- f(0) = 3, f(n + 1) = 2f(n) + 3. Unroll it: f(1) = 2·3 + 3 = 9, f(2) = 2·9 + 3 = 21, f(3) = 45, f(4) = 93.
- Factorial: 0! = 1 and (n + 1)! = (n + 1)·n!.
- Fibonacci: f₀ = 0, f₁ = 1, fₙ = fₙ₋₁ + fₙ₋₂. That gives 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, … Two basis values are needed because each step looks back two.
A recursive definition is a recipe that refers to earlier batches: “Day 0: 3 cookies. Each day: double yesterday's cookies and add 3.” To know day 4, work up from day 0.
Claim: fₙ < 2ⁿ for all n ≥ 1. Basis: f₁ = 1 < 2 and f₂ = 1 < 4. Step: f_{k+1} = f_k + f_{k−1} < 2ᵏ + 2ᵏ⁻¹ < 2ᵏ + 2ᵏ = 2ᵏ⁺¹ ✓. (It uses two earlier cases, so it's strong induction.)
Basis: list some starting elements. Recursive step: rules for building new elements from ones already in the set. Nothing else is in the set.
Example: 3 ∈ S, and if x, y ∈ S then x + y ∈ S. Then S = {3, 6, 9, …}, the positive multiples of 3.
Strings over an alphabet Σ: the empty string λ is in Σ*, and if w ∈ Σ* and x ∈ Σ then wx ∈ Σ* (add one symbol at the end).
To prove every element of a recursively defined set has a property: (1) show the basis elements have it; (2) show each recursive rule preserves it (if the inputs have it, so does the output).
Example: every x in S above is divisible by 3. Basis: 3 is. Step: if 3 | x and 3 | y then 3 | x + y ✓.
a₀ = 1, aₙ₊₁ = 3aₙ − 1. Find a₁, a₂, a₃.
Answer
2, 5, 14.Give a recursive definition of 2ⁿ.
Answer
2⁰ = 1 and 2ⁿ⁺¹ = 2·2ⁿ.1 ∈ S, and if x ∈ S then x + 2 ∈ S. What is S?
Answer
The positive odd numbers.
§25Recursive algorithms
Rosen §5.4 · syllabus: Oct 13
A recursive algorithm solves a problem by calling itself on a smaller version, until it hits a case small enough to answer directly.
Open the doll, find a smaller doll, and repeat until you hit the solid one in the middle (the base case). Every recursive algorithm needs a base case and must shrink the input each call, or it never stops.
gcd(84, 33) → gcd(33, 18) → gcd(18, 15) → gcd(15, 3) → gcd(3, 0) = 3.
Why they're correct: by (strong) induction on the input size. The base case is right, and if the smaller calls return the right answer, then so does this one.
Trace the recursive gcd(30, 12).
Answer
gcd(30, 12) → gcd(12, 6) → gcd(6, 0) = 6.What goes wrong if a recursive algorithm has no base case?
Answer
It never stops.
Part VI · recent lectures
Counting
§26The basic counting rules
Rosen §6.1 · syllabus: Oct 15
Count without listing. Steps done one after another (“and”) multiply; separate alternatives (“or”) add.
3 appetizers and 4 mains: 3 × 4 = 12 different meals (pick one, then the other). Soup or salad, with 2 soups and 3 salads: 2 + 3 = 5 choices (pick from one group or the other).
- Product rule: if a task is a sequence of two steps, with n₁ ways to do the first and n₂ ways to do the second (no matter how the first went), there are n₁·n₂ ways.
- Sum rule: if a task can be done in one of n₁ ways or one of n₂ ways, with no overlap, there are n₁ + n₂ ways.
- Subtraction rule (inclusion–exclusion): if the two groups overlap, n₁ + n₂ − (overlap). Same as |A ∪ B| = |A| + |B| − |A ∩ B| from §11.
- Division rule: if a count of n treats every outcome as d different ones, the true count is n / d.
- License plates with 3 letters then 3 digits: 26·26·26·10·10·10 = 17,576,000.
- Bit strings of length n: 2·2·⋯·2 = 2ⁿ (each position is 0 or 1).
- Subsets of an n-element set: each element is in or out, so 2ⁿ. That's why |𝒫(A)| = 2ⁿ (§10).
- Functions from an m-element set to an n-element set: each of the m inputs picks one of n outputs, so nᵐ. Injective ones: n(n − 1)⋯(n − m + 1), since each input must avoid the outputs already used.
How many 8-bit strings start with 1 or end with 00? Start with 1: 2⁷ = 128. End with 00: 2⁶ = 64. Both: 2⁵ = 32 (counted twice). Total: 128 + 64 − 32 = 160.
4-digit PINs (0000–9999) with at least one 7. Easier to count the opposite: PINs with no 7 at all = 9⁴ = 6561. So the answer is 10⁴ − 9⁴ = 3439. When you see “at least one,” count “none” and subtract.
Seat 4 people around a round table, where rotations count as the same seating. In a row there are 4! = 24 orders, but each circular seating shows up 4 times (once per rotation), so there are 24 / 4 = 6.
The sum rule needs the options to be disjoint. If they overlap, subtract the overlap. The product rule needs the number of choices at each step to not depend on earlier choices.
How many 3-letter strings (A–Z) are there with repeats allowed? With no repeats?
Answer
26³ = 17,576. 26·25·24 = 15,600.5 shirts, 3 pants, and either one of 4 hats or no hat. How many outfits?
Hint
The hat choice has 4 + 1 options.Answer
5·3·5 = 75.How many 3-digit numbers (100–999) have at least one 0?
Hint
Count the ones with no 0, then subtract.Answer
900 − 9·9·9 = 900 − 729 = 171.
§27The pigeonhole principle
Rosen §6.2 · syllabus: Oct 15
If you put more objects than boxes, some box gets at least two. It proves something must happen without saying where.
Pigeonhole principle: if k + 1 or more objects go into k boxes, some box has at least 2 objects.
Generalized: if N objects go into k boxes, some box has at least ⌈N/k⌉ objects.
By contradiction: if every box had at most 1 object (at most ⌈N/k⌉ − 1 for the general version), the total would be at most k (less than N). Contradiction.
- Birthdays: among 367 people, two share a birthday (only 366 possible days).
- Months: among 100 people, at least ⌈100/12⌉ = 9 were born in the same month.
- Socks in the dark: black and white socks only. Grab 3 and you're guaranteed a matching pair (3 socks, 2 colors).
- Number theory: among any n + 1 integers, two have the same remainder mod n (n possible remainders). So their difference is divisible by n.
How many cards must you draw to be sure of 3 cards of the same suit? With 4 suits you need ⌈N/4⌉ ≥ 3, so N ≥ 9. Check: 8 isn't enough (2 of each suit is possible). Answer 9. The pattern: worst case plus one.
Figure out what the “boxes” are. That's usually the whole problem (days, remainders, suits, colors). The principle tells you a box is crowded, never which one.
How many people do you need to guarantee two share a birth month?
Answer
13 (12 months are the boxes).25 students: at least how many were born on the same day of the week?
Answer
⌈25/7⌉ = 4.Why must two of any 6 integers have the same remainder mod 5?
Answer
There are only 5 possible remainders (boxes) for 6 numbers.
§28Permutations & combinations
Rosen §6.3 · syllabus: Oct 15
Choosing r things from n: if order matters it's a permutation P(n, r); if order doesn't matter it's a combination C(n, r).
An r-permutation is an ordered arrangement of r distinct elements chosen from n:
P(n, r) = n(n − 1)(n − 2)⋯(n − r + 1) = n! / (n − r)!
An r-combination is an unordered selection (a subset) of r elements from n:
C(n, r) = n! / (r!(n − r)!) = P(n, r) / r!
C(n, r) is read “n choose r” and is also written (n r) stacked. Note C(n, r) = C(n, n − r): choosing who's in is the same as choosing who's out.
Podium (gold, silver, bronze): Alice-Bob-Cat is different from Bob-Alice-Cat, so order matters → permutation.
Committee of 3: {Alice, Bob, Cat} is one committee in any order, so order doesn't matter → combination.
Each committee corresponds to 3! = 6 podiums, which is why C = P / r! (division rule).
- Medals among 8 runners: P(8, 3) = 8·7·6 = 336.
- A 3-person committee from 8 people: C(8, 3) = 336 / 3! = 56.
- Poker hands: C(52, 5) = 2,598,960.
- Bit strings of length 10 with exactly four 1s: choose which 4 positions get a 1: C(10, 4) = 210.
- A committee of 3 from 9 math and 11 CS majors, with exactly 1 math major: choose the math major, and 2 CS majors: C(9, 1)·C(11, 2) = 9·55 = 495 (product rule).
C(n, k) is the coefficient in (x + y)ⁿ = Σ C(n, k) xⁿ⁻ᵏ yᵏ. Why: expanding n factors of (x + y), a term xⁿ⁻ᵏyᵏ comes from choosing which k of the n factors contribute a y. That's the “Freshman's dream” idea behind Fermat's little theorem (§20).
Ask “if I swap two of my picks, is it a different outcome?” Yes → permutation. No → combination. A “combination lock” is really a permutation, since order matters.
From 10 people, choose (a) a president, VP and treasurer; (b) a 3-person team. How many ways?
Hint
Does swapping two people change the outcome?Answer
(a) order matters: P(10, 3) = 720. (b) it doesn't: C(10, 3) = 120.Compute C(6, 2).
Answer
6·5/2 = 15.How many 5-card hands are all hearts?
Answer
C(13, 5) = 1287.Why is C(n, r) = C(n, n − r)?
Answer
Choosing who's in is the same as choosing who's out.
Review
Exam-day sheet
★Everything on one screen
Condensed from §1–21
Negation table
| Statement | Negation |
|---|---|
| p ∧ q | ¬p ∨ ¬q |
| p ∨ q | ¬p ∧ ¬q |
| p → q | p ∧ ¬q |
| p ↔ q | p ↔ ¬q (≡ p ⊕ q) |
| ∀x P(x) | ∃x ¬P(x) |
| ∃x P(x) | ∀x ¬P(x) |
| ∀x (P(x) → Q(x)) | ∃x (P(x) ∧ ¬Q(x)) |
| ∃x (P(x) ∧ Q(x)) | ∀x (P(x) → ¬Q(x)) |
| ∀x ∃y P(x, y) | ∃x ∀y ¬P(x, y) |
Proof templates
| To prove | Do this |
|---|---|
| p → q | Direct: “Assume p.” … “Therefore q.” |
| p → q | Contraposition: “By contraposition. Assume ¬q.” … “So ¬p.” |
| p | Contradiction: “Assume for a contradiction ¬p.” … “Contradiction!” + why |
| p ↔ q | Prove (⇒) and (⇐) separately |
| (p₁ ∨ … ∨ pₙ) → q | Cases: show each pᵢ → q |
| ∀x P(x) | “Let x be arbitrary.” Prove P(x). Never by examples. |
| disprove ∀x P(x) | One counterexample, verified |
| ∃x P(x) | Exhibit x (constructive), or argue it must exist |
| ∃!x P(x) | Existence, then: if P(x) and P(y) then x = y |
| A ⊆ B | “Let x ∈ A.” … “So x ∈ B.” |
| A = B | Chain of ⟺, or A ⊆ B and B ⊆ A |
| f injective | Assume f(a) = f(b), show a = b |
| f not injective | Two different inputs, same output |
| f surjective | Let b ∈ B; find a ∈ A with f(a) = b |
| f not surjective | One b in the codomain never hit |
| |A| = |B| | Build a bijection (or injections both ways) |
| a | b | Write b = a·c with c an integer |
| a ≡ b (mod m) | Show m | a − b |
| P(n) for all n ≥ b | Induction: basis P(b); assume P(k), prove P(k + 1) |
| P(k + 1) needs several earlier cases | Strong induction: assume P(b), …, P(k) |
| “some box must have ≥ 2” | Pigeonhole: name the boxes, count the objects |
Definitions to write from memory
- even: n = 2k for some integer k; odd: n = 2k + 1 for some integer k
- rational: r = p/q for integers p, q with q ≠ 0; irrational: real and not rational
- |x| = x if x ≥ 0, −x if x < 0
- A ⊆ B: ∀x (x ∈ A → x ∈ B); 𝒫(A) = {B | B ⊆ A}; A × B = {(a, b) | a ∈ A, b ∈ B}
- injective: f(a) = f(b) → a = b; surjective: ∀b ∃a f(a) = b; bijective: both
- |A| = |B|: bijection exists; |A| ≤ |B|: injection exists; countable: same cardinality as a subset of ℕ
- a | b: b = ac for some integer c (a ≠ 0); a ≡ b (mod m): m | a − b
- prime: p > 1 with only positive factors 1 and p; gcd: largest common divisor; lcm: smallest positive common multiple
Number theory toolkit
| Task | Tool |
|---|---|
| a mod d | a = dq + r with 0 ≤ r < d (remainder never negative) |
| base b digits | Divide by b repeatedly; remainders are the digits, last first |
| aⁿ mod m | Repeated squaring + binary expansion of n |
| gcd(a, b) | Euclid: gcd(a, b) = gcd(b, a mod b); last nonzero remainder |
| gcd, lcm from factorizations | min / max of exponents; gcd·lcm = ab |
| gcd = sa + tb | Extended Euclid (back-substitute) |
| inverse of a mod m | Exists iff gcd(a, m) = 1; it's s from 1 = sa + tm |
| ax ≡ b (mod m) | d = gcd(a, m); none if d ∤ b; else x₀ = (b/d)s, all x₀ + k(m/d) |
| system of congruences | CRT: x = Σ aᵢMᵢyᵢ mod M (moduli pairwise coprime) |
| aⁿ mod prime p | Fermat: aᵖ⁻¹ ≡ 1 if p ∤ a, so reduce n mod p − 1 |
| is n composite? | aⁿ⁻¹ ≢ 1 (mod n) proves composite; trial division up to √n |
| RSA | n = pq; gcd(e, (p−1)(q−1)) = 1; de ≡ 1 mod (p−1)(q−1); c = mᵉ, m = cᵈ (mod n) |
Counting toolkit
| Situation | Count |
|---|---|
| step 1 and step 2 | multiply: n₁·n₂ |
| option A or option B (disjoint) | add: n₁ + n₂ |
| A or B, overlapping | |A| + |B| − |A ∩ B| |
| each outcome counted d times | divide by d |
| “at least one” | total − none |
| N objects, k boxes | some box has ≥ ⌈N/k⌉ |
| arrange r of n, order matters | P(n, r) = n!/(n − r)! |
| choose r of n, order doesn't matter | C(n, r) = n!/(r!(n − r)!) |
| bit strings of length n / subsets of an n-set | 2ⁿ |
!Mistakes to avoid
Collected from every “Caution” in lecture
Logic
- “Or” in math is inclusive. Use ⊕ for exclusive or.
- A false hypothesis makes p → q true.
- “p only if q” is p → q. “p unless q” is ¬q → p.
- The converse q → p is not equivalent to p → q; the contrapositive ¬q → ¬p is.
- “Every P is Q” uses →, not ∧. “Some P is Q” uses ∧, not →.
- ∀x ∃y and ∃y ∀x mean different things.
- ∀ doesn't distribute over ∨; ∃ doesn't distribute over ∧.
Proofs
- Say “by contraposition” / “assume for a contradiction” at the start.
- A ∀ statement is never proved by checking examples.
- Use a different letter for each number's definition (m = 2k + 1, n = 2j + 1).
- Don't prove the converse by accident: start from the hypothesis, not the conclusion.
- To contradict p → q, assume p ∧ ¬q.
Sets & functions
- ∈ vs ⊆: {1, 2} ∈ B and {1, 2} ⊆ B are different questions. ∈ isn't transitive.
- ∅ ≠ {∅}. ∅ is a subset of everything, but an element only if listed.
- Range ≠ codomain. Changing the domain or codomain changes injective/surjective.
- f ∘ g applies g first.
- f⁻¹ is the inverse function, not 1/f.
Number theory
- a | b is true/false; b/a is a number.
- a mod m is in {0, …, m − 1}; −11 mod 10 = 9.
- No cancelling in congruences unless gcd(c, m) = 1.
- 1 is not prime. p₁⋯pₙ + 1 need not be prime.
- p | ab ⇒ p | a or p | b only works for prime p.
- CRT needs pairwise relatively prime moduli.
- Fermat: reduce exponents mod p − 1, and only when p is prime and p ∤ a.
- Passing the Fermat test doesn't prove primality (pseudoprimes, Carmichael numbers).
Induction & counting
- Assume P(k) and prove P(k + 1); never assume P(k + 1).
- Actually use the inductive hypothesis, and don't skip the basis.
- If the step reaches back more than one case, you need more basis cases (postage: 4).
- Sum rule only for non-overlapping options; otherwise subtract the overlap.
- Decide whether order matters before choosing P or C.
- “At least one” is almost always easier as total − none.