{"docId":9850,"paperId":8555,"url":"https:\/\/lmcs.episciences.org\/8555","doi":"10.46298\/lmcs-18(3:6)2022","journalName":"Logical Methods in Computer Science","issn":"","eissn":"1860-5974","volume":[{"vid":657,"name":"Volume 18, Issue 3"}],"section":[],"repositoryName":"arXiv","repositoryIdentifier":"2003.14342","repositoryVersion":9,"repositoryLink":"https:\/\/arxiv.org\/abs\/2003.14342v9","dateSubmitted":"2021-10-06 08:56:21","dateAccepted":"2022-05-23 23:33:01","datePublished":"2022-07-28 11:06:43","titles":["Fusible numbers and Peano Arithmetic"],"authors":["Erickson, Jeff","Nivasch, Gabriel","Xu, Junyan"],"abstracts":["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.\""],"keywords":["Computer Science - Logic in Computer Science","Mathematics - Combinatorics","Mathematics - Logic","03F30, 03B70, 03F40"]}