Skip to content

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.