论文标题
易熔的数字和Peano算术
Fusible numbers and Peano Arithmetic
论文作者
论文摘要
受涉及保险丝的数学谜语的启发，我们定义了“熔体数字”，如下所示：$ 0 $是fusible的，每当$ x，y $都与$ | y-x | <1 $熔解时，数字$（x+y+y+1）/2 $也是熔解的。我们证明，按$ \ Mathbb r $上订购的一组易熔号已订购良好，订单类型$ \ varepsilon_0 $。此外，我们证明，沿实际线路的易熔数密度以非常快的速度增长：让$ g（n）$是间隔$ [n，\ infty）$中连续的熔融数字之间的最大差距，我们有$ g（n）^{-1} {-1}} {-1} {-1} \ ge f _ $ c $ c $ c $ c $ c $ c $ c $ c $ c。 $f_α$表示快速增长的层次结构。最后，我们得出了一些可以在Peano Arithmetic中制定但无法证明的真实陈述，其风味与以前已知的陈述不同：PA无法证明“对于每个自然数量$ n $，都有大于$ n $的最小的熔融数字”。另外，请考虑算法“ $ m（x）$：如果$ x <0 $返回$ -x $，else返回$ m（x-m（x-1）/2 $”。然后，$ m $终止了实际输入，尽管PA无法证明“ $ m $在所有自然输入上终止”。
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_α$ 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."
