What Is Formal Verification
Formal verification is using a mathematical proof to show that a program satisfies its requirements for all inputs, and having a computer check every step of that proof. It differs from testing in only one way: testing checks the inputs you have tried, while a proof covers all of them.
This section starts by building a staircase and grounds that statement in practice. No installation required.
What You Will Be Able to Do
- State what testing and proof each guarantee
- Understand what a Lean theorem says
- Know what “Lean check passed” means and what it does not mean
First, Build a Staircase
Build a staircase out of bricks: the first step takes 1 brick, the second 2, the third 3. How many bricks does it take to build n steps in total?
Count one by one (testing)
1 + 2 + … + 4 = 10
n=4 ✓
Have you tried 1 n's. Drag the slider and try a few more. But there are infinitely many n's—you can never try them all.
Piece it together (proof)
Now take an identical set of steps, in reverse.
You did two different things:
- Dragging the slider to count bricks: each time you only know the answer for one n. No matter how many you try, all you have is “these particular values of n are fine.”
- Assembling a rectangle: you saw all values of n at once. No matter how many steps the staircase has, the two copies always fit into n rows and n + 1 columns, so the two copies together use n × (n + 1) bricks.
The first is testing; the second is proof.
- I have dragged the slider and assembled the rectangle
Writing the Staircase as a Program
Here is what counting bricks looks like as a Lean function. Don't worry if you can't follow the details—it says “bricks for an n-step staircase = bricks for the first n − 1 steps + the n bricks of the nth step”:
def sumTo : Nat → Nat
| 0 => 0
| n + 1 => sumTo n + (n + 1)One Function, Two Ways to Check It
The testing approach: pick a number and compute it.
#eval sumTo 100You should see:
5050100 × 101 ÷ 2 is also 5050, which matches. But this only shows it holds for n = 100. What about n = 101? n = one hundred million? You can test more values, but you will never finish.
The proof approach: take the conclusion you got from assembling the rectangle, state it as a sentence that holds for all n, and then prove it.
theorem sumTo_formula (n : Nat) : 2 * sumTo n = n * (n + 1) := by
induction n with
| zero =>
rfl
| succ k ih =>
simp [sumTo]
rw [Nat.mul_add, ih]
simp [Nat.mul_add, Nat.add_mul]
omegaIt's fine if you can't understand the part after by for now—that's the subject of later sections. Just look at the first line:
theorem sumTo_formula: a theorem, namedsumTo_formula.(n : Nat): for any natural number n.2 * sumTo n = n * (n + 1): the brick count of two staircases equals n × (n + 1). That's exactly the rectangle you assembled.
Lean checked this proof. From now on, this statement holds for every natural number—no more testing needed.
- I can state what
#eval sumTo 100andtheorem sumTo_formulaeach guarantee
What Happens If You Get It Wrong
Suppose you misremembered the formula and thought adding 1 up to n equals n × n:
theorem wrong_formula (n : Nat) : sumTo n = n * n := by
induction n with
| zero => rfl
| succ k ih => simp [sumTo, ih]; omegaLean rejects it. Its response begins with this line:
omega could not prove the goal:You can't sneak by with “it looks about right.” A false statement cannot be proved no matter how you write it. This is why formal verification deserves trust: the proof is checked by a program, not by human patience.
Quiz timeYou wrote 200 tests for a sorting function and all of them passed. What does this show?
What It Does Not Guarantee
What Lean guarantees is: the statement you wrote down has been proved. It does not guarantee that the statement you wrote is what you actually wanted.
The theorem above says “twice sumTo n equals n × (n + 1).” If you actually wanted a different property but wrote this sentence instead, Lean can't help you. That's why reading the first line of a theorem matters more than reading the proof. Leave the proof to Lean; the statement is yours to read.
- I know that “proof passed” guarantees the statement holds, not that the statement matches the requirements
Checkpoint
- I can explain formal verification in one sentence: using a proof to show a program is correct for all inputs, and having a computer check the proof
- I can state the difference between testing and proof: tried inputs vs. all inputs
- I can read the meaning of each part of
theorem 名字 (n : Nat) : 命题 - I know that a false statement cannot be proved in Lean
Common Misconceptions
“Formal verification is just more testing.” No. Testing runs the program and looks at the results; a proof does not run the program—it reasons from definitions and covers all cases at once.
“If the proof passes, the program has no problems at all.” The proof only covers the statement you wrote down. Properties not included in the statement are not guaranteed.
FAQ
What does formal verification mean?
Formal verification is using a mathematical proof to show that a program satisfies its requirements for all inputs, and having a computer check every step of that proof. It differs from testing in only one way: testing checks the inputs you have tried, while a proof covers all of them. The definition at the top of this page and the brick example in the “First, Build a Staircase” section illustrate this point.
What does Lean 4 mean?
Lean 4 is a tool for writing programs and proofs. On this page, you used it to define the function sumTo, then used theorem to state a proposition that holds for all natural numbers, with Lean checking every step of the proof. The proof is checked by a program, not by human patience.
How do you write formal verification?
First write the property you want to establish as a proposition that holds for all inputs, for example theorem sumTo_formula (n : Nat) : 2 * sumTo n = n * (n + 1), then provide a proof for the computer to check. The proof on this page uses induction; the details are covered in later sections.
If the proof passes, does that mean the program has no problems at all?
No. What Lean guarantees is that the statement you wrote down has been proved, not that the statement is what you actually wanted. Properties not included in the statement are not guaranteed, which is why reading the first line of a theorem matters more than reading the proof—see the “What It Does Not Guarantee” section.
Next Section
To check this code with Lean yourself, first install Lean 4.