leanprover / leanprover/lean4

Termination goal for a wf recursive function involving `cases` lacks necessary hypotheses

Open
#10,094 3 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

bug P-medium
Dominant language
Lean
Stars
9.2k
Forks
990
Avg merge
1d 17h
Merged PRs (30d)
175

Description

Prerequisites

Please put an X between the brackets as you perform the following steps:

Description

I have a situation in which a well-founded recursive function produces a decreasing_by goal that lacks necessary information about a cases-based match on the recursion variable. If I replace the cases tactic with a match expression, it works.

This might be related to #5690 in that highlights a difference of cases and match, but the symptoms seem different.

Steps to Reproduce

Consider this example:

inductive P1 : Nat → Type where
  | nil : P1 n
  | p1 : P1 n → P1 (n + 1)

opaque P2 : Nat → Type

/--
error: unsolved goals
case refl.refl.refl.refl
n✝ : Nat
a✝ : P1 n✝
p1 : P1 (n✝ + 1)
p2 : P2 (n✝ + 1)
this : sizeOf a✝ < sizeOf a✝.p1
β : Type
⊢ sizeOf a✝ < sizeOf p1
-/
#guard_msgs in
def f (p1 : P1 ms) (p2 : P2 ms) : Unit := by
  cases hp1 : p1
  · exact ()
  · rename_i p1'
    -- recursive call is decreasing:
    have : sizeOf p1' < sizeOf p1 := by simp [hp1]; omega
    -- recursive call:
    exact f p1' sorry
termination_by sizeOf p1
decreasing_by
  · subst_eqs

(The example works with structural recursion, but my real-world use case doesn't.)

Expected behavior:

Because p1 = P1.p1 p1', it should be possible to use this fact to close the termination goal.

Actual behavior:

Because p1 is a free variable without any information about its size or its relation to a✝ (which seems to be the name for p1' in the termination goal), it is impossible to finish the termination proof.

Also note that the have :sizeOf p1' < sizeOf p was transformed into a tautology in the termination goal.

Versions
Lean 4.23.0-rc2
Target: x86_64-unknown-linux-gnu
Impact

Add 👍 to issues you consider important. If others are impacted by this issue, please ask them to add 👍 to it.

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Run the minimal reproducer against Lean 4.23.0-rc2 or the latest nightly, focusing on the cases-based well-founded recursive function, termination_by, and decreasing_by goal. Compare it with the reported match-expression variant; done means the generated termination goal preserves the constructor information needed to close the proof.

Written by the indexing model from the issue text.

Assessment

Domain
compilers
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.