🔢 mathematics

An Intuitionistic Glance at Primes

本文在直觉主义逻辑中提供了一个证明论解释，论证了将正整数分类为 1、质数和合数可以通过有界搜索来判定，从而引向一个递归筛法、一个模消解的特征化，以及直觉主义算术内部证明的内容与依赖于自然数标准解释的内容之间的区别。

原作者： Milan Rosko

发布于 2026-07-15

📖 1 分钟阅读🧠 深度阅读

原作者： Milan Rosko

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象你是一名侦探，正试图将一大堆数字分类到三个不同的盒子中：单位元 (The Unit)、素数 (The Primes) 和 合数 (The Composites)。大多数人认为这只是一个数学游戏，但米兰·罗斯科（Milan Rosko）在 2026 年 7 月撰写的这篇论文提出了一个更深层的问题：我们究竟如何证明一个数字属于某个盒子，而不仅仅是靠猜测？

论文指出，在“直觉主义逻辑”（一种要求必须展示推导过程，而不仅仅是断言某事为真的严格思维方式）的世界里，证明一个数是“合数”的方式与证明它是“素数”的方式截然不同。

两种侦探风格：寻找与穷尽

以数字 6 为例。要证明它是合数，你只需要找到一对能乘出 6 的伙伴即可。你大喊道：“啊哈！2 乘以 3 等于 6！”你拥有了一个正向见证者 (positive witness)。你找到了证据。这被称为“存在性”搜索。这就像找到一把丢失的钥匙；一旦你看到了它，任务就完成了。

现在，看看数字 5。要证明它是素数，你不能仅仅是找一个伙伴；你必须证明它没有任何伙伴（除了 1 和它本身）。你必须检查所有可能相乘得到 5 的数字对，并证明其中没有任何一对奏效。你必须穷尽所有的嫌疑人名单。论文称之为“有界反驳 (bounded refutation)”。你通过证明“缺乏内部因子分解”来证明一个素数。

重大发现： 论文证明，对于你选出的任何数字，你总能判定它属于哪个盒子。你不需要猜测。你只需运行一个有限搜索。如果你找到了因子对，它就是合数；如果你检查了直到该数字为止的所有可能对且一无所获，它就是素数。而“单位元”（数字 1）是一个特殊的案例，它不属于这两个盒子中的任何一个。

“捕手”游戏与筛法

论文引入了一个有趣的名为**“有限捕手 (Finite Catcher)”**的游戏。想象你有一个由特定数字（如 2 和 3）组成的网。你向网中投掷一个合数。如果这个数是由 2 和 3 组成的（如 6 或 12），网会抓住它。但如果你投掷一个像 25 这样的数字，网就会漏掉它！为什么？因为 25 是由 5 组成的，而你的网里没有 5。

论文展示了一个巧妙的技巧，称为**“欧几里得逃逸 (Euclidean Escape)”**。无论你的网有多大，你总能构造出一个能从孔洞中溜走的数字。这证明了你永远无法用一个有限的网捕捉到所有的合数。

那么，我们如何捕捉到它们呢？论文描述了一种**“递归筛法 (Recursive Sieve)”**：

从一个空网开始。
向网中投掷数字。第一个幸存（溜走）的数字是 2。
因为 2 幸存了，我们知道它是素数。所以，我们将 2 加入我们的网中。
现在，向这个新的网（捕捉 2 的倍数）投掷数字。下一个幸存者是 3。将 3 加入网中。
继续进行。下一个幸存者是 5，然后是 7，依此类推。

这个过程逐一构建了素数列表。论文证明，第一个总是能从由前 $k$ 个素数组成的网中溜走的合数，是下一个素数的平方（例如 $5^2 = 25$ ）。

论文排除了什么（“禁区”）

这篇论文非常谨慎地说明了它没有声称的内容。

它排除了“非素数”自动意味着对于数字 1 而言是“合数”的观点。 在这种严格的逻辑中，1 是它自己的特殊类别。你不能简单地说“它不是素数，所以它一定是合数”。它既不是素数也不是合数。
它反对认为我们可以拥有一种单一、完美的“通用机器”来瞬间决定每一个数学真理的观点。 论文利用著名的 莱斯定理 (Rice's Theorem) 来表明，虽然我们可以检查特定的数字（例如“25 是合数吗？”），但我们无法构建一台单一的机器，仅通过观察代码就能判定所有可能的数字模式的真理性（例如“是否存在无穷多个孪生素数？”）。
它拒绝了认为在数学系统中证明一个数是素数，等同于证明它符合我们现实生活中的数字这一观点。 论文区分了游戏的规则（语法）与游戏的意义（语义）。计算机可以完美地遵循规则并证明一个数是素数，但这并不自动意味着它理解了现实世界中的“素数”是什么意思。这需要额外的解释步骤。

我们有多确定？

这篇论文是经过数学证明的，而不仅仅是模拟或建议。

数字的分类（1、素数、合数）是可判定的 (decidable)。这意味着对于你喂给它的任何数字，都存在一个保证有效的、循序渐进的配方，总能给你正确的答案。
“筛法”是构造性的 (constructive)。它不仅说“素数存在”，还展示了你如何一步步构建它们。
它所讨论的限制（如无法拥有处理所有模式的通用机器）是基于既定逻辑（哥德尔不完备定理和莱斯定理）的严谨证明。

素数的“海市蜃楼”

论文以一个美丽的隐喻结束。它说合数就像是由数字相乘构建起来的一堵实墙。而素数则是这堵墙上的孔洞。

合数很容易识别，因为你可以看到支撑它的砖块（因子）。
素数是通过它不是什么来定义的。它是没有任何砖块能嵌入其中的孔洞。

论文总结道，虽然我们可以轻松检查任何单个孔洞以确认它是否为孔洞（因为搜索是有限的），但所有孔洞共同构成的模式却是一个谜团。我们可以验证墙上的局部区域，但这些孔洞在无限空间中分布的整体模式，仍然是一个我们无法用单一、简单规则完全捕捉到的“海市蜃楼”。

简而言之：我们拥有一把完美的、好用的手电筒来检查任何单个数字。但整个无限数字森林的地图又是另一回事，而这篇论文划定了我们能用手电筒证明的内容与那些依然美丽且未被证明的奥秘之间的界限。

技术摘要：直觉主义视角下的素数

问题陈述
本文探讨了在直觉主义逻辑（具体为希尔伯特算术，HA）框架下，将正整数分类为单位元（units）、素数（primes）和合数（composites）的证明论分类。虽然经典算术将这些类别视为互斥且穷尽的扩张，但本文研究了建立这些属性所需的不同形式的证据。核心问题在于，如何形式化“合数性”（一个存在性断言）与“素数性”（一个全称否定断言）在搜索空间受限时如何作为可判定谓词发挥作用，并区分形式理论的句法规则、模型的内部一致性以及相对于标准自然数 $\mathbb{N}$ 的语义解释。

方法论
作者采用了基于直觉主义逻辑的构造性、证明论方法。其方法论通过以下几个层面展开：

通过证据形式进行的项三分类： 本文定义了三个谓词——单位元 ( $U$ )、合数 ( $C$ ) 和素数 ( $P$ )，它们基于特定的证据类型：
- $U(n)$ ：等式 $n=1$ 的证据。
- $C(n)$ ：内部因数分解 $n=ab $（其中$ a,b > 1$）的证据（一个存在性见证）。
- $P(n)$ ： $n > 1$ 结合对所有可能的内部因数分解的有界否定（一个全称否定）。
  由于任何 $n$ 的潜在因子域是有限且可判定的，因此 $C(n)$ 和 $P(n)$ 被证明是可判定谓词。
阶段性块呈现： 为了使有界搜索具有可操作性，本文引入了“阶段性块配置”（staged block configurations）。这些是候选因子对的有限有序列表。本文分析了在扩展这些阶段时产生的“缺陷”关系（遗漏、重复、顺序违规）。它区分了局部填充（特定阶段下的有效决策）与统一全总化（针对所有阶段的全局选择器）。
欧几里得逃逸与筛法： 本文利用欧几里得论证的构造性变体（“欧几里得逃逸”）来证明，任何有限的“捕获器”（合数的生成器）集合都无法捕捉所有的合数。这导致了一个递归筛法构造，其中有限捕获器集合中的最小幸存者被提升为新的生成器，从而有效地枚举出素数序列。
代数与语义分析： 本文考察了这种分类的代数后果，特别是模约减（对于素数）与零因子湮灭（对于合数）之间的对比。随后，论文转向语义分析，区分了：
- 规则符合性： 证明的句法验证。
- 内部乘法一致性： 在固定模型内对定义的满足。
- 标准定义一致性： 理论与标准结构 $\mathbb{N}$ 的对齐，这需要元理论表示。

主要贡献与结果

素数的可判定性： 本文确立了素数在 HA 中是一个可判定属性，因为其定义中的全称量词受限于输入 $n$ 。素数与合数的区别在于“证明极性”（存在性见证 vs 全称否定），而非算术层级复杂度（两者均为 $\Delta_0$ ）。
单位元边界： 对单位元 ($1 $) 进行了严格处理，表明二元对立$ \neg P(n) \to C(n) $在$ n=1 $时失效。本文构造性地证明了三元分类$ U(n) \lor P(n) \lor C(n)$ 成立。
有限捕获器与筛法转换： 本文证明了任何有限的合数生成器集合都会遗漏某些合数（具体而言是最小幸存者的平方）。这一机制驱动了生成普通素数序列的递归筛法。
代数特征： 本文将素数的数论定义与环 $\mathbb{Z}/n\mathbb{Z}$ 中的消去代数性质联系起来。当且仅当乘以任何非零剩余都是单射时， $n > 1$ 是素数。
语义层级： 本文描绘了一个认证层级：
1. 局部证据： 特定 $n$ 的有限见证或否定。
2. 模型一致性： 固定模型中谓词的扩展。
3. 元理论表示： 断言一个理论与标准 $\mathbb{N}$ 一致。
  本文表明，虽然局部理论是 HA 的保守扩张，但建立与标准模型的协议需要外部元理论数据。
统一性的限制： 本文应用莱斯定理（Rice's Theorem）和哥德尔第二不完备定理表明，虽然单个素数测试是可判定的，但统一的双边认证（为所有 $n$ 生成素性和合数性的证明）或停机问题的统一完成界限，其计算强度等价于停机问题预言机 ( $0'$ )。

意义与主张
本文声称提供了一种关于整数分类的“证明论说明”，强调素数与合数的区别是结构性和证据性的，而非仅仅是外延性的。

直觉主义严谨性： 本文认为，“单位元边界”以及有界搜索的本质对于理解素数的构造性内容至关重要。本文澄清了素数的“缺乏内部因数分解”并非负无穷，而是一种有限的、详尽的否定。
层级的分离： 本文的一个主要贡献是明确分离了句法规则符合性、内部模型满足以及标准结构的表示。本文断言，“与素数的一致性”是一个取决于所选元理论和解释的相对概念。
素数作为“幻象”： 在结论中，本文提出了一个隐喻性的特征描述：相对于内部乘法，合数构成了正向生成的图像，而素数则是该图像中的“空洞”。本文声称，关于素数的全局猜想（如孪生素数猜想或哥德巴赫猜想）是在没有提供其分布的正向生成器的情况下，在这些“空洞”之间寻求组织形式，这凸显了它们在构造性呈现上的根本不对称性。

本文并不提出新的分解算法或素性测试算法，也不声称解决开放性猜想。相反，它提供了一种基础分析，探讨这些概念在直觉主义算术中是如何被构造、验证和解释的，并区分了什么是内部可证明的，什么又取决于自然数的标准解释。

两种侦探风格：寻找与穷尽

“捕手”游戏与筛法

论文排除了什么（“禁区”）

我们有多确定？

素数的“海市蜃楼”

类似论文