Learning objectives
By the end of this week you can:
- 1 Write a direct proof of a statement of the form p → q.
- 2 Prove a statement by contraposition and by contradiction, and choose between them.
- 3 Use proof by cases and exhaustive proof on small domains.
- 4 Disprove a universal statement with a counterexample.
- 5 Use a computer to search for counterexamples and understand why that is not a proof.
★ the wow moment
n² + n + 41 is prime for n = 0, 1, …, 39. Then it isn’t.
Forty cases in a row look like a pattern, and a pattern is not a proof. In the lab you let Python test millions of cases of famous claims, find where some break, and see why only a proof settles ∀n.
Topics
- Direct proof
- Proof by contraposition
- Proof by contradiction (√2 is irrational)
- Proof by cases, exhaustive proof
- Counterexamples
- Proof strategy
Before class
- Skim Rosen 1.7–1.8 (20 minutes is enough; we go through it together).
- Bring paper and a pen: part of every lecture is solving by hand.
In industry
-
Verified software
The seL4 microkernel and the CompCert C compiler come with machine-checked proofs of correctness.
-
AI and mathematics
Proof assistants like Lean now check proofs written by humans and AI systems alike.
-
Security
Cryptographic protocols are proven secure by contradiction: “if an attacker could break this, they could also factor large numbers”.
Lab 6: Counterexample Hunting
Test famous claims about primes and integers by computer, find counterexamples, and see what a search can and cannot prove.
due Fri, Nov 6 · 23:59 · 100 points · opens in week 7
Go deeper
- Book of Proof (Richard Hammack) · Chapters 4–6, direct, contrapositive, contradiction
- Mathematics for Computer Science (Lehman, Leighton, Meyer) · Chapter 1, proofs
- Lean Natural Number Game · prove theorems with a computer
- seL4: the verified microkernel
Tags:proofdirect proofcontrapositivecontradictioncounterexampleLean