# Fusible numbers and Peano Arithmetic

Jeff Erickson<EMAIL_ADDRESS>University of Illinois. Gabriel Nivasch
<EMAIL_ADDRESS>Ariel University, Israel. Junyan Xu
<EMAIL_ADDRESS>
###### Abstract

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 $\varepsilon_{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,\infty)$, we have $g(n)^{-1}\geq F_{\varepsilon_{0}}(n-c)$ for
some constant $c$, where $F_{\alpha}$ 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.”

##  1 Introduction

A popular mathematical riddle goes as follows: We have available two fuses,
each of which will burn for one hour when lit. How can we use the two fuses to
measure 45 minutes? The fuses do not burn at a uniform rate, so we cannot
predict how much of a fuse will burn after any period of time smaller than an
hour.

The solution is to light both ends of one fuse simultaneously, and at the same
time light one end of the second fuse. The first fuse will burn after 30
minutes. At that moment we light the second end of the second fuse. The second
fuse will burn after an additional 15 minutes.

This riddle appears for example in Peter Winkler’s puzzle collection ([36] p.
2), where he attributes it to Carl Morris. It was also aired by Ray Magliozzi
in his _Car Talk_ radio show [19]. Frank Morgan called it an “old challenge”
in 1999 [20]. The puzzle (or variants using strings, shoelaces, or candles)
even became a standard interview question at some job interviews.

Based on this puzzle, we define the set $\mathcal{F}\subset\mathbb{Q}$ of
_fusible numbers_ as the set of all times that can be similarly measured by
using any number of fuses that burn for unit time. Formally, let us first
define

$x\sim y=(x+y+1)/2\qquad\text{for $x,y\in\mathbb{R}$.}$

If $|y-x|<1$, then the number $x\sim y$ (read “$x$ fuse $y$”) represents the
time at which a fuse burns, if its endpoints are lit at times $x$ and $y$,
respectively. Then $\mathcal{F}$ is defined recursively by $0\in\mathcal{F}$,
and $x\sim y\in\mathcal{F}$ whenever $x,y\in\mathcal{F}$ with $|y-x|<1$.

Note that we do not allow lighting a fuse at only one endpoint. This entails
no loss of generality, since the same effect can be obtained by lighting a
fuse at both endpoints simultaneously, and then lighting a second fuse at both
endpoints simultaneously. Hence, for example, $1\in\mathcal{F}$ since
$1=(0\sim 0)\sim(0\sim 0)$.

Every $z\in\mathcal{F}$ is a nonnegative dyadic rational, meaning a
nonnegative rational number whose denominator, when in lowest terms, is a
power of $2$.

There might be several ways of obtaining a given fusible number
$z\in\mathcal{F}$. For example, $3/4\sim 3/4=1/2\sim 1=5/4$.

Figure 1: Two different representations of the fusible number $5/4$.

We distinguish between fusible numbers, which belong to $\mathbb{Q}$, and
their _representations_. A representation is an algebraic expression using
“$0$” and “$\sim$” that gives rise to a fusible number. We can think of a
representation as a full binary tree (i.e. a binary tree each of whose nodes
has either zero or two children). Each leaf of the tree corresponds to a $0$,
and each internal node corresponds to a $\sim$ operation. Not every full
binary tree is a valid representation, however, because of the $|y-x|<1$
requirement. Hence, $5/4\in\mathcal{F}$ has the two representations

$\displaystyle T_{1}$ $\displaystyle=``(0\sim(0\sim 0))\sim(0\sim(0\sim 0))",$
$\displaystyle T_{2}$ $\displaystyle=``(0\sim 0)\sim((0\sim 0)\sim(0\sim
0))",$

whose corresponding trees are shown in Figure 1. (When necessary, we
distinguish representations from their corresponding fusible numbers by
enclosing representations in quotation marks.)

We will usually represent fusible numbers with lowercase letters and
representations with uppercase letters. The fusible number corresponding to a
representation $T$ is denoted by $v(T)$.

The _height_ $h(T)$ of a representation $T$ is the height of the corresponding
tree, i.e. the length of the longest path from the root to a leaf. Hence,
$h(``0")=0$ and $h(``0\sim 0")=1$. Both representations $T_{1}$, $T_{2}$ of
$5/4$ above have height $3$. The fusible number $11/8$ has a representation of
height $3$ (as $11/8=3/4\sim 1$), as well as one of height $4$ (as
$11/8=7/8\sim 7/8$ or $11/8=1/2\sim 5/4$).

We have $v(T)=\sum_{x}2^{-\mathrm{depth}(x)-1}$, where the sum ranges over all
internal nodes $x$ of $T$.

There are infinitely many fusible numbers smaller than $1$. In fact, the
fusible numbers smaller than $1$ are exactly those of the form $1-2^{-n}$
for111We denote $\mathbb{N}=\\{0,1,2,3,\ldots\\}$ and
$\mathbb{N}^{+}=\\{1,2,3,\ldots\\}$. $n\in\mathbb{N}$, given by
$1-2^{-(n+1)}=0\sim(1-2^{-n})$. This sequence converges to $1$. The number $1$
itself is also fusible, given by $1=1/2\sim 1/2$. Figure 2 shows part of the
set $\mathcal{F}$.

Figure 2: The fusible numbers and their corresponding ordinals.

###  1.1 Our results

As we show in this paper, the set $\mathcal{F}$ of fusible numbers is related
to ordinals, proof theory, computability theory, and fast-growing functions
(in fact, functions growing much faster than Ackermann’s function). In this
paper we prove the following:

######  Theorem 1.1.

The set $\mathcal{F}$ of fusible numbers, when ordered by the usual order
“$<$” on $\mathbb{R}$, is well-ordered, with order type $\varepsilon_{0}$.

######  Theorem 1.2.

The density of the fusible numbers along the real line grows very fast: Let
$g(n)$ be the largest gap between consecutive fusible numbers in
$\mathcal{F}\cap[n,\infty)$. Then $g(n)^{-1}\geq F_{\varepsilon_{0}}(n-7)$ for
all $n\geq 8$, where $F_{\alpha}$ denotes the fast-growing hierarchy.

#### Peano Arithmetic.

After Gödel published his incompleteness results, mathematicians became
interested in finding examples of _natural_ true statements that cannot be
proven in different formal theories. Peano Arithmetic is a nice example of a
simple theory, since it allows making “finitary” statements (statements
involving finite sets and structures built on the natural numbers) though not
“infinitary” statements (statements involving infinite sets). Despite its
limitations, a good portion of modern mathematics can be carried out in PA
(see e.g. Bovykin [3]).

There are several known natural true statements that can be formulated in PA,
but whose proofs require “infinitary” arguments and thus cannot be carried out
in PA. The most famous examples concern Goodstein sequences (Kirby and Paris
[16]), hydras (Kirby and Paris [16]), and a variant of Ramsey’s theorem (Paris
and Harrington [21]). Further examples include another variant of Ramsey’s
theorem involving regressive colorings (Kanamori and McAloon [15]); so-called
worms (Beklemishev [2], previously discovered by Hamano and Okada [13]); a
finite miniaturization of Kruskal’s tree theorem (Friedman, mentioned in
[28]); a finite miniaturization of the Robertson–Seymour graph minor theorem
(Friedman et al. [12]); and a finite miniaturization of a topological result
of Galvin and Prikry (Friedman et al. [11], also mentioned in [7]). See the
survey by Simpson [29].

There are many articles on the topic aimed at a wide readership. See for
example Sladek [31] and Smoryński [32, 33].

As we show in this paper, fusible numbers are a source of a few other true
statements that can be formulated but not proven in PA. Interestingly, these
statements are of a different flavor than the previously known ones:

######  Theorem 1.3.

  1. 1.

PA cannot prove the true statement “For every $n\in\mathbb{N}$ there exists a
smallest fusible number larger than $n$.”

  2. 2.

PA cannot prove the true statement “Every fusible number $x\in\mathcal{F}$ has
a maximum-height representation $h_{\mathrm{max}}(x)$.”

  3. 3.

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

#### Organization of this paper.

In Section 2 we derive some basic results about fusible numbers. Section 3
contains some necessary background on ordinals and fast-growing functions up
to $\varepsilon_{0}$. In Section 4 we prove the lower bound of Theorem 1.1, as
well as Theorem 1.2, by considering a subset of $\mathcal{F}$ which we call
_tame_ fusible numbers. In Section 5 we prove the upper bound of Theorem 1.1.
In Section 6 we give some background on Peano Arithmetic and prove Theorem
1.3. Section 7 presents a conjecture which, if true, would further clarify the
structure of $\mathcal{F}$. We conclude in Section 8.

Fusible numbers were first introduced by the first author at a talk in a
satellite Gathering 4 Gardner event at UIUC at around 2010, in which he
mentioned some of the above results. The slides of the talk are available at
[10]. The third author later on released a manuscript [37] with further
results, as well as some corrections to the claims in the slides. The present
paper builds upon these two unpublished works, also making some additional
minor corrections.

##  2 Basic results

In this section we derive some basic results about $\mathcal{F}$. In
particular, we give a simple proof that $\mathcal{F}$ is well-ordered. As a
corollary, we also derive an algorithm $\textsc{Succ}(x)$ for finding the
smallest fusible number larger than $x$, as well as an algorithm
$\textsc{IsFusible}(x)$ for deciding whether $x\in\mathcal{F}$ or not. The
well-orderedness of $\mathcal{F}$ implies that both algorithms terminate on
all inputs.

######  Observation 2.1.

Suppose $x\leq y$ with $|y-x|<1$, and let $z=x\sim y$. Then $x+1/2\leq z<x+1$
and $y<z$.

######  Lemma 2.2 (Window lemma).

Suppose $z\in\mathcal{F}$, and let $0<m\leq 1$. Then there exists a fusible
number in the window $I=(z+1-2m,z+1-m]$.

###### Proof.

Let $z_{n}=z+1-2^{-n}$ for $n\in\mathbb{N}$. Since $z_{0}=z$ and
$z_{n+1}=z\sim z_{n}$, we have $z_{n}\in\mathcal{F}$ for all $n$. One of these
numbers belongs to $I$. ∎

######  Lemma 2.3.

The set $\mathcal{F}$, ordered by the usual order “$<$” of real numbers, is
well-ordered, meaning every nonempty subset of $\mathcal{F}$ has a smallest
element.

###### Proof.

Suppose for a contradiction that $\mathcal{F}$ is not well-ordered, so there
exist nonempty subsets $\mathcal{G}\subseteq\mathcal{F}$ without a smallest
element. Every such subset contains an infinite descending sequence
$S=(z_{1}>z_{2}>z_{3}>\cdots)$.222To avoid relying on the axiom of choice, we
can choose each $z_{n}$ canonically from $z_{n-1}$ in some way. For example,
we could let $z_{n}$ be the element of $\mathcal{G}\cap(0,z_{n-1})$ with
smallest denominator, and from among them, the one with the smallest
numerator. Each infinite descending sequence $S$ of $\mathcal{F}$ converges to
some limit $\lim S\in\mathbb{R}$. Let $\mathcal{L}$ be the set of all such
limits. Then $\mathcal{L}$ must have a smallest element $\ell_{0}$, since the
limit of an infinite descending sequence in $\mathcal{L}$ must also be in
$\mathcal{L}$. So let $S_{0}=(z_{1}>z_{2}>z_{3}>\cdots)$ be an infinite
descending sequence in $\mathcal{F}$ converging to $\ell_{0}$.

Write $z_{i}=x_{i}\sim y_{i}$ with $x_{i}\leq y_{i}$. We can assume without
loss of generality (by applying the infinite Ramsey theorem and taking a
subsequence of $S_{0}$, if necessary) that the sequence $\\{x_{i}\\}$ is
either ascending, descending, or constant. But by Observation 2.1 and the
minimality of $\ell_{0}$, the sequence $\\{x_{i}\\}$ cannot be descending.
Hence, $\\{x_{i}\\}$ is either constant or ascending, and therefore
$\\{y_{i}\\}$ is descending. Let $y^{*}$ be such that $x_{1}\sim
y^{*}=\ell_{0}$. By Observation 2.1 we have $y^{*}<\ell_{0}$, and by the
continuity of “$\sim$” and the fact that $x_{i}\geq x_{1}$ for all $i$, we
have $\lim y_{i}\leq y^{*}$. This contradicts the minimality of $\ell_{0}$. ∎

Given a well-ordered subset $\mathcal{G}\subset\mathbb{R}$ (with respect to
the usual order “$<$”), let $\operatorname{ord}(\mathcal{G})$ be the ordinal
corresponding to $\mathcal{G}$.333Note that $\mathcal{G}$ must be countable in
order to be well-ordered, since after every element of $\mathcal{G}$ there
must be an open interval disjoint from $\mathcal{G}$, which contains a
rational number. Conversely, every countable ordinal $\alpha$ can be realized
by some $\mathcal{G}\subset\mathbb{R}$. Lemma 2.3 raises the problem of
identifying the ordinal $\operatorname{ord}(\mathcal{F})$. As mentioned, we
will prove that $\operatorname{ord}(\mathcal{F})=\varepsilon_{0}$.

Given $r\in\mathbb{R}$, we will denote
$\operatorname{ord}(\mathcal{F}\cap[0,r))$ by $\operatorname{ord}(r)$.
Conversely, given a countable ordinal
$\alpha<\operatorname{ord}(\mathcal{F})$, let $\operatorname{fus}(\alpha)$ be
the unique element $z\in\mathcal{F}$ such that $\operatorname{ord}(z)=\alpha$.
So for example, $\operatorname{ord}(0)=0$, $\operatorname{ord}(1/2)=1$,
$\operatorname{ord}(3/4)=2$, $\operatorname{ord}(1)=\omega$, and
$\operatorname{ord}(9/8)=\omega+1$. Conversely $\operatorname{fus}(\omega)=1$
and $\operatorname{fus}(\omega+1)=9/8$.

######  Lemma 2.4.

$\mathcal{F}$ is closed, meaning if $z_{1}<z_{2}<z_{3}<\cdots$ is a sequence
in $\mathcal{F}$ converging to $z\in\mathbb{R}$, then $z\in\mathcal{F}$.

###### Proof.

Let $\mathcal{L}$ be the set of all “missing limits” in $\mathcal{F}$, i.e.
the set of all real numbers $x\notin\mathcal{F}$ for which there exists an
ascending sequence in $\mathcal{F}$ converging to $x$. Assuming for a
contradiction that $\mathcal{L}\neq\emptyset$, let $\ell=\inf\mathcal{L}$. We
must have $\ell\in\mathcal{L}$, because otherwise we would obtain a
contradiction to Lemma 2.3.

Write $z_{i}=x_{i}\sim y_{i}$. As before, we can assume without loss of
generality that $\\{x_{i}\\}$ and $\\{y_{i}\\}$ are nondecreasing. Let $x=\lim
x_{i}$ and $y=\lim y_{i}$. By the continuity of “$\sim$”, we have $\ell=x\sim
y$. By Observation 2.1 we have $\ell-1\leq x\leq\ell-1/2$. Hence, by the
minimality of $\ell$, we must have $x\in\mathcal{F}$. If $x>\ell-1$ then
$y<\ell$, so by the minimality of $\ell$ we also have $y\in\mathcal{F}$,
implying that $\ell\in\mathcal{F}$. And if $x=\ell-1$ (and so $y=\ell$), then
$\ell=(x\sim x)\sim(x\sim x)$. ∎

Hence, $\mathcal{F}$ contains two types of nonzero fusible numbers:
_successors_ and _limits_. They correspond exactly to the successor and limit
nonzero ordinals below $\operatorname{ord}(\mathcal{F})$.

Given a dyadic fraction $r=p/q$ with $p$ odd and $q=2^{n}$, we denote $e(r)=n$
and call it the _exponent_ of $r$.

######  Observation 2.5.

Let $r_{1}=(p-1)/q$ and $r_{2}=p/q$ be two dyadic fractions (not necessarily
in lowest terms) with $q=2^{n}$. Then every dyadic fraction $r_{1}<r<r_{2}$
satisfies $e(r)>n$.

######  Observation 2.6.

Let $x,y,z$ be dyadic fractions with $z=x\sim y$, and suppose that $1\leq
e(x)\leq e(y)$. If $e(x)<e(y)$ then $e(z)=e(y)+1$. And if $e(x)=e(y)$ then
$e(z)\leq e(x)$.

######  Corollary 2.7.

For every representation $T$ of a fusible number $z=v(T)$, we have $h(T)\geq
e(z)$.

######  Lemma 2.8.

Let $T$ be a representation of $z=v(T)$ with height $h(T)=n$. Then
$z^{\prime}=z+2^{-(n+1)}\in\mathcal{F}$, and it has a representation of height
$n+1$.

###### Proof.

By induction on $n$. If $n=0$ then $T=``0"$ and $z=0$, and then
$z^{\prime}=1/2=0\sim 0$. Now suppose the claim is true for height $n-1$, and
let $T=``T_{1}\sim T_{2}"$ be a representation of height $n$. Then
$h(T_{1}),h(T_{2})\leq n-1$, with equality in at least one case. Say
$h(T_{1})=n-1$. Let $x=v(T_{1})$ and $y=v(T_{2})$. We have $|y-x|<1$ and
$e(x),e(y)\leq n-1$, so actually $|y-x|\leq 1-2^{-(n-1)}$. By the induction
hypothesis, there exists a representation $T^{\prime}$ of
$x^{\prime}=x+2^{-n}$ with $h(T^{\prime})=n$. Furthermore, we still have
$|y-x^{\prime}|<1$, so $``T^{\prime}\sim T_{2}"$ is valid, and it represents
$z^{\prime}=z+2^{-(n+1)}$. ∎

######  Lemma 2.9.

Let $T$ be a representation of $z=v(T)$ with height $h(T)=n>0$. Then
$z^{\prime}=z-2^{-n}\in\mathcal{F}$, and it has a representation of height at
least $n-1$, as well as a representation of height at most $n$.

###### Proof.

Again by induction on $n$. If $n=1$ then $T=``0\sim 0"$ and $z=1/2$, and then
$z^{\prime}=0$. Now suppose the claim is true for height $n-1$, and let
$T=``T_{1}\sim T_{2}"$ be a representation of height $n$. Then
$h(T_{1}),h(T_{2})\leq n-1$, with equality in at least one case. Say
$h(T_{1})=n-1$. Let $x=v(T_{1})$ and $y=v(T_{2})$. We have $|y-x|<1$ and
$e(x),e(y)\leq n-1$, so actually $|y-x|\leq 1-2^{-(n-1)}$. By the induction
hypothesis, $x^{\prime}=x-2^{-(n-1)}$ has a representation $T^{\prime}$ with
$h(T^{\prime})\geq n-2$, as well as a representation $T^{\prime\prime}$ with
$h(T^{\prime\prime})\leq n-1$. If we still have $|y-x^{\prime}|<1$ then
$``T^{\prime}\sim T_{2}"$ and $``T^{\prime\prime}\sim T_{2}"$ are valid and we
are done. Otherwise, we have $y-x^{\prime}=1$, and so
$z^{\prime}=z-2^{-n}=y=x^{\prime}+1$, so $T_{2}$ and $``(T^{\prime}\sim
T^{\prime})\sim(T^{\prime}\sim T^{\prime})"$ are two representations of
$z^{\prime}$. The first one has height at most $n-1$, and the second one has
height at least $n$. ∎

Lemma 2.8 implies that every fusible number has a maximum-height
representation, since otherwise we would obtain an infinite decreasing
sequence in $\mathcal{F}$. Given $z\in\mathcal{F}$, denote by
$h_{\mathrm{max}}(z)$ the maximum of $h(T)$ over all representations $T$ with
$v(T)=z$.

######  Lemma 2.10.

Let $z\in\mathcal{F}$ be a fusible number satisfying
$h_{\mathrm{max}}(z)>e(z)$. Then $z$ is a limit.

###### Proof.

Assuming for a contradiction that $z$ is a successor, let
$z^{\prime}\in\mathcal{F}$ be the predecessor of $z$. Let
$n=h_{\mathrm{max}}(z)$. By Lemma 2.9 we have
$z^{\prime\prime}=z-2^{-n}\in\mathcal{F}$. Hence, $z^{\prime\prime}\leq
z^{\prime}<z$. Since $e(z^{\prime\prime})=n$, by Observation 2.5 we have
$e(z^{\prime})\geq n$ as well. Hence, by Lemma 2.8 we have
$z^{\prime\prime\prime}=z^{\prime}+2^{-(n+1)}\in\mathcal{F}$, and by
Observation 2.5 we still have $z^{\prime\prime\prime}<z$. This contradicts the
fact that $z^{\prime}$ is the predecessor of $z$. ∎

By the continuity of “$\sim$”, if $z=x\sim y$ where $x,y,z\in\mathcal{F}$ and
one of $x$, $y$ is a limit, then $z$ is also a limit. The converse is also
true:

######  Lemma 2.11.

Let $z>1$ be a limit fusible number. Then $z$ can be written as $z=x\sim y$
where $x,y\in\mathcal{F}$ and at least one of $x$, $y$ is a limit.444Lemmas
2.11, 2.15, 2.16 and Corollary 2.17 are not used in the rest of this paper.

###### Proof.

Let $\\{z_{i}\\}$ be an increasing sequence converging to $z$. Let
$z_{i}=x_{i}\sim y_{i}$, and assume without loss of generality that each of
$\\{x_{i}\\}$, $\\{y_{i}\\}$ is either constant or increasing. At least one of
these sequences must be increasing. Let $x=\lim x_{i}$ and $y=\lim y_{i}$. We
have $x,y\in\mathcal{F}$ by Lemma 2.4. If $x,y<z$, then $z=x\sim y$, and we
are done. Otherwise, suppose for example that $x=z-1$ and $y=z$. Then,
$z=(x\sim x)\sim(x\sim x)$. In this case, $x\sim x$ is a limit by Observation
2.6 and Lemma 2.10, and we are done again. ∎

Since $\mathcal{F}$ is well-ordered, every fusible number has a successor.
Denote the successor of $z\in\mathcal{F}$ by $s(z)$.

######  Lemma 2.12.

Let $z\in\mathcal{F}$ be a fusible number with $h_{\mathrm{max}}(z)=n$. Then
its successor is $s(z)=z+2^{-(n+1)}$, and its maximum height is
$h_{\mathrm{max}}(s(z))=n+1$.

###### Proof.

We already know by Lemma 2.8 that $z^{\prime}=z+2^{-(n+1)}\in\mathcal{F}$. By
Corollary 2.7 we have $e(z)\leq n$, so $e(z^{\prime})=n+1$. Suppose for a
contradiction that there exist fusible numbers
$z^{\prime\prime}\in(z,z^{\prime})$. Let $m$ be the smallest height of a
representation of such a fusible number. Choose
$z^{\prime\prime}\in\mathcal{F}\cap(z,z^{\prime})$ minimally from among those
having a representation $T$ of height $m$. By Corollary 2.7 and Observation
2.5 we have $m\geq e(z^{\prime\prime})\geq n+2$. Hence, by Lemma 2.9 and
Observation 2.5, there exists
$z^{\prime\prime\prime}\in\mathcal{F}\cap[z,z^{\prime\prime})$ with a
representation of height at least $n+1$ and a representation of height at most
$m$. If $z^{\prime\prime\prime}>z$ this contradicts the minimality of $m$ or
$z^{\prime\prime}$, whereas if $z^{\prime\prime\prime}=z$ this contradicts the
assumption $h_{\mathrm{max}}(z)=n$. Hence, we must have
$\mathcal{F}\cap(z,z^{\prime})=\emptyset$, so $s(z)=z^{\prime}$. If
$h_{\mathrm{max}}(z^{\prime})$ were larger than $n+1$, then again applying
Lemma 2.9 on $z^{\prime}$ would lead to a contradiction. ∎

######  Corollary 2.13.

Let $z\in\mathcal{F}$ have maximum height $h_{\mathrm{max}}(z)=n$. Then the
next $\omega$ fusible numbers following $z$ are $z+2^{-n}-2^{-(n+m)}$ for
$m=1,2,3,\ldots$.

######  Lemma 2.14.

Let $z=p/q\in\mathcal{F}$ be a successor fusible number, with $p$ odd. Then
its predecessor is $z^{\prime}=(p-1)/q$.

###### Proof.

By Lemma 2.10 we have $h_{\mathrm{max}}(z)=e(z)=n$ where $q=2^{n}$. Hence, by
Lemma 2.9 we know that $z^{\prime}\in\mathcal{F}$. Let $z^{\prime\prime}$ be
the predecessor of $z$, and suppose for a contradiction that
$z^{\prime}<z^{\prime\prime}<z$. Then Observation 2.5 together with Lemma 2.12
yields a contradiction. ∎

######  Lemma 2.15.

Let $z\in\mathcal{F}$ be a limit, and let $m=e(z)$. Then
$z_{n}=z-2^{-(m+n)}\in\mathcal{F}$ for all $n\in\mathbb{N}$.

###### Proof.

Given $n$, suppose for a contradiction that $z_{n}\notin\mathcal{F}$. Since
$\mathcal{F}$ is closed, there exists a maximum element
$z^{\prime}\in\mathcal{F}\cap[0,z_{n})$. Let $z^{\prime\prime}=s(z^{\prime})$.
Since $z$ is a limit, we must have $z_{n}<z^{\prime\prime}<z$. By Observation
2.5 on $z_{n}$ and $z$, we have $e(z^{\prime\prime})>e(z_{n})$. But
$z^{\prime\prime}$ is a successor ordinal, so by Lemma 2.14 and Observation
2.5 on $z^{\prime}$ and $z^{\prime\prime}$, we have
$e(z_{n})>e(z^{\prime\prime})$. Contradiction. ∎

Finally, we prove the converse of Lemma 2.10.

######  Lemma 2.16.

Suppose $z\in\mathcal{F}$ is a limit. Then $h_{\mathrm{max}}(z)>e(z)$.

###### Proof.

Let $n=e(z)$. In light of Corollary 2.7 and Lemma 2.12, it is enough to prove
the existence of a fusible number $z^{\prime}\in(z,z+2^{-(n+1)})$. If $z=1$
then we can take $z^{\prime}=9/8\in\mathcal{F}$ and we are done. Otherwise, by
Lemma 2.11, we have $z=x\sim y$ where $y$ is a limit. Denote $n_{1}=e(x)$,
$n_{2}=e(y)$.

Suppose first that $n_{1}\leq n_{2}$. Then $n\leq n_{2}+1$. Since $|y-x|<1$,
we actually have $|y-x|\leq 1-2^{-n_{2}}$. By structural induction, we can
assume that there exists a fusible number $y^{\prime}\in(y,y+2^{-(n_{2}+1)})$.
Hence, $z^{\prime}=x\sim y^{\prime}$ is valid, and it is smaller than
$z+2^{-(n_{2}+2)}\leq z+2^{-(n+1)}$, as desired.

Otherwise, we have $n_{1}>n_{2}$ and $x$ is a successor fusible number. In
this case we have $n=n_{1}+1$, and $|y-x|\leq 1-2^{-n_{1}}$. By Lemma 2.10 we
have $h_{\mathrm{max}}(x)=n_{1}$, so By Lemma 2.8 we have
$x^{\prime}=x+2^{-(n_{1}+1)}\in\mathcal{F}$. Furthermore, by Lemma 2.15 we
have $y^{\prime}=y-2^{-(n_{1}+2)}\in\mathcal{F}$. Hence,
$z^{\prime}=x^{\prime}\sim y^{\prime}$ is valid, and it equals
$z+2^{-(n_{1}+3)}=z+2^{-(n+2)}$. ∎

######  Corollary 2.17.

Let $z\in\mathcal{F}$. Then $z$ is a limit if and only if
$h_{\mathrm{max}}(z)>e(z)$.

###  2.1 Algorithms

Algorithm 1 Finds $\min(\mathcal{F}\cap(r,\infty))$

procedure Succ($r$)

if $r<0$ then

return $0$

$min\leftarrow\infty$

5: $y\leftarrow r$

repeat

$x\leftarrow$Succ($2r-y-1$)

$y\leftarrow$Succ($2r-x-1$)

if $x\sim y<min$ then

10: $min\leftarrow x\sim y$

$y\leftarrow y-1/$Denominator($y$)

until $y\leq r-1/2$

return $min$

Algorithm 2 Decides whether $r\in\mathcal{F}$

procedure IsFusible($r$)

if $r$ is not a dyadic rational then

return false

return $r=$WeakSucc($r$)

Algorithm 3 Finds $\min(\mathcal{F}\cap[r,\infty))$

procedure WeakSucc($r$)

if $r\leq 0$ then

return $0$

$min\leftarrow\infty$

5: $y\leftarrow r$

repeat

$x\leftarrow$WeakSucc($2r-y-1$)

if $x=2r-y-1$ then

return $r$

10: $y\leftarrow$WeakSucc($2r-x-1$)

if $y=2r-x-1$ then

return $r$

if $x\sim y<min$ then

$min\leftarrow x\sim y$

15: $y\leftarrow y-1/$Denominator($y$)

until $y<r-1/2$

return $min$

Table 1: Some algorithms for fusible numbers.

Suppose we are given $z\in\mathcal{F}$ and we want to find $s(z)$, or we want
to decide whether a given number $z\in\mathbb{Q}$ belongs to $\mathcal{F}$. It
is not clear a priori that these problems are computable, since there are
usually infinitely many fusible numbers smaller than $z$, all of which might
potentially be useful in building $z$ or fusible numbers larger than $z$.

Table 1 shows a recursive algorithm $\textsc{Succ}(r)$ for the slightly more
general problem of, given $r\in\mathbb{Q}$, finding the smallest fusible
number $z$ that is strictly larger than $r$. It also shows a decision
algorithm IsFusible, which relies on WeakSucc, a modification of Succ.

######  Lemma 2.18.

Algorithms Succ, WeakSucc, and IsFusible terminate on all inputs and return
the correct output.

###### Proof.

Consider algorithm Succ. Given $r\in\mathbb{Q}$, let $z=s(r)$ be the smallest
fusible number larger than $r$. If $r<1/2$ the claim is easy to verify, so
assume $r\geq 1/2$. We must have $z=x\sim y$ for some $x,y\in\mathcal{F}$
satisfying $r-1<x\leq y\leq r$ and $y>r-1/2$. We will show that the algorithm
tries all the relevant candidates for $x,y$ by increasing value of $x$ and
decreasing value of $y$, and that there is a finite number of such candidates.

The following invariant is true at the beginning of the loop (line $6$): The
variable $y$ holds either $r$ or a fusible number smaller than $r$, and if
$y<r$ then the variable $\mathit{min}$ holds the smallest fusible number $z>r$
of the form $z=x^{\prime}\sim y^{\prime}$ with $y<y^{\prime}\leq r$. Then,
line $7$ increases $x$ to the next possible candidate, and line $8$ sets $y$
to the fusible number that minimizes $z^{\prime}=x\sim y$ subject to
$z^{\prime}>r$.

Line $8$ never sets $y$ larger than its previous value $y_{\mathrm{old}}$: We
have $2r-x-1<2r-(2r-y_{\mathrm{old}}-1)-1=y_{\mathrm{old}}$, so if
$y_{\mathrm{old}}<r$ then $y_{\mathrm{old}}$ is fusible, and hence (assuming
that the recursive call in line $8$ returns the correct value) line 8 sets $y$
to $s(2r-x-1)\leq y_{\mathrm{old}}$. Further, as we prove below, the recursive
call on line $8$ never returns a value larger than $r$.

In addition, by Lemma 2.14, line $11$ replaces the successor fusible number
$y$ by its predecessor, so the algorithm does not miss any candidate.

We still have to prove that the recursive calls on lines $7$, $8$ return the
correct values $s(2r-y-1)$, $s(2r-x-1)$. This will follow by ordinal induction
once we show that these values are smaller than $z$. For this, first note that
at the beginning of the loop we always have $y>r-1/2$, which implies
$2r-y-1<r-1/2$. Since every interval of length $1/2$ contains a fusible
number, we have $s(2r-y-1)<r$. Hence, by ordinal induction line $7$ indeed
sets $x$ to $s(2r-y-1)$.

Next, recall that at the beginning of the loop we always have $y\leq r$.
Hence, after line $7$ we have $x>2r-y-1\geq r-1$. Denote $m=x+1-r$, so
$0<m<1$. By the window lemma (Lemma 2.2) there exists a fusible number in the
interval $(x+1-2m,x+1-m]$. But $x+1-2m=2r-x-1$ and $x+1-m=r$. Hence, by
ordinal induction line $8$ correctly sets $y$ to $s(2r-x-1)$, which is at most
$r$.

Finally, the loop must end after a finite number of iterations, or else we
would have an infinite descending sequence of fusible numbers.

The proof for the other two algorithms is similar. Lines $2$, $3$ in IsFusible
are only for efficiency purposes. ∎

In algorithm Succ, the first candidate $x\sim y$ is not always the best one.
Consider for example $r=33/16\in\mathcal{F}$. Its successor is
$r+1/4096=8449/4096=19/16\sim 3969/2048$, but the first candidate Succ tries
is $r+1/2048=9/8\sim 2049/1024$.

#### Running time.

We will prove below that, already for $r\in\mathbb{N}$, algorithm
$\textsc{Succ}(r)$ has an incredibly large running time in the size of the
input. On the other hand, we have not been able to rule out the possibility
that algorithms WeakSucc and IsFusible run in polynomial time in the size of
the input. These two latter algorithms terminate very quickly when
$r\in\mathbb{N}$.

##  3 Background on ordinals

The ordinal $\varepsilon_{0}$ is the limit of
$\omega,\omega^{\omega},\omega^{\omega^{\omega}},\ldots$. Each ordinal
$\alpha<\varepsilon_{0}$ can be uniquely written in _Cantor Normal Form_ (CNF)
as $\alpha=\omega^{\alpha_{1}}+\cdots+\omega^{\alpha_{k}}$, for some $k\geq 0$
and some ordinals $\alpha_{1},\ldots,\alpha_{k}$ satisfying
$\alpha>\alpha_{1}\geq\alpha_{2}\geq\cdots\geq\alpha_{k}$. Alternatively,
$\alpha$ can be uniquely written in _weighted CNF_ as
$\alpha=\omega^{\alpha_{1}}n_{1}+\cdots+\omega^{\alpha_{k}}n_{k}$, for some
$k\geq 0$, some ordinals $\alpha>\alpha_{1}>\cdots>\alpha_{k}$, and some
positive integers $n_{1},\ldots,n_{k}$.

Given a limit ordinal $\alpha<\varepsilon_{0}$, the _canonical sequence_
$[\alpha]_{n}$ for $n\geq 1$ is a sequence that converges to $\alpha$. It is
defined as follows: For limit $\beta<\omega^{\alpha+1}$ we let
$[\omega^{\alpha}+\beta]_{n}=\omega^{\alpha}+[\beta]_{n}$. We let
$[\omega^{\alpha+1}]_{n}=\omega^{\alpha}n$. And for limit $\alpha$ we let
$[\omega^{\alpha}]_{n}=\omega^{[\alpha]_{n}}$. For example,
$[\omega^{\omega+2}7]_{5}=\omega^{\omega+2}6+\omega^{\omega+1}5$.

Let us define for successor ordinals $[\alpha+1]_{n}=\alpha$, independently of
$n$. A _canonical descent_ is a sequence
$\alpha_{1}>\alpha_{2}>\cdots>\alpha_{k}$ in which
$\alpha_{i+1}=[\alpha_{i}]_{n_{i}}$ for each $i$, for some parameters $n_{i}$.
We call the parameters $n_{i}$ the _descent parameters_.

For each pair of ordinals $\beta<\alpha<\varepsilon_{0}$ there exists a
canonical descent starting at $\alpha$ and ending at $\beta$. If there exists
such a descent in which all the descent parameters are bounded by $k$, then we
write $\alpha\mathrel{\to_{k}}\beta$. Given $\alpha,\beta$, the shortest
canonical descent from $\alpha$ to $\beta$ can be found greedily, by choosing
at each step the smallest descent parameter that gives an ordinal at least
$\beta$. This is implied by the following lemma:

######  Lemma 3.1 (Bachmann property [1, 24]).

Let $\alpha,\beta<\varepsilon_{0}$ be limit ordinals satisfying
$[\alpha]_{n}<\beta<\alpha$. Then $[\beta]_{1}\geq[\alpha]_{n}$ and
$[\beta]_{2}>[\alpha]_{n}+1$.

###### Proof.

Without loss of generality we can assume $\alpha$ consists of a single term.
Then we use induction on the height of $\alpha$. ∎

Hence, if $[\alpha]_{n}<\beta<\alpha$ (in particular, if $\beta=[\alpha]_{m}$
for some $m>n$), then every canonical descent from $\beta$ to $0$ must contain
$[\alpha]_{n}$. Furthermore, if all the descent parameters are at least $2$,
then the canonical descent must contain $[\alpha]_{n}+1$ as well.

We will need the following lemma:

######  Lemma 3.2 (Hiccup lemma).

Let $\alpha,\beta<\varepsilon_{0}$ be limit ordinals satisfying
$\beta<\omega^{\alpha}$, and let $k\geq 2$. If $\beta=\omega^{[\alpha]_{n}+1}$
then we have
$\bigl{[}\omega^{[\alpha]_{n}}+\beta\bigr{]}_{k}=\omega^{[\alpha]_{n}}+[\beta]_{k-1}$.555Note
that if $\beta\geq\omega^{[\alpha]_{n}+1}$ then
$\omega^{[\alpha]_{n}}+\beta=\beta$. For every other $\beta$ we have
$\bigl{[}\omega^{[\alpha]_{n}}+\beta\bigr{]}_{k}=\omega^{[\alpha]_{n}}+[\beta]_{k}$.

###### Proof.

If $\beta<\omega^{[\alpha]_{n}+1}$ then the expression
“$\omega^{[\alpha]_{n}}+\beta$” is in CNF, so the claim follows by the
definition of the canonical sequence. If $\beta=\omega^{[\alpha]_{n}+1}$ the
claim is immediate. Hence, suppose $\beta>\omega^{[\alpha]_{n}+1}$, so
$\omega^{[\alpha]_{n}}+\beta=\beta$. If $\beta$ consists of at least two terms
then the first term is unchanged in $[\beta]_{k}$, and the claim follows.
Finally, if $\beta=\omega^{\gamma}$ for some $[\alpha]_{n}<\gamma<\alpha$ then
we consider separately the cases where $\gamma$ is a successor or a limit
ordinal. We make use of the Bachmann property (Lemma 3.1) in the latter case,
using the fact that $k\geq 2$. ∎

Given $n\geq 0$, denote $\tau_{n}=\omega^{\omega^{\cdots^{\omega}}}$ with
height $n$. In other words, $\tau_{0}=1$, and $\tau_{n+1}=\omega^{\tau_{n}}$
for $n\geq 0$.

#### Left-subtraction of ordinals.

Given $\alpha\geq\beta$, define $-\beta+\alpha$ as the unique ordinal $\gamma$
such that $\beta+\gamma=\alpha$. In other words,
$-\beta+\alpha=\operatorname{ord}(\alpha\setminus\beta)$ under von Neumann’s
definition of ordinals. For example, $-(\omega^{\omega}+\omega^{3}\cdot
2)+(\omega^{\omega}+\omega^{4})=\omega^{4}$, and $-5+\omega=\omega$. In
general, for every $\alpha<\omega^{\beta}$ we have
$-\alpha+\omega^{\beta}=\omega^{\beta}$. Left-subtraction satisfies
$-(\beta+\gamma)+\alpha=-\gamma+(-\beta+\alpha)$; and
$-\beta+(\gamma+\alpha)=(-\beta+\gamma)+\alpha$ whenever $\gamma\geq\beta$.

###  3.1 Natural sum and product

Let $\alpha=\omega^{\alpha_{1}}+\cdots+\omega^{\alpha_{n}}$ and
$\beta=\omega^{\beta_{1}}+\cdots+\omega^{\beta_{m}}$ be two ordinals in Cantor
normal form, with $m,n\geq 0$ and $\alpha_{1}\geq\cdots\geq\alpha_{n}$ and
$\beta_{1}\geq\cdots\geq\beta_{m}$. Then their _natural sum_ is given by

$\alpha\oplus\beta=\omega^{\gamma_{1}}+\cdots+\omega^{\gamma_{n+m}},$

where $\gamma_{1},\ldots,\gamma_{n+m}$ are
$\alpha_{1},\ldots,\alpha_{n},\beta_{1},\ldots,\beta_{m}$ sorted in
nonincreasing order. For example, if $\alpha=\omega^{3}+\omega$ and
$\beta=\omega^{4}+\omega+1$, then
$\alpha\oplus\beta=\omega^{4}+\omega^{3}+\omega 2+1$ (whereas
$\alpha+\beta=\omega^{4}+\omega+1$ and
$\beta+\alpha=\omega^{4}+\omega^{3}+\omega$). The natural sum is commutative
and associative.

Let $A$ and $B$ be two disjoint well-ordered sets, with respective well-orders
$\mathrel{<_{A}}$ and $\mathrel{<_{B}}$. Define the partial order $\prec$ on
$C=A\cup B$ by $x\prec y$ whenever $x,y\in A$ with $x\mathrel{<_{A}}y$, or
$x,y\in B$ with $x\mathrel{<_{B}}y$. Let $\alpha$ and $\beta$ be the order
types of $A$ and $B$, respectively. There might be several ways of
_linearizing_ the partial order of $C$, i.e. extending it into a total order.
The largest possible order type of such a linearization equals
$\alpha\oplus\beta$ (de Jongh and Parikh [8]).

Let $\alpha=\omega^{\alpha_{1}}+\cdots+\omega^{\alpha_{n}}$ and
$\beta=\omega^{\beta_{1}}+\cdots+\omega^{\beta_{m}}$ as before. Then their
_natural product_ is given by

$\alpha\otimes\beta=\bigoplus_{i,j}\omega^{\alpha_{i}\oplus\beta_{j}}.$

The natural product is commutative and associative, and it distributes over
the natural sum. If $\alpha>\beta$ then
$\gamma\oplus\alpha>\gamma\oplus\beta$, and if $\gamma>0$ then also
$\gamma\otimes\alpha>\gamma\otimes\beta$.

Let $A$ and $B$ be well-ordered sets, with respective well-orders
$\mathrel{<_{A}}$ and $\mathrel{<_{B}}$. Define the partial order $\prec$ on
$C=A\times B$ by $(a_{1},b_{1})\prec(a_{2},b_{2})$ whenever both
$a_{1}\mathrel{<_{A}}a_{2}$ and $b_{1}\mathrel{<_{B}}b_{2}$. Then the largest
possible order type of a linearization of $C$ equals $\alpha\otimes\beta$ [8].

###  3.2 The fast-growing hierarchy

Here we largely follow Buchholz and Wainer [5]. The _fast-growing hierarchy_
is a family of functions $F_{\alpha}:\mathbb{N}^{+}\to\mathbb{N}^{+}$ indexed
by ordinals $\alpha$, where $\alpha$ ranges up to some large countable
ordinal. It has the property that for $\beta>\alpha$, the function
$F_{\beta}(n)$ grows much faster than $F_{\alpha}(n)$. In fact, for every
fixed $k$, the function $F_{\beta}(n)$ eventually overtakes
$F_{\alpha}^{(k)}(n)$, where $f^{(k)}=f\circ f\circ\cdots\circ f$ denotes the
$k$-fold composition of the function $f$.

The hierarchy up to $\varepsilon_{0}$ is known as the _Wainer hierarchy_. It
is defined as follows:

$\displaystyle F_{0}(n)$ $\displaystyle=n+1,$ $\displaystyle F_{\alpha+1}(n)$
$\displaystyle=F_{\alpha}^{(n)}(n),$ $\displaystyle F_{\alpha}(n)$
$\displaystyle=F_{[\alpha]_{n}}(n),\qquad\text{for limit
$\alpha<\varepsilon_{0}$.}$

The well-known _Ackermann function_ $A(n)$ corresponds to $F_{\omega}$ in this
hierarchy, in the sense that $F_{\omega}(n-c)\leq A(n)\leq F_{\omega}(n+c)$
for some constant $c$.

The fast-growing hierarchy is related to the _Hardy hierarchy_ , which is
defined as follows:

$\displaystyle H_{0}(n)$ $\displaystyle=n,$ $\displaystyle H_{\alpha+1}(n)$
$\displaystyle=H_{\alpha}(n+1),$ $\displaystyle H_{\alpha}(n)$
$\displaystyle=H_{[\alpha]_{n}}(n),\qquad\text{for limit
$\alpha<\varepsilon_{0}$.}$

######  Lemma 3.3.

For every $\alpha<\varepsilon_{0}$ and every $n$ we have
$F_{\alpha}(n)=H_{\omega^{\alpha}}(n)$.

###### Proof.

It follows by ordinal induction on $\beta$ that for every
$\alpha=\omega^{\alpha_{1}}+\cdots+\omega^{\alpha_{k}}$ in CNF and every
$\beta<\omega^{\alpha_{k}+1}$, we have
$H_{\alpha+\beta}(n)=H_{\alpha}(H_{\beta}(n))$. Then the claim follows by
ordinal induction on $\alpha$. ∎

######  Lemma 3.4.

Let $\alpha<\varepsilon_{0}$. Then:

  * •

$H_{\alpha}$ is strictly increasing.

  * •

Suppose $\alpha\mathrel{\to_{k}}\beta$. Then $H_{\alpha}(n)>H_{\beta}(n)$ for
every $n>k$.

  * •

The same properties hold for the functions $F_{\alpha}$.

###### Proof.

The first two claims are proven simultaneously by ordinal induction on
$\alpha$. Then the third claim follows by Lemma 3.3. ∎

Finally, we top the hierarchy by defining
$F_{\varepsilon_{0}}(n)=F_{\tau_{n}}(n)$. Hence, $F_{\varepsilon_{0}}(n)$
eventually overtakes $F_{\alpha}(n)$ for every $\alpha<\varepsilon_{0}$.

######  Lemma 3.5.

Let $z(n)=H_{\tau_{n}}(2)$. Then $z(n)>F_{\varepsilon_{0}}(n-2)$ for every
$n\geq 3$.

###### Proof.

We first observe the following: Suppose $\alpha\mathrel{\to_{2}}\beta$, and
let $r$ be the number of successor ordinals in the canonical descent from
$\alpha$ to $\beta$ always using descent parameter $2$. Then
$H_{\alpha}(n)\geq H_{\beta}(n+r)$ for every $n\geq 2$. Indeed, this follows
by repeated application of the definition of $H$ and Lemma 3.4.

Now consider the particular case $\alpha=\tau_{n+1}$, $\beta=\tau_{n}$. In
this case, the canonical descent from $\alpha$ to $\beta$ contains at least
$n$ successor ordinals: Consider the ordinals $\gamma_{i}=\delta_{i,i-1}$ for
$1\leq i\leq n$, where $\delta_{i,0}=\tau_{n-i+1}+1$ and
$\delta_{i,j+1}=\omega^{\delta_{i,j}}$. (For example, for $n=3$ we have
$\gamma_{1}=\omega^{\omega^{\omega}}+1$,
$\gamma_{2}=\omega^{\omega^{\omega}+1}$,
$\gamma_{3}=\omega^{\omega^{\omega+1}}$.) Then the descent from $\alpha$ to
$\beta$ contains $\gamma_{n}+1$ for each $i=n,\ldots,2$, as well as
$\gamma_{1}$.

Hence, $z(n)=H_{\tau_{n}}(2)\geq
H_{\tau_{n-1}}(n)=F_{\tau_{n-2}}(n)>F_{\tau_{n-2}}(n-2)=F_{\varepsilon_{0}}(n-2)$.
∎

Hence, even though for fixed $\alpha<\varepsilon_{0}$, the function
$H_{\alpha}$ grows slower than $F_{\alpha}$, once we “columnize” by taking
$\alpha=\tau_{n}$, the rates of growth of both functions match up.

##  4 Lower bounds: Tame fusible numbers

In this section we prove the lower bound
$\operatorname{ord}(\mathcal{F})\geq\varepsilon_{0}$ of Theorem 1.1, as well
as Theorem 1.2. For this we consider a subset
$\mathcal{F}^{\prime}\subset\mathcal{F}$ of fusible numbers, which we call
_tame fusible numbers_.

$\mathcal{F}^{\prime}$ is defined from the bottom up by transfinite induction.
At each stage of the induction, an initial segment $\mathcal{H}$ of the
current $\mathcal{F}^{\prime}$ is marked as “used”. The following invariant is
kept throughout the construction process: If
$x=\min(\mathcal{F}^{\prime}\setminus\mathcal{H})$ is the smallest unused
element, then $\mathcal{F}^{\prime}\cap[0,x+1)$ has already been defined, and
$x+1$ is a limit point in this set.

Figure 3: Constructing the tame fusible numbers.

We start by leting
$\mathcal{F}^{\prime}\cap[0,1)=\\{1-2^{-n}:n\in\mathbb{N}\\}$ and
$\mathcal{H}=\emptyset$. Now let
$x=\min(\mathcal{F}^{\prime}\setminus\mathcal{H})$ be the smallest unused
element, and suppose by induction that $\mathcal{F}^{\prime}\cap[0,x+1)$ has
already been defined, and that $x+1$ is a limit point in this set. Let $y$ be
the successor of $x$ in $\mathcal{F}^{\prime}$, and let $m=y-x$. We define
$\mathcal{F}^{\prime}\cap[x+1,y+1)$ by taking the interval
$\mathcal{F}^{\prime}\cap I_{0}$ for $I_{0}=[x+1-m,x+1)$ (which has already
been defined), and applying to it “$y\sim{}$”, obtaining
$\mathcal{F}^{\prime}\cap I_{1}$ for $I_{1}=[x+1,x+1+m/2)$, and then applying
“$y\sim{}$” to this latter set to obtain $\mathcal{F}^{\prime}\cap I_{2}$ for
$I_{2}=[x+1+m/2,x+1+3m/4)$, and so on. In general, denoting
$I_{n}=[y+1-m/2^{n-1},y+1-m/2^{n})$ for $n\in\mathbb{N}$, each interval
$\mathcal{F}^{\prime}\cap I_{n+1}$ is a scaled-down copy of
$\mathcal{F}^{\prime}\cap I_{n}$ obtained by applying “$y\sim{}$”. For each
$n\in\mathbb{N}$ let $\ell_{n}=y+1-m/2^{n-1}$ be the left endpoint of $I_{n}$.
We next add $\ell_{n}$ for each $n\geq 1$ to $\mathcal{F}^{\prime}$, if these
elements are not already there. (We will prove later on that this operation is
unnecessary since we always have $\ell_{0}\in\mathcal{F}^{\prime}$.) Finally,
we add $x$ to $\mathcal{H}$ and repeat.

At the end of the transfinite induction, $\mathcal{F}^{\prime}\cap[0,\infty)$
is defined, and $\mathcal{H}=\mathcal{F}^{\prime}$. See Figure 3. The set
$\mathcal{F}^{\prime}$ is closed by construction, thanks to the addition the
endpoints $\ell_{n}$ in the construction.

Not all fusible numbers are tame. The smallest “wild” fusible number that we
know of is $8449/4096$.

Algorithm 4 Finds $\min(\mathcal{F}^{\prime}\cap(r,\infty))$

procedure TameSucc($r$)

if $r<0$ then

return $0$

$x\leftarrow$TameSucc($r-1$)

5: $y\leftarrow$TameSucc($2r-x-1$)

return $x\sim y$

Algorithm 5 Computes $\textsc{TameSucc}(r)-r$

procedure M($r$)

if $r<0$ then

return $-r$

return $\textsc{M}(r-\textsc{M}(r-1))/2$

Table 2: Algorithms for tame fusible numbers.

The recursive algorithm $\textsc{TameSucc}(r)$ shown in Table 2 returns the
smallest tame fusible number larger than $r$, and $M$ is a concise algorithm
that returns the difference $\textsc{TameSucc}(r)-r$.

######  Lemma 4.1.

Given $z\in\mathcal{F}^{\prime}$, let
$\alpha=\operatorname{ord}(\mathcal{F}^{\prime}\cap[0,z))$ and let
$\beta=\operatorname{ord}(\mathcal{F}^{\prime}\cap[0,z+1))$. Then
$\beta=\omega^{1+\alpha}$. (Hence, for $z\geq 1$ we have
$\beta=\omega^{\alpha}$.)

###### Proof.

By transfinite induction on $\alpha$. If $\alpha=0$ then $z=0$ and
$\beta=\omega$. Next, suppose that $\alpha=\gamma+1$ is a successor ordinal,
and let $y$ be the predecessor of $z$ in $\mathcal{F}^{\prime}$. Assume by
induction that
$\operatorname{ord}(\mathcal{F}^{\prime}\cap[0,y+1))=\omega^{1+\gamma}$. Let
$m=z-y$. Consider the intervals $I_{n}=[z+1-2^{-(n-1)}m,z+1-2^{-n}m)$ for
$n\in\mathbb{N}$. Let $\mathcal{G}=\mathcal{F}\cap I_{0}$. We have
$\operatorname{ord}(\mathcal{G})=-\delta+\omega^{\gamma}$ for some
$\delta<\omega^{\gamma}$, so
$\operatorname{ord}(\mathcal{G})=\omega^{\gamma}$. Since $[y+1,z+1)$ contains
$\omega$-many copies of $\mathcal{G}$, we have

$\operatorname{ord}(\mathcal{F}^{\prime}\cap[0,z+1))=\omega^{1+\gamma}+\omega^{1+\gamma}\omega=\omega^{1+\gamma+1}=\omega^{1+\alpha},$

as desired.

Finally, suppose $\alpha$ is a limit ordinal. For every $\beta<\alpha$ there
exists a corresponding fusible number $y<z$, which by induction satisfies
$\operatorname{ord}(\mathcal{F}^{\prime}\cap[0,y+1))=\omega^{1+\beta}$.
Furthermore, since $\mathcal{F}^{\prime}$ is closed, as $\alpha\to\beta$ we
have $y\to z$. Hence,
$\operatorname{ord}(\mathcal{F}^{\prime}\cap[0,z+1))=\lim_{\beta<\alpha}\omega^{1+\beta}=\omega^{1+\alpha}$.
∎

Hence, for every positive integer $n$ we have
$\operatorname{ord}(n)\geq\tau_{n}$, and
$\operatorname{ord}(\mathcal{F}^{\prime})=\varepsilon_{0}$, proving the lower
bound of Theorem 1.1.

###  4.1 Recurrence relations for the gaps

Given $z\in\mathcal{F}^{\prime}$, define
$\operatorname{ord}^{\prime}(z)=1+\operatorname{ord}(\mathcal{F}^{\prime}\cap[0,z))$.
Hence, by Lemma 4.1 we have
$\operatorname{ord}^{\prime}(z+1)=\omega^{\operatorname{ord}^{\prime}(z)}$ for
all $z$, and for $z\geq 1$ the “$1+{}$” has no effect. Given
$0<\alpha<\varepsilon_{0}$, define $\operatorname{fus}^{\prime}(\alpha)$ as
the unique $z\in\mathcal{F}^{\prime}$ with
$\operatorname{ord}^{\prime}(z)=\alpha$, define
$m(\alpha)=\operatorname{fus}^{\prime}(\alpha+1)-\operatorname{fus}^{\prime}(\alpha)$,
and define $d(\alpha)=-\log_{2}m(\alpha)$.

Hence, $d$ is a function from ordinals to natural numbers. Our objective is to
show that $d(\alpha)$ experiences $F_{\varepsilon_{0}}$-like growth. For this,
we first need to derive recurrence relations for $d$. Unfortunately, the
recurrence relations are quite complex, as they involve an auxiliary function
$\chi(\alpha)$, which is itself defined recursively in terms of $\chi$ and
$d$.

######  Lemma 4.2.

Let $\gamma<\varepsilon_{0}$ be a limit ordinal, and let
$y=\operatorname{fus}^{\prime}(\gamma)-m(\gamma)$. Then
$y\in\mathcal{F}^{\prime}$, and furthermore,
$\operatorname{ord}^{\prime}(y)=[\gamma]_{\chi(\gamma)}$ for some integer
$\chi(\gamma)$. Specifically, $\chi(\gamma)$ is given recursively as follows:

$\displaystyle\chi(\omega^{\alpha}(k+1)+\beta)$
$\displaystyle=\chi(\omega^{\alpha}+\beta),$ $\displaystyle\text{$k\geq 1$,
$\beta<\omega^{\alpha}$ limit};$ (1)
$\displaystyle\chi(\omega^{\alpha}+\beta)$
$\displaystyle=\chi(\omega^{[\alpha]_{\chi(\alpha)}}+\beta),$
$\displaystyle\text{$\alpha,\beta$ limits, $\beta<\omega^{\alpha}$,
$\beta\neq\omega^{[\alpha]_{\chi(\alpha)}+1}$};$ (2)
$\displaystyle\chi(\omega^{\alpha}+\omega^{[\alpha]_{\chi(\alpha)}+1})$
$\displaystyle=\chi(\omega^{[\alpha]_{\chi(\alpha)}+1})-1,$
$\displaystyle\text{$\alpha$ limit};$ (3)
$\displaystyle\chi(\omega^{\alpha+1}+\beta)$
$\displaystyle=\chi(\omega^{\alpha}2+\beta),$
$\displaystyle\text{$\beta<\omega^{\alpha+1}$ limit};$ (4)
$\displaystyle\chi(\omega^{\alpha+1}(k+1))$
$\displaystyle=\chi(\omega^{\alpha+1})-2,$ $\displaystyle\text{$k\geq 1$};$
(5) $\displaystyle\chi(\omega^{\alpha+1})$
$\displaystyle=d(\omega^{\alpha+1})-d(\alpha)+1;$ (6)
$\displaystyle\chi(\omega^{\alpha}k)$
$\displaystyle=d(\omega^{\alpha})-d(\alpha)+\chi(\alpha),$ $k\geq 1$, $\alpha$
limit. (7)

Moreover for every $n\geq 0$ we have
$\operatorname{fus}^{\prime}([\gamma]_{\chi(\gamma)+n})=\operatorname{fus}^{\prime}(\gamma)-m(\gamma)/2^{n}$.

Figure 4: Illustration for Lemma 4.2. We have $\chi(\gamma)=5$ in this
example.

See Figure 4. Lemma 4.2 implies that, in the construction of
$\mathcal{F}^{\prime}$, we always have $\ell_{0}\in\mathcal{F}^{\prime}$, so
the addition of the numbers $\ell_{n}$, $n\geq 1$ to $\mathcal{F}^{\prime}$
was unnecessary.

###### Proof.

By ordinal induction on $\gamma$. Let $\gamma=\omega^{\alpha}k+\beta$ be a
limit ordinal, with $\beta<\omega^{\alpha}$. Let
$y=\operatorname{fus}^{\prime}(\gamma)$ and
$z=\operatorname{fus}^{\prime}(\gamma+1)$. Let
$\ell_{n}=\operatorname{fus}^{\prime}(\alpha+1)+1-2^{1-n}m(\alpha)$ for
$n\in\mathbb{N}$, so $I_{n}=[\ell_{n},\ell_{n+1})$ were the intervals used in
the construction of $\mathcal{F}^{\prime}$. Then $y\in I_{k}$. Hence, for
$n\geq 1$ we have $\operatorname{ord}^{\prime}(\ell_{n})=\omega^{\alpha}n$.

What is $\operatorname{ord}^{\prime}(\ell_{0})$? If $\alpha=\alpha^{\prime}+1$
is a successor ordinal, then
$\operatorname{ord}^{\prime}(\ell_{0})=\omega^{\alpha^{\prime}}2$. And if
$\alpha$ is a limit ordinal, then letting $z_{0}=\ell_{0}-1$,
$z_{1}=\ell_{1}-1$, we have $\operatorname{ord}^{\prime}(z_{1})=\alpha$, so by
the induction assumption,
$\operatorname{ord}^{\prime}(z_{0})=[\alpha]_{\chi(\alpha)}$, and hence
$\operatorname{ord}^{\prime}(\ell_{0})=\omega^{[\alpha]_{\chi(\alpha)}}$.

Each $\mathcal{F}^{\prime}\cap I_{n}$ is a scaled copy of
$\mathcal{F}^{\prime}\cap I_{n-1}$. Hence, whenever
$u\in\mathcal{F}^{\prime}\cap I_{n}$ for some $n\geq 1$, if
$u^{\prime}\in\mathcal{F}^{\prime}\cap I_{n-1}$ is the pre-image from which
$u$ was copied (so $u=\operatorname{fus}^{\prime}(\alpha+1)\sim u^{\prime}$),
then the relation between $\operatorname{ord}^{\prime}(u^{\prime})$ and
$\operatorname{ord}^{\prime}(u)$ is

$-\operatorname{ord}^{\prime}(\ell_{n-1})+\operatorname{ord}^{\prime}(u^{\prime})=-\operatorname{ord}^{\prime}(\ell_{n})+\operatorname{ord}^{\prime}(u).$
(8)

In our case, let $y^{\prime},z^{\prime}\in\mathcal{F}^{\prime}\cap I_{k-1}$ be
the images from which $y,z$ were copied.

Letting $\gamma^{\prime}=\operatorname{ord}^{\prime}(y^{\prime})$, we have
$\gamma^{\prime}=\operatorname{ord}^{\prime}(\ell_{k-1})+\beta$ by (8). Let
$x^{\prime}_{n}=\operatorname{fus}^{\prime}([\gamma^{\prime}]_{\chi(\gamma^{\prime})+n})$
for each $n\in\mathbb{N}$. By induction assumption we have
$x^{\prime}_{n}=y^{\prime}-m(y^{\prime})/2^{n}$.

Suppose first that $\beta>0$. In this case, for every $p\geq 2$ we have
$[\gamma^{\prime}]_{p}>\operatorname{ord}^{\prime}(\ell_{k-1})$ (the case in
which $k=1$ and $\alpha$ is a limit ordinal follows from the Bachmann
property; all the remaining cases are simpler). Hence, $x^{\prime}_{n}\in
I_{k-1}$ for all $n$.

For each $n$ let $x_{n}\in I_{k}$ be the image of $x^{\prime}_{n}$. By (8) we
have

$\operatorname{ord}^{\prime}(x_{n})=\operatorname{ord}^{\prime}(\ell_{n})+(-\operatorname{ord}^{\prime}(\ell_{n-1})+\operatorname{ord}^{\prime}(x^{\prime}_{n})).$

Furthermore, the ratios between distances among
$x^{\prime}_{n},y^{\prime},z^{\prime}$ are preserved among $x_{n},y,z$. Hence,
(1–4) follow, using Lemma 3.2 for (3).

Now suppose $\beta=0$, so
$\gamma=\omega^{\alpha}k=\operatorname{ord}^{\prime}(\ell_{k})$. In this case
the numbers $x_{n}$ belong to $I_{k-1}$. If $k\geq 2$ then $I_{k-1}\cup I_{k}$
is a scaled copy of $I_{k-2}\cup I_{k-1}$, and (5) follows.

Now suppose $k=1$, so $\gamma=\omega^{\alpha}$. If $\alpha=\alpha^{\prime}+1$
is a successor ordinal, then for every $p\geq 1$ we have

$\operatorname{fus}^{\prime}([\gamma]_{p})=\operatorname{fus}^{\prime}(\omega^{\alpha^{\prime}}p)=y-2^{1-p}m(\alpha^{\prime})=y-2^{1-p-d(\alpha^{\prime})}.$

Hence,
$\operatorname{fus}^{\prime}(\gamma)-m(\gamma)/2^{n}=y-2^{-d(\gamma)-n}=\operatorname{fus}^{\prime}([\gamma]_{p})$
for $p=(d(\gamma)-d(\alpha^{\prime})+1)+n$, yielding (6).

Finally, if $\gamma=\omega^{\alpha}$ for limit $\alpha$, then
$\operatorname{fus}^{\prime}(\alpha)=y-1$. We know by induction that

$\operatorname{fus}^{\prime}([\alpha]_{\chi(\alpha)+p})=y-1-m(\alpha)/2^{p}=y-1-2^{-d(\alpha)-p}\qquad\text{for
every $p\in\mathbb{N}$.}$

Hence, for every $q\geq\chi(\alpha)$ we have
$\operatorname{fus}^{\prime}([\omega^{\alpha}]_{q})=y-2^{-d(\alpha)-q+\chi(\alpha)}$.
Hence, $y-m(\gamma)/2^{n}=y-2^{-d(\gamma)-n}$ is obtained by taking
$q=(d(\gamma)-d(\alpha)+\chi(\alpha))+n$, yielding (7). ∎

######  Lemma 4.3.

Let $0<\gamma<\varepsilon_{0}$. Then $d(\gamma)$ is given recursively by:

$\displaystyle d(1)$ $\displaystyle=1;$ (9) $\displaystyle d(\alpha+1)$
$\displaystyle=1+d(\alpha);$ (10) $\displaystyle
d(\omega^{\alpha}\cdot(k+1)+\beta)$
$\displaystyle=k+d(\omega^{\alpha}+\beta),$
$\displaystyle\beta<\omega^{\alpha};$ (11) $\displaystyle
d(\omega^{\alpha+1}+\beta)$ $\displaystyle=1+d(\omega^{\alpha}2+\beta),$
$\displaystyle\beta<\omega^{\alpha+1};$ (12) $\displaystyle
d(\omega^{\alpha}+\beta)$
$\displaystyle=1+d(\omega^{[\alpha]_{\chi(\alpha)}}+\beta),$
$\displaystyle\text{$\alpha$ limit, $\beta<\omega^{\alpha}$}.$ (13)

###### Proof.

Using similar considerations as in the proof of Lemma 4.2. ∎

Let us illustrate Lemmas 4.2 and 4.3 by sketching the computation of
$d(\omega^{\omega^{\omega}})$. We have $d(\omega^{\omega})=10$ and
$\chi(\omega^{\omega})=11$. More generally,

$d\left(\omega^{\omega^{n}}\right)=n+9+4c_{1}+5c_{2}+\cdots+(n+2)c_{n-1},\qquad\text{for
$n\geq 1$},$

where $c_{0}=2$, and $c_{n}=1+(n+1)c_{n-1}$ for $n\geq 1$. Hence,
$d\left(\omega^{\omega^{n}}\right)$ grows with $n$ roughly like $n!$. The
precise value of $d(\omega^{\omega^{\omega}})$ is
$d(\omega^{\omega^{\omega}})=1+d(\omega^{\omega^{11}})=1541023937$.

###  4.2 Growth rate

We now prove that there exists a constant $c$ such that $d(\tau_{n})\geq
F_{\varepsilon_{0}}(n-c)$ for all large enough $n$. We achieve this by
bounding $d$ from below in terms of the Hardy hierarchy, since it is easier to
work with.

######  Lemma 4.4.

For every $\alpha$ we have $d(\omega^{\alpha})>d(\alpha)$.

###### Proof.

This is immediate from the construction of $\mathcal{F}^{\prime}$. ∎

######  Corollary 4.5.

For every limit $\alpha$ we have $\chi(\omega^{\alpha})>\chi(\alpha)$.

###### Proof.

By (7). ∎

######  Observation 4.6.

Starting from an expression of the form $d(\omega^{\gamma})$, repeated
application of (11–13) yields expressions of the form
$n_{k}+d(\omega^{\gamma_{k}})$, where $\gamma_{1},\gamma_{2},\ldots$ is a
canonical descent starting from $\gamma$, each
$n_{k+1}\in\\{n_{k}+1,n_{k}+2\\}$, and the descent parameter at step $k$ is
$\chi(\gamma_{k-1})$.

######  Lemma 4.7.

For every $\alpha$ we have $d\bigl{(}\omega^{\omega^{\alpha}}\bigr{)}\geq
2d(\omega^{\alpha})$.

###### Proof.

By Observation 4.6 and ordinal induction on $\alpha$. Suppose first that
$\alpha$ is a limit ordinal. Then by (13) we have
$d(\omega^{\alpha})=1+d(\omega^{[\alpha]_{\chi(\alpha)}})$, whereas
$d\bigl{(}\omega^{\omega^{\alpha}}\bigr{)}=1+d\bigl{(}\omega^{\omega^{[\alpha]_{n}}}\bigr{)}$
for $n=\chi(\omega^{\alpha})>\chi(\alpha)$. By the Bachmann property (Lemma
3.1), the canonical descent from $\omega^{[\alpha]_{n}}$ must go through
$\omega^{[\alpha]_{\chi(\alpha)}}$. Hence, using induction on $\alpha$,

$d\bigl{(}\omega^{\omega^{\alpha}}\bigr{)}\geq
2+d\bigl{(}\omega^{\omega^{[\alpha]_{\chi(\alpha)}}}\bigr{)}\geq
2+2d(\omega^{[\alpha]_{\chi(\alpha)}})=2d(\omega^{\alpha}).$

Similarly, for a successor ordinal, denoting $n=\chi(\omega^{\alpha+1})$,

$d\bigl{(}\omega^{\omega^{\alpha+1}}\bigr{)}=1+d\bigl{(}\omega^{\omega^{\alpha}n}\bigr{)}\geq
4+d\bigl{(}\omega^{\omega^{\alpha}}\bigr{)}\geq
4+2d(\omega^{\alpha})=2d(\omega^{\alpha+1}),$

since the canonical descent from $\omega^{\alpha}n$ must go through
$\omega^{\alpha}$, and it must take at least three steps. ∎

######  Corollary 4.8.

For every $\alpha$ we have $\chi\bigl{(}\omega^{\omega^{\alpha}}\bigr{)}\geq
d(\omega^{\alpha})$.

###### Proof.

Substituting into (7). ∎

######  Lemma 4.9.

Define

$f_{\beta,\alpha}(n)=d\Bigl{(}\omega^{\omega^{\omega^{\beta+\omega^{\alpha}n}}}\Bigr{)}.$

Then $f_{\beta,\alpha}(n)\geq H_{\alpha}(n)$ for all $\beta$.

###### Proof.

By ordinal induction on $\alpha$. For $\alpha=0$ we have

$f_{\beta,0}(n)=d\Bigl{(}\omega^{\omega^{\omega^{\beta+n}}}\Bigr{)}\geq
n=H_{0}(n),$

by Observation 4.6.

Next, suppose the claim is true for $\alpha$. Then

$f_{\beta,\alpha+1}(n)=d\Bigl{(}\omega^{\omega^{\omega^{\beta+\omega^{\alpha+1}n}}}\Bigr{)}=1+d\Bigl{(}\omega^{\omega^{\omega^{\beta+\omega^{\alpha+1}(n-1)+\omega^{\alpha}m}}}\Bigr{)},$

where

$m=\chi\bigl{(}\omega^{\omega^{\beta+\omega^{\alpha+1}n}}\bigr{)}\geq
d\bigl{(}\omega^{\beta+\omega^{\alpha+1}n}\bigr{)}\geq n+1.$

Hence, letting
$\beta^{\prime}=\beta+\omega^{\alpha+1}(n-1)+\omega^{\alpha}(m-n-1)$,

$f_{\beta,\alpha+1}(n)\geq
d\Bigl{(}\omega^{\omega^{\omega^{\beta^{\prime}+\omega^{\alpha}(n+1)}}}\Bigr{)}=f_{\beta^{\prime},\alpha}(n+1)\geq
H_{\alpha}(n+1)=H_{\alpha+1}(n).$

Finally, let $\alpha$ be a limit ordinal, and suppose the claim is true for
all $\alpha^{\prime}<\alpha$. Then

$f_{\beta,\alpha}(n)=d\Bigl{(}\omega^{\omega^{\omega^{\beta+\omega^{\alpha}n}}}\Bigr{)}=1+d\Bigl{(}\omega^{\omega^{\omega^{\beta+\omega^{\alpha}(n-1)+\omega^{[\alpha]_{m}}}}}\Bigr{)},$

where $m\geq n+1$ as before. By the Bachmann property, any canonical descent
from $[\alpha]_{m}$ must go through $[\alpha]_{n}+1$. Hence,

$f_{\beta,\alpha}(n)\geq
d\Bigl{(}\omega^{\omega^{\omega^{\beta+\omega^{\alpha}(n-1)+\omega^{[\alpha]_{n}+1}}}}\Bigr{)}=1+d\Bigl{(}\omega^{\omega^{\omega^{\beta+\omega^{\alpha}(n-1)+\omega^{[\alpha]_{n}}p}}}\Bigr{)},$

where $p\geq n$ as before. Hence, letting
$\beta^{\prime}=\beta+\omega^{\alpha}(n-1)+\omega^{[\alpha]_{n}}(p-n)$, we
have

$f_{\beta,\alpha}(n)\geq
d\Bigl{(}\omega^{\omega^{\omega^{\beta^{\prime}+\omega^{[\alpha]_{n}}n}}}\Bigr{)}=f_{\beta^{\prime},[\alpha]_{n}}(n)\geq
H_{[\alpha]_{n}}(n)=H_{\alpha}(n).$

∎

######  Corollary 4.10.

For every $n\geq 8$ we have $d(\tau_{n})\geq F_{\varepsilon_{0}}(n-7)$.

###### Proof.

Any canonical descent from $\tau_{n-1}$ with descent parameter at least $2$
must go through $\gamma=\omega^{\omega^{\delta}}$ for $\delta=\tau_{n-4}2$.
Hence, by Observation 4.6 and Lemma 3.5 we have

$d(\tau_{n})=d(\omega^{\tau_{n-1}})\geq
d(\omega^{\gamma})=f_{0,\tau_{n-5}}(2)\geq H_{\tau_{n-5}}(2)\geq
F_{\varepsilon_{0}}(n-7).$

∎

Finally, we prove that for every $\alpha\geq\tau_{n}$ we have $d(\alpha)\geq
d(\tau_{n})$.

######  Lemma 4.11.

If $0<\beta<\omega^{\alpha+1}$ then
$d(\omega^{\alpha})<d(\omega^{\alpha}+\beta)$.

###### Proof.

By ordinal induction on $\gamma=\omega^{\alpha}+\beta$. Suppose first that
$\alpha$ is a limit ordinal. Denote $k=\chi(\alpha)$, so
$d(\omega^{\alpha})=1+d(\omega^{[\alpha]_{k}})$ by (13). Let $\omega^{\delta}$
be the first term of $\beta$. If $\delta=\alpha$ then by (11) we have
$d(\gamma)>d(\omega^{\alpha}+\beta^{\prime})$ for some $\beta^{\prime}<\beta$,
so the claim follows by induction.

Now suppose $\delta<\alpha$, so $d(\gamma)=1+d(\omega^{[\alpha]_{k}}+\beta)$
by (13). If $\beta<\omega^{[\alpha]_{k}+1}$ then the claim follows by
induction. Otherwise we have $\omega^{[\alpha]_{k}}+\beta=\beta$, and the
first term of $\beta$ is $\omega^{\delta}$ for some
$[\alpha]_{k}<\delta\leq\alpha$. By induction we have $d(\beta)\geq
d(\omega^{\delta})$, which by the Bachmann property and Observation 4.6 is
larger than $d(\omega^{[\alpha]_{k}})$.

If $\alpha$ is a successor ordinal we proceed similarly. ∎

######  Lemma 4.12.

If $\alpha>\tau_{n}$ then $d(\alpha)>d(\tau_{n})$.

###### Proof.

If the first term of $\alpha$ is $\tau_{n}$ then the claim follows by Lemma
4.11. Otherwise, the first term of $\alpha$ is $\omega^{\beta}$ for some
$\beta>\tau_{n-1}$. By Lemma 4.11 we have $d(\alpha)\geq d(\omega^{\beta})$.
Furthermore, any canonical descent from $\beta$ must contain $\tau_{n-1}$, so
the claim follows by Observation 4.6. ∎

Corollary 4.10 together with Lemma 4.12 implies Theorem 1.2. This in turn
implies a similar lower bound for the running time of the algorithms TameSucc
and Succ, since in order to output a fraction with denominator $2^{d}$, the
recursion depth must be at least $d$.

##  5 Upper bound

Here we show that $\operatorname{ord}(\mathcal{F})\leq\varepsilon_{0}$.

######  Lemma 5.1.

Let $\mathcal{G}_{1},\mathcal{G}_{2}\subset\mathbb{R}$ be two well-ordered
sets, and let $\mathcal{H}=\\{x\sim
y:x\in\mathcal{G}_{1},y\in\mathcal{G}_{2},|y-x|<1\\}$. Then
$\operatorname{ord}(\mathcal{H})\leq\operatorname{ord}(\mathcal{G}_{1})\otimes\operatorname{ord}(\mathcal{G}_{2})$.

###### Proof.

By the above-mentioned result of de Jongh and Parikh [8]. ∎

######  Lemma 5.2.

Let $y,z\in\mathcal{F}$ satisfy $z=s(y)$. Suppose
$\operatorname{ord}(y+1)\leq\omega^{\omega^{\alpha}}$. Then
$\operatorname{ord}(z+1)\leq\omega^{\omega^{\alpha+1}}$.

###### Proof.

Let $J_{1}=[0,y+1)$ and $J_{2}=[y+1,z+1)$. Let $m=z-y$. Define the numbers
$\ell_{n}=z+1-2^{-(n-1)}m$ and the intervals $I_{n}=[\ell_{n},\ell_{n+1})$ for
$n\in\mathbb{N}$. Hence, $\ell_{1}=y+1$, so the interval $I_{0}$ lies at the
end of $J_{1}$, while the intervals $I_{1},I_{2},I_{3},\ldots$ disjointly
cover $J_{2}$. Given $n\in\mathbb{N}$, let $\mathcal{F}_{n}=\mathcal{F}\cap
I_{n}$ and $\mathcal{G}_{n}=\mathcal{F}\cap[0,\ell_{n+1})$, so
$\mathcal{G}_{n+1}=\mathcal{G}_{n}\cup\mathcal{F}_{n+1}$. We will bound
$\operatorname{ord}(\mathcal{G}_{n})$ by induction on $n$.

There is no fusible number between $y$ and $z$, and already “$z\sim{}$” sends
$\ell_{n}$ into $\ell_{n+1}$. Therefore, every $x\in\mathcal{F}_{n}$, $n\geq
1$ must be of the form $x=x_{1}\sim x_{2}$ for $x_{1},x_{2}<\ell_{n}$.
Therefore,

$\operatorname{ord}(\mathcal{F}_{n})\leq\operatorname{ord}(\mathcal{G}_{n-1})\otimes\operatorname{ord}(\mathcal{G}_{n-1}).$

Furthermore,
$\operatorname{ord}(\mathcal{G}_{n+1})=\operatorname{ord}(\mathcal{G}_{n})+\operatorname{ord}(\mathcal{F}_{n+1})$.
Hence, it follows by induction on $n$ that
$\operatorname{ord}(\mathcal{F}_{n})$, $\operatorname{ord}(\mathcal{G}_{n})$
are both bounded by $\omega^{\omega^{\alpha}2^{n}}$ for every $n\geq 1$.

Since $\omega^{\omega^{\alpha+1}}>\omega^{\omega^{\alpha}m}$ for every
$m\in\mathbb{N}$, the claim follows. ∎

######  Corollary 5.3.

For every $z\in\mathcal{F}$ we have
$\operatorname{ord}(z+1)\leq\omega^{\omega^{\operatorname{ord}(z)}}$.

###### Proof.

By transfinite induction on $z$, as in the proof of Lemma 4.1. ∎

Hence, for every positive integer $n$ we have
$\operatorname{ord}(n)\leq\tau_{2n-1}$, and
$\operatorname{ord}(\mathcal{F})\leq\varepsilon_{0}$, proving the upper bound
of Theorem 1.1.

###  5.1 A shorter proof of the upper bound

As one of the referees pointed out, there is a shorter way to prove that
$\operatorname{ord}(\mathcal{F})\leq\varepsilon_{0}$, by invoking Kruskal’s
tree theorem [18] and the upper bounds on the maximal order types of the
corresponding well-partial-orders [14, 22, 25, 26]. Let $T_{1}$ and $T_{2}$ be
the binary-tree representations of two fusible numbers. It can be easily
checked that, if $T_{1}$ embeds into $T_{2}$ in the sense of Kruskal’s tree
theorem, then $v(T_{1})\leq v(T_{2})$. Hence, $\mathcal{F}$ is a linearization
of a subset of the well-partially-ordered set of unlabeled binary trees.
Therefore, $\operatorname{ord}(\mathcal{F})\leq\varepsilon_{0}$ (as can be
seen e.g. from Theorem 3.2 of [26], by taking $T(X,\emptyset,X)$ for a one-
element set $X$, and noting that
$f^{+}\binom{0\,0\,1}{0\,1\,2}=f\binom{0\,0\,1}{0\,1\,2}=f\binom{1}{2}=\varepsilon_{0}$).

(For a similar appeal to Kruskal’s tree theorem, see e.g. Ehrenfeucht [9].)

##  6 Results on Peano Arithmetic

###  6.1 Background

(For more details see e.g. Rautenberg [23].) _First-order arithmetic_ is a
formal language that includes the quantifiers $\exists$, $\forall$; logical
operators $\wedge$, $\vee$, $\neg$; the constant symbol $0$; variables
$x,y,z,\ldots$ which represent natural numbers; the equality and inequality
symbols $=$, $\neq$; the binary operators $+$, $\cdot$; and the unary operator
$S$, which represents the operation of adding $1$. The operator $S$ together
with the symbol $0$ allows us to express any natural number. For example, $3$
can be represented by $SSS0$. However, for readability we will use the
notation “$3$”.

Any arithmetical formula with no free variables is either true or false. For
example, the formula $\forall x\,\exists y\,x+2=y$ is true, whereas the
formula $\forall x\,\exists y\,y+2=x$ is false since the variables range over
$\mathbb{N}$.

One can express the notion “$x<y$” by the formula $\exists z\,x+z+1=y$, or
else by the formula $\forall z\,y+z\neq x$. The formula

$x\bmod y=z\quad\bm{:=}\quad z<y\wedge\exists q\,x=q\cdot y+z$

expresses the remainder operation as a ternary relation on the free variables
$x$, $y$, $z$.

One can encode any pair of numbers as a single number by exploiting the fact
that the _pairing function_ $\langle a,b\rangle=(a+b)(a+b+1)/2+a$ is a
bijection between $\mathbb{N}^{2}$ and $\mathbb{N}$. Hence, the formula

$\langle a,b\rangle=c\quad\bm{:=}\quad 2\cdot c=(a+b)\cdot(a+b+1)+2\cdot a$

expresses the pairing function as a ternary relation. By repeatedly applying
the pairing function we can encode any $k$-tuple as a single natural number.
The number $k$ must be fixed in advance, however. Hence, it is not immediately
clear how to encode sequences of _arbitrary_ length in a way that enables
access to each element of the sequence. Gödel found a way to accomplish this
using the Chinese Remainder Theorem. The idea is to encode the sequence
$a_{0},\ldots,a_{n-1}$ as $a_{i}=x\bmod r_{i}$ where the numbers $r_{i}$ form
an arithmetic progression. Specifically, one can take $r_{i}=(i+1)m+1$ for
some appropriately chosen $m$. We can also provide the length of the sequence
as an additional parameter. Hence, the number $z=\langle\langle
n,x\rangle,m\rangle$ encodes the finite sequence $a_{0},\ldots,a_{n-1}$ in
which $a_{i}=x\bmod((i+1)m+1)$ for each $0\leq i<n$. Denote by $[z]_{i}=a$ the
statement that “the $i$-th element of the sequence encoded by $z$ equals $a$”.
Then we can express “$[z]_{i}=a$” in first-order arithmetic as a ternary
relation:

$[z]_{i}=a\quad\bm{:=}\quad\exists q\,\exists n\,\exists x\,\exists m\,\langle
n,x\rangle=q\wedge\langle q,m\rangle=z\wedge i<n\wedge x\bmod((i+1)\cdot
m+1)=a.$

Using finite sequences, it is possible to represent exponentiation,
factorials, Fibonacci numbers, etc. We can also represent any kind of discrete
structures, such as trees, graphs, etc. We can also represent rational numbers
and their arithmetical operations.

Once we have a representation of rational numbers, we can formulate the
statement “the rational number $x$ is fusible” as follows: “There exists a
finite set $S$ of rational numbers that includes $x$, and such that for every
$w\in S$, either $w=0$ or there exist $y,z\in S$ such that $|z-y|<1$ and
$w=y\sim z$.” And we can formulate the statement “algorithm TameSucc
terminates on input $r_{0}$ outputting $f_{0}$” as follows: “There exists a
finite set $S$ of quadruples $(r,x,y,f)$ that contains $(r_{0},x,y,f_{0})$ for
some $x,y$, and such that for every $(r,x,y,f)\in S$, if $r<0$ then $f=0$,
otherwise $f=x\sim y$ and we have
$(r-1,x^{\prime},y^{\prime},x),(2r-x-1,x^{\prime\prime},y^{\prime\prime},y)\in
S$ for some $x^{\prime},y^{\prime},x^{\prime\prime},y^{\prime\prime}$.”

More generally, in first-order arithmetic we can represent Turing machines and
formulate statements such as “Turing machine $T$ halts on input $x$”.

However, in first-order arithmetic it is not possible to quantify over all
real numbers, nor over all infinite sequences or sets, as follows trivially
from countability considerations (though one can formulate statements about
specific real numbers such as $\pi$ and $e$). Still, one can quantify over
infinite sequences in which each element of the sequence is uniquely
determined in some pre-defined way by the previous elements.

_Peano Arithmetic_ is a theory for first-order arithmetic given by a set of
axioms. The _PA-theorems_ are those statements that can be derived from the
axioms and from previously derived PA-theorems by the inference rules of
first-order logic. Since the natural numbers satisfy the axioms, all PA-
theorems are true (when interpreted in the natural numbers, which is the
intended interpretation). Moreover, by use of the inference rules, any
“finitary” mathematical proof (involving only finite sets and structures) can
be carried out step by step in PA. However, as Gödel showed, PA, like any
formal system strong enough to represent basic arithmetic, is incomplete, in
the sense that there exist true arithmetical statements that are not PA-
theorems.

#### Unprovability in PA.

There are finitary statements whose only obvious proofs involve infinitary
arguments. Consider for example the following statement:

$\begin{split}&\text{For every ordinal $\alpha<\varepsilon_{0}$, the canonical
descent $\\{\alpha_{n}\\}$ given}\\\ &\text{by $\alpha_{1}=\alpha$ and
$\alpha_{n+1}=[\alpha_{n}]_{n}$ eventually reaches $0$.}\end{split}$ (14)

This statement can be formulated in first-order arithmetic. However, the
obvious way to prove it is by arguing that the ordinals up to
$\varepsilon_{0}$ are well-ordered, so, more generally, there exists no
infinite descending sequence starting from $\alpha$. Unfortunately, this
latter statement involves quantification over infinite sequences. Hence, this
proof approach to (14) cannot be carried out in PA.

An important tool for showing true arithmetical formulas to be unprovable in
PA is the following result:

######  Theorem 6.1 ([5]).

Let $T$ be a Turing machine that computes a function
$g:\mathbb{N}\to\mathbb{N}$, terminating on every input. Suppose that PA can
prove the statement “$T$ terminates on every input.” Then $g$ cannot grow too
fast: There exist $\alpha<\varepsilon_{0}$ and $n_{0}\in\mathbb{N}$ such that
$g(n)<F_{\alpha}(n)$ for every $n\geq n_{0}$.

Theorem 6.1 is due independently to Schwichtenberg [27] and Wainer [34, 35],
building on earlier work by Kreisel [17]. The above form follows Buchholz and
Wainer [5], who give a nice, self-contained proof (which is actually a simple
base-case of a much more general result of Buchholz [4]).

Theorem 6.1 implies that statement (14) has _no_ proof in PA, because the
length of the canonical descent starting from $\alpha=\tau_{n}$ grows like
$F_{\varepsilon_{0}}(n-c)$ for some $c$ (as quickly follows by comparing to
the definition of $H_{\alpha}(n)$). Hence, let $T$ be a Turing machine that,
given $n$, outputs the length of the canonical descent starting from
$\tau_{n}$. If PA could prove (14), it could also conclude that $T$ halts on
all inputs, contradicting Theorem 6.1.

###  6.2 Proof of Theorem 1.3

We start by analyzing algorithms TameSucc and $M$ within PA. For convenience,
in this section we will denote the algorithm TameSucc by $T$.

######  Lemma 6.2.

PA cannot prove the statement “for every $n\in\mathbb{N}$, algorithm $M(n)$
terminates,” nor the statement “for every $n\in\mathbb{N}$, algorithm $T(n)$
terminates.”

###### Proof.

Let $A$ be a Turing machine that, given $n$, outputs $1/M(n)$. If PA could
prove that $M$ terminates, it could conclude that $A$ terminates as well. But
this contradicts Theorem 6.1, in light of Corollary 4.10. The argument for $T$
is similar. ∎

######  Lemma 6.3.

PA can prove that for every $r\in\mathbb{Q}$, if $T(r)$ terminates then its
output is a fusible number.

###### Proof.

We reason within PA. The general approach is to proceed by induction on the
depth of the recursion. Suppose $T(r)$ terminates. Recall that for $r<0$ the
algorithm returns $0$, whereas for $r\geq 0$ the algorithm recursively sets
$x=T(r-1)$, $y=T(2r-x-1)$, and then outputs $x\sim y$. Denote $u=2r-x-1$ for
convenience.

All we need to prove is that for $r\geq 0$ we have $|y-x|<1$, since then the
claim follows immediately by induction. For $0\leq r<1/2$ we have $x=y=0$. We
will show that for $r\geq 1/2$ we in fact have $x<y<x+1$.

######  Claim 6.4.

If $T(r)$ terminates then it returns $T(r)>r$. If $r\geq-1/2$ then we also
have $T(r)\leq r+1/2$.

###### Proof.

If $r<1/2$ the claim follows easily, so suppose $r\geq 1/2$. By induction we
have $x=T(r-1)\leq r-1/2$, so $u\geq r-1/2\geq 0$, and by induction we have
$u<y\leq u+1/2$. Substituting this into $x\sim y$ yields the desired result. ∎

Claim 6.4 implies that for $r\geq 1/2$ we have $x=T(r-1)\leq r-1/2$, so
$y=T(2r-x-1)>2r-x-1\geq r-1/2\geq x$.

######  Claim 6.5.

Suppose $T(r)$ terminates. Then:

  1. (a)

If $r\geq 0$ then $y<x+1$.

  2. (b)

For every $r<r^{\prime}<T(r)$, $T(r^{\prime})$ also terminates, outputting
$T(r^{\prime})=T(r)$. (Therefore, for every $r^{\prime}>r$, if $T(r^{\prime})$
terminates then $T(r^{\prime})\geq T(r)$).

###### Proof.

We prove both properties jointly by induction on the recursion depth. Let us
start with item (a). If $0\leq r<1/2$ then $x=0$, $y=0$ and we are done.
Hence, suppose $r\geq 1/2$. Claim 6.4 implies $r-1<x\leq r-1/2$, so $0\leq
u<r$. We know $T(u-1)$ terminates and $u-1<r-1$, so by induction, item (b)
implies $T(u-1)\leq T(r-1)=x$. The second recursive call in the computation of
$T(u)$ is $v=T(2u-T(u-1)-1)$. By induction, item (a) implies $v<T(u-1)+1$, so
$y=T(u)=T(u-1)\sim v<T(u-1)\sim(T(u-1)+1)=T(u-1)+1\leq x+1$, $T(r)=x\sim
y<x+1=T(r-1)+1$, and $T(r)-1<T(r-1)$.

For item (b), if $r<0$ the claim is immediate, so let $r\geq 0$ and let
$r<r^{\prime}<T(r)$. Then $r-1<r^{\prime}-1<T(r)-1<T(r-1)$, so by induction,
item (b) implies that $T(r^{\prime}-1)$ terminates outputting $x$. Next, let
$u^{\prime}=2r^{\prime}-x-1$. Then:

$\displaystyle u^{\prime}-u$ $\displaystyle=2(r^{\prime}-r),$ $\displaystyle
T(u)-u$ $\displaystyle=2(T(r)-r).$

Therefore, $T(u)-u^{\prime}=2(T(r)-r^{\prime})$, so $u^{\prime}<T(u)$. Hence,
$u<u^{\prime}<T(u)$, so by induction, item (b) implies that $T(u^{\prime})$
terminates outputting $y$. Hence, $T(r^{\prime})$ terminates giving the same
output as $T(r)$. ∎

This finishes the proof of Lemma 6.3. ∎

######  Lemma 6.6.

PA can prove that for every $r\in\mathbb{Q}$, if $T(r)$ does not terminate,
then for every $n\in\mathbb{N}$ there exists a fusible number $z_{n}$
satisfying $r<z_{n}<r+2^{-n}$.

###### Proof.

We reason within PA. Suppose $T(r)$ does not terminate. Then there exists an
infinite recursive-call sequence with inputs $r_{0},r_{1},r_{2},\ldots$
starting with $r_{0}=r$. Specifically, for each $n\geq 1$, _either_
$r_{n}=r_{n-1}-1$ and $T(r_{n})$ does not terminate, _or_ $T(r_{n-1}-1)$
terminates outputting $x_{n}$, but $r_{n}=2r_{n-1}-x_{n}-1$ and $T(r_{n})$
does not terminate. Either way, $r_{n}<r_{n-1}$.

The number of indices $n$ for which $r_{n}=r_{n-1}-1$ must be finite. Call
this number $d$. We proceed by induction on $d$.

Suppose first that $d=0$, so $r_{n}=2r_{n-1}-x_{n}-1$ for all $n$. Given
$n\geq 1$, we know by Lemma 6.3 that $x_{n}$ is fusible. Therefore, by the
window lemma (Lemma 2.2) there exists a fusible number
$z_{n}\in(r_{n},r_{n-1}]$. Let $z_{n-1}=x_{n}\sim z_{n}$. Then $z_{n-1}$ is
fusible, and $r_{n-1}<z_{n-1}\leq r_{n-2}$ (the lower bound follows from
$z_{n}>r_{n}$, while the upper bound follows from $z_{n}\leq r_{n-1}$ and
$x_{n}\leq x_{n-1}$, the latter of which follows from Claim 6.5 (b)).
Furthermore, we have $z_{n}-r_{n}=2(z_{n-1}-r_{n-1})$. In general, letting
$z_{i}=x_{i+1}\sim z_{i+1}$ for each $i=n-1,\ldots,1,0$, each $z_{i}$ is
fusible and satisfies $r_{i}<z_{i}\leq r_{i-1}$ and
$z_{i}-r_{i}=2(z_{i-1}-r_{i-1})$. But
$z_{n}-r_{n}<r_{n-1}-r_{n}=x_{n}-(r_{n-1}-1)<1/2$ by Claim 6.4. Therefore,
$z_{0}-r_{0}<2^{-n-1}$, as desired.

Now suppose the claim is true whenever the number of indices with
$r_{n}=r_{n-1}-1$ is $d-1$, and suppose that in our sequence this number is
$d$. Let $n$ be smallest such index in our sequence. By induction, for each
$m$ there exists a fusible number $z_{m}$ satisfying
$r_{n}<z_{m}<r_{n}+2^{-m}$. Then $z_{m}+1$ is also fusible, and if $m$ is
large enough then it will fall in the range $(r_{n-1},r_{n-2}]$. From here we
proceed as before. ∎

Hence, PA cannot prove the statement “for every $n\in\mathbb{N}$ there exists
a smallest fusible number larger than $n$,” because then PA would conclude by
contradiction that $T(n)$ terminates for all $n\in\mathbb{N}$.

Therefore, since PA can prove Lemma 2.12, it follows that PA cannot prove the
statement “every fusible number has a maximum-height representation.”

##  7 A conjecture

Given $x\in\mathcal{F}$, let $y=s(x)$ be the successor of $x$, let $m=y-x$,
let $\ell_{n}=y+1-2^{1-n}m$ for $n\in\mathbb{N}$, and let
$I_{x,n}=[\ell_{n},\ell_{n+1})$ for $n\in\mathbb{N}$, so the interval
$I_{x,0}$ ends at $x+1$, while the intervals $I_{x,n}$, $n\geq 1$ form a
partition of $[x+1,y+1)$. Recall that by Corollary 2.13 we have
$s^{(n)}(x)=x+(2-2^{1-n})m$ for every $n\in\mathbb{N}$. We conjecture the
following:

######  Conjecture 7.1.

Every fusible number in $I_{x,n}$, $n\geq 1$ can be written as $s^{(n)}(x)\sim
z$ for some $z\in\mathcal{F}\cap[x+1-2^{1-n}m,x+1)$.

Figure 5: We conjecture that all fusible numbers can be obtained this way.
Algorithm 6 Finds $\min(\mathcal{F}^{\prime\prime}\cap(r,\infty))$

procedure MeekSucc($r$)

if $r<0$ then

return $0$

$x\leftarrow$MeekSucc($r-1$)

5:
$y\leftarrow$MeekSucc($2r-x-1-1/\textsc{Denominator}(x)+2^{\lceil\log_{2}(x-r+1)\rceil}$)

return $x\sim y$

Table 3: Algorithm for meek fusible numbers.

See Figure 5. In other words, by repeatedly performing the operations
$s^{(n)}(x)\sim z$, we obtain a subset
$\mathcal{F}^{\prime\prime}\subseteq\mathcal{F}$, in a way analogous to the
construction of the tame fusible numbers $\mathcal{F}^{\prime}$. Let us call
the fusible numbers in $\mathcal{F}^{\prime\prime}$ _meek_. Conjecture 7.1
states that $\mathcal{F}^{\prime\prime}=\mathcal{F}$. We have done extensive
computer experiments, and we have not found any counterexample to Conjecture
7.1. Table 3 shows a recursive algorithm for the next meek fusible number,
analogous to algorithm TameSucc of Table 2. If Conjecture 7.1 is true, then
this algorithm is equivalent to algorithm Succ of Table 1.

###  7.1 Recurrence relations for meek fusible numbers

$\mathcal{F}^{\prime\prime}$ satisfies recurrence relations similar to those
of $\mathcal{F}^{\prime}$. Given $z\in\mathcal{F}^{\prime\prime}$, define
$\operatorname{ord}^{\prime\prime}(z)=1+\operatorname{ord}(\mathcal{F}^{\prime\prime}\cap[0,z))$.
Then
$\operatorname{ord}^{\prime\prime}(z+1)=\omega^{\operatorname{ord}^{\prime\prime}(z)}$
for all $z$, and for $z\geq 1$ the “$1+{}$” has no effect. Given
$0<\alpha<\varepsilon_{0}$, define $\operatorname{fus}^{\prime\prime}(\alpha)$
as the unique $z\in\mathcal{F}^{\prime\prime}$ with
$\operatorname{ord}^{\prime\prime}(z)=\alpha$, define
$m^{\prime\prime}(\alpha)=\operatorname{fus}^{\prime\prime}(\alpha+1)-\operatorname{fus}^{\prime\prime}(\alpha)$,
and define $d^{\prime\prime}(\alpha)=-\log_{2}m^{\prime\prime}(\alpha)$.

######  Lemma 7.2.

Let $\gamma<\varepsilon_{0}$ be a limit ordinal, and let
$y=\operatorname{fus}^{\prime\prime}(\gamma)-m^{\prime\prime}(\gamma)$. Then
$y\in\mathcal{F}^{\prime\prime}$, and furthermore,
$\operatorname{ord}^{\prime\prime}(y)=[\gamma]_{\chi^{\prime\prime}(\gamma)}$
for some integer $\chi^{\prime\prime}(\gamma)$. Specifically,
$\chi^{\prime\prime}(\gamma)$ is given recursively as follows:

$\displaystyle\chi^{\prime\prime}(\omega^{\alpha}k+\beta)$
$\displaystyle=\chi^{\prime\prime}(\omega^{[\alpha]_{\chi^{\prime\prime}(\alpha)+k-1}}+\beta),$
$k\geq 1$, $\alpha,\beta$ limits,
$\displaystyle\qquad\text{$\beta<\omega^{\alpha}$ limit,
$\beta\neq\omega^{[\alpha]_{\chi^{\prime\prime}(\alpha)+k-1}+1}$};$
$\displaystyle\chi^{\prime\prime}(\omega^{\alpha}k+\omega^{[\alpha]_{\chi^{\prime\prime}(\alpha)+k-1}+1})$
$\displaystyle=\chi^{\prime\prime}(\omega^{[\alpha]_{\chi^{\prime\prime}(\alpha)+k-1}+1})-1,$
$\displaystyle\text{$\alpha$ limit};$
$\displaystyle\chi^{\prime\prime}(\omega^{\alpha+1}k+\beta)$
$\displaystyle=\chi^{\prime\prime}(\omega^{\alpha}(k+1)+\beta),$
$\displaystyle\text{$\beta<\omega^{\alpha+1}$ limit};$
$\displaystyle\chi^{\prime\prime}(\omega^{\alpha}k)$
$\displaystyle=d^{\prime\prime}(\omega^{\alpha}k)-d^{\prime\prime}(\alpha)+\chi^{\prime\prime}(\alpha)-1,$
$\displaystyle\text{$\alpha$ limit, $k\geq 2$};$
$\displaystyle\chi^{\prime\prime}(\omega^{\alpha})$
$\displaystyle=d^{\prime\prime}(\omega^{\alpha})-d^{\prime\prime}(\alpha)+\chi^{\prime\prime}(\alpha),$
$\displaystyle\text{$\alpha$ limit};$
$\displaystyle\chi^{\prime\prime}(\omega^{\alpha}k)$
$\displaystyle=d^{\prime\prime}(\omega^{\alpha}k)-d^{\prime\prime}(\alpha)-k+1,$
$\displaystyle\text{$\alpha$ successor, $k\geq 2$};$
$\displaystyle\chi^{\prime\prime}(\omega^{\alpha})$
$\displaystyle=d^{\prime\prime}(\omega^{\alpha})-d^{\prime\prime}(\alpha)+2,$
$\displaystyle\text{$\alpha$ successor}.$

Moreover for every $n\geq 0$ we have
$\operatorname{fus}^{\prime\prime}([\gamma]_{\chi^{\prime\prime}(\gamma)+n})=\operatorname{fus}^{\prime\prime}(\gamma)-m^{\prime\prime}(\gamma)/2^{n}$.
Furthermore, $d^{\prime\prime}(\gamma)$ is given recursively by:

$\displaystyle d^{\prime\prime}(k)$ $\displaystyle=k;$ $\displaystyle
d^{\prime\prime}(\omega^{\alpha}k+\beta)$
$\displaystyle=1+d^{\prime\prime}(\omega^{[\alpha]_{\chi^{\prime\prime}(\alpha)+k-1}}+\beta),$
$\displaystyle\text{$k\geq 1$, $\alpha$ limit, $\beta<\omega^{\alpha}$};$
$\displaystyle d^{\prime\prime}(\omega^{\alpha+1}k+\beta)$
$\displaystyle=1+d^{\prime\prime}(\omega^{\alpha}(k+1)+\beta),$
$\displaystyle\text{$k\geq 1$, $\beta<\omega^{\alpha+1}$}.$

###  7.2 Rate of growth of $d^{\prime\prime}(\omega^{\omega^{n}})$

We saw in Section 4.1 that, for the tame fusible numbers,
$d(\omega^{\omega^{n}})$ grows roughly like $n!$. In contrast,
$d^{\prime\prime}(\omega^{\omega^{n}})$ exhibits Ackermannian growth, as we
proceed to show.

First of all, we have:

$\displaystyle d^{\prime\prime}(\omega^{n}k)$ $\displaystyle=2n+k,\qquad k\geq
1;$ $\displaystyle\chi^{\prime\prime}(\omega^{n})$ $\displaystyle=n+3;$
$\displaystyle\chi^{\prime\prime}(\omega^{n}k)$ $\displaystyle=n+1,\qquad
k\geq 2;$

and, more generally, if $\alpha+\omega^{n}$ is in CNF with
$0<\alpha<\omega^{\omega}$, then $\chi^{\prime\prime}(\alpha+\omega^{n})=n+1$.

By repeatedly applying the recurrences for $d^{\prime\prime}$, starting from
$d^{\prime\prime}(\omega^{\alpha_{0}}k_{0})$, $\alpha_{0}<\omega^{\omega}$, we
obtain

$d^{\prime\prime}(\omega^{\alpha_{0}}k_{0})=1+d^{\prime\prime}(\omega^{\alpha_{1}}k_{1})=2+d^{\prime\prime}(\omega^{\alpha_{2}}k_{2})=\cdots$

where the sequence $\\{\alpha_{n}\\}$ is a canonical descent.

Furthermore, the precise identities of the higher-order terms of $\alpha_{0}$
are unimportant for the descent until the lower-order terms disappear.
Meaning, let $\alpha=\beta+\gamma$ and $\alpha^{\prime}=\beta^{\prime}+\gamma$
be two ordinals in CNF smaller than $\omega^{\omega}$, with the same lower-
order terms $\gamma$, and with $\beta,\beta^{\prime}>0$. Suppose that,
starting from $d^{\prime\prime}(\omega^{\alpha}k)$, it takes $m$ steps to get
down to $m+d^{\prime\prime}(\omega^{\beta}\ell)$. Then, starting from
$d^{\prime\prime}(\omega^{\alpha^{\prime}}k)$, after the same number $m$ of
steps we will get down to $m+d^{\prime\prime}(\omega^{\beta^{\prime}}\ell)$
for the same $\ell$.

Hence, let $y_{n}(k)$ and $\ell_{n}(k)$ be the integers such that, starting
from $d^{\prime\prime}(\omega^{\alpha+\omega^{n}}k)$, where
$0<\alpha<\omega^{\omega}$ and $\alpha+\omega^{n}$ is in CNF, after $y_{n}(k)$
steps we get down to $y_{n}(k)+d^{\prime\prime}(\omega^{\alpha}\ell_{n}(k))$.

And more generally, let $y_{n,m}(k)$ and $\ell_{n,m}(k)$ be the integers such
that, under the same conditions, starting from
$d^{\prime\prime}(\omega^{\alpha+\omega^{n}m}k)$ we get down to
$y_{n,m}(k)+d^{\prime\prime}(\omega^{\alpha}\ell_{n,m}(k))$.

Then,

$\displaystyle y_{n,1}(k)$ $\displaystyle=y_{n}(k);$
$\displaystyle\ell_{n,1}(k)$ $\displaystyle=\ell_{n}(k);$ $\displaystyle
y_{n,m}(k)$ $\displaystyle=y_{n}(k)+y_{n,m-1}(\ell_{n}(k)),\qquad m\geq 2;$
$\displaystyle\ell_{n,m}(k)$ $\displaystyle=\ell_{n,m-1}(\ell_{n}(k));$
$\displaystyle y_{n}(k)$ $\displaystyle=1+y_{n-1,n+k}(1),\qquad n\geq 2;$
$\displaystyle\ell_{n}(k)$ $\displaystyle=\ell_{n-1,n+k}(1),\qquad n\geq 2;$

with base cases $y_{1}(k)=\ell_{1}(k)=k+2$.

It follows that $\ell_{n,m}(k)=\ell_{n}^{(m)}(k)$ and
$\ell_{n}(k)=\ell_{n-1}^{(n+k)}(1)$. Hence, $\ell_{n}(k)$ grows roughly like
$F_{n-1}(k)$ in the fast-growing hierarchy. Further, $y_{n}(k)$ also grows
roughly like $F_{n-1}(k)$.

Next, let $u_{n}(k)$ and $j_{n}(k)$ be such that

$d^{\prime\prime}(\omega^{\omega^{n}}k)=u_{n}(k)+d^{\prime\prime}(\omega^{\omega^{n-1}}j_{n}(k)).$

Then,

$\displaystyle u_{n}(k)$ $\displaystyle=1+y_{n-1,n+k+1}(1),\qquad n\geq 2;$
$\displaystyle j_{n}(k)$ $\displaystyle=\ell_{n-1,n+k+1}(1),\qquad n\geq 2.$

Finally, let $v_{n}(k)=d^{\prime\prime}(\omega^{\omega^{n}}k)$. Then,

$v_{n}(k)=u_{n}(k)+v_{n-1}(j_{n}(k)),\qquad n\geq 2;$

with base case $v_{1}(k)=2k+8$. Hence, $u_{n}(k)$, $j_{n}(k)$, and $v_{n}(k)$
also grow roughly like $F_{n-1}(k)$, and hence,
$d^{\prime\prime}(\omega^{\omega^{n}})$ grows roughly like $F_{\omega}(n)$.

The precise value of $d^{\prime\prime}(\omega^{\omega^{\omega}})$ is given by
$d^{\prime\prime}(\omega^{\omega^{\omega}})=1+d^{\prime\prime}(\omega^{\omega^{11}})=1+v_{11}(1)$,
which is too large to calculate explicitly.

##  8 Discussion

A main open problem is to derive an upper bound for the inverse-largest-gap
$g(n)^{-1}$. One way to do this would be to prove Conjecture 7.1 and then
establish an upper bound for the growth rate of $d^{\prime\prime}$.

We are also missing upper bounds for the running time of algorithms IsFusible
and WeakSucc.

Experimentally, it seems that whenever a fusible number $z$ has
representations $T_{1}$ and $T_{2}$ with heights $h(T_{1})<h(T_{2})$, it also
has representations of all intermediate heights. However, we have not been
able to prove this.

$\mathrm{ACA}_{0}$ is a subsystem of second-order arithmetic studied within
the framework of reverse mathematics [30]. Since $\mathrm{ACA}_{0}$ is a
_conservative extension_ of PA (meaning that the first-order statements
provable in $\mathrm{ACA}_{0}$ are exactly the PA-theorems), it follows that
the second-order statements “$\mathcal{F}$ is well-ordered”, “algorithm
TameSucc terminates on all real inputs”, and “algorithm $M$ terminates on all
real inputs” are unprovable in $\mathrm{ACA}_{0}$.

#### Generalizations of fusible numbers.

In a forthcoming paper, the second author, together with Alexander Bufetov and
Fedor Pakhomov, study sets of reals generated by $n$-ary functions [6]. They
show that the natural generalization of $\sim$ to an $n$-ary function yields a
well-ordered set of order type $\varphi_{n-1}(0)$. They also show that no
linear $n$-ary function can get beyond $\varphi_{n-1}(0)$. Finally, they show
that there exist continuous $n$-ary functions for which the order types of the
resulting sets approach the small Veblen ordinal (matching the upper bound
yielded by Kruskal’s theorem).

#### Acknowledgements

Thanks to Fedor Pakhomov and the anonymous referees for their useful comments.

## References

  * [1] Heinz Bachmann.  Transfinite Zahlen.  Ergebnisse der Mathematik und ihrer Grenzgebiete, 2 Folge. Springer, 1967.
  * [2] Lev D. Beklemishev.  The worm principle.  In Z. Chatzidakis, P. Koepke, and W. Pohlers, editors, Logic Colloquium ’02, volume 27 of Lecture Notes in Logic, pages 75–95. Cambridge University Press, 2006.
  * [3] Andrey Bovykin.  Brief introduction to unprovability.  In S. B. Cooper, H. Geuvers, A. Pillay, and J. Väänänen, editors, Logic Colloquium 2006, volume 32 of Lecture Notes in Logic, pages 38–64. Cambridge University Press, 2009.
  * [4] Wilfried Buchholz.  An independence result for ($\Pi_{1}^{1}$-CA)+BI.  Annals of Pure and Applied Logic, pages 131–155, 1987.
  * [5] Wilfried Buchholz and Stan S. Wainer.  Provably computable functions and the fast growing hierarchy.  In S. G. Simpson, editor, Logic and Combinatorics, volume 65 of Contemporary Mathematics, pages 179–198. AMS, 1987.
  * [6] Alexander Bufetov, Gabriel Nivasch, and Fedor Pakhomov.  Well-ordered sets of reals generated by monotone functions and recursive algorithms.  In preparation.
  * [7] Timothy J. Carlson and Stephen G. Simpson.  A dual form of Ramsey’s theorem.  Advances in Mathematics, 53:265–290, 1984.
  * [8] Dick H. J. de Jongh and Rohit Parikh.  Well-partial orderings and hierarchies.  Indagationes Mathematicae, 39:195–206, 1977.
  * [9] Andrzej Ehrenfeucht.  Polynomial functions with exponentiation are well ordered.  Algebra Universalis, 3:261–262, 1973.
  * [10] Jeff Erickson.  Fusible numbers.  http://www.mathpuzzle.com/fusible.pdf.  Accessed: 2020-03-25.
  * [11] Harvey Friedman, Kenneth McAloon, and Stephen G. Simpson.  A finite combinatorial principle which is equivalent to the 1-consistency of predicative analysis.  In G. Metakides, editor, Patras Logic Symposion, volume 109 of Studies in Logic and the Foundations of Mathematics, pages 197–230. North-Holland, 1982.
  * [12] Harvey Friedman, Neil Robertson, and Paul D. Seymour.  The metamathematics of the graph minor theorem.  In S. G. Simpson, editor, Logic and Combinatorics, volume 65 of Contemporary Mathematics, pages 229–261. AMS, 1987.
  * [13] Masahiro Hamano and Mitsuhiro Okada.  A relationship among Gentzen’s proof-reduction, Kirby–Paris’ hydra game and Buchholz’s hydra game.  Mathematical Logic Quarterly, 43:103–120, 1997.
  * [14] Ryu Hasegawa.  Well-ordering of algebras and Kruskal’s theorem.  In N. D. Jones, M. Hagiya, and M. Sato, editors, Logic, language and computation, volume 792 of Lecture Notes in Computer Science, pages 133–172. Springer, 1994.  doi:10.1007/BFb0032399.
  * [15] Akihiro Kanamori and Kenneth McAloon.  On Gödel incompleteness and finite combinatorics.  Annals of Pure and Applied Logic, 33:23–41, 1987.
  * [16] Laurie Kirby and Jeff Paris.  Accessible independence results for Peano Arithmetic.  Bulletin of the London Mathematical Society, 14:285–293, 1982.
  * [17] Georg Kreisel.  On the interpretation of non-finitist proofs: Part II. Interpretation of number theory. Applications.  The Journal of Symbolic Logic, 17(1):43–58, 1952.
  * [18] Joseph B. Kruskal.  Well-quasi-ordering, the tree theorem, and Vazsonyi’s conjecture.  Transactions of the American Mathematical Society, 95(2):210–225, 1960.  URL: http://www.jstor.org/stable/1993287.
  * [19] Ray Magliozzi.  Car talk: Burning time.  https://www.cartalk.com/radio/puzzler/burning-time.  Accessed: 2020-03-25.
  * [20] Frank Morgan.  Frank Morgan’s math chat—burning 1-hour fuses in 45 minutes.  https://www.maa.org/frank-morgans-math-chat-burning-1-hour-fuses-in-45-minutes.  Accessed: 2020-03-25.
  * [21] Jeff Paris and Leo Harrington.  A mathematical incompleteness in Peano Arithmetic.  In J. Barwise, editor, Handbook of Mathematical Logic, volume 90 of Studies in Logic and the Foundations of Mathematics, pages 1133–1142. North-Holland, 1977.
  * [22] Michael Rathjen and Andreas Weiermann.  Proof-theoretic investigations on Kruskal’s theorem.  Annals of Pure and Applied Logic, 60(1):49–88, 1993.  URL: https://www.sciencedirect.com/science/article/pii/016800729390192G, doi:https://doi.org/10.1016/0168-0072(93)90192-G.
  * [23] Wolfgang Rautenberg.  A Concise Introduction to Mathematical Logic.  Springer, third edition, 2010.
  * [24] Horace E. Rose.  Subrecursion: Functions and Hierarchies.  Oxford University Press, 1984.
  * [25] Diana Schmidt.  Well-partial orderings and their maximal order types.  habilitation, Heidelberg, 1979.
  * [26] Diana Schmidt.  Well-partial orderings and their maximal order types.  In Peter M. Schuster, Monika Seisenberger, and Andreas Weiermann, editors, Well-Quasi Orders in Computation, Logic, Language and Reasoning: A Unifying Concept of Proof Theory, Automata Theory, Formal Languages and Descriptive Set Theory, pages 351–391. Springer International Publishing, Cham, 2020.  doi:10.1007/978-3-030-30229-0_13.
  * [27] Helmut Schwichtenberg.  Eine Klassifikation der $\varepsilon_{0}$-rekursiven Funktionen.  Zeitschrift für mathematische Logik und Grundlagenforschung, (17):61–74, 1971.
  * [28] Stephen G. Simpson.  Nonprovability of certain combinatorial properties of finite trees.  In L. A. Harrington, M. D. Morley, A. Sĉêdrov, and S. G. Simpson, editors, Harvey Friedman’s Research on the Foundations of Mathematics, volume 117 of Studies in Logic and the Foundations of Mathematics, pages 87–117. North-Holland, 1985.
  * [29] Stephen G. Simpson.  Unprovable theorems and fast-growing functions.  In S. G. Simpson, editor, Logic and Combinatorics, volume 65 of Contemporary Mathematics, pages 359–394. AMS, 1987.
  * [30] Stephen G. Simpson.  Subsystems of Second Order Arithmetic.  Perspectives in Logic. Cambridge University Press, second edition, 2009\.
  * [31] Will Sladek.  The termite and the tower: Goodstein sequences and provability in PA.  https://www.uio.no/studier/emner/matnat/ifi/nedlagte-emner/INF5170/v08/undervisningsmateriale/sladekgoodstein.pdf.  Accessed: 2020-03-25.
  * [32] Craig Smoryński.  Some rapidly growing functions.  The Mathematical Intelligencer, 2:149–154, 1980.
  * [33] Craig Smoryński.  The varieties of arboreal expericence.  The Mathematical Intelligencer, 4:182–189, 1982.
  * [34] Stan S. Wainer.  A classification of the ordinal recursive functions.  Archiv für mathematische Logik und Grundlagenforschung, 13(3):136–153, 1970.
  * [35] Stan S. Wainer.  Ordinal recursion, and a refinement of the extended Grzegorczyk hierarchy.  The Journal of Symbolic Logic, 37(2):281–292, 1972.
  * [36] Peter Winkler.  Mathematical Puzzles: A Connoisseur’s Collection.  CRC Press, 2004.
  * [37] Junyan Xu.  Survey on fusible numbers.  arXiv e-prints, page arXiv:1202.5614, February 2012.  arXiv:1202.5614.