2020/03/31 by Jeff Erickson, Gabriel Nivasch, Junyan Xu · 1 voice
Computer Science · Mathematics · #Advanced Topology and Set Theory #Benford’s Law and Fraud Detection #Computability, Logic, AI Algorithms #cs.LO #math.CO #math.LO
paper · pdf · doi:10.46298/lmcs-18(3:6)2022
openalex publication_date 2022/07/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 ε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,∞), we have g(n)-1 ≥ Fε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."