Skip to content

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?

Click a domino and pull it away to try

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."

Give it a tryFirst prove it in plain words, without any symbols

Given (what you have)

and

What needs to be shown

🌬️It's windy
and
☔It's raining

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 half

p 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:

lean
example (p q : Prop) (h : p ∧ q) : q ∧ p := by
  constructor
  exact h.right
  exact h.left

You 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 ​

StageLessonYou will be able to
Getting startedWhat is formal verificationExplain the difference between testing and proof
Install Lean 4Have Lean compute 1 + 1 on your own computer
First proofWrite and read a theorem
LogicIf... then...Use intro, apply, exact
And and orTake apart and build up compound propositions
Let Lean compute for youUse rw, simp, omega, decide
InductionInduction on natural numbersProve things that hold for all natural numbers
Induction on listsProve "reversing twice equals no reversal"
Verifying programsProve a compiler correctComplete 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:

lean
example (p q : Prop) (h : p ∧ q) : q ∧ p := by
  constructor
  exact h.right
  exact h.left

What 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.

gaodong.aiAboutPrivacyContact

Independent tutorials, not affiliated with any product mentioned. Product names and trademarks belong to their owners. Check official pages for prices and policies.