When Lean asks why it terminates¶
9 November 2025
Every function in Lean has to terminate, or the logic would fall apart: a
definition that loops forever could "prove" anything. Structural recursion,
where each call works on a smaller piece of the input, is checked
automatically. Euclid's algorithm isn't structural, since a % b isn't a
piece of b, so the definition says what shrinks and why:
def gcd' (a b : Nat) : Nat :=
if h : b = 0 then a
else
have : a % b < b := Nat.mod_lt _ (Nat.pos_of_ne_zero h)
gcd' b (a % b)
termination_by b
termination_by b names the measure, and the have proves it goes down,
using the h : ¬b = 0 that if h : put in scope. Lean's termination checker
picks the fact up from the context on its own.
For code that really might not stop, a read-eval-print loop or a server,
there's partial def. Lean compiles it, but won't let a proof look inside.