Recursive theorems with `cases` vs `match`

hargoniX commented 1 week ago

Prerequisites

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

[X] Check that your issue is not already filed: https://github.com/leanprover/lean4/issues
[X] Reduce the issue to a minimal, self-contained, reproducible test case. Avoid dependencies to Mathlib or Batteries.
[X] Test your test case against the latest nightly release, for example on https://live.lean-lang.org/#project=lean-nightly (You can also use the settings there to switch to “Lean nightly”)

Description

Consider:

inductive C : Nat → Type where
| C0  : C 0
| C1  : C n → C (1 + n)
| C2  : C n → C n → C n

open C

def id_C (c : C n) : C n :=
  match c with
  | C0       => C0
  | C1 c     => C1 (id_C c)
  | C2 c₁ c₂ => C2 (id_C c₁) (id_C c₂)

We can prove the following theorem with match or induction:

theorem id_c_is_identity (c : C n) : id_C c = c := by
  match c with
  | C0 => simp [id_C]
  | C1 inner => simp [id_C, id_c_is_identity inner]
  | C2 lhs rhs => simp [id_C, id_c_is_identity lhs, id_c_is_identity rhs]

this will use the structural termination metric on c as expected. However the following:

theorem id_c_is_identity (c : C n) : id_C c = c := by
  cases c with
  | C0 => simp [id_C]
  | C1 inner => simp [id_C, id_c_is_identity inner]
  | C2 lhs rhs => simp [id_C, id_c_is_identity lhs, id_c_is_identity rhs]

Fails to prove termination, if we force a use of the structural metric:

theorem id_c_is_identity (c : C n) : id_C c = c := by
  cases c with
  | C0 => simp [id_C]
  | C1 inner => simp [id_C, id_c_is_identity inner]
  | C2 lhs rhs => simp [id_C, id_c_is_identity lhs, id_c_is_identity rhs]
termination_by structural c

We get

failed to infer structural recursion:
Cannot use parameter c:
  failed to eliminate recursive application
    id_c_is_identity lhs

Steps to Reproduce

Expected behavior: Given that it works with match it should either also work with cases or there should be a better error message explaining why that is not the case (haha).

Actual behavior: match works, cases doesn't.

Versions

"4.12.0-nightly-2024-10-13"

Impact

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

nomeata commented 1 week ago

What happens if you pass explicit arguments to the theorem before passing them to rw? I.e. is the problem with rw or with cases?

hargoniX commented 1 week ago

Breaks in the same fashion, updated the issue to align the code.

leanprover / lean4