Coq 中 -> 的传递性

Question

我试图在 Coq 的命题中证明 -> 的传递性：

Theorem implies_trans : forall P Q R : Prop,
  (P -> Q) -> (Q -> R) -> (P -> R).
Proof.

我想破坏所有命题，并简单地处理所有8种可能性自反性。显然不是那么简单。这是我尝试过的：

Theorem implies_trans : forall P Q R : Prop,
  (P -> Q) -> (Q -> R) -> (P -> R).
Proof.
  intros P Q R H1 H2.
  destruct P. (** Hmmm ... this doesn't work *)
Admitted.

这就是我得到的：

1 subgoal
P, Q, R : Prop
H1 : P -> Q
H2 : Q -> R
______________________________________(1/1)
P -> R

随后出现此错误：

Error: Not an inductive product.

非常感谢任何帮助，谢谢！

Answer 1

Coq 的逻辑不是命题为真或假的经典逻辑。相反，它基于类型论，默认情况下具有直觉主义风格。¹ 在类型论中，您应该将 P -> Q 视为从 "things of type P" 到 "things of type Q".²

证明P -> Q类型目标的通常方法是使用intro或intros引入类型P的假设，然后使用该假设以某种方式生成 Q.

类型的元素

例如，我们可以证明(P -> Q -> R) -> (Q -> P -> R)。在 "implication is a function" 解释中，这可以理解为如果我们有一个接受 P 和 Q 并产生 R 的函数，那么我们可以定义一个接受Q 和 P 并生成 R。这是相同的函数，但交换了参数。

Definition ArgSwap_1 {P Q R: Prop}: (P -> Q -> R) -> (Q -> P -> R) :=
  fun f q p => f p q.

使用策略，我们可以看到各个元素的类型。

Lemma ArgSwap_2 {P Q R: Prop}: (P -> Q -> R) -> (Q -> P -> R).
Proof.
  intro f.
  intros q p.
  exact (f p q).
Qed.

在 intro 之后，我们看到 f: P -> Q -> R，所以 f 是我们的函数，它接受 Ps 和 Qs 并产生 R秒。在 intros（引入多个术语）之后，我们看到 q: Q 和 p: P。最后一行（在 Qed. 之前）简单地将函数 f 应用到 p 和 q 以获得 R.

中的内容

对于你的问题，intros引入了命题P、Q和R，以及H1: P -> Q和H2: Q -> R .不过，我们仍然可以再引入一个 P 类型的术语，因为目标是 P -> R。你能看出如何使用 H1 和 H2 以及 P 的元素来生成 R 的元素吗？提示：您将完成 Q。另外，请记住 H1 和 H2 是函数。

¹ 您可以添加排中律作为公理，这将允许进行您想要的案例分析，但我认为它错过了 Coq 的要点。

² 如果您想知道，Prop 的元素仍然是类型并且与 Set 或 [=58 的元素具有非常相似的行为=].唯一的区别是 Prop 是 "impredicative"，它允许命题对所有命题进行量化。例如 forall P: Prop, P -> P 是 Prop 的一个元素，但是 forall A: Type, A -> A 是 Type 的上一层元素（Type 实际上是一个无限层次）。

Coq 中 -> 的传递性

Transitivity of -> in Coq

coq

implication