1
Inductive Foo : Type :=
  | foo : Foo
  | bar : Foo -> Foo.

Lemma Foo_contr f:
  bar f = f -> False.
Proof.
  intros H.
  induction f as [|f IH].
  - discriminate.
  - injection H.
    apply IH.
Qed.

Is there a tactic which would prove Foo_circ_contr automatically? It's annoying to have to write out and prove the lemma every time, especially because AFAICT, this kind of property is true for all inductive types.

discriminate can prove that foo <> bar f, but it's not smart enough to reason about the circular equality like this.

2
  • You wrote it! Just put all the text together in one command, give it a name, and there you are you have your tactic. There is nothing in the text you wrote that is specific to a given inductive type. You can probably make it resistant to having an arbitrary number of constructors and the base cases not coming first.
    – Yves
    Commented Jun 28 at 7:05
  • Good Ltac(2) exercise indeed. The tactic should probably take H and f as arguments. Commented Jun 28 at 7:16

1 Answer 1

3

The tactic to solve more complicated equality goals is called "congruence". It can solve both goals immediately:

Lemma Foo_contr f:
  bar f = f -> False.
Proof.
  induction f; congruence.
Qed.

Not the answer you're looking for? Browse other questions tagged or ask your own question.