在 Coq 中用圆对称求解证明

Question

我正在使用结构同余进行证明，其定义与此示例非常相似：

Require Import Nat.
Require Import Omega.

Inductive expr :=
  | Const : nat -> expr
  | Add : expr -> expr -> expr.


Reserved Notation "e1 === e2" (at level 80).
Inductive expr_congruence : expr -> expr -> Prop :=
  | Commutative : forall e1 e2, Add e1 e2 === Add e2 e1
  | Associative : forall e1 e2 e3, Add (Add e1 e2) e3 === Add e1 (Add e2 e3)
  | CongruenceReflexive : forall e, e === e
  | CongruenceSymmetric : forall e1 e2, e1 === e2 -> e2 === e1
  | CongruenceTransitive :
      forall e1 e2 e3, e1 === e2 -> e2 === e3 -> e1 === e3
  where "e1 === e2" := (expr_congruence e1 e2).

我运行在尝试定义 forall e1 e2, e1 === e2 -> P e1 -> P e2 形式的东西时遇到问题：我总是以循环逻辑结束。例如：

Inductive is_zero : expr -> Prop :=
  | ZConst : is_zero (Const 0)
  | ZAdd : forall e1 e2, is_zero e1 -> is_zero e2 -> is_zero (Add e1 e2).

Hint Constructors is_zero expr_congruence.

Lemma is_zero_over_congruence :
  forall e1 e2,
    e1 === e2 ->
    is_zero e1 ->
    is_zero e2.
Proof.
  induction 1; eauto; intros.

  Show 3.
(**
1 subgoal
e1, e2 : expr
H : e1 === e2
IHexpr_congruence : is_zero e1 -> is_zero e2
H0 : is_zero e2
**)

这里 e1 和 e2 之间的唯一联系是它们是一致的。对它们进行反演或归纳最终会回到相同的情况，但不会提供额外的信息。

当使用以这种方式定义的对称结构时，处理归纳的正确方法是什么？

Answer 1

至少在这个最小的例子中，你只需要证明更强大的东西：

Lemma is_zero_over_congruence :
  forall e1 e2, e1 === e2 -> is_zero e1 <-> is_zero e2.
Proof.
  induction 1.
  - split; intros HI; inversion HI; eauto.
  - split; intros HI; inversion HI; [inversion H1 | inversion H2]; eauto.
  - reflexivity.
  - symmetry. auto.
  - rewrite IHexpr_congruence1, IHexpr_congruence2. reflexivity.
Qed.

以便在需要证明 is_zero e2 <-> is_zero e1 时可以使用 is_zero e1 <-> is_zero e2 作为归纳假设。

在 Coq 中用圆对称求解证明

Solve Proof with Circular Symmetry in Coq

coq

induction