在 Coq 中加入记录成员？

Question

考虑一个简单的记录成员归纳示例：

Record Foo : Type := mkFoo { foo: nat }.

Definition double (f: Foo) : Foo :=
  mkFoo (2 * foo f)%nat.


Theorem double_doubles: forall (f: Foo),
    foo (double f) = (2 * foo f)%nat.
Proof.
  intros.
  induction (foo f).
  (* How do I prevent this loss of information? *)
  (* stuck? *)
Abort.


Theorem double_doubles: forall (f: Foo),
    foo (double f) = (2 * foo f)%nat.
Proof.
  intros.
  destruct f.
  (* destruct is horrible if your record is large / contains many things *)
  induction foo0.
  simpl. auto.
  intros. simpl. auto.
Qed.

在 induction (foo f)，我坚持目标 foo (double f) = 2 * 0.

我以某种方式丢失了我正在对 foo f 进行归纳的信息（我没有假设表明 foo f = 0。

然而，destruct f并不令人满意，因为我有~5个成员记录在假设部分展开时看起来非常难看。

非常感谢任何帮助！

Answer 1

您可以使用 remember 策略为表达式命名，生成一个您可以归纳分析的变量。该策略生成一个将变量与记住的表达式连接起来的方程式，使您可以跟踪所需的信息。

为了说明，请考虑以下证明脚本。

Record Foo : Type := mkFoo { foo: nat }.

Definition double (f: Foo) : Foo :=
  mkFoo (2 * foo f)%nat.

Theorem double_doubles: forall (f: Foo),
    foo (double f) = (2 * foo f)%nat.
Proof.
  intros.
  remember (foo f) as n eqn:E.
  revert f E.
  induction n.

调用remember后目标变为：

  f : Foo
  n : nat
  E : n = foo f
  ============================
  foo (double f) = 2 * n

如果你在remember之后直接对n进行归纳，你可能无法完成你的证明，因为你得到的归纳假设不够普遍.如果您运行解决了这个问题，您可能需要概括出现在定义 n 的表达式中的一些变量。在上面的脚本中，调用 revert f E 将 f 和 E 放回目标，从而解决了这个问题。

在 Coq 中加入记录成员？

Induction on record member in Coq?

coq

coq-tactic