归纳 Coq 定义中存在量词和全称量词之间的关系

Question

假设我想要一个子字符串的归纳定义（字符串只是列表的同义词）。

Inductive substring {A : Set} (w : string A) :
                    (string A) -> Prop :=
  | SS_substr : forall x y z : string A,
                  x ++ y ++ z = w ->
                  substring w y.

这里我可以举例证明如下：

Theorem test : substring [3;4;1] [4].
Proof.
  eapply SS_substr.
  cbn.
  instantiate (1:=[1]).
  instantiate (1:=[3]).
  reflexivity.
Qed.

然而，证明是 "existential" 而不是 "universal"，尽管归纳定义声明 forall x y z 并且仅在那时限制了它们的形状。这对我来说似乎有点不直观。给出了什么？

此外，是否可以使用 exists x : string A, exists y : string A, exists z : string, x ++ y ++ z = w -> substring w y 进行归纳定义？

Answer 1

需要注意的一件重要事情是 exists 不是 Coq 的内置功能（与 forall 相反）。其实，exists本身就是一种记法，只是背后有一个归纳类型ex。符号和归纳类型在 Coq standard library 中定义。下面是 ex 的定义：

Inductive ex (A:Type) (P:A -> Prop) : Prop :=
    ex_intro : forall x:A, P x -> ex (A:=A) P.

它是使用一个构造函数和通用量化定义的，就像您的 substring 类型一样，因此您的 susbtring 类型在某些时候似乎是 "existential" 也就不足为奇了。

当然，你可以使用exists来定义你的类型，你甚至不需要Inductive。

Definition substring' {A : Set} (w y : string A) : Prop :=
    exists x z, x ++ y ++ z = w.

归纳 Coq 定义中存在量词和全称量词之间的关系

Relationship between existential and universal quantifier in an inductive Coq definition

coq

theorem-proving