Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

contradiction tries to make use of constructor disjunction for proof equalities #6515

Open
3 tasks done
kmill opened this issue Jan 3, 2025 · 3 comments · May be fixed by #6731
Open
3 tasks done

contradiction tries to make use of constructor disjunction for proof equalities #6515

kmill opened this issue Jan 3, 2025 · 3 comments · May be fixed by #6731
Labels
bug Something isn't working P-medium We may work on this issue if we find the time

Comments

@kmill
Copy link
Collaborator

kmill commented Jan 3, 2025

Prerequisites

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

  • Check that your issue is not already filed
  • Reduce the issue to a minimal, self-contained, reproducible test case.
  • Test your test case against the latest nightly release.

Description

If there is an equality of proofs in context, where the proofs use different constructors, contradiction will try reasoning using noConfusion, leading to a kernel typechecking error.

Context

Reported on Zulip.

Steps to Reproduce

With the following:

example : False := by
  have : Or.inl trivial = Or.inr trivial := rfl
  contradiction

Expected behavior: contradiction should fail to find a contradiction

Actual behavior: contradiction succeeds, but then there is a "(kernel) unknown constant 'Or.noConfusion'" error.

Versions

Lean 4.16.0-nightly-2025-01-02
Target: x86_64-unknown-linux-gnu

Additional Information

Perhaps other "no-confusion-like" tactics should be audited for similar errors.

Impact

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

@kmill kmill added the bug Something isn't working label Jan 3, 2025
@kmill
Copy link
Collaborator Author

kmill commented Jan 3, 2025

More examples:

example : False := by
  have : Or.inl trivial = Or.inr trivial := rfl
  injection this

example : False := by
  have : HEq (Or.inl trivial) (Or.inr trivial) := HEq.rfl
  contradiction

It looks like reduceCtorEq is affected too, but I haven't been able to configure simp to not use a builtin rule to simplify this to True on its own.

The cases tactic is not affected because it first does an isDefEq check for the LHS and RHS of an equality before doing any further reasoning.

@kmill
Copy link
Collaborator Author

kmill commented Jan 3, 2025

(@leodemoura Lean.Meta.Grind.injection? and Lean.Meta.Grind.propagateCtor are potentially affected by this. There's no problem if the grind framework simplifies away any equalities of the form h1 = h2 where h1 and h2 are proofs.)

@leanprover-bot leanprover-bot added the P-medium We may work on this issue if we find the time label Jan 10, 2025
@jrr6
Copy link
Contributor

jrr6 commented Jan 21, 2025

@kmill I was able to replicate the issue with simp (see below), but only in the absence of eq_self as a simp lemma—simp appears to try rewriting with eq_self before applying reduceCtorEq, which I think effectively serves as a definitional-equality check. Given that removing this simp lemma seems unlikely, might it not be worth the overhead of adding a check for no-confusion principles in reduceCtorEq? Also, simp reports an error about the nonexistent constant at the tactic site, rather than silently producing an incorrect proof term like injection and contradiction.

As for grind, it looks like propagateCtor already has a check to make sure a no-confusion principle exists; I think injection? shouldn't be affected because it only tries to construct a noConfusion term when there's an equality of matching constructors after the simp in introNext, which for propositional types (and PUnit) shouldn't happen because the simp will reduce away such an equality to True.

Here's the simp example (you can do it with Or too, but that requires eliminating even more simp lemmas):

inductive Or' (a b : Prop) : Prop
  | inl : a → Or' a b
  | inr : b → Or' a b

set_option trace.Meta.Tactic.simp true

attribute [-simp] eq_self  -- Commenting this line toggles the error below
example : False := by
  have h : Or'.inl trivial = Or'.inr trivial := rfl
  simp at h  -- error: unknown constant 'Or'.noConfusion'

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
bug Something isn't working P-medium We may work on this issue if we find the time
Projects
None yet
Development

Successfully merging a pull request may close this issue.

3 participants