一句话:定义可熔数,证明其序型为 ε₀,并给出 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 不能证明其在所有自然数输入上终止。
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."