Fusible numbers and Peano Arithmetic
2021
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| 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}} \geq {F_{{\varepsilon _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."
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
16
References
0
Citations
NaN
KQI