为什么我可以使用构造函数策略来证明自反性?

Why can I use the constructor tactic to prove reflexivity?

构造函数策略允许您通过自动应用构造函数来实现归纳数据类型的目标。但是,定义相等性不是 Coq 中的归纳积。那为什么 Coq 接受这个证明呢?

Example zeqz : 0 = 0. constructor.

Coq中的相等类型定义如下

Inductive eq (A : Type) (x : A) : A -> Prop :=  
   eq_refl : x = x

也就是说它有一个自反性构造函数。

要证明 0 = 0 你需要构造一个这种类型的项。执行此操作的唯一方法是调用 eq_refl。然而,为了调用 eq_refl,类型检查器需要知道 0 可以转换为 0(即它们在定义上是相等的)。


类型 eq 是相等的语义概念,而定义相等是句法概念。 这意味着证明助手无法区分定义上相等的术语,但它可以区分语义上相等的术语。因此构造函数eq_refl可以看作是定义(句法)的保证) 等式 包含 语义等式。

询问术语是否可以在语义上相等而不在句法上相等是富有成果的。这样的例子只能通过公理获得。例如,根据自然数的递归定义(nat_rec,或更专业地说,nat_ind),或 extensionality 公理。