leanprover / leanprover/lean4

non-variable induction fails on two-argument induction principles

Open
#9,417 0 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

bug P-low
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

When using induction h : x, hx using or induction x, hx using, the generalization appears to be applied incorrectly.

Context

I am trying to simplify the lift tactic in mathlib to be a macro for induction.

Steps to Reproduce
  1. Run the following code:
import Lean

theorem Nat.induction_pos {motive : (n : Nat) → 0 < n → Prop}
    (one : motive 1 (by omega))
    (succ_pos : ∀ n hn, motive n hn → motive (n + 1) (by omega)) :
    ∀ n hn, motive n hn :=
  fun _ hn => Nat.le.rec one @succ_pos hn

theorem broken {n : Nat} : (n + 1) ≠ 0 := by
  have hn : 0 < n + 1 := by omega
  induction n + 1, hn using Nat.induction_pos  -- fails

theorem broken_h {n : Nat} : (n + 1) ≠ 0 := by
  have hn : 0 < n + 1 := by omega
  induction h : n + 1, hn using Nat.induction_pos  -- fails

theorem ok {n : Nat} : (n + 1) ≠ 0 := by
  have hn : 0 < n + 1 := by omega
  generalize n + 1 = m at *
  induction m, hn using Nat.induction_pos -- ok
  all_goals sorry

theorem ok_h {n : Nat} : (n + 1) ≠ 0 := by
  have hn : 0 < n + 1 := by omega
  generalize h : n + 1 = m at *
  induction m, hn using Nat.induction_pos -- ok
  all_goals sorry

Expected behavior: induction succeeds in all cases

Actual behavior: The broken cases errors with

target
  hn
has type
  0 < n + 1 : Prop
but is expected to have type
  0 < x✝ : Prop

where the origin of x✝ is unclear.

Versions

[Output of #version or #eval Lean.versionString]
[OS version, if not using live.lean-lang.org.]

Additional Information

[Additional information, configuration or data that might be necessary to reproduce the issue]

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

Start by running the minimal reproduction in live.lean-lang.org or against the latest Lean nightly, focusing on the broken and broken_h induction cases using Nat.induction_pos. Compare them with the working generalize cases and confirm that induction succeeds without producing the x✝ type mismatch.

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
Clearly specified
Newbie friendliness
45/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.