如何证明排中在 Coq 中是无可辩驳的？

Question

我试图证明以下来自 an online course 的简单定理，即排中是无可辩驳的，但在第 1 步几乎卡住了：

Theorem excluded_middle_irrefutable: forall (P:Prop), ~~(P \/ ~ P).
Proof.
  intros P. unfold not. intros H.

现在我得到：

1 subgoals
P : Prop
H : P \/ (P -> False) -> False
______________________________________(1/1)
False

如果我apply H，那么目标就是P \/ ~P，它被排除在中间，无法被建设性地证明。但是除了apply，我不知道可以对假设P \/ (P -> False) -> False做些什么：蕴涵->是原始的，我不知道如何destruct或者分解它。这是唯一的假设。

我的问题是，如何仅使用原始策略（，即没有神秘的 autos）来证明这一点？

谢谢。

Answer 1

我不是这方面的专家，但最近在 Coq mailing-list. I'll summarize the conclusion from this thread. If you want to understand these kinds of problems more thoroughly, you should look at double-negation translation 上讨论过。

问题属于直觉命题演算，因此可以由tauto决定。

Theorem excluded_middle_irrefutable: forall (P:Prop), ~~(P \/ ~ P).
  tauto.
Qed.

线程还提供了更详尽的证明。我将尝试解释我是如何得出这个证明的。请注意，我通常更容易处理引理的编程语言解释，所以这就是我要做的：

Theorem excluded_middle_irrefutable: forall (P:Prop), ~~(P \/ ~ P).
  unfold not.
  intros P f.

我们被要求编写一个接受函数 f 并产生类型 False 的值的函数。此时到达 False 的唯一方法是调用函数 f.

 apply f.

因此，我们被要求为函数 f 提供参数。我们有两个选择，要么通过P，要么通过P -> False。我看不到构建 P 的方法，所以我选择了第二个选项。

  right.
  intro p.

我们回到了第一点，除了我们现在有一个 p 可以使用！所以我们申请 f 因为这是我们唯一能做的。

  apply f.

再次，我们被要求提供 f 的参数。不过现在这很容易，因为我们有一个 p 可以使用。

  left.
  apply p.
Qed.

该主题还提到了一个基于一些更简单的引理的证明。第一个引理是 ~(P /\ ~P).

Lemma lma (P:Prop) : ~(P /\ ~P).
  unfold not.
  intros H.
  destruct H as [p].
  apply H.
  apply p.
Qed.

第二个引理是~(P \/ Q) -> ~P /\ ~Q:

Lemma lma' (P Q:Prop) : ~(P \/ Q) -> ~P /\ ~Q.
  unfold not.
  intros H.
  constructor.
  - intro p.
    apply H.
    left.
    apply p.
  - intro q.
    apply H.
    right.
    apply q.
Qed.

这些引理足以说明：

Theorem excluded_middle_irrefutable: forall (P:Prop), ~~(P \/ ~ P).
  intros P H.
  apply lma' in H.
  apply lma in H.
  apply H.
Qed.

如何证明排中在 Coq 中是无可辩驳的？

How to prove excluded middle is irrefutable in Coq?

logic

coq

coq-tactic