Fusible numbers and Peano Arithmetic

With Gabriel Nivasch and Junyan Xu*

🔥To appear in Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science, 2021.
🔥Selected by the LICS program committee as a Disstinguished Paper.


Inspired by a mathematical riddle involving fuses, we define the fusible numbers as follows: 0 is fusible, and whenever x and 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 ℝ, is well-ordered, with order type ε₀. 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 greater than or equal to n, we have 1/g(n) ≥ Fε₀(nc) 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. For example, PA cannot prove the true statement “For every natural number n there exists a smallest fusible number larger than n.”

Publications - Jeff Erickson (jeffe@illinois.edu) 27 Apr 2020