episciences.org_8555_20230321085410629
20230321085410629
episciences.org
raphael.tournoy+crossrefapi@ccsd.cnrs.fr
episciences.org
Logical Methods in Computer Science
18605974
07
28
2022
Volume 18, Issue 3
Fusible numbers and Peano Arithmetic
Jeff
Erickson
Gabriel
Nivasch
Junyan
Xu
https://orcid.org/0000000237892319
Inspired by a mathematical riddle involving fuses, we define the "fusible
numbers" as follows: $0$ is fusible, and whenever $x,y$ are fusible with
$yx<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 wellordered,
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}(nc)$ for some constant
$c$, where $F_\alpha$ denotes the fastgrowing 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(xM(x1))/2$." Then $M$ terminates on real inputs,
although PA cannot prove the statement "$M$ terminates on all natural inputs."
07
28
2022
8555
https://creativecommons.org/licenses/by/4.0
arXiv:2003.14342
10.48550/arXiv.2003.14342
https://arxiv.org/abs/2003.14342v7
https://arxiv.org/abs/2003.14342v5
10.46298/lmcs18(3:6)2022
https://lmcs.episciences.org/8555

https://lmcs.episciences.org/9850/pdf

https://lmcs.episciences.org/9850/pdf