抽象术语...导致术语...类型不正确

Question

我要证明的是：

  A : Type
  i : nat
  index_f : nat → nat
  n : nat
  ip : n < i
  partial_index_f : nat → option nat
  L : partial_index_f (index_f n) ≡ Some n
  V : ∀ i0 : nat, i0 < i → option A
  l : ∀ z : nat, partial_index_f (index_f n) ≡ Some z → z < i
  ============================
   V n ip
   ≡ match
       partial_index_f (index_f n) as fn
       return (partial_index_f (index_f n) ≡ fn → option A)
     with
     | Some z => λ p : partial_index_f (index_f n) ≡ Some z, V z (l z p)
     | None => λ _ : partial_index_f (index_f n) ≡ None, None
     end eq_refl

显而易见的下一步是 rewrite L 或破坏 (partial_index_f (index_f n)。尝试应用重写给我一个错误：

Error: Abstracting over the term "partial_index_f (index_f n)"
leads to a term
"λ o : option nat,
 V n ip
 ≡ match o as fn return (o ≡ fn → option A) with
   | Some z => λ p : o ≡ Some z, V z (l z p)
   | None => λ _ : o ≡ None, None
   end eq_refl" which is ill-typed.

我不明白是什么导致了这个问题。我也想了解一般情况下我该如何处理。

我能够使用以下步骤证明它，但我不确定这是最好的方法：

  destruct (partial_index_f (index_f n)).
  inversion L.
  generalize (l n0 eq_refl).
  intros. subst n0.
  replace l0 with ip by apply proof_irrelevance.
  reflexivity.
  congruence.

Answer 1

在 Coq 的理论中，当您使用方程式执行重写时，您必须概括要替换的方程式的一侧。在你的例子中，你想要替换 partial_index_f (index_f n)，所以 Coq 试图概括它，正如你从收到的错误消息中可以看出的那样。

现在，如果您的目标包含某些 type 提到您要替换的东西，您可能运行会遇到麻烦，因为这种概括可能会使目标变得病态。（请注意，该类型并没有完全出现在目标中，因此 Coq 不会像在目标中出现某些事情时那样尝试处理它。）回到您的案例，您的 l 函数具有类型 ∀ z : nat, partial_index_f (index_f n) ≡ Some z → z < i，其中提到 partial_index_f (index_f n)，您要替换的术语。在 match 的第一个分支中，您将此函数应用于您抽象的 o = Some z 假设。在最初的目标上，o 是您想要替换的东西，但是当 Coq 尝试概括时，两者不再匹配，因此出现错误消息。

我无法尝试自己解决问题，但您通常可以通过概括上下文中提及您要替换的术语的术语来解决此类问题，因为这样它的类型就会显示在目标，与一个普遍量化的变量相关联。如果您的术语是全局定义的并且您需要它在重写后具有特定形状以便能够执行其他推理步骤，这可能无济于事，在这种情况下您可能还必须概括您需要的引理.

抽象术语...导致术语...类型不正确

Abstracting over the term ... leads to a term ... which is ill-typed

coq