如何自动证明归纳类型的循环等式矛盾？需智能替代discriminate策略

先贴出你给出的归纳类型定义和手动证明的引理：

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.

针对这类循环等式的矛盾证明，确实有几个自动/半自动的方案：

1. 使用size_change策略
   这个策略属于Program.Wf库，它能自动利用归纳类型的结构大小递归来推导矛盾。先导入依赖库，然后直接调用即可：

   Require Import Program.Wf.
   
   Lemma Foo_contr_auto f: bar f = f -> False.
   Proof. intros H; size_change; contradiction. Qed.
   

2. 自定义通用策略
   可以封装你手动证明的逻辑成一个通用Ltac，适配大多数严格正归纳类型的循环等式矛盾场景：

   Ltac inductive_cycle_contradiction :=
     intros H;
     induction H;
     try discriminate;
     try (injection H; apply IHl).
   

   调用时直接用这个策略就能完成证明：

   Lemma Foo_contr_custom f: bar f = f -> False.
   Proof. inductive_cycle_contradiction. Qed.
   

3. 半自动方案：inversion_clear结合归纳
   虽然不如前两种自动，但inversion_clear可以帮你拆解等式结构，再配合归纳也能快速完成证明：

   Lemma Foo_contr_semi_auto f: bar f = f -> False.
   Proof.
     intros H; inversion_clear H; induction f; discriminate.
   Qed.
   

补充说明：你提到的“该性质对所有归纳类型均成立”更准确的说法是——严格正归纳类型（Coq默认定义的归纳类型基本都属于此类，构造子参数不会出现在负位置）满足“无循环相等性”，即不存在t = c ... t ...这样的有效等式（c为构造子，t出现在构造子的参数中），所以这类矛盾总能被推导出来。

内容的提问来源于stack exchange，提问作者Mathieu Paturel