✎ Introduction to Proofs
Based on Jim Hefferon's Introduction to Proofs, licensed GFDL + CC BY-SA 2.5.
How to read and write mathematical proofs. Every proof technique here shows up in every branch of mathematics on this site.
| Chapter | |||
|---|---|---|---|
| 1. | Statements and Logic | Propositions, connectives, truth tables, and the conditional that trips everyone up | ✎ |
| 2. | Direct Proof | Assume P, deduce Q in a straight line | ✎ |
| 3. | Contrapositive and Contradiction | When the front door is locked, try the back door or blow up the building | ✎ |
| 4. | Mathematical Induction | Prove the base, prove the step, knock down infinitely many dominoes | ✎ |
| 5. | Sets | Element-chasing: to prove A is a subset of B, pick x in A and show x is in B | ✎ |
| 6. | Functions | Injective, surjective, bijective: the three properties that control invertibility | ✎ |
| 7. | Relations | Equivalence relations partition a set into non-overlapping classes | ✎ |
| 8. | Cardinality | Some infinities are bigger than others, and Cantor proved it with a diagonal | ✎ |
📺 Video lectures: MIT 6.042J Mathematics for Computer Science
Neighbors
- 🔑 Logic — formal foundations for the proof techniques used here
- 🔗 Abstract Algebra — groups, rings, and fields as proof territory
- 🔢 Discrete Math — combinatorics and graph theory as proof territory
- ✏️ Lean Proofs — machine-checked versions of the same proofs