证明在 Coq 中增加 iota

Question

我卡在了一个目标上。

假设我们有以下定义：

Fixpoint iota (n : nat) : list nat :=
  match n with
    | 0   => []
    | S k => iota k ++ [k]
  end.

而我们要证明：

Theorem t1 : forall n, In n (iota n) -> False.

到目前为止，我已经做到了以下几点：

Theorem t1 : forall n, In n (iota n) -> False.
Proof.
  intros.
  induction n.
    - cbn in H. contradiction.
    - cbn in H. apply app_split in H.
      Focus 2. unfold not. intros.
      unfold In in H0. destruct H0. assert (~(n = S n)) by now apply s_inj.
      contradiction.
      apply H0.
      apply IHn.

我用了这两个引理，省略了证明：

Axiom app_split : forall A x (l l2 : list A), In x (l ++ l2) -> not (In x l2) -> In x l.
Axiom s_inj     : forall n, ~(n = S n).

但是，我完全卡住了，我需要以某种方式表明：In n (iota n)假设In (S n) (iota n)。

Answer 1

正如您所观察到的，In n 中的 n 和 iota n 中的 iota n 在您的陈述中步调一致，这使得归纳假设难以调用（如果不是完全没用）。

这里的技巧是证明一个比你真正感兴趣的更一般的陈述，它打破了两个 n 之间的依赖关系。我会建议：

Theorem t : forall n k, n <= k -> In k (iota n) -> False.

从中你可以得出 t1 作为推论：

Corollary t1 : forall n, In n (iota n) -> False.
intro n; apply (t n n); reflexivity.
Qed.

如果你想偷看t的证明，你可以have a look at this self-contained gist

证明在 Coq 中增加 iota

Proving increasing iota in Coq

theorem-proving

coq