forall 和 exists 之间的这种关系是否可以在 Coq/intuitionistic 逻辑中证明？

Question

下面的定理在 Coq 中可以证明吗？如果不是，有没有办法证明它是不可证明的？

Theorem not_for_all_is_exists:
    forall (X : Set) (P : X -> Prop), ~(forall x : X, ~ P x) -> (exists x: X, P x).

我知道这个相关关系是真实的：

Theorem forall_is_not_exists : (forall (X : Set) (P : X -> Prop), (forall x, ~(P x)) -> ~(exists x, P x)).
Proof.
  (* This could probably be shortened, but I'm just starting out. *)
  intros X P.
  intros forall_x_not_Px.
  unfold not.
  intros exists_x_Px.
  destruct exists_x_Px as [ witness proof_of_Pwitness].
  pose (not_Pwitness := forall_x_not_Px witness).
  unfold not in not_Pwitness.
  pose (proof_of_False := not_Pwitness proof_of_Pwitness).
  case proof_of_False.
Qed.

但我不确定在没有双重否定消除的情况下是否对我有帮助。我也试过用不同的方法证明有问题的定理，但无济于事。我只是在学习 Coq，所以我可能只是遗漏了一些明显的东西。

N.B。我很清楚这在经典逻辑中是正确的，所以我不是在寻找向底层系统添加额外公理的证明。

Answer 1

你的 not_for_all_is_exists 命题在 Coq 中无法证明。我建议阅读 Dirk Van Dalen 的 "Logic and Structure" 第 5 章的开头以获得更深入的解释。

在直觉逻辑（以及 Coq 等系统）中，要证明 exists x, P x，您必须提供一种方法（或算法）来构建实际的 x，使得 P x持有。

假设 not (forall x, not (P x)) 具有大致的解释 "if I assume that P doesn't hold for all x, then I get a contradiction"，但这比您想要的结论要弱，构建模型将显示该假设不包含足够的信息来为 [选择见证人=15=].

然而，必须要说的是，对于 P 和 X 的受限类，这个原则在 Coq 中成立，一个特殊的例子是当 P 是可判定的谓词和 X 有限类型。

Answer 2

无法证明，因为它等同于消除双重否定（以及其他经典公理）。

我的 Coq 技能目前很生疏，但我可以快速说明为什么你的定理意味着消除双重否定。

在你的定理中，实例化 X 到 unit 和 P 到 fun _ => X 任意 X : Prop。现在我们有 ~(unit -> ~ X) -> exists (u : unit), X。但是由于 unit 的琐碎性，这相当于 ~ ~ X -> X.

可以通过对 ~ ~ (exists x, P x).

直接应用双重否定消除来证明反向蕴涵

我的 Agda 好多了，所以我至少可以在那里展示证明（不知道这是否有帮助，但它可能会稍微支持我的主张）：

open import Relation.Nullary
open import Data.Product
open import Data.Unit
open import Data.Empty
open import Function

∀∃ : Set _
∀∃ = (A : Set)(P : A → Set) → ¬ (∀ x → ¬ P x) → ∃ P

Dneg : Set _
Dneg = (A : Set) → ¬ ¬ A → A

to : ∀∃ → Dneg
to ∀∃ A ¬¬A = proj₂ (∀∃ ⊤ (const A) (λ f → ¬¬A (f tt)))

fro : Dneg → ∀∃
fro dneg A P f = dneg (∃ P) (f ∘ curry)

forall 和 exists 之间的这种关系是否可以在 Coq/intuitionistic 逻辑中证明？

Is this relationship between forall and exists provable in Coq/intuitionistic logic?

logic

implication

coq