Question

我最近了解了函数，以及它的一个公式，它本质上告诉我们，一个图灵机 $n$ n各州接管 $B B (n)$ BB(n)脚步，永不停歇。

我想到的一个结果是，如果我们能够构造一台图灵机，逐一检查每个偶数是否是两个素数的和，那么我们只需要运行这台机器有限步就可以确定哥德巴赫猜想。

因此，我们可以写出以下语句：

\exists N . （ 所有大于 2 且 \leq N 的偶数都是两个素数之和 ⟹ 所有大于二的偶数都是两个素数之和)

\exists N. (\text{All even numbers greater than 2 and $\leq$ N are a sum of two primes} \implies \text{All even numbers greater than two are a sum of two primes})

这似乎是一个相当不平凡的陈述，也可以用其他重要定理来复制。我的问题是，这样的事情是否可以在不深入研究计算理论的情况下得到证明（即仅使用一阶逻辑或类似性质）。

这也许是一种不同的思考方式，表明这实际上与图灵机或哥德巴赫猜想或其他东西无关。假设我们有一些逻辑形式，其中数学陈述及其证明可以用有限字符串表示。对于每个 $n$ n，一定有一些 $N$ N，这样所有长度的语句 $n$ n有长度证明 $N$ N或长度的反证 $N$ N，或者独立于我们的形式系统。如果我们知道这是什么 $N$ N就 $n$ n我们可以简单地检查我们陈述的所有证明/反证，这是一件“有限的”和“自动的”事情。 — 
我认为最好要求对你的陈述进行建设性证明，因为非建设性证明会使事情变得微不足道。此外，我认为甚至可以用经典的 $P A$ \sf PA，我们描述 $G C_{n}$ \sf GC_n达到元理论 $n$ n表示每个偶数直到 $S S S . . . . S_{n} (0)$ \sf SSS….S_n(0)大于 $4$ 4是两个偶数之和。 — 
继续……这样我们就能确保事情局限于标准自然数。然后问 $P A$ \sf PA可以证明推理规则 $I_{n}$ I_n对于一些元理论 $n$ n，在哪里 $I_{n}$ I_n规则是：
$GC n \forall x \in N ： G C （ x ） ¯ ¯ ¯ ¯ ¯ ¯ ¯ ¯ ¯ ¯ ¯ ¯ ¯ ¯ ¯ ¯ ¯ ¯ ¯ ¯ ¯ ¯ ¯ ¯ ¯ ¯ ¯ ¯ ¯ ¯ ¯ ¯ ¯$
{\sf GC}_n \\ \overline{\forall x \in N: {\sf GC}(x)} 在哪里 $G C (x)$ {\sf GC}(x)是哥德巴赫猜想的通常表述（这里 $x$ x范围涵盖所有天然标准和非标准。
\endgroup

– —

Answer 1

许多年前，我在伯克利参加一个聚会，发现自己站在一群研究生同学中间，听着著名数论学家亨德里克·伦斯特拉 (Hendrik Lenstra) 发表演讲。

有人问起孪生素数猜想，以及是否存在无穷多个素数，Lenstra 说他不知道答案。不过，他有一个有趣的观察。也就是说，有一个特定的数字 $N$ N，这样如果存在大于这个数的孪生素数，那么就会有无数个。所以如果我们能以某种方式知道这个数字，那么即使只有一个大于这个数的孪生素数实例也意味着一定有无数个孪生素数。太神奇了！

我们所有人都站在那里，思考着这个意义深远的声明。但他笑着说：“这完全是小事。”然后他等待着。我觉得这是他对我们这些新生提出的一种挑战。

我想了一会儿，然后说：好吧，如果孪生素数只有有限个，那么任何 $N$ N以上所有都可以。如果有无限个孪生素数，那么任意数 $N$ N会做。

Lenstra 回答说：“完全正确。所以就像我说的，这完全是小事一桩！”从那次聚会开始，我就一直记住了这个技巧。

这和你的问题是一样的，与 BB 或计算或可证明性无关。只是如果有一个反例，那么任何 $N$ N第一个反例可以成立。如果没有反例，那么任何 $N$ N会起作用。（这与 Will 在他的回答中提供的论点完全相同，但我想讲述 Lenstra 的故事，因为我总是想起使用这个技巧的那一刻，Lenstra 微笑着点头，说“完全微不足道”。）

我从 Peter Sarnak 的研究生那里听到了这个论点，他说他提出了一个定理“存在一个（无效的） $σ > 1 / 2$ \sigma>1/2如果黎曼 zeta 函数没有实部零点 $> σ$ >\sigma那么黎曼假设成立”作为无效常数结果的弱点的一个例子。我不知道这种想法在数论学家中是否特别常见。 — 
另请参阅饮酒者悖论：。在任何非空的酒吧中，都会有一个人，如果该人在那一刻喝酒，那么每个人都在那一刻喝酒。 — 
@ZuhairAl-Johar 我不同意。这个问题与直觉逻辑无关，直觉逻辑绝对不会解决 BB 函数的任何非平凡值——它们甚至都与 ZFC 无关，如果不能像 Will 描述的那样建设性地解决潜在问题，就不可能对这些事情进行建设性证明。问题和答案更确切地说是关于这种特定的平凡论证形式，一种特殊的案例证明，有时会让初学者感到困惑，但这也完全是一种经典逻辑现象。 — 
@IvanGalakhov: 不需要建设性的证据 $\exists N . (\forall x < N . P (x)) \to \forall x . P (x)$ \exists N. (\forall x < N. P(x)) \rightarrow \forall x. P(x)即使 $P (-)$ P(-)非常简单，例如可计算。事实上，一个足够有建设性的理论（例如具有数值存在性）无法证明可计算谓词的这一点 $P$ P除非它还证明 $\forall x . P (x)$ \forall x. P(x)或者 $\neg \forall x . P (x)$ \neg \forall x. P(x)思考这个问题的方式并不是“只要检查哥德巴赫是否成立就足够了 $B B (n)$ BB(n)对于一些 $n$ n“并且更接近于”我们必须首先解决哥德巴赫问题才能确定 $B B (n)$ BB(n)对于足够大的 $n$ n“。 —

Answer 2

是的，这可以直接证明。

假设所有大于 2 的偶数都是两个素数之和。那么 $N = 2$ N=2有效，因此该陈述是正确的。

假设并非所有大于 2 的偶数都是两个素数之和。设 $n$ n为大于 2 的偶数，且不是两个素数之和。则 $N = n$ N =n 有效，因此该陈述是正确的。

由于无论哪种情况，该陈述都是正确的，因此它是正确的。

证明方法清楚地表明：（1）这可以用其他重要定理来复制，但是（2）你写的陈述并不像乍一看那么有力。

lo.logic – 由于 Busy Beaver 数字而对定理进行有限验证 – MathOverflow

最佳答案
2

lo.logic – 由于 Busy Beaver 数字而对定理进行有限验证 – MathOverflow

最佳答案 2

最佳答案
2