Lean 4 and Formal Verification: Toppling a Row of Dominoes First
A row of dominoes stretching off out of sight. How can you be sure they will all fall?
The line of dominoes stretches out of sight. How can you be sure they'll all fall?
Check them one by one, and even by nightfall you only know "the ones I checked are fine." That's testing.
Try a different approach: confirm just two things—the first one falls, and each one knocks over the next. Then, without looking further, all of them will fall. That's proof.
Programs are the same. Testing can only say "the inputs I tried are fine," while proof can say "all inputs are fine." This course teaches you to write such proofs and to have a tool called Lean check them step by step for you—if one link is missing, it stops, just like when you pulled away a domino.
Try another: a proof in plain words
Proofs don't have to involve symbols. Given "it's raining and windy," show that "it's windy and raining."
Given (what you have)
What needs to be shown
What we need to show is "it's windy and raining", which is two things. Hard to say in one breath, so split it up first.
The same thing, in Lean
example (p q : Prop) (h : p ∧ q) : q ∧ p := byGiven h: p and q. To prove: q and p. constructorSplit into two smaller goals exact h.rightUsing the known right half exact h.leftUsing the known left halfp It's raining q It's windy ∧ and h The given statement
The four lines on the right are a real Lean proof, and it passes when submitted to Lean for checking:
example (p q : Prop) (h : p ∧ q) : q ∧ p := by
constructor
exact h.right
exact h.leftYou don't need to memorize these words yet. Just take away one feeling: there is a goal to establish, and every step must have a justification, until there is nothing left to establish. Later lessons all build on this feeling.
- I have toppled that row of dominoes, and tried pulling one away
- I proved "it's windy and raining" in plain words
What you'll have in hand after the course
A mini compiler you wrote yourself and that Lean proved correct: it translates expressions into instructions, and you proved that for any expression, the translated instructions compute the same result as the original expression.
No math background needed; a little programming in any language is enough.
Roadmap
| Stage | Lesson | You will be able to |
|---|---|---|
| Getting started | What is formal verification | Explain the difference between testing and proof |
| Install Lean 4 | Have Lean compute 1 + 1 on your own computer | |
| First proof | Write and read a theorem | |
| Logic | If... then... | Use intro, apply, exact |
| And and or | Take apart and build up compound propositions | |
| Let Lean compute for you | Use rw, simp, omega, decide | |
| Induction | Induction on natural numbers | Prove things that hold for all natural numbers |
| Induction on lists | Prove "reversing twice equals no reversal" | |
| Verifying programs | Prove a compiler correct | Complete the capstone project |
How this course guarantees it makes no mistakes
- Every piece of Lean code in the lessons is actually checked by Lean 4.35.0 before release. Examples marked "will raise an error" were also confirmed to really raise an error.
- The output following "you should see" was verified against Lean's real output.
- The goal states and errors in the interactive exercises are generated from Lean by scripts.
If Lean is updated and what you see differs from the lessons, tell us at the end of that section.
FAQ
What language is Lean 4?
Lean is a tool that checks proofs for you step by step, and Lean 4 is its current version. This course teaches you to write proofs and have Lean check every step—if one link is missing, it stops. Every piece of Lean code in the lessons was actually checked by Lean 4.35.0 before release.
What is formal verification? How should this term be understood in Chinese?
Formal verification means replacing testing with proof: testing can only say "the inputs I tried are fine," while proof can say "all inputs are fine." Like toppling dominoes—as long as you confirm the first one falls and each one knocks over the next, you can conclude they all fall, without checking one by one.
Are there examples with Lean 4?
Yes. The snippet below is a real Lean proof, and it passes when submitted to Lean for checking:
example (p q : Prop) (h : p ∧ q) : q ∧ p := by
constructor
exact h.right
exact h.leftWhat it shows is: given "it's raining and windy," you can conclude "it's windy and raining."
What if Lean 4 reports an error?
Lean's checking proceeds step by step; it stops at whichever step lacks a justification, and the error tells you which link is missing. Examples in the course marked "will raise an error" were confirmed before release to really raise an error, and the goal states and errors in the interactive exercises are generated from Lean by scripts. If Lean is updated and what you see differs from the lessons, tell us at the end of that section.
What background do I need for this course?
No math background needed; a little programming in any language is enough. After finishing, you will have a mini compiler you wrote yourself and that Lean proved correct.
Next steps
Start with What is formal verification. If you want to dive right in, go to Install Lean 4.