Coq：在不丢失信息的情况下破坏（共）归纳假设

Question

考虑以下发展：

Require Import Relation RelationClasses.

Set Implicit Arguments.

CoInductive stream (A : Type) : Type :=
| scons : A -> stream A -> stream A.

CoInductive stream_le (A : Type) {eqA R : relation A}
                      `{PO : PartialOrder A eqA R} :
                      stream A -> stream A -> Prop :=
| le_step : forall h1 h2 t1 t2, R h1 h2 ->
            (eqA h1 h2 -> stream_le t1 t2) ->
            stream_le (scons h1 t1) (scons h2 t2).

如果我有一个假设stream_le (scons h1 t1) (scons h2 t2)，destruct策略将它变成一对假设R h1 h2和eqA h1 h2 -> stream_le t1 t2是合理的。但事实并非如此，因为 destruct 在做任何重要的事情时都会丢失信息。相反，新术语 h0、h3、t0、t3 被引入到上下文中，没有记得它们分别等于 h1、h2, t1, t2.

我想知道是否有一种快速简便的方法来完成这种 "smart destruct"。这是我现在拥有的：

Theorem stream_le_destruct : forall (A : Type) eqA R
  `{PO : PartialOrder A eqA R} (h1 h2 : A) (t1 t2 : stream A),
  stream_le (scons h1 t1) (scons h2 t2) ->
  R h1 h2 /\ (eqA h1 h2 -> stream_le t1 t2).
Proof.
  intros.
  destruct H eqn:Heq.
  remember (scons h1 t1) as s1 eqn:Heqs1;
  remember (scons h2 t2) as s2 eqn:Heqs2;
  destruct H;
  inversion Heqs1; subst; clear Heqs1;
  inversion Heqs2; subst; clear Heqs2.
  split; assumption.
Qed.

Answer 1

调用destruct不会直接给你你想要的。您需要改用 inversion。

Theorem stream_le_destruct : forall h1 h2 t1 t2,
  stream_le (scons h1 t1) (scons h2 t2) ->
  h1 <= h2 /\ (h1 = h2 -> stream_le t1 t2).
Proof.
  intros.
  inversion H; subst; clear H.
  split; assumption.
Qed.

不幸的是，inversion 策略表现得非常糟糕，因为它往往会产生很多虚假的平等假设，因此很难一致地命名它们。一个（有点重量级，无可否认）替代方案是仅使用 inversion 来证明您所做的引理，并将该引理应用于证明而不是调用 inversion.

Answer 2

事实上，inversion 基本上可以满足您的要求，但是正如 Arthur 指出的那样，它有点不稳定，主要是由于不同的同余步骤。

在幕后，inversion 只是调用了 destruct 的一个版本，但首先要记住一些等式。正如您已经发现的那样，Coq 中的模式匹配将 "forget" 构造函数的参数，除非这些是变量，然后，将实例化 destruct 范围下的所有变量 .

这是什么意思？这意味着为了正确地破坏一个归纳 I : Idx -> Prop，你想要得到你的目标形式：I x -> Q x，这样破坏 I x 也会改进 x在 Q。因此，归纳 I term 和目标 Q (f term) 的标准转换是将其重写为 I x -> x = term -> Q (f x)。然后，解构 I x 会让你 x 实例化到正确的索引。

考虑到这一点，使用 Coq 8.7 的 case: 策略手动实现反转可能是一个很好的练习；

From Coq Require Import ssreflect. Theorem stream_le_destruct A eqA R `{PO : PartialOrder A eqA R} (h1 h2 : A) (t1 t2 : stream A) : stream_le (scons h1 t1) (scons h2 t2) -> R h1 h2 /\ (eqA h1 h2 -> stream_le t1 t2). Proof. move E1: (scons h1 t1) => sc1; move E2: (scons h2 t2) => sc2 H. by case: sc1 sc2 / H E1 E2 => h1' h2' t1' t2' hr ih [? ?] [? ?]; subst. Qed.

你可以阅读手册了解更多细节，但基本上在第一行，我们创建了我们需要的等式；然后，在第二个中我们可以破坏术语并获得解决目标的正确实例化。 case: 策略的一个很好的效果是，与 destruct 相反，它会试图阻止我们在没有首先将其依赖项纳入范围的情况下破坏一个术语。

Coq：在不丢失信息的情况下破坏（共）归纳假设

Coq: destruct (co)inductive hypothesis without losing information

coq

coq-tactic