Lean 4

Fail to show termination (Lean 4)

Lean could not prove that your recursive function always stops, so it will not accept it as an ordinary definition.

What it looks like

Main.lean:1:4: error: fail to show termination for
  collatz
with errors
failed to infer structural recursion:
…

failed to prove termination, possible solutions:
  - Use `have`-expressions to prove the remaining goals
  - Use `termination_by` to specify a different well-founded relation
  - Use `decreasing_by` to specify your own tactic for discharging this kind of goal
n : ℕ
h✝¹ : ¬n ≤ 1
h✝ : ¬n % 2 = 0
⊢ 3 * n + 1 < n

What does "Fail to show termination (Lean 4)" mean?

Every def that calls itself must be shown to terminate, or Lean's logic would become inconsistent. Lean first tries structural recursion (calling itself on a sub-term, like n from n + 1), then well-founded recursion with a measure it guesses and a proof by decreasing_tactic. When both fail it reports fail to show termination for, the reason each attempt failed, and the goal it could not prove — or Could not find a decreasing measure when no candidate measure worked at all.

What causes "Fail to show termination (Lean 4)"?

• The recursive call is not on a structurally smaller argument (f (n / 2) instead of f n when matching n + 1).
• The argument does get smaller, but Lean's automatic proof (decreasing_tactic) cannot show it.
• Several arguments change at once and no single one shrinks on every call.
• The function really can loop for some inputs.

How do I confirm the cause?

1. Read the goal at the end of the message — it is exactly the inequality Lean needed (here 3 * n + 1 < n, which is false, so no tactic can prove it).
2. Write termination_by? after the body to see the measure Lean guessed.
3. Check every recursive call, including ones inside match branches and if expressions.

How do I fix "Fail to show termination (Lean 4)"?

• Add termination_by with a measure that shrinks on every call, e.g. termination_by xs.length or termination_by n - i.
• Prove the decrease yourself: decreasing_by followed by tactics (decreasing_by omega), or a have h : n / 2 < n := … before the recursive call.
• Restructure to recurse on a smaller piece: match n with | n + 1 => … f n.
• For a program you will not reason about, use partial def (the return type must be inhabited, and proofs cannot unfold it).

How do I stop it happening again?

• Write the termination_by clause up front for any recursion that is not structural.
• Keep the recursive argument visibly smaller: match on n + 1 and recurse on n, or on xs from x :: xs.

Got a different error? Paste it into the Explain This Error tool → Identifies the family and the fix — runs locally, nothing uploaded.

Related errors