paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Fusible numbers and Peano Arithmetic

可熔数(Fusible numbers)与皮亚诺算术
LMCS vol.Volume 18, Issue 32022匹配度 2/10 · 该论文属于数理逻辑与序数分析,讨论可熔数的序型、快速生长层级以及 Peano 算术无法证明的终止性命题;虽然涉及终止性,但与用户核心方向(静态分析、Agentic/LLM 程序分析、浮点程序分析、贝叶斯程序分析)几乎没有直接交集。引用 1 inbox
Jeff Erickson, Gabriel Nivasch, Junyan Xu
crossref: 2026-09-10crossref: 2026-09-12

AI 速览

一句话:定义可熔数,证明其序型为 ε₀,并给出 PA 无法证明的真命题与终止性实例。

论文从关于保险丝的数学谜题出发,定义可熔数:0 可熔,且当 x,y 可熔且 |y-x|<1 时,(x+y+1)/2 也可熔。作者研究该集合在实数序下的结构及其与皮亚诺算术(PA)证明能力的关系。主要结果包括:可熔数集合良序且序型为 ε₀;相邻可熔数在 [n,∞) 中的最大间隔 g(n) 满足 g(n)^{-1} ≥ F_{ε₀}(n-c),其中 F 为快速增长层级。作者由此得到不同于以往类型的 PA 不可证真命题,例如 PA 不能证明“每个自然数 n 都存在大于 n 的最小可熔数”,并构造算法 M,虽然 M 在所有实数输入上终止,但 PA 不能证明其在所有自然数输入上终止。

问题
研究由保险丝谜题诱导的可熔数集合的序结构、密度增长,以及这些性质能否在皮亚诺算术中证明。
方法
通过序数分析、良序性与快速增长层级等数学论证,证明可熔数的序型和增长下界,并构造 PA 不可证命题与递归算法反例。
评估
以数学证明作为评估:确立良序性和序型 ε₀、给出密度下界,并验证相应命题在 PA 中不可证明、算法终止性不可证。
原文摘要(Abstract)

Inspired by a mathematical riddle involving fuses, we define the "fusible numbers" as follows: $0$ is fusible, and whenever $x,y$ are fusible with $|y-x|<1$, the number $(x+y+1)/2$ is also fusible. We prove that the set of fusible numbers, ordered by the usual order on $\mathbb R$, is well-ordered, with order type $\varepsilon_0$. Furthermore, we prove that the density of the fusible numbers along the real line grows at an incredibly fast rate: Letting $g(n)$ be the largest gap between consecutive fusible numbers in the interval $[n,\infty)$, we have $g(n)^{-1} \ge F_{\varepsilon_0}(n-c)$ for some constant $c$, where $F_\alpha$ denotes the fast-growing hierarchy. Finally, we derive some true statements that can be formulated but not proven in Peano Arithmetic, of a different flavor than previously known such statements: PA cannot prove the true statement "For every natural number $n$ there exists a smallest fusible number larger than $n$." Also, consider the algorithm "$M(x)$: if $x<0$ return $-x$, else return $M(x-M(x-1))/2$." Then $M$ terminates on real inputs, although PA cannot prove the statement "$M$ terminates on all natural inputs."

链接与引用

DOI 原文 · PDF(开放获取) ·

BibTeX
@article{paperbot1684,
  title = {Fusible numbers and Peano Arithmetic},
  author = {Jeff Erickson and Gabriel Nivasch and Junyan Xu},
  journal = {Logical Methods in Computer Science},
  volume = {Volume 18, Issue 3},
  year = {2022},
  doi = {10.46298/lmcs-18(3:6)2022}
}