缺失的德摩根定律

Question

Coq 使用建设性逻辑，这意味着如果您尝试填写德摩根定律，你最终会错过 2。也就是说，你无法证明：

Theorem deMorgan_nand P Q (andPQ : ~(P /\ Q)) : P \/ Q.
Abort.

Theorem deMorgan_nall {A} (P : A -> Prop) (allPa : ~forall a, P a) : exists a, ~P a.
Abort.

这是有道理的，因为你必须计算它是否是 or 的左项或右项，一般情况下是做不到的。

正在看 “建设性世界的经典数学” (https://arxiv.org/pdf/1008.1213.pdf) 有定义

Definition orW P Q := ~(~P /\ ~Q).
Definition exW {A} (P : A -> Prop) := ~forall a, ~P a.

类似于德摩根定律。这表明了另一种表述方式。

Theorem deMorgan_nand P Q (andPQ : ~(P /\ Q)) : orW (~P) (~Q).
  hnf; intros nnPQ; destruct nnPQ as [ nnP nnQ ].
  apply nnP; clear nnP; hnf; intros p.
  apply nnQ; clear nnQ; hnf; intros q.
  apply (andPQ (conj p q)).  
Qed.

Theorem deMorgan_nall {A} (P : A -> Prop) (allPa : ~forall a, P a) : exW (fun a => ~P a).
Abort.

但是，它不适用于否定 forall。特别是，它卡在试图将 ~~P a 转换为 P a。所以，尽管在 nand 的情况下将 ~~P 转换为 P，它似乎不适用于 forall。您还可以证明 a 的某些元素具有 P a.

同样，你可以尝试显示

Theorem deMorgan_nexn {A} (P : A -> Prop) (exPa : ~exists a, ~P a) : ~~forall a, P a.
Abort.

但是一旦你有了论点a，它就会陷入困境，结论不再是False，所以不能用~~P -> P.

所以，如果你不能证明deMorgan_nall，有没有类似的定理？还是 ~forall a, P a 已经尽可能简化了？更一般地，当结论是 False 时，允许使用排中律 (P \/ ~P)。有没有对应的到当命题进行论证时有效的那个，那就是 P : A -> Prop 而不是 P : Prop ?

Answer 1

您要查找的原理称为 double negation shift。一般来说，它不在直觉逻辑中有效。尽管起初看起来相当无害，但由于它的结论是一个双重否定公式，它实际上非常有效。事实上，DNS 本质上是通过双重否定翻译来解释选择公理所需要的。

scubed编辑：

所以，这意味着我必须添加一个公理来处理这种情况。使用公理，

Axiom deMorgan_allnn : forall {A} (P : A -> Prop) (allPa : forall a, ~~P a), ~~forall a, P a.

Theorem deMorgan_nall {A} (P : A -> Prop) (allPa : ~forall a, P a) : exW (fun a => ~P a).
  hnf; intros ex1; apply deMorgan_allnn in ex1.
  apply ex1; clear ex1; hnf; intros all2.
  apply (allPa all2).
Qed.

缺失的德摩根定律

The missing De Morgan's law

coq

demorgans-law