Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science, 1–13, 2021.

Distinguished Paper.

arXiv:2003.14342

- Download LICS version:
- Official LICS version from IEEE
- Download arXiv preprint:
- Talks by Gabriel Nivasch:
- Department of Mathematical Logic, Moscow State University, May 2020
- Prerecorded talk for LICS, May 2021

- OEIS entry for –log
_{2}(gap between n and the smallest fusible number larger than n) - Watch Brian Brushwood and friends and Dianna Cowern (Physics Girl) and Simone Giertz and Dan Finkel at TED-Ed discuss the original fuse puzzle
- Watch Ed Pegg Jr. measure 9/8 minutes with three 1-minute fuses

Abstract:

Inspired by a mathematical riddle involving fuses, we define thefusiblenumbers as follows: 0 is fusible, and wheneverxandyare 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 ℝ, 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: Lettingg(n) be the largest gap between consecutive fusible numbers greater than or equal ton, we have 1/g(n) ≥F_{ε₀}(n−c) for some constantc, whereF_{α}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 numbernthere exists a smallest fusible number larger thann.”

Publications - Jeff Erickson (jeffe@illinois.edu) 18 Jul 2021