寻找可判定谓词的反例
Searching for a counterexample to a decidable predicate
感觉下面的 Coq 语句应该是有建设性的：
Require Import Decidable.
Lemma dec_search_nat_counterexample (P : nat -> Prop) (decH : forall i, decidable (P i))
: (~ (forall i, P i)) -> exists i, ~ P i.
如果有上限，我希望能够显示某种形式的东西“假设不是每个 i < N 都满足 P i。然后有一个 i < N 其中 ~ P i”。事实上，您实际上可以编写一个函数来通过从零开始搜索来查找最小示例。
当然，最初的说法没有上限，但我觉得应该有一个归纳论证可以从上面的有界版本得到它。但我还不够聪明，不知道怎么做！我错过了一个聪明的把戏吗？还是有一个根本原因导致这行不通，尽管自然数是有序的？
在 Meven Lennon-Bertrand 的评论后修改了答案
这个语句等同于 Markov's principle 交换了 P 和 ~P。由于 P 是可判定的，我们有 P <-> (~ ~ P)，因此可以进行此替换。
这篇论文 (http://pauillac.inria.fr/~herbelin/articles/lics-Her10-markov.pdf) 表明马尔可夫原理在 Coq 中是不可证明的，因为作者（Coq 的作者之一）在这篇论文中提出了一种新的逻辑，可以证明马尔可夫原理。
旧答案：
这在道德上是“全知的有限原则”- LPO（参见 https://en.wikipedia.org/wiki/Limited_principle_of_omniscience）。它需要经典公理来在 Coq 中证明它——或者你断言自己是公理。
参见示例：
Require Import Coquelicot.Markov.
Check LPO.
Print Assumptions LPO.
当然没有它的标准库版本。
感觉下面的 Coq 语句应该是有建设性的：
Require Import Decidable.
Lemma dec_search_nat_counterexample (P : nat -> Prop) (decH : forall i, decidable (P i))
: (~ (forall i, P i)) -> exists i, ~ P i.
如果有上限，我希望能够显示某种形式的东西“假设不是每个 i < N 都满足 P i。然后有一个 i < N 其中 ~ P i”。事实上，您实际上可以编写一个函数来通过从零开始搜索来查找最小示例。
当然，最初的说法没有上限，但我觉得应该有一个归纳论证可以从上面的有界版本得到它。但我还不够聪明，不知道怎么做！我错过了一个聪明的把戏吗？还是有一个根本原因导致这行不通，尽管自然数是有序的？
在 Meven Lennon-Bertrand 的评论后修改了答案
这个语句等同于 Markov's principle 交换了 P 和 ~P。由于 P 是可判定的，我们有 P <-> (~ ~ P)，因此可以进行此替换。
这篇论文 (http://pauillac.inria.fr/~herbelin/articles/lics-Her10-markov.pdf) 表明马尔可夫原理在 Coq 中是不可证明的，因为作者（Coq 的作者之一）在这篇论文中提出了一种新的逻辑，可以证明马尔可夫原理。
旧答案：
这在道德上是“全知的有限原则”- LPO（参见 https://en.wikipedia.org/wiki/Limited_principle_of_omniscience）。它需要经典公理来在 Coq 中证明它——或者你断言自己是公理。
参见示例：
Require Import Coquelicot.Markov.
Check LPO.
Print Assumptions LPO.
当然没有它的标准库版本。