Zulip Chat Archive

Stream: lean4

Topic: Trouble with a `rw`


Mac (Feb 23 2022 at 22:11):

So I have been toying around with Nat.add that is not left or right recursive and while trying to prove add_succ I ran into the following problem, which I think may be an bug in Lean, but I am not sure.

open Nat (zero succ)

def add : Nat  Nat  Nat
| 0, 0 => 0
| succ n, 0 => succ n
| 0, succ n => succ n
| succ m, succ n => succ (succ (add m n))

infixl:65 (priority := high) " + " => add

instance : Add Nat := add -- removing this fixes the theorem error

@[simp] theorem succ_zero : succ 0 = 1 := rfl

@[simp] theorem zero_add_zero : 0 + 0 = 0 := rfl

@[simp] theorem add_zero : n + 0 = n := by cases n; repeat rfl
@[simp] theorem zero_add : 0 + n = n := by cases n; repeat rfl

theorem succ_add_succ : succ m + succ n = succ (succ (m + n)) := rfl

@[simp] theorem add_one : n + 1 = succ n := by
  cases n with | zero => rfl | succ n => rw [succ_add_succ, add_zero]

@[simp] theorem one_add : 1 + n = succ n := by
  cases n with | zero => rfl | succ => rw [succ_add_succ, zero_add]

-- error: theorem fails despite goals accomplished
theorem add_succ {m n : Nat} : m + succ n = succ (m + n) := by
  revert m
  induction n with
  | zero => simp
  | succ n ih =>
    intro m
    cases m with
    | zero => simp
    | succ m =>
      rw [succ_add_succ, succ_add_succ] -- produces an `n + 1` for some reason
      show succ (succ (m + succ n)) = succ (succ (succ (m + n)))
      rw [@ih m]

The error on add_succ is as follows:

application type mismatch
  @Eq.ndrec Nat (succ m + succ (n + 1))
    (fun _a => (succ m + succ (succ n) = succ (succ m + succ n)) = (_a = succ (succ m + succ n)))
    (Eq.refl (succ m + succ (succ n) = succ (succ m + succ n)))
argument has type
  (succ m + succ (succ n) = succ (succ m + succ n)) = (succ m + succ (succ n) = succ (succ m + succ n))
but function has type
  (fun _a => (succ m + succ (succ n) = succ (succ m + succ n)) = (_a = succ (succ m + succ n)))
      (succ m + succ (n + 1)) →
    ∀ {b : Nat},
      succ m + succ (n + 1) = b →
        (fun _a => (succ m + succ (succ n) = succ (succ m + succ n)) = (_a = succ (succ m + succ n))) b

I am very confused as to why the n + 1 is introduced during rewriting. I am also curious as to why removing the Add instance fixes the error (and why the n + 1 still appears even then). Is this some weird bug in rw (or show) or are there details I am missing?

Mario Carneiro (Feb 23 2022 at 22:47):

Here's a minimized version:

open Nat

def add : Nat  Nat  Nat
| 0, 0 => 0
| succ n, 0 => succ n
| 0, succ n => succ n
| succ m, succ n => succ (succ (add m n))

instance : Add Nat := add -- removing this fixes the theorem error

theorem succ_add_succ : succ m + succ n = succ (succ (m + n)) := rfl

theorem add_succ : succ m + succ (succ n) = 0 := by
  rw [succ_add_succ]
  sorry

This is certainly a bug, and my guess is that it is caused by something that has a hardcoded match on Add.add Nat thinking that it's surely Nat.add and your alternate definition is confusing it. (Lean 3 simp has the same problem with numerals encoded using nonstandard instances of standard typeclasses)

Kevin Buzzard (Feb 24 2022 at 05:24):

So the problem should go away if you try this on a custom nat'?


Last updated: Dec 20 2023 at 11:08 UTC