有没有更优雅的方法让 coq 相信基于列表的假设是矛盾的？

Question

我在研究一个简单的引理时遇到了矛盾或注入策略都没有我预期的那么强大的情况。

Theorem list_app_single: forall (T : Type) (x : T) (l1 l2 : list T),
   l1++[x] =  l2++[x] -> l1 = l2.
Proof.
intros. generalize dependent l2. induction l1.
  - intros. induction l2.
  --  reflexivity.
  -- inversion H.

到此为止，证明状态为：

1 subgoal
T : Type
x, x0 : T
l2 : list T
H : [ ] ++ [x] = (x0 :: l2) ++ [x]
IHl2 : [ ] ++ [x] = l2 ++ [x] -> [ ] = l2
H1 : x = x0
H2 : [ ] = l2 ++ [x0]
______________________________________(1/1)
[ ] = x0 :: l2

显然 H2 不正确，但 coq 在应用判别策略时没有看到这一点。有没有更合适的策略可以解决 H2 实际上是错误的？

编辑：使问题更侧重于克服歧视限制的特定策略。

Answer 1

要使用 discriminate 策略，您需要将表达式部分的“顶部”项作为构造函数（简化后）。因此，discriminate 可以看到[经过一些 'thinking'] 构造函数不同。

你在H2中等式右侧的顶部没有构造函数。即，l2 ++ [x0] 不是构造函数。它是函数app（++运算符的别称）的一个应用，它有两个参数，即l2和[x0]。所以，你的表情看起来像

H2 : [ ] = app l2 [x0]

而右边的部分显然不是构造函数。

你可以尝试destruct l2.。由于 app 函数通过匹配其第一个参数然后在简化之后（在 H2 中）工作，因此 H2 的右上部分将是一个构造函数。而discriminate就能完成证明。

至于另一个更聪明的策略：据我所知，这里不可能有通用的解决方案（我们应该陷入停机问题）。但我认为经过一些研究，有人可以创造出比 discrimite 更聪明的东西。您可以在 Adam Chlipala 的 Certified Programming with Dependent Types 书中看到此类策略的示例，并对其工作原理进行了很好的解释（该策略被命名为 crush）。

即 crush 可能无法解决这个特定问题。但我认为您可以使用作者建议的技术编写此类策略的示例。

Answer 2

为了完成@Andrey 的回答，discriminate 确实适用于具有不同构造函数的等式，例如 [] = x :: l。这个问题的解决方案可以通过在你的平等之上添加另一个观察来实现。例如，在这里，您可以观察到此类表达式的长度不匹配：从 [] = l ++ [x] 你得到 length [] = length (l ++ [x]) 简化为 0 = length l + 1.

From Coq Require Import List Lia.
Import ListNotations.

Lemma foo :
  forall (A : Type) (l : list A) (x : A),
    [] = l ++ [x] ->
    False.
Proof.
  intros A l x e.
  apply (f_equal (@length A)) in e.
  rewrite app_length in e. simpl in e. lia.
Qed.

请注意，最后，我应用 lia 策略从 0 = n + 1 推导出矛盾。

在仅销毁 l 无法立即工作的情况下，此方法非常有用。如果您经常有歧视行为，那么采用自己的 discr 策略来为您解决问题可能是值得的。

Answer 3

我偏爱@Theo 的解决方案。开始向左和向右分解项很容易，但这样做会开始在太低的层次上进行推理——推理数据的实现而不是属性，这使得证明不太可能结转到其他情况。

因此，如果您只想要“一种有效的策略”，那么 destruct 通常很有用。你可以用

解决你的目标

  now destruct l2.

但是，如果您希望您的证明在您推理的事物的理论中进行推理 - 列表 - 那么这个证明就是这样做的。

  enough (@length T [] <> 0) by auto.
  rewrite H2, app_length, PeanoNat.Nat.add_comm; auto.

有没有更优雅的方法让 coq 相信基于列表的假设是矛盾的？

Is there a more elegant way to convince coq that a list based hypothesis is a contradiction?

coq