Jeff Erickson, Gabriel Nivasch, Junyan Xu

Research output: Contribution to journalArticlepeer-review


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 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.”.

Original languageEnglish (US)
Pages (from-to)6:1-6:26
JournalLogical Methods in Computer Science
Issue number3
StatePublished - 2022


  • Peano Arithmetic
  • fast-growing hierarchy
  • ordinal
  • well-ordering

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'FUSIBLE NUMBERS AND PEANO ARITHMETIC'. Together they form a unique fingerprint.

Cite this